Permit NoSQL results to be out-of-order

Just like with a SQL database, a NoSQL system might be able to return
results out of order more efficiently than in-order when there is
no explicit ORDER BY clause in the query.  Support that by passing
through a hint indicating if the order needs to be preserved, or not.

Change-Id: Ic601fd3277936e599b590c508e2435bc5bf5f95b
Signed-off-by: Shawn O. Pearce <sop@google.com>

6 files changed, 296 insertions, 22 deletions

diff --git a/src/main/java/com/google/gwtorm/nosql/AccessGen.java b/src/main/java/com/google/gwtorm/nosql/AccessGen.java
index d2fffe7..5344e1e 100644
--- a/src/main/java/com/google/gwtorm/nosql/AccessGen.java
+++ b/src/main/java/com/google/gwtorm/nosql/AccessGen.java
@@ -411,16 +411,21 @@ class AccessGen implements Opcodes {
       cgs.push(0);
     }
 
+    // Only keep order if there is an order by clause present
+    //
+    cgs.push(info.hasOrderBy() ? 1 : 0);
+
     if (needsIndexFunction(info)) {
       mv.visitMethodInsn(INVOKEVIRTUAL, accessType.getInternalName(),
           "scanIndex", Type.getMethodDescriptor(resultSet, new Type[] {
-              indexFunction, byteArray, byteArray, Type.INT_TYPE}));
+              indexFunction, byteArray, byteArray, Type.INT_TYPE,
+              Type.BOOLEAN_TYPE}));
     } else {
       // No where and no order by clause? Use the primary key instead.
       //
       mv.visitMethodInsn(INVOKEVIRTUAL, accessType.getInternalName(),
           "scanPrimaryKey", Type.getMethodDescriptor(resultSet, new Type[] {
-              byteArray, byteArray, Type.INT_TYPE}));
+              byteArray, byteArray, Type.INT_TYPE, Type.BOOLEAN_TYPE}));
     }
 
     mv.visitInsn(ARETURN);
diff --git a/src/main/java/com/google/gwtorm/nosql/NoSqlAccess.java b/src/main/java/com/google/gwtorm/nosql/NoSqlAccess.java
index 291279b..52e84ab 100644
--- a/src/main/java/com/google/gwtorm/nosql/NoSqlAccess.java
+++ b/src/main/java/com/google/gwtorm/nosql/NoSqlAccess.java
@@ -29,16 +29,24 @@ public abstract class NoSqlAccess<T, K extends Key<?>> extends
 
   /**
    * Scan a range of keys from the data rows and return any matching objects.
+   * <p>
+   * All NoSQL implementations must provide their own variant of this method.
+   * <p>
+   * To fetch a single record with a scan, set {@code toKey} to the same array
+   * as {@code fromKey}, but append a trailing NUL byte (0x00). The caller
+   * should validate that the returned ResultSet contains no more than 1 row.
    *
    * @param fromKey key to start the scan on. This is inclusive.
    * @param toKey key to stop the scan on. This is exclusive.
-   * @param limit maximum number of results to return.
+   * @param limit maximum number of results to return, 0 for unlimited.
+   * @param order if true the order will be preserved, false if the result order
+   *        order can be arbitrary.
    * @return result set for the requested range. The result set may be lazily
    *         filled, or filled completely.
    * @throws OrmException an error occurred preventing the scan from completing.
    */
   protected abstract ResultSet<T> scanPrimaryKey(byte[] fromKey, byte[] toKey,
-      int limit) throws OrmException;
+      int limit, boolean order) throws OrmException;
 
   /**
    * Scan a range of keys and return any matching objects.
@@ -52,13 +60,16 @@ public abstract class NoSqlAccess<T, K extends Key<?>> extends
    * @param index definition of the index the scan occurs over.
    * @param fromKey key to start the scan on. This is inclusive.
    * @param toKey key to stop the scan on. This is exclusive.
-   * @param limit maximum number of results to return.
+   * @param limit maximum number of results to return, 0 for unlimited.
+   * @param order if true the order will be preserved, false if the result order
+   *        order can be arbitrary.
    * @return result set for the requested range. The result set may be lazily
    *         filled, or filled completely.
    * @throws OrmException an error occurred preventing the scan from completing.
    */
   protected abstract ResultSet<T> scanIndex(IndexFunction<T> index,
-      byte[] fromKey, byte[] toKey, int limit) throws OrmException;
+      byte[] fromKey, byte[] toKey, int limit, boolean order)
+      throws OrmException;
 
   // -- These are all provided by AccessGen when it builds a subclass --
 
