0026-Avoid-recursive-collection-listing-in-SearchHelper.patch

   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
   5
   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.
  12 ---
  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
  21
  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()
  27      }
  28
  29      if ( recursive ) {
  30 -      Q_FOREACH ( qint64 collection, collectionIds ) {
  31 -        collections << SearchHelper::listCollectionsRecursive( QVector<qint64>() << collection, mimeTypes );
  32 -      }
  33 +      collections << SearchHelper::matchSubcollectionsByMimeType( collectionIds, mimeTypes );
  34      } else {
  35        collections = collectionIds;
  36      }
  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
  41 @@ -20,6 +20,7 @@
  42
  43  #include "searchhelper.h"
  44  #include "storage/countquerybuilder.h"
  45 +#include <storage/queryhelper.h>
  46  #include "entities.h"
  47
  48  #include <libs/protocol_p.h>
  49 @@ -89,55 +90,77 @@ QString SearchHelper::extractMimetype( const QList<QByteArray> &junks, int start
  50  }
  51
  52
  53 -QVector<qint64> SearchHelper::listCollectionsRecursive( const QVector<qint64> &ancestors, const QStringList &mimeTypes )
  54 +static qint64 parentCollectionId(qint64 collectionId)
  55  {
  56 -  QVector<qint64> recursiveChildren;
  57 -  Q_FOREACH ( qint64 ancestor, ancestors ) {
  58 -    QVector<qint64> searchChildren;
  59 -
  60 -    { // Free the query before entering recursion to prevent too many opened connections
  61 -
  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 );
  68 -      }
  69 +    QueryBuilder qb(Collection::tableName(), QueryBuilder::Select);
  70 +    qb.addColumn(Collection::parentIdColumn());
  71 +    qb.addValueCondition(Collection::idColumn(), Query::Equals, collectionId);
  72 +    if (!qb.exec()) {
  73 +        return -1;
  74 +    }
  75 +    if (!qb.query().next()) {
  76 +        return -1;
  77 +    }
  78 +    return qb.query().value(0).toLongLong();
  79 +}
  80
  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() );
  87 -      } else {
  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 );
  93 -      }
  94 -      qb.addValueCondition( Collection::isVirtualFullColumnName(), Query::Equals, false );
  95 -      qb.addGroupColumn( Collection::idFullColumnName() );
  96 -      qb.exec();
  97 -
  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;
 104 +
 105 +QVector<qint64> SearchHelper::matchSubcollectionsByMimeType(const QVector<qint64> &ancestors, const QStringList &mimeTypes)
 106 +{
 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);
 119 +    }
 120 +    qb.addCondition(cond);
 121 +
 122 +    if (!qb.exec()) {
 123 +        qWarning() << "Failed to query search collections";
 124 +        return QVector<qint64>();
 125 +    }
 126 +
 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());
 130 +    }
 131 +
 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()) {
 137 +            results += res;
 138          }
 139 -        if ( query.value( 0 ).toInt() > 0 ) { // count( mimeTypeTable.name ) > 0
 140 -          recursiveChildren << id;
 141 +        return results;
 142 +    }
 143 +
 144 +    // Try to resolve direct descendants
 145 +    Q_FOREACH (qint64 ancestor, ancestors) {
 146 +        const QVector<qint64> cols = candidateCollections.take(ancestor);
 147 +        if (!cols.isEmpty()) {
 148 +            results += cols;
 149          }
 150 -      }
 151      }
 152 -    if ( !searchChildren.isEmpty() ) {
 153 -      recursiveChildren << listCollectionsRecursive( searchChildren, mimeTypes );
 154 +
 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);
 160 +        }
 161 +        // Ok, we found a requested ancestor in the parent chain
 162 +        if (parentId > 0) {
 163 +            results += iter.value();
 164 +        }
 165      }
 166 -  }
 167
 168 -  return recursiveChildren;
 169 +    return results;
 170  }
 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
 176    public:
 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 );
 181  };
 182
 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
 189    }
 190
 191    if ( recursive ) {
 192 -    queryCollections = SearchHelper::listCollectionsRecursive( queryAncestors, queryMimeTypes );
 193 +    queryCollections = SearchHelper::matchSubcollectionsByMimeType( queryAncestors, queryMimeTypes );
 194    } else {
 195      queryCollections = queryAncestors;
 196    }
 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)
 205 +
 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
 209 new file mode 100644
 210 index 0000000..f523b09
 211 --- /dev/null
 212 +++ b/server/tests/unittest/searchtest.cpp
 213 @@ -0,0 +1,158 @@
 214 +/*
 215 + * Copyright (C) 2014  Daniel Vrátil <dvratil@redhat.com>
 216 + *
 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.
 221 + *
 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.
 226 + *
 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
 230 + *
 231 + */
 232 +
 233 +#include "fakeakonadiserver.h"
 234 +#include "searchhelper.h"
 235 +#include "akdebug.h"
 236 +#include "aktest.h"
 237 +
 238 +#include <entities.h>
 239 +
 240 +#include <QTest>
 241 +
 242 +using namespace Akonadi::Server;
 243 +
 244 +Q_DECLARE_METATYPE(QList<qint64>)
 245 +Q_DECLARE_METATYPE(QList<QString>)
 246 +
 247 +
 248 +class SearchTest : public QObject
 249 +{
 250 +    Q_OBJECT
 251 +
 252 +public:
 253 +    SearchTest()
 254 +        : QObject()
 255 +    {
 256 +        try {
 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";
 262 +        }
 263 +    }
 264 +
 265 +    ~SearchTest()
 266 +    {
 267 +        FakeAkonadiServer::instance()->quit();
 268 +    }
 269 +
 270 +    Collection createCollection(const Resource &res, const QString &name, const Collection &parent, const QStringList &mimetypes)
 271 +    {
 272 +        Collection col;
 273 +        col.setName(name);
 274 +        col.setResource(res);
 275 +        col.setParentId(parent.isValid() ? parent.id() : 0);
 276 +        col.insert();
 277 +        Q_FOREACH (const QString &mimeType, mimetypes) {
 278 +            MimeType mt = MimeType::retrieveByName(mimeType);
 279 +            if (!mt.isValid()) {
 280 +                mt = MimeType(mimeType);
 281 +                mt.insert();
 282 +            }
 283 +            col.addMimeType(mt);
 284 +        }
 285 +        return col;
 286 +    }
 287 +
 288 +private Q_SLOTS:
 289 +    void testSearchHelperCollectionListing_data()
 290 +    {
 291 +        /*
 292 +        Fake Resource
 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)
 302 +        */
 303 +
 304 +        Resource res(QLatin1String("Test Resource"), false);
 305 +        res.insert();
 306 +
 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"));
 330 +
 331 +        QTest::addColumn<QVector<qint64>>("ancestors");
 332 +        QTest::addColumn<QStringList>("mimetypes");
 333 +        QTest::addColumn<QVector<qint64>>("expectedResults");
 334 +
 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() });
 350 +    }
 351 +
 352 +    void testSearchHelperCollectionListing()
 353 +    {
 354 +        QFETCH(QVector<qint64>, ancestors);
 355 +        QFETCH(QStringList, mimetypes);
 356 +        QFETCH(QVector<qint64>, expectedResults);
 357 +
 358 +        QVector<qint64> results = SearchHelper::matchSubcollectionsByMimeType(ancestors, mimetypes);
 359 +
 360 +        qSort(expectedResults);
 361 +        qSort(results);
 362 +
 363 +        QCOMPARE(results.size(), expectedResults.size());
 364 +        QCOMPARE(results, expectedResults);
 365 +    }
 366 +
 367 +};
 368 +
 369 +AKTEST_FAKESERVER_MAIN(SearchTest)
 370 +
 371 +#include "searchtest.moc"
 372 --
 373 2.1.0
 374