Optimize findLast

This just gave a 700% boost to query performance from ~2k
to 14k reads per second...

2 files changed, 89 insertions, 12 deletions

diff --git a/common/storage_lmdb.cpp b/common/storage_lmdb.cpp
index 1516e69..a247e38 100644
--- a/common/storage_lmdb.cpp
+++ b/common/storage_lmdb.cpp
@@ -253,22 +253,69 @@ int Storage::NamedDatabase::scan(const QByteArray &k,
 
     return numberOfRetrievedValues;
 }
-void Storage::NamedDatabase::findLatest(const QByteArray &uid,
+
+void Storage::NamedDatabase::findLatest(const QByteArray &k,
             const std::function<void(const QByteArray &key, const QByteArray &value)> &resultHandler,
             const std::function<void(const Storage::Error &error)> &errorHandler) const
 {
-    QByteArray latestKey;
-    scan(uid, [&](const QByteArray &key, const QByteArray &value) -> bool {
-        latestKey = key;
-        return true;
-    },
-    errorHandler, true);
+    if (!d || !d->transaction) {
+        //Not an error. We rely on this to read nothing from non-existing databases.
+        return;
+    }
 
-    scan(latestKey, [=](const QByteArray &key, const QByteArray &value) -> bool {
-        resultHandler(key, value);
-        return false;
-    },
-    errorHandler);
+    int rc;
+    MDB_val key;
+    MDB_val data;
+    MDB_cursor *cursor;
+
+    key.mv_data = (void*)k.constData();
+    key.mv_size = k.size();
+
+    rc = mdb_cursor_open(d->transaction, d->dbi, &cursor);
+    if (rc) {
+        Error error(d->name.toLatin1(), getErrorCode(rc), QByteArray("Error during mdb_cursor open: ") + QByteArray(mdb_strerror(rc)));
+        errorHandler ? errorHandler(error) : d->defaultErrorHandler(error);
+        return;
+    }
+
+    MDB_cursor_op op = MDB_SET_RANGE;
+    if ((rc = mdb_cursor_get(cursor, &key, &data, op)) == 0) {
+        //The first lookup will find a key that is equal or greather than our key
+        if (QByteArray::fromRawData((char*)key.mv_data, key.mv_size).startsWith(k)) {
+            bool advanced = false;
+            while (QByteArray::fromRawData((char*)key.mv_data, key.mv_size).startsWith(k)) {
+                advanced = true;
+                MDB_cursor_op nextOp = MDB_NEXT;
+                rc = mdb_cursor_get(cursor, &key, &data, nextOp);
+                if (rc) {
+                    break;
+                }
+            }
+            if (advanced) {
+                MDB_cursor_op prefOp = MDB_PREV;
+                //We read past the end above, just take the last value
+                if (rc == MDB_NOTFOUND) {
+                    prefOp = MDB_LAST;
+                }
+                rc = mdb_cursor_get(cursor, &key, &data, prefOp);
+                resultHandler(QByteArray::fromRawData((char*)key.mv_data, key.mv_size), QByteArray::fromRawData((char*)data.mv_data, data.mv_size));
+            }
+        }
+    }
+
+    //We never find the last value
+    if (rc == MDB_NOTFOUND) {
+        rc = 0;
+    }
+
+    mdb_cursor_close(cursor);
+
+    if (rc) {
+        Error error(d->name.toLatin1(), getErrorCode(rc), QByteArray("Key: ") + k + " : " + QByteArray(mdb_strerror(rc)));
+        errorHandler ? errorHandler(error) : d->defaultErrorHandler(error);
+    }
+
+    return;
 }
 
 
diff --git a/tests/storagetest.cpp b/tests/storagetest.cpp
index bef8755..d950961 100644
--- a/tests/storagetest.cpp
+++ b/tests/storagetest.cpp
@@ -376,6 +376,7 @@ private Q_SLOTS:
         db.write("sub1","value1");
         db.write("sub2","value2");
         db.write("wub3","value3");
+        db.write("wub4","value4");
         QByteArray result;
         db.findLatest("sub", [&](const QByteArray &key, const QByteArray &value) {
             result = value;
@@ -384,6 +385,35 @@ private Q_SLOTS:
         QCOMPARE(result, QByteArray("value2"));
     }
 
+    void testFindLatestInSingle()
+    {
+        Akonadi2::Storage store(testDataPath, dbName, Akonadi2::Storage::ReadWrite);
+        auto transaction = store.createTransaction(Akonadi2::Storage::ReadWrite);
+        auto db = transaction.openDatabase("test", nullptr, false);
+        db.write("sub2","value2");
+        QByteArray result;
+        db.findLatest("sub", [&](const QByteArray &key, const QByteArray &value) {
+            result = value;
+        });
+
+        QCOMPARE(result, QByteArray("value2"));
+    }
+
+    void testFindLast()
+    {
+        Akonadi2::Storage store(testDataPath, dbName, Akonadi2::Storage::ReadWrite);
+        auto transaction = store.createTransaction(Akonadi2::Storage::ReadWrite);
+        auto db = transaction.openDatabase("test", nullptr, false);
+        db.write("sub2","value2");
+        db.write("wub3","value3");
+        QByteArray result;
+        db.findLatest("wub", [&](const QByteArray &key, const QByteArray &value) {
+            result = value;
+        });
+
+        QCOMPARE(result, QByteArray("value3"));
+    }
+
     void testRecordRevision()
     {
         Akonadi2::Storage store(testDataPath, dbName, Akonadi2::Storage::ReadWrite);