1 From 059d52845cbbc10e882764f64245c5995af4e741 Mon Sep 17 00:00:00 2001
2 From: =?UTF-8?q?Dan=20Vr=C3=A1til?= <dvratil@redhat.com>
3 Date: Mon, 8 Dec 2014 13:49:27 +0100
4 Subject: [PATCH 26/30] Avoid recursive collection listing in SearchHelper
6 The recursive listing generates one SQL query per collection, and since search
7 is invoked rather often (basically whenever you open an email in KMail), we get
8 lots of unnecessary queries. This new algorithm does one query to fetch all
9 folders with matching mime types, and only falls back to query the parent chain
10 when the requested ancestor is not 0 (root), or when the result collection is
11 not a direct descendant of the requested ancestor.
13 server/src/handler/search.cpp | 4 +-
14 server/src/handler/searchhelper.cpp | 111 ++++++++++++++----------
15 server/src/handler/searchhelper.h | 2 +-
16 server/src/search/searchmanager.cpp | 2 +-
17 server/tests/unittest/CMakeLists.txt | 2 +
18 server/tests/unittest/searchtest.cpp | 158 +++++++++++++++++++++++++++++++++++
19 6 files changed, 230 insertions(+), 49 deletions(-)
20 create mode 100644 server/tests/unittest/searchtest.cpp
22 diff --git a/server/src/handler/search.cpp b/server/src/handler/search.cpp
23 index 06d172f..00484ff 100644
24 --- a/server/src/handler/search.cpp
25 +++ b/server/src/handler/search.cpp
26 @@ -95,9 +95,7 @@ bool Search::parseStream()
30 - Q_FOREACH ( qint64 collection, collectionIds ) {
31 - collections << SearchHelper::listCollectionsRecursive( QVector<qint64>() << collection, mimeTypes );
33 + collections << SearchHelper::matchSubcollectionsByMimeType( collectionIds, mimeTypes );
35 collections = collectionIds;
37 diff --git a/server/src/handler/searchhelper.cpp b/server/src/handler/searchhelper.cpp
38 index aa6694d..1a06c0e 100644
39 --- a/server/src/handler/searchhelper.cpp
40 +++ b/server/src/handler/searchhelper.cpp
43 #include "searchhelper.h"
44 #include "storage/countquerybuilder.h"
45 +#include <storage/queryhelper.h>
48 #include <libs/protocol_p.h>
49 @@ -89,55 +90,77 @@ QString SearchHelper::extractMimetype( const QList<QByteArray> &junks, int start
53 -QVector<qint64> SearchHelper::listCollectionsRecursive( const QVector<qint64> &ancestors, const QStringList &mimeTypes )
54 +static qint64 parentCollectionId(qint64 collectionId)
56 - QVector<qint64> recursiveChildren;
57 - Q_FOREACH ( qint64 ancestor, ancestors ) {
58 - QVector<qint64> searchChildren;
60 - { // Free the query before entering recursion to prevent too many opened connections
62 - Query::Condition mimeTypeCondition;
63 - mimeTypeCondition.addColumnCondition( CollectionMimeTypeRelation::rightFullColumnName(), Query::Equals, MimeType::idFullColumnName() );
64 - // Exclude top-level collections and collections that cannot have items!
65 - mimeTypeCondition.addValueCondition( MimeType::nameFullColumnName(), Query::NotEquals, QLatin1String( "inode/directory" ) );
66 - if ( !mimeTypes.isEmpty() ) {
67 - mimeTypeCondition.addValueCondition( MimeType::nameFullColumnName(), Query::In, mimeTypes );
69 + QueryBuilder qb(Collection::tableName(), QueryBuilder::Select);
70 + qb.addColumn(Collection::parentIdColumn());
71 + qb.addValueCondition(Collection::idColumn(), Query::Equals, collectionId);
75 + if (!qb.query().next()) {
78 + return qb.query().value(0).toLongLong();
81 - CountQueryBuilder qb( Collection::tableName(), MimeType::nameFullColumnName(), CountQueryBuilder::All );
82 - qb.addColumn( Collection::idFullColumnName() );
83 - qb.addJoin( QueryBuilder::LeftJoin, CollectionMimeTypeRelation::tableName(), CollectionMimeTypeRelation::leftFullColumnName(), Collection::idFullColumnName() );
84 - qb.addJoin( QueryBuilder::LeftJoin, MimeType::tableName(), mimeTypeCondition );
85 - if ( ancestor == 0 ) {
86 - qb.addValueCondition( Collection::parentIdFullColumnName(), Query::Is, QVariant() );
88 - // Also include current ancestor's result, so that we know whether we should search in the ancestor too
89 - Query::Condition idCond( Query::Or );
90 - idCond.addValueCondition( Collection::parentIdFullColumnName(), Query::Equals, ancestor );
91 - idCond.addValueCondition( Collection::idFullColumnName(), Query::Equals, ancestor );
92 - qb.addCondition( idCond );
94 - qb.addValueCondition( Collection::isVirtualFullColumnName(), Query::Equals, false );
95 - qb.addGroupColumn( Collection::idFullColumnName() );
98 - QSqlQuery query = qb.query();
99 - while ( query.next() ) {
100 - const qint64 id = query.value( 1 ).toLongLong();
101 - // Don't add ancestor into search children, we are resolving it right now
102 - if ( id != ancestor ) {
103 - searchChildren << id;
105 +QVector<qint64> SearchHelper::matchSubcollectionsByMimeType(const QVector<qint64> &ancestors, const QStringList &mimeTypes)
107 + // Get all collections with given mime types
108 + QueryBuilder qb(Collection::tableName(), QueryBuilder::Select);
109 + qb.setDistinct(true);
110 + qb.addColumn(Collection::idFullColumnName());
111 + qb.addColumn(Collection::parentIdFullColumnName());
112 + qb.addJoin(QueryBuilder::LeftJoin, CollectionMimeTypeRelation::tableName(),
113 + CollectionMimeTypeRelation::leftFullColumnName(), Collection::idFullColumnName());
114 + qb.addJoin(QueryBuilder::LeftJoin, MimeType::tableName(),
115 + CollectionMimeTypeRelation::rightFullColumnName(), MimeType::idFullColumnName());
116 + Query::Condition cond(Query::Or);
117 + Q_FOREACH (const QString &mt, mimeTypes) {
118 + cond.addValueCondition(MimeType::nameFullColumnName(), Query::Equals, mt);
120 + qb.addCondition(cond);
123 + qWarning() << "Failed to query search collections";
124 + return QVector<qint64>();
127 + QMap<qint64 /* parentId */, QVector<qint64> /* collectionIds */> candidateCollections;
128 + while (qb.query().next()) {
129 + candidateCollections[qb.query().value(1).toLongLong()].append(qb.query().value(0).toLongLong());
132 + // If the ancestors list contains root, then return what we got, since everything
133 + // is sub collection of root
134 + QVector<qint64> results;
135 + if (ancestors.contains(0)) {
136 + Q_FOREACH (const QVector<qint64> &res, candidateCollections.values()) {
139 - if ( query.value( 0 ).toInt() > 0 ) { // count( mimeTypeTable.name ) > 0
140 - recursiveChildren << id;
144 + // Try to resolve direct descendants
145 + Q_FOREACH (qint64 ancestor, ancestors) {
146 + const QVector<qint64> cols = candidateCollections.take(ancestor);
147 + if (!cols.isEmpty()) {
152 - if ( !searchChildren.isEmpty() ) {
153 - recursiveChildren << listCollectionsRecursive( searchChildren, mimeTypes );
155 + for (auto iter = candidateCollections.begin(); iter != candidateCollections.end(); ++iter) {
156 + // Traverse the collection chain up to root
157 + qint64 parentId = iter.key();
158 + while (!ancestors.contains(parentId) && parentId > 0) {
159 + parentId = parentCollectionId(parentId);
161 + // Ok, we found a requested ancestor in the parent chain
162 + if (parentId > 0) {
163 + results += iter.value();
168 - return recursiveChildren;
171 diff --git a/server/src/handler/searchhelper.h b/server/src/handler/searchhelper.h
172 index a64bb61..1595501 100644
173 --- a/server/src/handler/searchhelper.h
174 +++ b/server/src/handler/searchhelper.h
175 @@ -33,7 +33,7 @@ class SearchHelper
177 static QList<QByteArray> splitLine( const QByteArray &line );
178 static QString extractMimetype( const QList<QByteArray> &junks, int start );
179 - static QVector<qint64> listCollectionsRecursive( const QVector<qint64> &ancestors, const QStringList &mimeTypes );
180 + static QVector<qint64> matchSubcollectionsByMimeType( const QVector<qint64> &ancestors, const QStringList &mimeTypes );
183 } // namespace Server
184 diff --git a/server/src/search/searchmanager.cpp b/server/src/search/searchmanager.cpp
185 index c821aa3..b940fcc 100644
186 --- a/server/src/search/searchmanager.cpp
187 +++ b/server/src/search/searchmanager.cpp
188 @@ -296,7 +296,7 @@ void SearchManager::updateSearchImpl( const Collection &collection, QWaitConditi
192 - queryCollections = SearchHelper::listCollectionsRecursive( queryAncestors, queryMimeTypes );
193 + queryCollections = SearchHelper::matchSubcollectionsByMimeType( queryAncestors, queryMimeTypes );
195 queryCollections = queryAncestors;
197 diff --git a/server/tests/unittest/CMakeLists.txt b/server/tests/unittest/CMakeLists.txt
198 index b9744d9..acdc180 100644
199 --- a/server/tests/unittest/CMakeLists.txt
200 +++ b/server/tests/unittest/CMakeLists.txt
201 @@ -77,3 +77,5 @@ add_server_test(listhandlertest.cpp akonadiprivate)
202 add_server_test(modifyhandlertest.cpp akonadiprivate)
203 add_server_test(createhandlertest.cpp akonadiprivate)
204 add_server_test(collectionreferencetest.cpp akonadiprivate)
206 +add_server_test(searchtest.cpp akonadiprivate)
207 \ No newline at end of file
208 diff --git a/server/tests/unittest/searchtest.cpp b/server/tests/unittest/searchtest.cpp
210 index 0000000..f523b09
212 +++ b/server/tests/unittest/searchtest.cpp
215 + * Copyright (C) 2014 Daniel Vrátil <dvratil@redhat.com>
217 + * This library is free software; you can redistribute it and/or
218 + * modify it under the terms of the GNU Lesser General Public
219 + * License as published by the Free Software Foundation; either
220 + * version 2.1 of the License, or (at your option) any later version.
222 + * This library is distributed in the hope that it will be useful,
223 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
224 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
225 + * Lesser General Public License for more details.
227 + * You should have received a copy of the GNU Lesser General Public
228 + * License along with this library; if not, write to the Free Software
229 + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
233 +#include "fakeakonadiserver.h"
234 +#include "searchhelper.h"
235 +#include "akdebug.h"
238 +#include <entities.h>
242 +using namespace Akonadi::Server;
244 +Q_DECLARE_METATYPE(QList<qint64>)
245 +Q_DECLARE_METATYPE(QList<QString>)
248 +class SearchTest : public QObject
257 + FakeAkonadiServer::instance()->setPopulateDb(false);
258 + FakeAkonadiServer::instance()->init();
259 + } catch (const FakeAkonadiServerException &e) {
260 + akError() << "Server exception: " << e.what();
261 + akFatal() << "Fake Akonadi Server failed to start up, aborting test";
267 + FakeAkonadiServer::instance()->quit();
270 + Collection createCollection(const Resource &res, const QString &name, const Collection &parent, const QStringList &mimetypes)
274 + col.setResource(res);
275 + col.setParentId(parent.isValid() ? parent.id() : 0);
277 + Q_FOREACH (const QString &mimeType, mimetypes) {
278 + MimeType mt = MimeType::retrieveByName(mimeType);
279 + if (!mt.isValid()) {
280 + mt = MimeType(mimeType);
283 + col.addMimeType(mt);
289 + void testSearchHelperCollectionListing_data()
293 + |- Col 1 (inode/directory)
294 + | |- Col 2 (inode/direcotry, application/octet-stream)
295 + | | |- Col 3(application/octet-stream)
296 + | |- Col 4 (text/plain)
297 + |- Col 5 (inode/directory, text/plain)
298 + |- Col 6 (inode/directory, application/octet-stream)
299 + |- Col 7 (inode/directory, text/plain)
300 + |- Col 8 (inode/directory, application/octet-stream)
301 + |- Col 9 (unique/mime-type)
304 + Resource res(QLatin1String("Test Resource"), false);
307 + Collection col1 = createCollection(res, QLatin1String("Col 1"), Collection(),
308 + QStringList() << QLatin1String("inode/directory"));
309 + Collection col2 = createCollection(res, QLatin1String("Col 2"), col1,
310 + QStringList() << QLatin1String("inode/directory")
311 + << QLatin1String("application/octet-stream"));
312 + Collection col3 = createCollection(res, QLatin1String("Col 3"), col2,
313 + QStringList() << QLatin1String("application/octet-stream"));
314 + Collection col4 = createCollection(res, QLatin1String("Col 4"), col2,
315 + QStringList() << QLatin1String("text/plain"));
316 + Collection col5 = createCollection(res, QLatin1String("Col 5"), Collection(),
317 + QStringList() << QLatin1String("inode/directory")
318 + << QLatin1String("text/plain"));
319 + Collection col6 = createCollection(res, QLatin1String("Col 6"), col5,
320 + QStringList() << QLatin1String("inode/directory")
321 + << QLatin1String("application/octet-stream"));
322 + Collection col7 = createCollection(res, QLatin1String("Col 7"), col5,
323 + QStringList() << QLatin1String("inode/directory")
324 + << QLatin1String("text/plain"));
325 + Collection col8 = createCollection(res, QLatin1String("Col 8"), col7,
326 + QStringList() << QLatin1String("text/directory")
327 + << QLatin1String("application/octet-stream"));
328 + Collection col9 = createCollection(res, QLatin1String("Col 9"), col8,
329 + QStringList() << QLatin1String("unique/mime-type"));
331 + QTest::addColumn<QVector<qint64>>("ancestors");
332 + QTest::addColumn<QStringList>("mimetypes");
333 + QTest::addColumn<QVector<qint64>>("expectedResults");
335 + QTest::newRow("") << QVector<qint64>({ 0 })
336 + << QStringList({ QLatin1String("text/plain") })
337 + << QVector<qint64>({ col4.id(), col5.id(), col7.id() });
338 + QTest::newRow("") << QVector<qint64>({ 0 })
339 + << QStringList({ QLatin1String("application/octet-stream") })
340 + << QVector<qint64>({ col2.id(), col3.id(), col6.id(), col8.id() });
341 + QTest::newRow("") << QVector<qint64>({ col1.id() })
342 + << QStringList({ QLatin1String("text/plain") })
343 + << QVector<qint64>({ col4.id() });
344 + QTest::newRow("") << QVector<qint64>({ col1.id() })
345 + << QStringList({ QLatin1String("unique/mime-type") })
346 + << QVector<qint64>();
347 + QTest::newRow("") << QVector<qint64>({ col2.id(), col7.id() })
348 + << QStringList({ QLatin1String("application/octet-stream") })
349 + << QVector<qint64>({ col3.id(), col8.id() });
352 + void testSearchHelperCollectionListing()
354 + QFETCH(QVector<qint64>, ancestors);
355 + QFETCH(QStringList, mimetypes);
356 + QFETCH(QVector<qint64>, expectedResults);
358 + QVector<qint64> results = SearchHelper::matchSubcollectionsByMimeType(ancestors, mimetypes);
360 + qSort(expectedResults);
363 + QCOMPARE(results.size(), expectedResults.size());
364 + QCOMPARE(results, expectedResults);
369 +AKTEST_FAKESERVER_MAIN(SearchTest)
371 +#include "searchtest.moc"