diff --git a/src/main/java/com/google/gwtorm/nosql/generic/GenericAccess.java b/src/main/java/com/google/gwtorm/nosql/generic/GenericAccess.java
index 3884a31..524cb12 100644
--- a/src/main/java/com/google/gwtorm/nosql/generic/GenericAccess.java
+++ b/src/main/java/com/google/gwtorm/nosql/generic/GenericAccess.java
@@ -32,7 +32,6 @@ import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Iterator;
 import java.util.LinkedHashMap;
-import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
 
@@ -66,8 +65,8 @@ public abstract class GenericAccess<T, K extends Key<?>> extends
    * Lookup a single entity via its primary key.
    * <p>
    * The default implementation of this method performs a scan over the primary
-   * key with {@link #scanPrimaryKey(byte[], byte[], int)}, '\0' appended onto
-   * the fromKey and a result limit of 2.
+   * key with {@link #scanPrimaryKey(byte[], byte[], int, boolean)}, '\0'
+   * appended onto the fromKey and a result limit of 2.
    * <p>
    * If multiple records are discovered {@link OrmDuplicateKeyException} is
    * thrown back to the caller.
@@ -87,7 +86,7 @@ public abstract class GenericAccess<T, K extends Key<?>> extends
     dst.nul();
     final byte[] toKey = dst.toByteArray();
 
-    Iterator<T> r = scanPrimaryKey(fromKey, toKey, 2).iterator();
+    Iterator<T> r = scanPrimaryKey(fromKey, toKey, 2, false).iterator();
     if (!r.hasNext()) {
       return null;
     }
@@ -105,13 +104,15 @@ public abstract class GenericAccess<T, K extends Key<?>> extends
    * @param fromKey key to start the scan on. This is inclusive.
    * @param toKey key to stop the scan on. This is exclusive.
    * @param limit maximum number of results to return.
+   * @param order if true the order will be preserved, false if the result order
+   *        order can be arbitrary.
    * @return result set for the requested range. The result set may be lazily
    *         filled, or filled completely.
    * @throws OrmException an error occurred preventing the scan from completing.
    */
   @Override
-  protected ResultSet<T> scanPrimaryKey(byte[] fromKey, byte[] toKey, int limit)
-      throws OrmException {
+  protected ResultSet<T> scanPrimaryKey(byte[] fromKey, byte[] toKey,
+      int limit, boolean order) throws OrmException {
     IndexKeyBuilder b;
 
     b = new IndexKeyBuilder();
@@ -126,7 +127,9 @@ public abstract class GenericAccess<T, K extends Key<?>> extends
     b.addRaw(toKey);
     toKey = b.toByteArray();
 
-    final ResultSet<Map.Entry<byte[], byte[]>> rs = db.scan(fromKey, toKey, limit);
+    final ResultSet<Map.Entry<byte[], byte[]>> rs =
+        db.scan(fromKey, toKey, limit, order);
+
     final Iterator<Map.Entry<byte[], byte[]>> i = rs.iterator();
 
     return new AbstractResultSet<T>() {
@@ -157,13 +160,15 @@ public abstract class GenericAccess<T, K extends Key<?>> extends
    * @param fromKey key to start the scan on. This is inclusive.
    * @param toKey key to stop the scan on. This is exclusive.
    * @param limit maximum number of results to return.
+   * @param order if true the order will be preserved, false if the result order
+   *        order can be arbitrary.
    * @return result set for the requested range. The result set may be lazily
    *         filled, or filled completely.
    * @throws OrmException an error occurred preventing the scan from completing.
    */
   @Override
   protected ResultSet<T> scanIndex(IndexFunction<T> idx, byte[] fromKey,
-      byte[] toKey, int limit) throws OrmException {
+      byte[] toKey, int limit, boolean order) throws OrmException {
     final long now = System.currentTimeMillis();
     IndexKeyBuilder b;
 
@@ -188,7 +193,8 @@ public abstract class GenericAccess<T, K extends Key<?>> extends
 
     SCAN: for (;;) {
       int scanned = 0;
-      ResultSet<Entry<byte[], byte[]>> rs = db.scan(lastKey, toKey, limit);
+      ResultSet<Entry<byte[], byte[]>> rs =
+          db.scan(lastKey, toKey, limit, order);
       for (Map.Entry<byte[], byte[]> ent : rs) {
         final byte[] idxkey = ent.getKey();
         lastKey = idxkey;
@@ -319,8 +325,8 @@ public abstract class GenericAccess<T, K extends Key<?>> extends
    * Insert or update operations should invoke this method before the main data
    * row is written, allowing the secondary index rows to be put into the data
    * store before the main data row arrives. Compatible scan implementations
-   * (such as {@link #scanIndex(IndexFunction, byte[], byte[], int)} above) will
-   * ignore these rows for a short time period.
+   * (such as {@link #scanIndex(IndexFunction, byte[], byte[], int, boolean)}
+   * above) will ignore these rows for a short time period.
    *
    * @param oldObj an old copy of the object; if non-null this may be used to
    *        avoid writing unnecessary secondary index rows that already exist.
diff --git a/src/main/java/com/google/gwtorm/nosql/generic/GenericSchema.java b/src/main/java/com/google/gwtorm/nosql/generic/GenericSchema.java
index 37fdde3..e6268a7 100644
--- a/src/main/java/com/google/gwtorm/nosql/generic/GenericSchema.java
+++ b/src/main/java/com/google/gwtorm/nosql/generic/GenericSchema.java
@@ -113,8 +113,8 @@ public abstract class GenericSchema extends NoSqlSchema {
    * Fetch one row's data.
    * <p>
    * The default implementation of this method creates a pair of keys and passes
-   * them to {@link #scan(byte[], byte[], int)}. The {@code fromKey} is the
-   * supplied {@code key}, while the {@code toKey} has '\0' appended onto
+   * them to {@link #scan(byte[], byte[], int, boolean)}. The {@code fromKey} is
+   * the supplied {@code key}, while the {@code toKey} has '\0' appended onto
    * {@code key}. If more than one row matches in that range, the method throws
    * an exception.
    *
@@ -130,7 +130,7 @@ public abstract class GenericSchema extends NoSqlSchema {
     final byte[] toKey = new byte[key.length + 1];
     System.arraycopy(key, 0, toKey, 0, key.length);
 
-    ResultSet<Entry<byte[], byte[]>> r = scan(fromKey, toKey, 2);
+    ResultSet<Entry<byte[], byte[]>> r = scan(fromKey, toKey, 2, false);
     try {
       Iterator<Entry<byte[], byte[]>> i = r.iterator();
       if (!i.hasNext()) {
@@ -162,12 +162,14 @@ public abstract class GenericSchema extends NoSqlSchema {
    * @param fromKey key to start the scan on. This is inclusive.
    * @param toKey key to stop the scan on. This is exclusive.
    * @param limit maximum number of results to return.
+   * @param order if true the order will be preserved, false if the result order
+   *        order can be arbitrary.
    * @return result iteration for the requested range. The result set may be
    *         lazily filled, or filled completely.
    * @throws OrmException an error occurred preventing the scan from completing.
    */
   public abstract ResultSet<Map.Entry<byte[], byte[]>> scan(byte[] fromKey,
-      byte[] toKey, int limit) throws OrmException;
+      byte[] toKey, int limit, boolean order) throws OrmException;
 
   /**
    * Atomically insert one row, failing if the row already exists.
diff --git a/src/main/java/com/google/gwtorm/nosql/heap/TreeMapSchema.java b/src/main/java/com/google/gwtorm/nosql/heap/TreeMapSchema.java
index 4cc1a2a..9b75422 100644
--- a/src/main/java/com/google/gwtorm/nosql/heap/TreeMapSchema.java
+++ b/src/main/java/com/google/gwtorm/nosql/heap/TreeMapSchema.java
@@ -48,7 +48,7 @@ public abstract class TreeMapSchema extends GenericSchema {
 
   @Override
   public ResultSet<Map.Entry<byte[], byte[]>> scan(byte[] fromKey,
-      byte[] toKey, int limit) {
+      byte[] toKey, int limit, boolean order) {
     db.lock.lock();
     try {
       final List<Map.Entry<byte[], byte[]>> res =
diff --git a/src/test/java/com/google/gwtorm/nosql/NoSqlPhoneBookTest.java b/src/test/java/com/google/gwtorm/nosql/NoSqlPhoneBookTest.java
new file mode 100644
index 0000000..8532809
--- /dev/null
+++ b/src/test/java/com/google/gwtorm/nosql/NoSqlPhoneBookTest.java
@@ -0,0 +1,250 @@
+// Copyright 2008 Google Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gwtorm.nosql;
+
+import com.google.gwtorm.client.Access;
+import com.google.gwtorm.client.OrmConcurrencyException;
+import com.google.gwtorm.client.OrmException;
+import com.google.gwtorm.data.PersonAccess;
+import com.google.gwtorm.data.PhoneBookDb;
+import com.google.gwtorm.data.TestPerson;
+import com.google.gwtorm.jdbc.JdbcExecutor;
+import com.google.gwtorm.jdbc.JdbcSchema;
+import com.google.gwtorm.nosql.heap.MemoryDatabase;
+
+import junit.framework.TestCase;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+public class NoSqlPhoneBookTest extends TestCase {
+  protected MemoryDatabase<PhoneBookDb> db;
+  private List<PhoneBookDb> openSchemas;
+
+  @Override
+  public void setUp() throws Exception {
+    super.setUp();
+
+    db = new MemoryDatabase<PhoneBookDb>(PhoneBookDb.class);
+    openSchemas = new ArrayList<PhoneBookDb>();
+  }
+
+  @Override
+  public void tearDown() throws Exception {
+    if (openSchemas != null) {
+      for (PhoneBookDb schema : openSchemas) {
+        schema.close();
+      }
+      openSchemas = null;
+    }
+    super.tearDown();
+  }
+
+  protected PhoneBookDb open() throws OrmException {
+    final PhoneBookDb r = db.open();
+    if (r != null) {
+      openSchemas.add(r);
+    }
+    return r;
+  }
+
+  public void testCreateDatabaseHandle() throws Exception {
+    assertNotNull(db);
+  }
+
+  public void testOpenSchema() throws Exception {
+    final PhoneBookDb schema1 = open();
+    assertNotNull(schema1);
+
+    final PhoneBookDb schema2 = open();
+    assertNotNull(schema2);
+    assertNotSame(schema1, schema2);
+  }
+
+  public void testGetPeopleAccess() throws Exception {
+    final PhoneBookDb schema = open();
+    assertNotNull(schema.people());
+    assertEquals("people", schema.people().getRelationName());
+    assertEquals(1, schema.people().getRelationID());
+  }
+
+  public void testGetAddressAccess() throws Exception {
+    final PhoneBookDb schema = open();
+    assertNotNull(schema.addresses());
+    assertEquals("addresses", schema.addresses().getRelationName());
+    assertEquals(2, schema.addresses().getRelationID());
+  }
+
+  public void testGetAllRelations() throws Exception {
+    final PhoneBookDb schema = open();
+    Access<?, ?>[] all = schema.allRelations();
+    assertNotNull(all);
+    assertEquals(2, all.length);
+    assertSame(schema.people(), all[0]);
+    assertSame(schema.addresses(), all[1]);
+  }
+
+  public void testNextAddressId() throws Exception {
+    final PhoneBookDb schema = open();
+    final int a = schema.nextAddressId();
+    final int b = schema.nextAddressId();
+    assertTrue(a != b);
+  }
+
+  public void testPersonPrimaryKey() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson.Key key = new TestPerson.Key("Bob");
+    final TestPerson bob = new TestPerson(key, 18);
+    assertSame(key, schema.people().primaryKey(bob));
+  }
+
+  public void testInsertOnePerson() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson bob = new TestPerson(new TestPerson.Key("Bob"), 18);
+    schema.people().insert(Collections.singleton(bob));
+
+    TestPerson copy = schema.people().all().toList().get(0);
+    assertNotSame(copy, bob);
+    assertEquals(bob.name(), copy.name());
+  }
+
+  public void testGetOnePerson() throws Exception {
+    final PhoneBookDb schema = open();
+    final PersonAccess sp = schema.people();
+    final TestPerson p1 = new TestPerson(new TestPerson.Key("Bob"), 18);
+    sp.insert(Collections.singleton(p1));
+
+    final TestPerson p2 = sp.get(sp.primaryKey(p1));
+    assertNotNull(p2);
+    assertNotSame(p1, p2);
+    assertEquals(sp.primaryKey(p1), sp.primaryKey(p2));
+  }
+
+  public void testGetOnePersonIterator() throws Exception {
+    final PhoneBookDb schema = open();
+    final PersonAccess sp = schema.people();
+    final TestPerson p1 = new TestPerson(new TestPerson.Key("Bob"), 18);
+    sp.insert(Collections.singleton(p1));
+
+    final List<TestPerson> list =
+        sp.get(Collections.singleton(sp.primaryKey(p1))).toList();
+    assertNotNull(list);
+    assertEquals(1, list.size());
+
+    final TestPerson p2 = list.get(0);
+    assertNotNull(p2);
+    assertNotSame(p1, p2);
+    assertEquals(sp.primaryKey(p1), sp.primaryKey(p2));
+  }
+
+  public void testInsertManyPeople() throws Exception {
+    final PhoneBookDb schema = open();
+    final ArrayList<TestPerson> all = new ArrayList<TestPerson>();
+    all.add(new TestPerson(new TestPerson.Key("Bob"), 18));
+    all.add(new TestPerson(new TestPerson.Key("Mary"), 22));
+    all.add(new TestPerson(new TestPerson.Key("Zak"), 33));
+    schema.people().insert(all);
+  }
+
+  public void testDeleteOnePerson() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson bob = new TestPerson(new TestPerson.Key("Bob"), 18);
+    schema.people().insert(Collections.singleton(bob));
+    schema.people().delete(Collections.singleton(bob));
+  }
+
+  public void testUpdateOnePerson() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson bob = new TestPerson(new TestPerson.Key("Bob"), 18);
+    schema.people().insert(Collections.singleton(bob));
+    bob.growOlder();
+    schema.people().update(Collections.singleton(bob));
+  }
+
+  public void testUpdateNoPerson() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson bob = new TestPerson(new TestPerson.Key("Bob"), 18);
+    try {
+      schema.people().update(Collections.singleton(bob));
+      fail("Update of missing person succeeded");
+    } catch (OrmConcurrencyException e) {
+      assertEquals("Concurrent modification detected", e.getMessage());
+    }
+  }
+
+  public void testFetchOnePerson() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson bob = new TestPerson(new TestPerson.Key("Bob"), 18);
+    schema.people().insert(Collections.singleton(bob));
+
+    final List<TestPerson> all = schema.people().all().toList();
+    assertNotNull(all);
+    assertEquals(1, all.size());
+    assertNotSame(bob, all.get(0));
+    assertEquals(bob.name(), all.get(0).name());
+    assertEquals(bob.age(), all.get(0).age());
+    assertEquals(bob.isRegistered(), all.get(0).isRegistered());
+  }
+
+  public void testFetchOnePersonByName() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson bob1 = new TestPerson(new TestPerson.Key("Bob"), 18);
+    schema.people().insert(Collections.singleton(bob1));
+
+    final TestPerson bob2 =
+        schema.people().get(new TestPerson.Key(bob1.name()));
+    assertNotNull(bob2);
+    assertNotSame(bob1, bob2);
+    assertEquals(bob1.name(), bob2.name());
+    assertEquals(bob1.age(), bob2.age());
+    assertEquals(bob1.isRegistered(), bob2.isRegistered());
+  }
+
+  public void testFetchByAge() throws Exception {
+    final PhoneBookDb schema = open();
+    final ArrayList<TestPerson> all = new ArrayList<TestPerson>();
+    all.add(new TestPerson(new TestPerson.Key("Bob"), 18));
+    all.add(new TestPerson(new TestPerson.Key("Mary"), 22));
+    all.add(new TestPerson(new TestPerson.Key("Zak"), 33));
+    schema.people().insert(all);
+
+    final List<TestPerson> r = schema.people().olderThan(20).toList();
+    assertEquals(2, r.size());
+    assertEquals(all.get(1).name(), r.get(0).name());
+    assertEquals(all.get(2).name(), r.get(1).name());
+  }
+
+  public void testBooleanType() throws Exception {
+    final PhoneBookDb schema = open();
+    final TestPerson bob = new TestPerson(new TestPerson.Key("Bob"), 18);
+    schema.people().insert(Collections.singleton(bob));
+
+    assertEquals(bob.isRegistered(), schema.people().all().toList().get(0)
+        .isRegistered());
+
+    bob.register();
+    schema.people().update(Collections.singleton(bob));
+
+    assertEquals(bob.isRegistered(), schema.people().all().toList().get(0)
+        .isRegistered());
+
+    bob.unregister();
+    schema.people().update(Collections.singleton(bob));
+
+    assertEquals(bob.isRegistered(), schema.people().all().toList().get(0)
+        .isRegistered());
+  }
+}