From 059d52845cbbc10e882764f64245c5995af4e741 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Dan=20Vr=C3=A1til?= Date: Mon, 8 Dec 2014 13:49:27 +0100 Subject: [PATCH 26/30] Avoid recursive collection listing in SearchHelper The recursive listing generates one SQL query per collection, and since search is invoked rather often (basically whenever you open an email in KMail), we get lots of unnecessary queries. This new algorithm does one query to fetch all folders with matching mime types, and only falls back to query the parent chain when the requested ancestor is not 0 (root), or when the result collection is not a direct descendant of the requested ancestor. --- server/src/handler/search.cpp | 4 +- server/src/handler/searchhelper.cpp | 111 ++++++++++++++---------- server/src/handler/searchhelper.h | 2 +- server/src/search/searchmanager.cpp | 2 +- server/tests/unittest/CMakeLists.txt | 2 + server/tests/unittest/searchtest.cpp | 158 +++++++++++++++++++++++++++++++++++ 6 files changed, 230 insertions(+), 49 deletions(-) create mode 100644 server/tests/unittest/searchtest.cpp diff --git a/server/src/handler/search.cpp b/server/src/handler/search.cpp index 06d172f..00484ff 100644 --- a/server/src/handler/search.cpp +++ b/server/src/handler/search.cpp @@ -95,9 +95,7 @@ bool Search::parseStream() } if ( recursive ) { - Q_FOREACH ( qint64 collection, collectionIds ) { - collections << SearchHelper::listCollectionsRecursive( QVector() << collection, mimeTypes ); - } + collections << SearchHelper::matchSubcollectionsByMimeType( collectionIds, mimeTypes ); } else { collections = collectionIds; } diff --git a/server/src/handler/searchhelper.cpp b/server/src/handler/searchhelper.cpp index aa6694d..1a06c0e 100644 --- a/server/src/handler/searchhelper.cpp +++ b/server/src/handler/searchhelper.cpp @@ -20,6 +20,7 @@ #include "searchhelper.h" #include "storage/countquerybuilder.h" +#include #include "entities.h" #include @@ -89,55 +90,77 @@ QString SearchHelper::extractMimetype( const QList &junks, int start } -QVector SearchHelper::listCollectionsRecursive( const QVector &ancestors, const QStringList &mimeTypes ) +static qint64 parentCollectionId(qint64 collectionId) { - QVector recursiveChildren; - Q_FOREACH ( qint64 ancestor, ancestors ) { - QVector searchChildren; - - { // Free the query before entering recursion to prevent too many opened connections - - Query::Condition mimeTypeCondition; - mimeTypeCondition.addColumnCondition( CollectionMimeTypeRelation::rightFullColumnName(), Query::Equals, MimeType::idFullColumnName() ); - // Exclude top-level collections and collections that cannot have items! - mimeTypeCondition.addValueCondition( MimeType::nameFullColumnName(), Query::NotEquals, QLatin1String( "inode/directory" ) ); - if ( !mimeTypes.isEmpty() ) { - mimeTypeCondition.addValueCondition( MimeType::nameFullColumnName(), Query::In, mimeTypes ); - } + QueryBuilder qb(Collection::tableName(), QueryBuilder::Select); + qb.addColumn(Collection::parentIdColumn()); + qb.addValueCondition(Collection::idColumn(), Query::Equals, collectionId); + if (!qb.exec()) { + return -1; + } + if (!qb.query().next()) { + return -1; + } + return qb.query().value(0).toLongLong(); +} - CountQueryBuilder qb( Collection::tableName(), MimeType::nameFullColumnName(), CountQueryBuilder::All ); - qb.addColumn( Collection::idFullColumnName() ); - qb.addJoin( QueryBuilder::LeftJoin, CollectionMimeTypeRelation::tableName(), CollectionMimeTypeRelation::leftFullColumnName(), Collection::idFullColumnName() ); - qb.addJoin( QueryBuilder::LeftJoin, MimeType::tableName(), mimeTypeCondition ); - if ( ancestor == 0 ) { - qb.addValueCondition( Collection::parentIdFullColumnName(), Query::Is, QVariant() ); - } else { - // Also include current ancestor's result, so that we know whether we should search in the ancestor too - Query::Condition idCond( Query::Or ); - idCond.addValueCondition( Collection::parentIdFullColumnName(), Query::Equals, ancestor ); - idCond.addValueCondition( Collection::idFullColumnName(), Query::Equals, ancestor ); - qb.addCondition( idCond ); - } - qb.addValueCondition( Collection::isVirtualFullColumnName(), Query::Equals, false ); - qb.addGroupColumn( Collection::idFullColumnName() ); - qb.exec(); - - QSqlQuery query = qb.query(); - while ( query.next() ) { - const qint64 id = query.value( 1 ).toLongLong(); - // Don't add ancestor into search children, we are resolving it right now - if ( id != ancestor ) { - searchChildren << id; + +QVector SearchHelper::matchSubcollectionsByMimeType(const QVector &ancestors, const QStringList &mimeTypes) +{ + // Get all collections with given mime types + QueryBuilder qb(Collection::tableName(), QueryBuilder::Select); + qb.setDistinct(true); + qb.addColumn(Collection::idFullColumnName()); + qb.addColumn(Collection::parentIdFullColumnName()); + qb.addJoin(QueryBuilder::LeftJoin, CollectionMimeTypeRelation::tableName(), + CollectionMimeTypeRelation::leftFullColumnName(), Collection::idFullColumnName()); + qb.addJoin(QueryBuilder::LeftJoin, MimeType::tableName(), + CollectionMimeTypeRelation::rightFullColumnName(), MimeType::idFullColumnName()); + Query::Condition cond(Query::Or); + Q_FOREACH (const QString &mt, mimeTypes) { + cond.addValueCondition(MimeType::nameFullColumnName(), Query::Equals, mt); + } + qb.addCondition(cond); + + if (!qb.exec()) { + qWarning() << "Failed to query search collections"; + return QVector(); + } + + QMap /* collectionIds */> candidateCollections; + while (qb.query().next()) { + candidateCollections[qb.query().value(1).toLongLong()].append(qb.query().value(0).toLongLong()); + } + + // If the ancestors list contains root, then return what we got, since everything + // is sub collection of root + QVector results; + if (ancestors.contains(0)) { + Q_FOREACH (const QVector &res, candidateCollections.values()) { + results += res; } - if ( query.value( 0 ).toInt() > 0 ) { // count( mimeTypeTable.name ) > 0 - recursiveChildren << id; + return results; + } + + // Try to resolve direct descendants + Q_FOREACH (qint64 ancestor, ancestors) { + const QVector cols = candidateCollections.take(ancestor); + if (!cols.isEmpty()) { + results += cols; } - } } - if ( !searchChildren.isEmpty() ) { - recursiveChildren << listCollectionsRecursive( searchChildren, mimeTypes ); + + for (auto iter = candidateCollections.begin(); iter != candidateCollections.end(); ++iter) { + // Traverse the collection chain up to root + qint64 parentId = iter.key(); + while (!ancestors.contains(parentId) && parentId > 0) { + parentId = parentCollectionId(parentId); + } + // Ok, we found a requested ancestor in the parent chain + if (parentId > 0) { + results += iter.value(); + } } - } - return recursiveChildren; + return results; } diff --git a/server/src/handler/searchhelper.h b/server/src/handler/searchhelper.h index a64bb61..1595501 100644 --- a/server/src/handler/searchhelper.h +++ b/server/src/handler/searchhelper.h @@ -33,7 +33,7 @@ class SearchHelper public: static QList splitLine( const QByteArray &line ); static QString extractMimetype( const QList &junks, int start ); - static QVector listCollectionsRecursive( const QVector &ancestors, const QStringList &mimeTypes ); + static QVector matchSubcollectionsByMimeType( const QVector &ancestors, const QStringList &mimeTypes ); }; } // namespace Server diff --git a/server/src/search/searchmanager.cpp b/server/src/search/searchmanager.cpp index c821aa3..b940fcc 100644 --- a/server/src/search/searchmanager.cpp +++ b/server/src/search/searchmanager.cpp @@ -296,7 +296,7 @@ void SearchManager::updateSearchImpl( const Collection &collection, QWaitConditi } if ( recursive ) { - queryCollections = SearchHelper::listCollectionsRecursive( queryAncestors, queryMimeTypes ); + queryCollections = SearchHelper::matchSubcollectionsByMimeType( queryAncestors, queryMimeTypes ); } else { queryCollections = queryAncestors; } diff --git a/server/tests/unittest/CMakeLists.txt b/server/tests/unittest/CMakeLists.txt index b9744d9..acdc180 100644 --- a/server/tests/unittest/CMakeLists.txt +++ b/server/tests/unittest/CMakeLists.txt @@ -77,3 +77,5 @@ add_server_test(listhandlertest.cpp akonadiprivate) add_server_test(modifyhandlertest.cpp akonadiprivate) add_server_test(createhandlertest.cpp akonadiprivate) add_server_test(collectionreferencetest.cpp akonadiprivate) + +add_server_test(searchtest.cpp akonadiprivate) \ No newline at end of file diff --git a/server/tests/unittest/searchtest.cpp b/server/tests/unittest/searchtest.cpp new file mode 100644 index 0000000..f523b09 --- /dev/null +++ b/server/tests/unittest/searchtest.cpp @@ -0,0 +1,158 @@ +/* + * Copyright (C) 2014 Daniel Vrátil + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + * + */ + +#include "fakeakonadiserver.h" +#include "searchhelper.h" +#include "akdebug.h" +#include "aktest.h" + +#include + +#include + +using namespace Akonadi::Server; + +Q_DECLARE_METATYPE(QList) +Q_DECLARE_METATYPE(QList) + + +class SearchTest : public QObject +{ + Q_OBJECT + +public: + SearchTest() + : QObject() + { + try { + FakeAkonadiServer::instance()->setPopulateDb(false); + FakeAkonadiServer::instance()->init(); + } catch (const FakeAkonadiServerException &e) { + akError() << "Server exception: " << e.what(); + akFatal() << "Fake Akonadi Server failed to start up, aborting test"; + } + } + + ~SearchTest() + { + FakeAkonadiServer::instance()->quit(); + } + + Collection createCollection(const Resource &res, const QString &name, const Collection &parent, const QStringList &mimetypes) + { + Collection col; + col.setName(name); + col.setResource(res); + col.setParentId(parent.isValid() ? parent.id() : 0); + col.insert(); + Q_FOREACH (const QString &mimeType, mimetypes) { + MimeType mt = MimeType::retrieveByName(mimeType); + if (!mt.isValid()) { + mt = MimeType(mimeType); + mt.insert(); + } + col.addMimeType(mt); + } + return col; + } + +private Q_SLOTS: + void testSearchHelperCollectionListing_data() + { + /* + Fake Resource + |- Col 1 (inode/directory) + | |- Col 2 (inode/direcotry, application/octet-stream) + | | |- Col 3(application/octet-stream) + | |- Col 4 (text/plain) + |- Col 5 (inode/directory, text/plain) + |- Col 6 (inode/directory, application/octet-stream) + |- Col 7 (inode/directory, text/plain) + |- Col 8 (inode/directory, application/octet-stream) + |- Col 9 (unique/mime-type) + */ + + Resource res(QLatin1String("Test Resource"), false); + res.insert(); + + Collection col1 = createCollection(res, QLatin1String("Col 1"), Collection(), + QStringList() << QLatin1String("inode/directory")); + Collection col2 = createCollection(res, QLatin1String("Col 2"), col1, + QStringList() << QLatin1String("inode/directory") + << QLatin1String("application/octet-stream")); + Collection col3 = createCollection(res, QLatin1String("Col 3"), col2, + QStringList() << QLatin1String("application/octet-stream")); + Collection col4 = createCollection(res, QLatin1String("Col 4"), col2, + QStringList() << QLatin1String("text/plain")); + Collection col5 = createCollection(res, QLatin1String("Col 5"), Collection(), + QStringList() << QLatin1String("inode/directory") + << QLatin1String("text/plain")); + Collection col6 = createCollection(res, QLatin1String("Col 6"), col5, + QStringList() << QLatin1String("inode/directory") + << QLatin1String("application/octet-stream")); + Collection col7 = createCollection(res, QLatin1String("Col 7"), col5, + QStringList() << QLatin1String("inode/directory") + << QLatin1String("text/plain")); + Collection col8 = createCollection(res, QLatin1String("Col 8"), col7, + QStringList() << QLatin1String("text/directory") + << QLatin1String("application/octet-stream")); + Collection col9 = createCollection(res, QLatin1String("Col 9"), col8, + QStringList() << QLatin1String("unique/mime-type")); + + QTest::addColumn>("ancestors"); + QTest::addColumn("mimetypes"); + QTest::addColumn>("expectedResults"); + + QTest::newRow("") << QVector({ 0 }) + << QStringList({ QLatin1String("text/plain") }) + << QVector({ col4.id(), col5.id(), col7.id() }); + QTest::newRow("") << QVector({ 0 }) + << QStringList({ QLatin1String("application/octet-stream") }) + << QVector({ col2.id(), col3.id(), col6.id(), col8.id() }); + QTest::newRow("") << QVector({ col1.id() }) + << QStringList({ QLatin1String("text/plain") }) + << QVector({ col4.id() }); + QTest::newRow("") << QVector({ col1.id() }) + << QStringList({ QLatin1String("unique/mime-type") }) + << QVector(); + QTest::newRow("") << QVector({ col2.id(), col7.id() }) + << QStringList({ QLatin1String("application/octet-stream") }) + << QVector({ col3.id(), col8.id() }); + } + + void testSearchHelperCollectionListing() + { + QFETCH(QVector, ancestors); + QFETCH(QStringList, mimetypes); + QFETCH(QVector, expectedResults); + + QVector results = SearchHelper::matchSubcollectionsByMimeType(ancestors, mimetypes); + + qSort(expectedResults); + qSort(results); + + QCOMPARE(results.size(), expectedResults.size()); + QCOMPARE(results, expectedResults); + } + +}; + +AKTEST_FAKESERVER_MAIN(SearchTest) + +#include "searchtest.moc" -- 2.1.0