[datastore] Fix #3743

This change adds support for key == NULL to the datastore plugins
and replaces the offset argument with a next_uid and random arguments to
increase performance in the key == NULL case.

With the offset argument a datastore plugin would have to count all
matching keys before fetching the key at the right offset, which would
iterate over the entire database in the case of key == NULL.

The offset argument was used in two ways: to iterate over a set of
matching values and to start iteration at a random matching value. The new API
seperates these into two arguments: if random is true it will return a
random matching value, otherwise next_uid can be set to uid + 1 to return the
next matching value.

The random argument was not added to get_zero_anonymity. This function
is used to periodically insert zero anonymity values into the DHT. I
don't think it's necessary to randomize this.

12 files changed, 317 insertions, 740 deletions

diff --git a/src/datastore/datastore.h b/src/datastore/datastore.h
index 9de72f064..5fd360161 100644
--- a/src/datastore/datastore.h
+++ b/src/datastore/datastore.h
@@ -119,9 +119,14 @@ struct GetKeyMessage
   uint32_t type GNUNET_PACKED;
 
   /**
-   * Offset of the result.
+   * UID at which to start the search
    */
-  uint64_t offset GNUNET_PACKED;
+  uint64_t next_uid GNUNET_PACKED;
+
+  /**
+   * If true return a random result
+   */
+  uint32_t random GNUNET_PACKED;
 
   /**
    * Desired key.
@@ -148,9 +153,14 @@ struct GetMessage
   uint32_t type GNUNET_PACKED;
 
   /**
-   * Offset of the result.
+   * UID at which to start the search
+   */
+  uint64_t next_uid GNUNET_PACKED;
+
+  /**
+   * If true return a random result
    */
-  uint64_t offset GNUNET_PACKED;
+  uint32_t random GNUNET_PACKED;
 
 };
 
@@ -172,9 +182,9 @@ struct GetZeroAnonymityMessage
   uint32_t type GNUNET_PACKED;
 
   /**
-   * Offset of the result.
+   * UID at which to start the search
    */
-  uint64_t offset GNUNET_PACKED;
+  uint64_t next_uid GNUNET_PACKED;
 
 };
 
diff --git a/src/datastore/datastore_api.c b/src/datastore/datastore_api.c
index c677654aa..26e1e501d 100644
--- a/src/datastore/datastore_api.c
+++ b/src/datastore/datastore_api.c
@@ -1325,10 +1325,7 @@ GNUNET_DATASTORE_get_for_replication (struct GNUNET_DATASTORE_Handle *h,
  * Get a single zero-anonymity value from the datastore.
  *
  * @param h handle to the datastore
- * @param offset offset of the result (modulo num-results); set to
- *               a random 64-bit value initially; then increment by
- *               one each time; detect that all results have been found by uid
- *               being again the first uid ever returned.
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param queue_priority ranking of this request in the priority queue
  * @param max_queue_size at what queue size should this request be dropped
  *        (if other requests of higher priority are in the queue)
@@ -1342,7 +1339,7 @@ GNUNET_DATASTORE_get_for_replication (struct GNUNET_DATASTORE_Handle *h,
  */
 struct GNUNET_DATASTORE_QueueEntry *
 GNUNET_DATASTORE_get_zero_anonymity (struct GNUNET_DATASTORE_Handle *h,
-                                     uint64_t offset,
+                                     uint64_t next_uid,
                                      unsigned int queue_priority,
                                      unsigned int max_queue_size,
                                      enum GNUNET_BLOCK_Type type,
@@ -1357,13 +1354,12 @@ GNUNET_DATASTORE_get_zero_anonymity (struct GNUNET_DATASTORE_Handle *h,
   GNUNET_assert (NULL != proc);
   GNUNET_assert (type != GNUNET_BLOCK_TYPE_ANY);
   LOG (GNUNET_ERROR_TYPE_DEBUG,
-       "Asked to get %llu-th zero-anonymity entry of type %d\n",
-       (unsigned long long) offset,
+       "Asked to get a zero-anonymity entry of type %d\n",
        type);
   env = GNUNET_MQ_msg (m,
                        GNUNET_MESSAGE_TYPE_DATASTORE_GET_ZERO_ANONYMITY);
   m->type = htonl ((uint32_t) type);
-  m->offset = GNUNET_htonll (offset);
+  m->next_uid = GNUNET_htonll (next_uid);
   qc.rc.proc = proc;
   qc.rc.proc_cls = proc_cls;
   qe = make_queue_entry (h,
@@ -1392,10 +1388,8 @@ GNUNET_DATASTORE_get_zero_anonymity (struct GNUNET_DATASTORE_Handle *h,
  * will only be called once.
  *
  * @param h handle to the datastore
- * @param offset offset of the result (modulo num-results); set to
- *               a random 64-bit value initially; then increment by
- *               one each time; detect that all results have been found by uid
- *               being again the first uid ever returned.
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
  * @param type desired type, 0 for any
  * @param queue_priority ranking of this request in the priority queue
@@ -1409,7 +1403,8 @@ GNUNET_DATASTORE_get_zero_anonymity (struct GNUNET_DATASTORE_Handle *h,
  */
 struct GNUNET_DATASTORE_QueueEntry *
 GNUNET_DATASTORE_get_key (struct GNUNET_DATASTORE_Handle *h,
-                          uint64_t offset,
+                          uint64_t next_uid,
+                          bool random,
                           const struct GNUNET_HashCode *key,
                           enum GNUNET_BLOCK_Type type,
                           unsigned int queue_priority,
@@ -1433,14 +1428,16 @@ GNUNET_DATASTORE_get_key (struct GNUNET_DATASTORE_Handle *h,
     env = GNUNET_MQ_msg (gm,
                          GNUNET_MESSAGE_TYPE_DATASTORE_GET);
     gm->type = htonl (type);
-    gm->offset = GNUNET_htonll (offset);
+    gm->next_uid = GNUNET_htonll (next_uid);
+    gm->random = random;
   }
   else
   {
     env = GNUNET_MQ_msg (gkm,
                          GNUNET_MESSAGE_TYPE_DATASTORE_GET_KEY);
     gkm->type = htonl (type);
-    gkm->offset = GNUNET_htonll (offset);
+    gkm->next_uid = GNUNET_htonll (next_uid);
+    gkm->random = random;
     gkm->key = *key;
   }
   qc.rc.proc = proc;
diff --git a/src/datastore/gnunet-datastore.c b/src/datastore/gnunet-datastore.c
index 509c7f8b1..c93bc8dd3 100644
--- a/src/datastore/gnunet-datastore.c
+++ b/src/datastore/gnunet-datastore.c
@@ -171,7 +171,7 @@ static void
 do_get ()
 {
   qe = GNUNET_DATASTORE_get_key (db_src,
-                                 offset,
+                                 0, false,
                                  NULL, GNUNET_BLOCK_TYPE_ANY,
                                  0, 1,
                                  &do_put, NULL);
diff --git a/src/datastore/gnunet-service-datastore.c b/src/datastore/gnunet-service-datastore.c
index dabec3d6d..af33c4412 100644
--- a/src/datastore/gnunet-service-datastore.c
+++ b/src/datastore/gnunet-service-datastore.c
@@ -984,12 +984,13 @@ handle_put (void *cls,
                         size,
                         &vhash);
     plugin->api->get_key (plugin->api->cls,
-                          0,
-                          &dm->key,
-                          &vhash,
+                          0,
+                          false,
+                          &dm->key,
+                          &vhash,
                           ntohl (dm->type),
-                          &check_present,
-                          pc);
+                          &check_present,
+                          pc);
     GNUNET_SERVICE_client_continue (client);
     return;
   }
@@ -1018,7 +1019,8 @@ handle_get (void *cls,
                             1,
                             GNUNET_NO);
   plugin->api->get_key (plugin->api->cls,
-                        GNUNET_ntohll (msg->offset),
+                        GNUNET_ntohll (msg->next_uid),
+                        msg->random,
                         NULL,
                         NULL,
                         ntohl (msg->type),
@@ -1069,7 +1071,8 @@ handle_get_key (void *cls,
     return;
   }
   plugin->api->get_key (plugin->api->cls,
-                        GNUNET_ntohll (msg->offset),
+                        GNUNET_ntohll (msg->next_uid),
+                        msg->random,
                         &msg->key,
                         NULL,
                         ntohl (msg->type),
@@ -1131,7 +1134,7 @@ handle_get_zero_anonymity (void *cls,
                             1,
                             GNUNET_NO);
   plugin->api->get_zero_anonymity (plugin->api->cls,
-                                   GNUNET_ntohll (msg->offset),
+                                   GNUNET_ntohll (msg->next_uid),
                                    type,
                                    &transmit_item,
                                    client);
@@ -1241,6 +1244,7 @@ handle_remove (void *cls,
               (uint32_t) ntohl (dm->type));
   plugin->api->get_key (plugin->api->cls,
                         0,
+                        false,
                         &dm->key,
                         &vhash,
                         (enum GNUNET_BLOCK_Type) ntohl (dm->type),
diff --git a/src/datastore/plugin_datastore_heap.c b/src/datastore/plugin_datastore_heap.c
index 199c03a50..e15cacb5b 100644
--- a/src/datastore/plugin_datastore_heap.c
+++ b/src/datastore/plugin_datastore_heap.c
@@ -323,19 +323,19 @@ struct GetContext
 {
 
   /**
-   * Desired result offset / number of results.
+   * Lowest uid to consider.
    */
-  uint64_t offset;
+  uint64_t next_uid;
 
   /**
-   * The plugin.
+   * Value with lowest uid >= next_uid found so far.
    */
-  struct Plugin *plugin;
+  struct Value *value;
 
   /**
    * Requested value hash.
    */
-  const struct GNUNET_HashCode * vhash;
+  const struct GNUNET_HashCode *vhash;
 
   /**
    * Requested type.
@@ -343,68 +343,15 @@ struct GetContext
   enum GNUNET_BLOCK_Type type;
 
   /**
-   * Function to call with the result.
+   * If true, return a random value
    */
-  PluginDatumProcessor proc;
+  bool random;
 
-  /**
-   * Closure for 'proc'.
-   */
-  void *proc_cls;
 };
 
 
 /**
- * Test if a value matches the specification from the 'get' context
- *
- * @param gc query
- * @param value the value to check against the query
- * @return GNUNET_YES if the value matches
- */
-static int
-match (const struct GetContext *gc,
-       struct Value *value)
-{
-  struct GNUNET_HashCode vh;
-
-  if ( (gc->type != GNUNET_BLOCK_TYPE_ANY) &&
-       (gc->type != value->type) )
-    return GNUNET_NO;
-  if (NULL != gc->vhash)
-  {
-    GNUNET_CRYPTO_hash (&value[1], value->size, &vh);
-    if (0 != memcmp (&vh, gc->vhash, sizeof (struct GNUNET_HashCode)))
-      return GNUNET_NO;
-  }
-  return GNUNET_YES;
-}
-
-
-/**
- * Count number of matching values.
- *
- * @param cls the 'struct GetContext'
- * @param key unused
- * @param val the 'struct Value'
- * @return GNUNET_YES (continue iteration)
- */
-static int
-count_iterator (void *cls,
-                const struct GNUNET_HashCode *key,
-                void *val)
-{
-  struct GetContext *gc = cls;
-  struct Value *value = val;
-
-  if (GNUNET_NO == match (gc, value))
-    return GNUNET_OK;
-  gc->offset++;
-  return GNUNET_OK;
-}
-
-
-/**
- * Obtain matching value at 'offset'.
+ * Obtain the matching value with the lowest uid >= next_uid.
  *
  * @param cls the 'struct GetContext'
  * @param key unused
@@ -418,23 +365,29 @@ get_iterator (void *cls,
 {
   struct GetContext *gc = cls;
   struct Value *value = val;
+  struct GNUNET_HashCode vh;
 
-  if (GNUNET_NO == match (gc, value))
+  if ( (gc->type != GNUNET_BLOCK_TYPE_ANY) &&
+       (gc->type != value->type) )
     return GNUNET_OK;
-  if (0 != gc->offset--)
+  if (NULL != gc->vhash)
+  {
+    GNUNET_CRYPTO_hash (&value[1], value->size, &vh);
+    if (0 != memcmp (&vh, gc->vhash, sizeof (struct GNUNET_HashCode)))
+      return GNUNET_OK;
+  }
+  if (gc->random)
+  {
+    gc->value = value;
+    return GNUNET_NO;
+  }
+  if ( (uint64_t) (intptr_t) value < gc->next_uid)
     return GNUNET_OK;
-  if (GNUNET_NO ==
-      gc->proc (gc->proc_cls,
-                key,
-                value->size,
-                &value[1],
-                value->type,
-                value->priority,
-                value->anonymity,
-            value->expiration,
-                (uint64_t) (long) value))
-    delete_value (gc->plugin, value);
-  return GNUNET_NO;
+  if ( (NULL != gc->value) &&
+       (value > gc->value) )
+    return GNUNET_OK;
+  gc->value = value;
+  return GNUNET_OK;
 }
 
 
@@ -442,8 +395,8 @@ get_iterator (void *cls,
  * Get one of the results for a particular key in the datastore.
  *
  * @param cls closure
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
  * @param vhash hash of the value, maybe NULL (to
  *        match all values that have the right key).
@@ -457,7 +410,7 @@ get_iterator (void *cls,
  * @param proc_cls closure for proc
  */
 static void
-heap_plugin_get_key (void *cls, uint64_t offset,
+heap_plugin_get_key (void *cls, uint64_t next_uid, bool random,
                      const struct GNUNET_HashCode *key,
                      const struct GNUNET_HashCode *vhash,
                      enum GNUNET_BLOCK_Type type, PluginDatumProcessor proc,
@@ -466,25 +419,14 @@ heap_plugin_get_key (void *cls, uint64_t offset,
   struct Plugin *plugin = cls;
   struct GetContext gc;
 
-  gc.plugin = plugin;
-  gc.offset = 0;
+  gc.value = NULL;
+  gc.next_uid = next_uid;
+  gc.random = random;
   gc.vhash = vhash;
   gc.type = type;
-  gc.proc = proc;
-  gc.proc_cls = proc_cls;
   if (NULL == key)
   {
     GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
-                                           &count_iterator,
-                                           &gc);
-    if (0 == gc.offset)
-    {
-      proc (proc_cls,
-            NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
-      return;
-    }
-    gc.offset = offset % gc.offset;
-    GNUNET_CONTAINER_multihashmap_iterate (plugin->keyvalue,
                                            &get_iterator,
                                            &gc);
   }
@@ -492,20 +434,27 @@ heap_plugin_get_key (void *cls, uint64_t offset,
   {
     GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
                                                 key,
-                                                &count_iterator,
-                                                &gc);
-    if (0 == gc.offset)
-    {
-      proc (proc_cls,
-            NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
-      return;
-    }
-    gc.offset = offset % gc.offset;
-    GNUNET_CONTAINER_multihashmap_get_multiple (plugin->keyvalue,
-                                                key,
                                                 &get_iterator,
                                                 &gc);
   }
+  if (NULL == gc.value)
+  {
+    proc (proc_cls, NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
+    return;
+  }
+  if (GNUNET_NO ==
+      proc (proc_cls,
+            &gc.value->key,
+            gc.value->size,
+            &gc.value[1],
+            gc.value->type,
+            gc.value->priority,
+            gc.value->anonymity,
+            gc.value->expiration,
+            (uint64_t) (intptr_t) gc.value))
+  {
+    delete_value (plugin, gc.value);
+  }
 }
 
 
@@ -559,7 +508,7 @@ heap_plugin_get_replication (void *cls,
             value->priority,
             value->anonymity,
             value->expiration,
-            (uint64_t) (long) value))
+            (uint64_t) (intptr_t) value))
     delete_value (plugin, value);
 }
 
@@ -595,7 +544,7 @@ heap_plugin_get_expiration (void *cls, PluginDatumProcessor proc,
             value->priority,
             value->anonymity,
             value->expiration,
-            (uint64_t) (long) value))
+            (uint64_t) (intptr_t) value))
     delete_value (plugin, value);
 }
 
@@ -628,7 +577,7 @@ heap_plugin_update (void *cls,
 {
   struct Value *value;
 
-  value = (struct Value*) (long) uid;
+  value = (struct Value*) (intptr_t) uid;
   GNUNET_assert (NULL != value);
   if (value->expiration.abs_value_us != expire.abs_value_us)
   {
@@ -649,53 +598,43 @@ heap_plugin_update (void *cls,
  * Call the given processor on an item with zero anonymity.
  *
  * @param cls our "struct Plugin*"
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param type entries of which type should be considered?
- *        Use 0 for any type.
+ *        Must not be zero (ANY).
  * @param proc function to call on each matching value;
- *        will be called  with NULL if no value matches
+ *        will be called with NULL if no value matches
  * @param proc_cls closure for proc
  */
 static void
-heap_plugin_get_zero_anonymity (void *cls, uint64_t offset,
+heap_plugin_get_zero_anonymity (void *cls, uint64_t next_uid,
                                 enum GNUNET_BLOCK_Type type,
                                 PluginDatumProcessor proc, void *proc_cls)
 {
   struct Plugin *plugin = cls;
   struct ZeroAnonByType *zabt;
-  struct Value *value;
-  uint64_t count;
+  struct Value *value = NULL;
 
-  count = 0;
   for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
   {
     if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
-         (type != zabt->type) )
+         (type != zabt->type) )
       continue;
-    count += zabt->array_pos;
+    for (int i = 0; i < zabt->array_pos; ++i)
+    {
+      if ( (uint64_t) (intptr_t) zabt->array[i] < next_uid)
+        continue;
+      if ( (NULL != value) &&
+           (zabt->array[i] > value) )
+        continue;
+      value = zabt->array[i];
+    }
   }
-  if (0 == count)
+  if (NULL == value)
   {
     proc (proc_cls,
-          NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
+          NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
     return;
   }
-  offset = offset % count;
-  for (zabt = plugin->zero_head; NULL != zabt; zabt = zabt->next)
-  {
-    if ( (type != GNUNET_BLOCK_TYPE_ANY) &&
-         (type != zabt->type) )
-      continue;
-    if (offset >= zabt->array_pos)
-    {
-      offset -= zabt->array_pos;
-      continue;
-    }
-    break;
-  }
-  GNUNET_assert (NULL != zabt);
-  value = zabt->array[offset];
   if (GNUNET_NO ==
       proc (proc_cls,
             &value->key,
@@ -705,7 +644,7 @@ heap_plugin_get_zero_anonymity (void *cls, uint64_t offset,
             value->priority,
             value->anonymity,
             value->expiration,
-            (uint64_t) (long) value))
+            (uint64_t) (intptr_t) value))
     delete_value (plugin, value);
 }
 
diff --git a/src/datastore/plugin_datastore_mysql.c b/src/datastore/plugin_datastore_mysql.c
index 1067064aa..5ae4485cb 100644
--- a/src/datastore/plugin_datastore_mysql.c
+++ b/src/datastore/plugin_datastore_mysql.c
@@ -150,28 +150,19 @@ struct Plugin
 #define DELETE_ENTRY_BY_UID "DELETE FROM gn090 WHERE uid=?"
   struct GNUNET_MYSQL_StatementHandle *delete_entry_by_uid;
 
-#define COUNT_ENTRY_BY_HASH "SELECT count(*) FROM gn090 FORCE INDEX (idx_hash) WHERE hash=?"
-  struct GNUNET_MYSQL_StatementHandle *count_entry_by_hash;
+#define SELECT_ENTRY "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 WHERE uid >= ? AND (rvalue >= ? OR 0 = ?) ORDER BY uid LIMIT 1"
+  struct GNUNET_MYSQL_StatementHandle *select_entry;
 
-#define SELECT_ENTRY_BY_HASH "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash) WHERE hash=? ORDER BY uid LIMIT 1 OFFSET ?"
+#define SELECT_ENTRY_BY_HASH "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash) WHERE hash=? AND uid >= ? AND (rvalue >= ? OR 0 = ?) ORDER BY uid LIMIT 1"
   struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash;
 
-#define COUNT_ENTRY_BY_HASH_AND_VHASH "SELECT count(*) FROM gn090 FORCE INDEX (idx_hash_vhash) WHERE hash=? AND vhash=?"
-  struct GNUNET_MYSQL_StatementHandle *count_entry_by_hash_and_vhash;
-
-#define SELECT_ENTRY_BY_HASH_AND_VHASH "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash_vhash) WHERE hash=? AND vhash=? ORDER BY uid LIMIT 1 OFFSET ?"
+#define SELECT_ENTRY_BY_HASH_AND_VHASH "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash_vhash) WHERE hash=? AND vhash=? AND uid >= ? AND (rvalue >= ? OR 0 = ?) ORDER BY uid LIMIT 1"
   struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash_and_vhash;
 
-#define COUNT_ENTRY_BY_HASH_AND_TYPE "SELECT count(*) FROM gn090 FORCE INDEX (idx_hash_type_uid) WHERE hash=? AND type=?"
-  struct GNUNET_MYSQL_StatementHandle *count_entry_by_hash_and_type;
-
-#define SELECT_ENTRY_BY_HASH_AND_TYPE "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash_type_uid) WHERE hash=? AND type=? ORDER BY uid LIMIT 1 OFFSET ?"
+#define SELECT_ENTRY_BY_HASH_AND_TYPE "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash_type_uid) WHERE hash=? AND type=? AND uid >= ? AND (rvalue >= ? OR 0 = ?) ORDER BY uid LIMIT 1"
   struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash_and_type;
 
-#define COUNT_ENTRY_BY_HASH_VHASH_AND_TYPE "SELECT count(*) FROM gn090 FORCE INDEX (idx_hash_vhash) WHERE hash=? AND vhash=? AND type=?"
-  struct GNUNET_MYSQL_StatementHandle *count_entry_by_hash_vhash_and_type;
-
-#define SELECT_ENTRY_BY_HASH_VHASH_AND_TYPE "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash_vhash) WHERE hash=? AND vhash=? AND type=? ORDER BY uid ASC LIMIT 1 OFFSET ?"
+#define SELECT_ENTRY_BY_HASH_VHASH_AND_TYPE "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_hash_vhash) WHERE hash=? AND vhash=? AND type=? AND uid >= ? AND (rvalue >= ? OR 0 = ?) ORDER BY uid LIMIT 1"
   struct GNUNET_MYSQL_StatementHandle *select_entry_by_hash_vhash_and_type;
 
 #define UPDATE_ENTRY "UPDATE gn090 SET prio=prio+?,expire=IF(expire>=?,expire,?) WHERE uid=?"
@@ -185,10 +176,8 @@ struct Plugin
 
 #define SELECT_IT_NON_ANONYMOUS "SELECT type,prio,anonLevel,expire,hash,value,uid "\
    "FROM gn090 FORCE INDEX (idx_anonLevel_type_rvalue) "\
-   "WHERE anonLevel=0 AND type=? AND "\
-   "(rvalue >= ? OR"\
-   "  NOT EXISTS (SELECT 1 FROM gn090 FORCE INDEX (idx_anonLevel_type_rvalue) WHERE anonLevel=0 AND type=? AND rvalue>=?)) "\
-   "ORDER BY rvalue ASC LIMIT 1"
+   "WHERE anonLevel=0 AND type=? AND uid >= ? "\
+   "ORDER BY uid LIMIT 1"
   struct GNUNET_MYSQL_StatementHandle *zero_iter;
 
 #define SELECT_IT_EXPIRATION "SELECT type,prio,anonLevel,expire,hash,value,uid FROM gn090 FORCE INDEX (idx_expire) WHERE expire < ? ORDER BY expire ASC LIMIT 1"
@@ -541,8 +530,8 @@ execute_select (struct Plugin *plugin,
  * Get one of the results for a particular key in the datastore.
  *
  * @param cls closure
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
  * @param key key to match, never NULL
  * @param vhash hash of the value, maybe NULL (to
  *        match all values that have the right key).
@@ -557,7 +546,8 @@ execute_select (struct Plugin *plugin,
  */
 static void
 mysql_plugin_get_key (void *cls,
-                      uint64_t offset,
+                      uint64_t next_uid,
+                      bool random,
                       const struct GNUNET_HashCode *key,
                       const struct GNUNET_HashCode *vhash,
                       enum GNUNET_BLOCK_Type type,
@@ -565,121 +555,33 @@ mysql_plugin_get_key (void *cls,
                       void *proc_cls)
 {
   struct Plugin *plugin = cls;
-  int ret;
-  uint64_t total;
-  struct GNUNET_MY_ResultSpec results_get[] = {
-    GNUNET_MY_result_spec_uint64 (&total),
-    GNUNET_MY_result_spec_end
-  };
+  uint64_t rvalue;
 
-  total = UINT64_MAX;
-  if (0 != type)
+  if (random)
   {
-    if (NULL != vhash)
-    {
-      struct GNUNET_MY_QueryParam params_get[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_auto_from_type (vhash),
-        GNUNET_MY_query_param_uint32 (&type),
-        GNUNET_MY_query_param_end
-      };
-
-      ret =
-        GNUNET_MY_exec_prepared (plugin->mc,
-                                 plugin->count_entry_by_hash_vhash_and_type,
-                                 params_get);
-      GNUNET_break (GNUNET_OK == ret);
-      if (GNUNET_OK == ret)
-        ret =
-          GNUNET_MY_extract_result (plugin->count_entry_by_hash_vhash_and_type,
-                                    results_get);
-      if (GNUNET_OK == ret)
-        GNUNET_break (GNUNET_NO ==
-                      GNUNET_MY_extract_result (plugin->count_entry_by_hash_vhash_and_type,
-                                                NULL));
-    }
-    else
-    {
-      struct GNUNET_MY_QueryParam params_get[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_uint32 (&type),
-        GNUNET_MY_query_param_end
-      };
-
-      ret =
-        GNUNET_MY_exec_prepared (plugin->mc,
-                                 plugin->count_entry_by_hash_and_type,
-                                 params_get);
-      GNUNET_break (GNUNET_OK == ret);
-      if (GNUNET_OK == ret)
-        ret =
-          GNUNET_MY_extract_result (plugin->count_entry_by_hash_and_type,
-                                    results_get);
-      if (GNUNET_OK == ret)
-        GNUNET_break (GNUNET_NO ==
-                      GNUNET_MY_extract_result (plugin->count_entry_by_hash_and_type,
-                                                NULL));
-    }
+    rvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                       UINT64_MAX);
+    next_uid = 0;
   }
   else
-  {
-    if (NULL != vhash)
-    {
-      struct GNUNET_MY_QueryParam params_get[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_auto_from_type (vhash),
-        GNUNET_MY_query_param_end
-      };
+    rvalue = 0;
 
-      ret =
-        GNUNET_MY_exec_prepared (plugin->mc,
-                                 plugin->count_entry_by_hash_and_vhash,
-                                 params_get);
-      GNUNET_break (GNUNET_OK == ret);
-      if (GNUNET_OK == ret)
-        ret =
-          GNUNET_MY_extract_result (plugin->count_entry_by_hash_and_vhash,
-                                    results_get);
-      if (GNUNET_OK == ret)
-        GNUNET_break (GNUNET_NO ==
-                      GNUNET_MY_extract_result (plugin->count_entry_by_hash_and_vhash,
-                                                NULL));
-    }
-    else
-    {
-      struct GNUNET_MY_QueryParam params_get[] = {
-        GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_end
-      };
-
-      ret =
-        GNUNET_MY_exec_prepared (plugin->mc,
-                                 plugin->count_entry_by_hash,
-                                 params_get);
-      GNUNET_break (GNUNET_OK == ret);
-      if (GNUNET_OK == ret)
-        ret =
-          GNUNET_MY_extract_result (plugin->count_entry_by_hash,
-                                    results_get);
-      if (GNUNET_OK == ret)
-        GNUNET_break (GNUNET_NO ==
-                      GNUNET_MY_extract_result (plugin->count_entry_by_hash,
-                                                NULL));
-    }
-  }
-  if ( (GNUNET_OK != ret) ||
-       (0 >= total) )
+  if (NULL == key)
   {
-    proc (proc_cls, NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
-    return;
+    struct GNUNET_MY_QueryParam params_select[] = {
+      GNUNET_MY_query_param_uint64 (&next_uid),
+      GNUNET_MY_query_param_uint64 (&rvalue),
+      GNUNET_MY_query_param_uint64 (&rvalue),
+      GNUNET_MY_query_param_end
+    };
+
+    execute_select (plugin,
+                    plugin->select_entry,
+                    proc,
+                    proc_cls,
+                    params_select);
   }
-  offset = offset % total;
-  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-              "Obtaining %llu/%lld result for GET `%s'\n",
-              (unsigned long long) offset,
-              (unsigned long long) total,
-              GNUNET_h2s (key));
-  if (type != GNUNET_BLOCK_TYPE_ANY)
+  else if (type != GNUNET_BLOCK_TYPE_ANY)
   {
     if (NULL != vhash)
     {
@@ -687,7 +589,9 @@ mysql_plugin_get_key (void *cls,
         GNUNET_MY_query_param_auto_from_type (key),
         GNUNET_MY_query_param_auto_from_type (vhash),
         GNUNET_MY_query_param_uint32 (&type),
-        GNUNET_MY_query_param_uint64 (&offset),
+        GNUNET_MY_query_param_uint64 (&next_uid),
+        GNUNET_MY_query_param_uint64 (&rvalue),
+        GNUNET_MY_query_param_uint64 (&rvalue),
         GNUNET_MY_query_param_end
       };
 
@@ -702,7 +606,9 @@ mysql_plugin_get_key (void *cls,
       struct GNUNET_MY_QueryParam params_select[] = {
         GNUNET_MY_query_param_auto_from_type (key),
         GNUNET_MY_query_param_uint32 (&type),
-        GNUNET_MY_query_param_uint64 (&offset),
+        GNUNET_MY_query_param_uint64 (&next_uid),
+        GNUNET_MY_query_param_uint64 (&rvalue),
+        GNUNET_MY_query_param_uint64 (&rvalue),
         GNUNET_MY_query_param_end
       };
 
@@ -720,7 +626,9 @@ mysql_plugin_get_key (void *cls,
       struct GNUNET_MY_QueryParam params_select[] = {
         GNUNET_MY_query_param_auto_from_type (key),
         GNUNET_MY_query_param_auto_from_type (vhash),
-        GNUNET_MY_query_param_uint64 (&offset),
+        GNUNET_MY_query_param_uint64 (&next_uid),
+        GNUNET_MY_query_param_uint64 (&rvalue),
+        GNUNET_MY_query_param_uint64 (&rvalue),
         GNUNET_MY_query_param_end
       };
 
@@ -734,7 +642,9 @@ mysql_plugin_get_key (void *cls,
     {
       struct GNUNET_MY_QueryParam params_select[] = {
         GNUNET_MY_query_param_auto_from_type (key),
-        GNUNET_MY_query_param_uint64 (&offset),
+        GNUNET_MY_query_param_uint64 (&next_uid),
+        GNUNET_MY_query_param_uint64 (&rvalue),
+        GNUNET_MY_query_param_uint64 (&rvalue),
         GNUNET_MY_query_param_end
       };
 
@@ -753,28 +663,26 @@ mysql_plugin_get_key (void *cls,
  * Get a zero-anonymity datum from the datastore.
  *
  * @param cls our `struct Plugin *`
- * @param offset offset of the result
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param type entries of which type should be considered?
- *        Use 0 for any type.
- * @param proc function to call on a matching value or NULL
+ *        Must not be zero (ANY).
+ * @param proc function to call on a matching value;
+ *        will be called with NULL if no value matches
  * @param proc_cls closure for @a proc
  */
 static void
 mysql_plugin_get_zero_anonymity (void *cls,
-                                 uint64_t offset,
+                                 uint64_t next_uid,
                                  enum GNUNET_BLOCK_Type type,
                                  PluginDatumProcessor proc,
                                  void *proc_cls)
 {
   struct Plugin *plugin = cls;
   uint32_t typei = (uint32_t) type;
-  uint64_t rvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
-                                              UINT64_MAX);
+
   struct GNUNET_MY_QueryParam params_zero_iter[] = {
     GNUNET_MY_query_param_uint32 (&typei),
-    GNUNET_MY_query_param_uint64 (&rvalue),
-    GNUNET_MY_query_param_uint32 (&typei),
-    GNUNET_MY_query_param_uint64 (&rvalue),
+    GNUNET_MY_query_param_uint64 (&next_uid),
     GNUNET_MY_query_param_end
   };
 
@@ -1209,6 +1117,7 @@ libgnunet_plugin_datastore_mysql_init (void *cls)
        ") ENGINE=InnoDB") || MRUNS ("SET AUTOCOMMIT = 1") ||
       PINIT (plugin->insert_entry, INSERT_ENTRY) ||
       PINIT (plugin->delete_entry_by_uid, DELETE_ENTRY_BY_UID) ||
+      PINIT (plugin->select_entry, SELECT_ENTRY) ||
       PINIT (plugin->select_entry_by_hash, SELECT_ENTRY_BY_HASH) ||
       PINIT (plugin->select_entry_by_hash_and_vhash,
              SELECT_ENTRY_BY_HASH_AND_VHASH) ||
@@ -1216,13 +1125,7 @@ libgnunet_plugin_datastore_mysql_init (void *cls)
              SELECT_ENTRY_BY_HASH_AND_TYPE) ||
       PINIT (plugin->select_entry_by_hash_vhash_and_type,
              SELECT_ENTRY_BY_HASH_VHASH_AND_TYPE) ||
-      PINIT (plugin->count_entry_by_hash, COUNT_ENTRY_BY_HASH) ||
       PINIT (plugin->get_size, SELECT_SIZE) ||
-      PINIT (plugin->count_entry_by_hash_and_vhash,
-             COUNT_ENTRY_BY_HASH_AND_VHASH) ||
-      PINIT (plugin->count_entry_by_hash_and_type, COUNT_ENTRY_BY_HASH_AND_TYPE)
-      || PINIT (plugin->count_entry_by_hash_vhash_and_type,
-                COUNT_ENTRY_BY_HASH_VHASH_AND_TYPE) ||
       PINIT (plugin->update_entry, UPDATE_ENTRY) ||
       PINIT (plugin->dec_repl, DEC_REPL) ||
       PINIT (plugin->zero_iter, SELECT_IT_NON_ANONYMOUS) ||
diff --git a/src/datastore/plugin_datastore_postgres.c b/src/datastore/plugin_datastore_postgres.c
index 8b8737935..0376ebb6c 100644
--- a/src/datastore/plugin_datastore_postgres.c
+++ b/src/datastore/plugin_datastore_postgres.c
@@ -80,6 +80,7 @@ init_connection (struct Plugin *plugin)
    * we only test equality on it and can cast it to/from uint32_t. For repl, prio, and anonLevel
    * we do math or inequality tests, so we can't handle the entire range of uint32_t.
    * This will also cause problems for expiration times after 294247-01-10-04:00:54 UTC.
+   * PostgreSQL also recommends against using WITH OIDS.
    */
   ret =
       PQexec (plugin->dbh,
@@ -176,40 +177,18 @@ init_connection (struct Plugin *plugin)
   }
   PQclear (ret);
   if ((GNUNET_OK !=
-       GNUNET_POSTGRES_prepare (plugin->dbh, "getvt",
-                   "SELECT type, prio, anonLevel, expire, hash, value, oid FROM gn090 "
-                   "WHERE hash=$1 AND vhash=$2 AND type=$3 "
-                   "ORDER BY oid ASC LIMIT 1 OFFSET $4", 4)) ||
-      (GNUNET_OK !=
-       GNUNET_POSTGRES_prepare (plugin->dbh, "gett",
-                   "SELECT type, prio, anonLevel, expire, hash, value, oid FROM gn090 "
-                   "WHERE hash=$1 AND type=$2 "
-                   "ORDER BY oid ASC LIMIT 1 OFFSET $3", 3)) ||
-      (GNUNET_OK !=
-       GNUNET_POSTGRES_prepare (plugin->dbh, "getv",
-                   "SELECT type, prio, anonLevel, expire, hash, value, oid FROM gn090 "
-                   "WHERE hash=$1 AND vhash=$2 "
-                   "ORDER BY oid ASC LIMIT 1 OFFSET $3", 3)) ||
-      (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "get",
                    "SELECT type, prio, anonLevel, expire, hash, value, oid FROM gn090 "
-                   "WHERE hash=$1 " "ORDER BY oid ASC LIMIT 1 OFFSET $2", 2)) ||
-      (GNUNET_OK !=
-       GNUNET_POSTGRES_prepare (plugin->dbh, "count_getvt",
-                                "SELECT count(*) FROM gn090 WHERE hash=$1 AND vhash=$2 AND type=$3", 3)) ||
-      (GNUNET_OK !=
-       GNUNET_POSTGRES_prepare (plugin->dbh, "count_gett",
-                                "SELECT count(*) FROM gn090 WHERE hash=$1 AND type=$2", 2)) ||
-      (GNUNET_OK !=
-       GNUNET_POSTGRES_prepare (plugin->dbh, "count_getv",
-                                "SELECT count(*) FROM gn090 WHERE hash=$1 AND vhash=$2", 2)) ||
-      (GNUNET_OK !=
-       GNUNET_POSTGRES_prepare (plugin->dbh, "count_get",
-                                "SELECT count(*) FROM gn090 WHERE hash=$1", 1)) ||
+                   "WHERE oid >= $1::bigint AND "
+                   "(rvalue >= $2 OR 0 = $3::smallint) AND "
+                   "(hash = $4 OR 0 = $5::smallint) AND "
+                   "(vhash = $6 OR 0 = $7::smallint) AND "
+                   "(type = $8 OR 0 = $9::smallint) "
+                   "ORDER BY oid ASC LIMIT 1", 9)) ||
       (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "put",
                    "INSERT INTO gn090 (repl, type, prio, anonLevel, expire, rvalue, hash, vhash, value) "
-                   "VALUES ($1, $2, $3, $4, $5, RANDOM(), $6, $7, $8)", 9)) ||
+                   "VALUES ($1, $2, $3, $4, $5, $6, $7, $8, $9)", 9)) ||
       (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "update",
                    "UPDATE gn090 SET prio = prio + $1, expire = CASE WHEN expire < $2 THEN $2 ELSE expire END "
@@ -221,8 +200,9 @@ init_connection (struct Plugin *plugin)
       (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "select_non_anonymous",
                    "SELECT type, prio, anonLevel, expire, hash, value, oid FROM gn090 "
-                   "WHERE anonLevel = 0 AND type = $1 ORDER BY oid DESC LIMIT 1 OFFSET $2",
-                   1)) ||
+                   "WHERE anonLevel = 0 AND type = $1 AND oid >= $2::bigint "
+                   "ORDER BY oid ASC LIMIT 1",
+                   2)) ||
       (GNUNET_OK !=
        GNUNET_POSTGRES_prepare (plugin->dbh, "select_expiration_order",
                    "(SELECT type, prio, anonLevel, expire, hash, value, oid FROM gn090 "
@@ -328,6 +308,8 @@ postgres_plugin_put (void *cls,
   struct Plugin *plugin = cls;
   uint32_t utype = type;
   struct GNUNET_HashCode vhash;
+  uint64_t rvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                              UINT64_MAX);
   PGresult *ret;
   struct GNUNET_PQ_QueryParam params[] = {
     GNUNET_PQ_query_param_uint32 (&replication),
@@ -335,6 +317,7 @@ postgres_plugin_put (void *cls,
     GNUNET_PQ_query_param_uint32 (&priority),
     GNUNET_PQ_query_param_uint32 (&anonymity),
     GNUNET_PQ_query_param_absolute_time (&expiration),
+    GNUNET_PQ_query_param_uint64 (&rvalue),
     GNUNET_PQ_query_param_auto_from_type (key),
     GNUNET_PQ_query_param_auto_from_type (&vhash),
     GNUNET_PQ_query_param_fixed_size (data, size),
@@ -495,12 +478,11 @@ process_result (struct Plugin *plugin,
 
 
 /**
- * Iterate over the results for a particular key
- * in the datastore.
+ * Get one of the results for a particular key in the datastore.
  *
  * @param cls closure with the 'struct Plugin'
- * @param offset offset of the result (modulo num-results);
- *        specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
  * @param vhash hash of the value, maybe NULL (to
  *        match all values that have the right key).
@@ -510,160 +492,52 @@ process_result (struct Plugin *plugin,
  * @param type entries of which type are relevant?
  *     Use 0 for any type.
  * @param proc function to call on the matching value;
- *        will be called once with a NULL if no value matches
- * @param proc_cls closure for iter
+ *        will be called with NULL if nothing matches
+ * @param proc_cls closure for @a proc
  */
 static void
 postgres_plugin_get_key (void *cls,
-                         uint64_t offset,
+                         uint64_t next_uid,
+                         bool random,
                          const struct GNUNET_HashCode *key,
                          const struct GNUNET_HashCode *vhash,
                          enum GNUNET_BLOCK_Type type,
-                         PluginDatumProcessor proc,
+                         PluginDatumProcessor proc,
                          void *proc_cls)
 {
   struct Plugin *plugin = cls;
   uint32_t utype = type;
+  uint16_t use_rvalue = random;
+  uint16_t use_key = NULL != key;
+  uint16_t use_vhash = NULL != vhash;
+  uint16_t use_type = GNUNET_BLOCK_TYPE_ANY != type;
+  uint64_t rvalue;
+  struct GNUNET_PQ_QueryParam params[] = {
+    GNUNET_PQ_query_param_uint64 (&next_uid),
+    GNUNET_PQ_query_param_uint64 (&rvalue),
+    GNUNET_PQ_query_param_uint16 (&use_rvalue),
+    GNUNET_PQ_query_param_auto_from_type (key),
+    GNUNET_PQ_query_param_uint16 (&use_key),
+    GNUNET_PQ_query_param_auto_from_type (vhash),
+    GNUNET_PQ_query_param_uint16 (&use_vhash),
+    GNUNET_PQ_query_param_uint32 (&utype),
+    GNUNET_PQ_query_param_uint16 (&use_type),
+    GNUNET_PQ_query_param_end
+  };
   PGresult *ret;
-  uint64_t total;
-  uint64_t limit_off;
 
-  if (0 != type)
+  if (random)
   {
-    if (NULL != vhash)
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_auto_from_type (vhash),
-        GNUNET_PQ_query_param_uint32 (&utype),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "count_getvt",
-                                     params);
-    }
-    else
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_uint32 (&utype),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "count_gett",
-                                     params);
-    }
+    rvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                       UINT64_MAX);
+    next_uid = 0;
   }
   else
-  {
-    if (NULL != vhash)
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_auto_from_type (vhash),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "count_getv",
-                                     params);
-    }
-    else
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "count_get",
-                                     params);
-    }
-  }
+    rvalue = 0;
 
-  if (GNUNET_OK !=
-      GNUNET_POSTGRES_check_result (plugin->dbh,
-                                    ret,
-                                    PGRES_TUPLES_OK,
-                                    "PQexecParams",
-                                    "count"))
-  {
-    proc (proc_cls, NULL, 0, NULL, 0, 0, 0,
-          GNUNET_TIME_UNIT_ZERO_ABS, 0);
-    return;
-  }
-  if ( (PQntuples (ret) != 1) ||
-       (PQnfields (ret) != 1) ||
-       (PQgetlength (ret, 0, 0) != sizeof (uint64_t)))
-  {
-    GNUNET_break (0);
-    PQclear (ret);
-    proc (proc_cls, NULL, 0, NULL, 0, 0, 0,
-          GNUNET_TIME_UNIT_ZERO_ABS, 0);
-    return;
-  }
-  total = GNUNET_ntohll (*(const uint64_t *) PQgetvalue (ret, 0, 0));
-  PQclear (ret);
-  if (0 == total)
-  {
-    proc (proc_cls, NULL, 0, NULL, 0, 0, 0,
-          GNUNET_TIME_UNIT_ZERO_ABS, 0);
-    return;
-  }
-  limit_off = offset % total;
-
-  if (0 != type)
-  {
-    if (NULL != vhash)
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_auto_from_type (vhash),
-        GNUNET_PQ_query_param_uint32 (&utype),
-        GNUNET_PQ_query_param_uint64 (&limit_off),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "getvt",
-                                     params);
-    }
-    else
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_uint32 (&utype),
-        GNUNET_PQ_query_param_uint64 (&limit_off),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "gett",
-                                     params);
-    }
-  }
-  else
-  {
-    if (NULL != vhash)
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_auto_from_type (vhash),
-        GNUNET_PQ_query_param_uint64 (&limit_off),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "getv",
-                                     params);
-    }
-    else
-    {
-      struct GNUNET_PQ_QueryParam params[] = {
-        GNUNET_PQ_query_param_auto_from_type (key),
-        GNUNET_PQ_query_param_uint64 (&limit_off),
-        GNUNET_PQ_query_param_end
-      };
-      ret = GNUNET_PQ_exec_prepared (plugin->dbh,
-                                     "get",
-                                     params);
-    }
-  }
+  ret = GNUNET_PQ_exec_prepared (plugin->dbh,
+                                 "get",
+                                 params);
   process_result (plugin,
                   proc,
                   proc_cls,
@@ -677,26 +551,25 @@ postgres_plugin_get_key (void *cls,
  * the given iterator for each of them.
  *
  * @param cls our `struct Plugin *`
- * @param offset offset of the result (modulo num-results);
- *        specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param type entries of which type should be considered?
- *        Use 0 for any type.
+ *        Must not be zero (ANY).
  * @param proc function to call on the matching value;
- *        will be called with a NULL if no value matches
+ *        will be called with NULL if no value matches
  * @param proc_cls closure for @a proc
  */
 static void
 postgres_plugin_get_zero_anonymity (void *cls,
-                                    uint64_t offset,
+                                    uint64_t next_uid,
                                     enum GNUNET_BLOCK_Type type,
                                     PluginDatumProcessor proc,
-                                    void *proc_cls)
+                                    void *proc_cls)
 {
   struct Plugin *plugin = cls;
   uint32_t utype = type;
   struct GNUNET_PQ_QueryParam params[] = {
     GNUNET_PQ_query_param_uint32 (&utype),
-    GNUNET_PQ_query_param_uint64 (&offset),
+    GNUNET_PQ_query_param_uint64 (&next_uid),
     GNUNET_PQ_query_param_end
   };
   PGresult *ret;
diff --git a/src/datastore/plugin_datastore_sqlite.c b/src/datastore/plugin_datastore_sqlite.c
index 9ca8f056a..76f791ad4 100644
--- a/src/datastore/plugin_datastore_sqlite.c
+++ b/src/datastore/plugin_datastore_sqlite.c
@@ -130,42 +130,7 @@ struct Plugin
   /**
    * Precompiled SQL for selection
    */
-  sqlite3_stmt *count_key;
-
-  /**
-   * Precompiled SQL for selection
-   */
-  sqlite3_stmt *count_key_vhash;
-
-  /**
-   * Precompiled SQL for selection
-   */
-  sqlite3_stmt *count_key_type;
-
-  /**
-   * Precompiled SQL for selection
-   */
-  sqlite3_stmt *count_key_vhash_type;
-
-  /**
-   * Precompiled SQL for selection
-   */
-  sqlite3_stmt *get_key;
-
-  /**
-   * Precompiled SQL for selection
-   */
-  sqlite3_stmt *get_key_vhash;
-
-  /**
-   * Precompiled SQL for selection
-   */
-  sqlite3_stmt *get_key_type;
-
-  /**
-   * Precompiled SQL for selection
-   */
-  sqlite3_stmt *get_key_vhash_type;
+  sqlite3_stmt *get;
 
   /**
    * Should the database be dropped on shutdown?
@@ -430,8 +395,10 @@ database_setup (const struct GNUNET_CONFIGURATION_Handle *cfg,
 #if SQLITE_VERSION_NUMBER >= 3007000
                     "INDEXED BY idx_anon_type_hash "
 #endif
-                    "WHERE (anonLevel = 0 AND type=?1) "
-                    "ORDER BY hash DESC LIMIT 1 OFFSET ?2",
+                    "WHERE _ROWID_ >= ? AND "
+                    "anonLevel = 0 AND "
+                    "type = ? "
+                    "ORDER BY _ROWID_ ASC LIMIT 1",
                     &plugin->selZeroAnon)) ||
        (SQLITE_OK !=
         sq_prepare (plugin->dbh,
@@ -440,44 +407,14 @@ database_setup (const struct GNUNET_CONFIGURATION_Handle *cfg,
                     &plugin->insertContent)) ||
        (SQLITE_OK !=
         sq_prepare (plugin->dbh,
-                    "SELECT count(*) FROM gn090 WHERE hash=?",
-                    &plugin->count_key)) ||
-       (SQLITE_OK !=
-        sq_prepare (plugin->dbh,
-                    "SELECT count(*) FROM gn090 WHERE hash=? AND vhash=?",
-                    &plugin->count_key_vhash)) ||
-       (SQLITE_OK !=
-        sq_prepare (plugin->dbh,
-                    "SELECT count(*) FROM gn090 WHERE hash=? AND type=?",
-                    &plugin->count_key_type)) ||
-       (SQLITE_OK !=
-        sq_prepare (plugin->dbh,
-                    "SELECT count(*) FROM gn090 WHERE hash=? AND vhash=? AND type=?",
-                    &plugin->count_key_vhash_type)) ||
-       (SQLITE_OK !=
-        sq_prepare (plugin->dbh,
-                    "SELECT type, prio, anonLevel, expire, hash, value, _ROWID_ FROM gn090 "
-                    "WHERE hash=?"
-                    "ORDER BY _ROWID_ ASC LIMIT 1 OFFSET ?",
-                    &plugin->get_key)) ||
-       (SQLITE_OK !=
-        sq_prepare (plugin->dbh,
-                    "SELECT type, prio, anonLevel, expire, hash, value, _ROWID_ FROM gn090 "
-                    "WHERE hash=? AND vhash=?"
-                    "ORDER BY _ROWID_ ASC LIMIT 1 OFFSET ?",
-                    &plugin->get_key_vhash)) ||
-       (SQLITE_OK !=
-        sq_prepare (plugin->dbh,
                     "SELECT type, prio, anonLevel, expire, hash, value, _ROWID_ FROM gn090 "
-                    "WHERE hash=? AND type=?"
-                    "ORDER BY _ROWID_ ASC LIMIT 1 OFFSET ?",
-                    &plugin->get_key_type)) ||
-       (SQLITE_OK !=
-        sq_prepare (plugin->dbh,
-                    "SELECT type, prio, anonLevel, expire, hash, value, _ROWID_ FROM gn090 "
-                    "WHERE hash=? AND vhash=? AND type=?"
-                    "ORDER BY _ROWID_ ASC LIMIT 1 OFFSET ?",
-                    &plugin->get_key_vhash_type)) ||
+                    "WHERE _ROWID_ >= ? AND "
+                    "(rvalue >= ? OR 0 = ?) AND "
+                    "(hash = ? OR 0 = ?) AND "
+                    "(vhash = ? OR 0 = ?) AND "
+                    "(type = ? OR 0 = ?) "
+                    "ORDER BY _ROWID_ ASC LIMIT 1",
+                    &plugin->get)) ||
        (SQLITE_OK !=
         sq_prepare (plugin->dbh,
                     "DELETE FROM gn090 WHERE _ROWID_ = ?",
@@ -523,22 +460,8 @@ database_shutdown (struct Plugin *plugin)
     sqlite3_finalize (plugin->selZeroAnon);
   if (NULL != plugin->insertContent)
     sqlite3_finalize (plugin->insertContent);
-  if (NULL != plugin->count_key)
-    sqlite3_finalize (plugin->count_key);
-  if (NULL != plugin->count_key_vhash)
-    sqlite3_finalize (plugin->count_key_vhash);
-  if (NULL != plugin->count_key_type)
-    sqlite3_finalize (plugin->count_key_type);
-  if (NULL != plugin->count_key_vhash_type)
-    sqlite3_finalize (plugin->count_key_vhash_type);
-  if (NULL != plugin->count_key)
-    sqlite3_finalize (plugin->get_key);
-  if (NULL != plugin->count_key_vhash)
-    sqlite3_finalize (plugin->get_key_vhash);
-  if (NULL != plugin->count_key_type)
-    sqlite3_finalize (plugin->get_key_type);
-  if (NULL != plugin->count_key_vhash_type)
-    sqlite3_finalize (plugin->get_key_vhash_type);
+  if (NULL != plugin->get)
+    sqlite3_finalize (plugin->get);
   result = sqlite3_close (plugin->dbh);
 #if SQLITE_VERSION_NUMBER >= 3007000
   if (result == SQLITE_BUSY)
@@ -895,38 +818,36 @@ execute_get (struct Plugin *plugin,
  * the given processor for the item.
  *
  * @param cls our plugin context
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param type entries of which type should be considered?
- *        Use 0 for any type.
- * @param proc function to call on each matching value;
- *        will be called once with a NULL value at the end
+ *        Must not be zero (ANY).
+ * @param proc function to call on the matching value;
+ *        will be called with NULL if no value matches
  * @param proc_cls closure for @a proc
  */
 static void
 sqlite_plugin_get_zero_anonymity (void *cls,
-                                  uint64_t offset,
+                                  uint64_t next_uid,
                                   enum GNUNET_BLOCK_Type type,
                                   PluginDatumProcessor proc,
                                   void *proc_cls)
 {
   struct Plugin *plugin = cls;
   struct GNUNET_SQ_QueryParam params[] = {
+    GNUNET_SQ_query_param_uint64 (&next_uid),
     GNUNET_SQ_query_param_uint32 (&type),
-    GNUNET_SQ_query_param_uint64 (&offset),
     GNUNET_SQ_query_param_end
   };
-  sqlite3_stmt *stmt = plugin->selZeroAnon;
 
   GNUNET_assert (type != GNUNET_BLOCK_TYPE_ANY);
   if (GNUNET_OK !=
-      GNUNET_SQ_bind (stmt,
+      GNUNET_SQ_bind (plugin->selZeroAnon,
                       params))
   {
     proc (proc_cls, NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
     return;
   }
-  execute_get (plugin, stmt, proc, proc_cls);
+  execute_get (plugin, plugin->selZeroAnon, proc, proc_cls);
 }
 
 
@@ -934,8 +855,9 @@ sqlite_plugin_get_zero_anonymity (void *cls,
  * Get results for a particular key in the datastore.
  *
  * @param cls closure
- * @param offset offset (mod count).
- * @param key key to match, never NULL
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
+ * @param key maybe NULL (to match all entries)
  * @param vhash hash of the value, maybe NULL (to
  *        match all values that have the right key).
  *        Note that for DBlocks there is no difference
@@ -949,7 +871,8 @@ sqlite_plugin_get_zero_anonymity (void *cls,
  */
 static void
 sqlite_plugin_get_key (void *cls,
-                       uint64_t offset,
+                       uint64_t next_uid,
+                       bool random,
                        const struct GNUNET_HashCode *key,
                        const struct GNUNET_HashCode *vhash,
                        enum GNUNET_BLOCK_Type type,
@@ -957,133 +880,45 @@ sqlite_plugin_get_key (void *cls,
                        void *proc_cls)
 {
   struct Plugin *plugin = cls;
+  uint64_t rvalue;
+  uint16_t use_rvalue = random;
   uint32_t type32 = (uint32_t) type;
-  int ret;
-  int total;
-  uint32_t limit_off;
-  struct GNUNET_SQ_QueryParam count_params_key[] = {
-    GNUNET_SQ_query_param_auto_from_type (key),
-    GNUNET_SQ_query_param_end
-  };
-  struct GNUNET_SQ_QueryParam count_params_key_vhash[] = {
-    GNUNET_SQ_query_param_auto_from_type (key),
-    GNUNET_SQ_query_param_auto_from_type (vhash),
-    GNUNET_SQ_query_param_end
-  };
-  struct GNUNET_SQ_QueryParam count_params_key_type[] = {
-    GNUNET_SQ_query_param_auto_from_type (key),
-    GNUNET_SQ_query_param_uint32 (&type32),
-    GNUNET_SQ_query_param_end
-  };
-  struct GNUNET_SQ_QueryParam count_params_key_vhash_type[] = {
-    GNUNET_SQ_query_param_auto_from_type (key),
-    GNUNET_SQ_query_param_auto_from_type (vhash),
-    GNUNET_SQ_query_param_uint32 (&type32),
-    GNUNET_SQ_query_param_end
-  };
-  struct GNUNET_SQ_QueryParam get_params_key[] = {
-    GNUNET_SQ_query_param_auto_from_type (key),
-    GNUNET_SQ_query_param_uint32 (&limit_off),
-    GNUNET_SQ_query_param_end
-  };
-  struct GNUNET_SQ_QueryParam get_params_key_vhash[] = {
-    GNUNET_SQ_query_param_auto_from_type (key),
-    GNUNET_SQ_query_param_auto_from_type (vhash),
-    GNUNET_SQ_query_param_uint32 (&limit_off),
-    GNUNET_SQ_query_param_end
-  };
-  struct GNUNET_SQ_QueryParam get_params_key_type[] = {
-    GNUNET_SQ_query_param_auto_from_type (key),
-    GNUNET_SQ_query_param_uint32 (&type32),
-    GNUNET_SQ_query_param_uint32 (&limit_off),
-    GNUNET_SQ_query_param_end
-  };
-  struct GNUNET_SQ_QueryParam get_params_key_vhash_type[] = {
+  uint16_t use_type = GNUNET_BLOCK_TYPE_ANY != type;
+  uint16_t use_key = NULL != key;
+  uint16_t use_vhash = NULL != vhash;
+  struct GNUNET_SQ_QueryParam params[] = {
+    GNUNET_SQ_query_param_uint64 (&next_uid),
+    GNUNET_SQ_query_param_uint64 (&rvalue),
+    GNUNET_SQ_query_param_uint16 (&use_rvalue),
     GNUNET_SQ_query_param_auto_from_type (key),
+    GNUNET_SQ_query_param_uint16 (&use_key),
     GNUNET_SQ_query_param_auto_from_type (vhash),
+    GNUNET_SQ_query_param_uint16 (&use_vhash),
     GNUNET_SQ_query_param_uint32 (&type32),
-    GNUNET_SQ_query_param_uint32 (&limit_off),
+    GNUNET_SQ_query_param_uint16 (&use_type),
     GNUNET_SQ_query_param_end
   };
-  struct GNUNET_SQ_QueryParam *count_params;
-  sqlite3_stmt *count_stmt;
-  struct GNUNET_SQ_QueryParam *get_params;
-  sqlite3_stmt *get_stmt;
 
-  if (NULL == vhash)
+  if (random)
   {
-    if (GNUNET_BLOCK_TYPE_ANY == type)
-    {
-      count_params = count_params_key;
-      count_stmt = plugin->count_key;
-      get_params = get_params_key;
-      get_stmt = plugin->get_key;
-    }
-    else
-    {
-      count_params = count_params_key_type;
-      count_stmt = plugin->count_key_type;
-      get_params = get_params_key_type;
-      get_stmt = plugin->get_key_type;
-    }
+    rvalue = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                       UINT64_MAX);
+    next_uid = 0;
   }
   else
-  {
-    if (GNUNET_BLOCK_TYPE_ANY == type)
-    {
-      count_params = count_params_key_vhash;
-      count_stmt = plugin->count_key_vhash;
-      get_params = get_params_key_vhash;
-      get_stmt = plugin->get_key_vhash;
-    }
-    else
-    {
-      count_params = count_params_key_vhash_type;
-      count_stmt = plugin->count_key_vhash_type;
-      get_params = get_params_key_vhash_type;
-      get_stmt = plugin->get_key_vhash_type;
-    }
-  }
-  if (GNUNET_OK !=
-      GNUNET_SQ_bind (count_stmt,
-                      count_params))
-  {
-    proc (proc_cls, NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
-    return;
-  }
-  ret = sqlite3_step (count_stmt);
-  if (ret != SQLITE_ROW)
-  {
-    LOG_SQLITE (plugin, GNUNET_ERROR_TYPE_ERROR | GNUNET_ERROR_TYPE_BULK,
-                "sqlite_step");
-    GNUNET_SQ_reset (plugin->dbh,
-                     count_stmt);
-    proc (proc_cls, NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
-    return;
-  }
-  total = sqlite3_column_int (count_stmt,
-                              0);
-  GNUNET_SQ_reset (plugin->dbh,
-                   count_stmt);
-  if (0 == total)
-  {
-    proc (proc_cls, NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
-    return;
-  }
-  limit_off = (uint32_t) (offset % total);
+    rvalue = 0;
+
   if (GNUNET_OK !=
-      GNUNET_SQ_bind (get_stmt,
-                      get_params))
+      GNUNET_SQ_bind (plugin->get,
+                      params))
   {
     proc (proc_cls, NULL, 0, NULL, 0, 0, 0, GNUNET_TIME_UNIT_ZERO_ABS, 0);
     return;
   }
   execute_get (plugin,
-               get_stmt,
+               plugin->get,
                proc,
                proc_cls);
-  GNUNET_SQ_reset (plugin->dbh,
-                   get_stmt);
 }
 
 
diff --git a/src/datastore/plugin_datastore_template.c b/src/datastore/plugin_datastore_template.c
index a1e03e8ee..187221798 100644
--- a/src/datastore/plugin_datastore_template.c
+++ b/src/datastore/plugin_datastore_template.c
@@ -89,8 +89,8 @@ template_plugin_put (void *cls, const struct GNUNET_HashCode * key, uint32_t siz
  * Get one of the results for a particular key in the datastore.
  *
  * @param cls closure
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
+ * @param random if true, return a random result instead of using next_uid
  * @param key maybe NULL (to match all entries)
  * @param vhash hash of the value, maybe NULL (to
  *        match all values that have the right key).
@@ -104,7 +104,7 @@ template_plugin_put (void *cls, const struct GNUNET_HashCode * key, uint32_t siz
  * @param proc_cls closure for proc
  */
 static void
-template_plugin_get_key (void *cls, uint64_t offset,
+template_plugin_get_key (void *cls, uint64_t next_uid, bool random,
                          const struct GNUNET_HashCode * key,
                          const struct GNUNET_HashCode * vhash,
                          enum GNUNET_BLOCK_Type type, PluginDatumProcessor proc,
@@ -185,16 +185,15 @@ template_plugin_update (void *cls, uint64_t uid, uint32_t delta,
  * Call the given processor on an item with zero anonymity.
  *
  * @param cls our "struct Plugin*"
- * @param offset offset of the result (modulo num-results);
- *               specific ordering does not matter for the offset
+ * @param next_uid return the result with lowest uid >= next_uid
  * @param type entries of which type should be considered?
- *        Use 0 for any type.
- * @param proc function to call on each matching value;
- *        will be called  with NULL if no value matches
+ *        Must not be zero (ANY).
+ * @param proc function to call on the matching value;
+ *        will be called with NULL if no value matches
  * @param proc_cls closure for proc
  */
 static void
-template_plugin_get_zero_anonymity (void *cls, uint64_t offset,
+template_plugin_get_zero_anonymity (void *cls, uint64_t next_uid,
                                     enum GNUNET_BLOCK_Type type,
                                     PluginDatumProcessor proc, void *proc_cls)
 {
diff --git a/src/datastore/test_datastore_api.c b/src/datastore/test_datastore_api.c
index a99668240..0da68b266 100644
--- a/src/datastore/test_datastore_api.c
+++ b/src/datastore/test_datastore_api.c
@@ -156,8 +156,6 @@ struct CpsRunContext
   void *data;
   size_t size;
 
-  uint64_t uid;
-  uint64_t offset;
   uint64_t first_uid;
 };
 
@@ -267,7 +265,6 @@ check_value (void *cls,
   GNUNET_assert (priority == get_priority (i));
   GNUNET_assert (anonymity == get_anonymity (i));
   GNUNET_assert (expiration.abs_value_us == get_expiration (i).abs_value_us);
-  crc->offset++;
   if (crc->i == 0)
   {
     crc->phase = RP_DEL;
@@ -343,7 +340,6 @@ check_multiple (void *cls,
   case RP_GET_MULTIPLE:
     crc->phase = RP_GET_MULTIPLE_NEXT;
     crc->first_uid = uid;
-    crc->offset++;
     break;
   case RP_GET_MULTIPLE_NEXT:
     GNUNET_assert (uid != crc->first_uid);
@@ -354,8 +350,6 @@ check_multiple (void *cls,
     crc->phase = RP_ERROR;
     break;
   }
-  if (priority == get_priority (42))
-    crc->uid = uid;
   GNUNET_SCHEDULER_add_now (&run_continuation, crc);
 }
 
@@ -400,7 +394,8 @@ run_continuation (void *cls)
                         sizeof (int),
                         &crc->key);
     GNUNET_DATASTORE_get_key (datastore,
-                              crc->offset,
+                              0,
+                              false,
                               &crc->key,
                               get_type (crc->i),
                               1,
@@ -417,7 +412,8 @@ run_continuation (void *cls)
     GNUNET_CRYPTO_hash (&crc->i, sizeof (int), &crc->key);
     GNUNET_assert (NULL !=
                    GNUNET_DATASTORE_get_key (datastore,
-                                             crc->offset,
+                                             0,
+                                             false,
                                              &crc->key,
                                              get_type (crc->i),
                                              1,
@@ -450,9 +446,15 @@ run_continuation (void *cls)
                 crc->i);
     GNUNET_CRYPTO_hash (&crc->i, sizeof (int), &crc->key);
     GNUNET_assert (NULL !=
-                   GNUNET_DATASTORE_get_key (datastore, crc->offset, &crc->key,
-                                             get_type (crc->i), 1, 1,
-                                             &check_nothing, crc));
+                   GNUNET_DATASTORE_get_key (datastore,
+                                             0,
+                                             false,
+                                             &crc->key,
+                                             get_type (crc->i),
+                                             1,
+                                             1,
+                                             &check_nothing,
+                                             crc));
     break;
   case RP_RESERVE:
     crc->phase = RP_PUT_MULTIPLE;
@@ -483,19 +485,26 @@ run_continuation (void *cls)
   case RP_GET_MULTIPLE:
     GNUNET_assert (NULL !=
                    GNUNET_DATASTORE_get_key (datastore,
-                                             crc->offset,
+                                             0,
+                                             false,
                                              &crc->key,
-                                             get_type (42), 1, 1,
-                                             &check_multiple, crc));
+                                             get_type (42),
+                                             1,
+                                             1,
+                                             &check_multiple,
+                                             crc));
     break;
   case RP_GET_MULTIPLE_NEXT:
     GNUNET_assert (NULL !=
                    GNUNET_DATASTORE_get_key (datastore,
-                                             crc->offset,
+                                             crc->first_uid + 1,
+                                             false,
                                              &crc->key,
                                              get_type (42),
-                                             1, 1,
-                                             &check_multiple, crc));
+                                             1,
+                                             1,
+                                             &check_multiple,
+                                             crc));
     break;
   case RP_DONE:
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
diff --git a/src/datastore/test_datastore_api_management.c b/src/datastore/test_datastore_api_management.c
index 9a3e5446b..de4dc657f 100644
--- a/src/datastore/test_datastore_api_management.c
+++ b/src/datastore/test_datastore_api_management.c
@@ -58,7 +58,6 @@ struct CpsRunContext
   const struct GNUNET_CONFIGURATION_Handle *cfg;
   void *data;
   enum RunPhase phase;
-  uint64_t offset;
 };
 
 
@@ -159,7 +158,6 @@ check_value (void *cls, const struct GNUNET_HashCode * key, size_t size,
   GNUNET_assert (priority == get_priority (i));
   GNUNET_assert (anonymity == get_anonymity (i));
   GNUNET_assert (expiration.abs_value_us == get_expiration (i).abs_value_us);
-  crc->offset++;
   crc->i--;
   if (crc->i == 0)
     crc->phase = RP_DONE;
@@ -221,8 +219,13 @@ run_continuation (void *cls)
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Executing `%s' number %u\n", "GET",
                 crc->i);
     GNUNET_CRYPTO_hash (&crc->i, sizeof (int), &crc->key);
-    GNUNET_DATASTORE_get_key (datastore, crc->offset++, &crc->key,
-                              get_type (crc->i), 1, 1,
+    GNUNET_DATASTORE_get_key (datastore,
+                              0,
+                              false,
+                              &crc->key,
+                              get_type (crc->i),
+                              1,
+                              1,
                               &check_value,
                               crc);
     break;
@@ -230,8 +233,13 @@ run_continuation (void *cls)
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Executing `%s' number %u\n", "GET(f)",
                 crc->i);
     GNUNET_CRYPTO_hash (&crc->i, sizeof (int), &crc->key);
-    GNUNET_DATASTORE_get_key (datastore, crc->offset++, &crc->key,
-                              get_type (crc->i), 1, 1,
+    GNUNET_DATASTORE_get_key (datastore,
+                              0,
+                              false,
+                              &crc->key,
+                              get_type (crc->i),
+                              1,
+                              1,
                               &check_nothing,
                               crc);
     break;
diff --git a/src/datastore/test_plugin_datastore.c b/src/datastore/test_plugin_datastore.c
index 9b85d57da..94d93aac6 100644
--- a/src/datastore/test_plugin_datastore.c
+++ b/src/datastore/test_plugin_datastore.c
@@ -64,7 +64,6 @@ struct CpsRunContext
   enum RunPhase phase;
   unsigned int cnt;
   unsigned int i;
-  uint64_t offset;
 };
 
 
@@ -308,7 +307,8 @@ test (void *cls)
                 "Looking for %s\n",
                 GNUNET_h2s (&key));
     crc->api->get_key (crc->api->cls,
-                       crc->offset++,
+                       0,
+                       false,
                        &key,
                        NULL,
                        GNUNET_BLOCK_TYPE_ANY,