Implement Overlap queries

Summary:
Notes:

- Introduces the concept of queries on multiple properties (which meant changing query's internals a bit)
- Dates are stored as well as the "reference" in the index to allow quick filtering without fetching the whole entity
- Buckets are weeks starting on Monday (guaranteed by the use of the Julian calendar)
- Some size improvements are definitely possible (dates are padded numbers again, not using integer databases, Julian calendar starts at a very old date, etc.)

Test Plan: Tested in querytest

Reviewers: cmollekopf

Reviewed By: cmollekopf

Tags: #sink

Differential Revision: https://phabricator.kde.org/D13477

12 files changed, 382 insertions, 34 deletions

diff --git a/common/datastorequery.cpp b/common/datastorequery.cpp
index 12c0ae1..263d3ea 100644
--- a/common/datastorequery.cpp
+++ b/common/datastorequery.cpp
@@ -119,7 +119,7 @@ class Filter : public FilterBase {
 public:
     typedef QSharedPointer<Filter> Ptr;
 
-    QHash<QByteArray, Sink::QueryBase::Comparator> propertyFilter;
+    QHash<QByteArrayList, Sink::QueryBase::Comparator> propertyFilter;
 
     Filter(FilterBase::Ptr source, DataStoreQuery *store)
         : FilterBase(source, store)
@@ -158,7 +158,16 @@ public:
 
     bool matchesFilter(const ApplicationDomain::ApplicationDomainType &entity) {
         for (const auto &filterProperty : propertyFilter.keys()) {
-            const auto property = entity.getProperty(filterProperty);
+            QVariant property;
+            if (filterProperty.size() == 1) {
+                property = entity.getProperty(filterProperty[0]);
+            } else {
+                QVariantList propList;
+                for (const auto &propName : filterProperty) {
+                    propList.push_back(entity.getProperty(propName));
+                }
+                property = propList;
+            }
             const auto comparator = propertyFilter.value(filterProperty);
             //We can't deal with a fulltext filter
             if (comparator.comparator == QueryBase::Comparator::Fulltext) {
@@ -420,7 +429,7 @@ public:
                 }))
             {}
             mBloomed = true;
-            propertyFilter.insert(mBloomProperty, mBloomValue);
+            propertyFilter.insert({mBloomProperty}, mBloomValue);
             return foundValue;
         } else {
             //Filter on bloom value
@@ -598,7 +607,7 @@ void DataStoreQuery::setupQuery(const Sink::QueryBase &query_)
             //We have a set of ids as a starting point
             return Source::Ptr::create(query.ids().toVector(), this);
         } else {
-            QSet<QByteArray> appliedFilters;
+            QSet<QByteArrayList> appliedFilters;
             auto resultSet = mStore.indexLookup(mType, query, appliedFilters, appliedSorting);
             if (!appliedFilters.isEmpty()) {
                 //We have an index lookup as starting point
diff --git a/common/domain/typeimplementations.cpp b/common/domain/typeimplementations.cpp
index a8f4baf..2b2d2ac 100644
--- a/common/domain/typeimplementations.cpp
+++ b/common/domain/typeimplementations.cpp
@@ -65,7 +65,8 @@ typedef IndexConfig<Addressbook,
 
 typedef IndexConfig<Event,
         ValueIndex<Event::Uid>,
-        SortedIndex<Event::StartTime>
+        SortedIndex<Event::StartTime>,
+        SampledPeriodIndex<Event::StartTime, Event::EndTime>
     > EventIndexConfig;
 
 typedef IndexConfig<Todo,
diff --git a/common/domain/typeimplementations_p.h b/common/domain/typeimplementations_p.h
index fc08048..51af113 100644
--- a/common/domain/typeimplementations_p.h
+++ b/common/domain/typeimplementations_p.h
@@ -126,6 +126,26 @@ public:
     }
 };
 
+template <typename RangeBeginProperty, typename RangeEndProperty>
+class SampledPeriodIndex
+{
+    static_assert(std::is_same<typename RangeBeginProperty::Type, QDateTime>::value &&
+                      std::is_same<typename RangeEndProperty::Type, QDateTime>::value,
+        "Date range index is not supported for types other than 'QDateTime's");
+
+public:
+    static void configure(TypeIndex &index)
+    {
+        index.addSampledPeriodIndex<RangeBeginProperty, RangeEndProperty>();
+    }
+
+    template <typename EntityType>
+    static QMap<QByteArray, int> databases()
+    {
+        return {{QByteArray{EntityType::name} +".index." + RangeBeginProperty::name + ".range." + RangeEndProperty::name, 1}};
+    }
+};
+
 template <typename EntityType, typename ... Indexes>
 class IndexConfig
 {
diff --git a/common/query.cpp b/common/query.cpp
index 404a304..ceb1897 100644
--- a/common/query.cpp
+++ b/common/query.cpp
@@ -179,6 +179,19 @@ bool QueryBase::Comparator::matches(const QVariant &v) const
 
             return range[0] <= v && v <= range[1];
         }
+        case Overlap: {
+            auto bounds = value.value<QList<QVariant>>();
+            if (bounds.size() < 2) {
+                return false;
+            }
+
+            auto range = v.value<QList<QVariant>>();
+            if (range.size() < 2) {
+                return false;
+            }
+
+            return range[0] <= bounds[1] && bounds[0] <= range[1];
+        }
         case Fulltext:
         case Invalid:
         default:
diff --git a/common/query.h b/common/query.h
index 7130116..cb9c8ca 100644
--- a/common/query.h
+++ b/common/query.h
@@ -37,6 +37,7 @@ public:
             Contains,
             In,
             Within,
+            Overlap,
             Fulltext
         };
 
@@ -53,7 +54,7 @@ public:
     class SINK_EXPORT Filter {
     public:
         QByteArrayList ids;
-        QHash<QByteArray, Comparator> propertyFilter;
+        QHash<QByteArrayList, Comparator> propertyFilter;
         bool operator==(const Filter &other) const;
     };
 
@@ -64,7 +65,12 @@ public:
 
     Comparator getFilter(const QByteArray &property) const
     {
-        return mBaseFilterStage.propertyFilter.value(property);
+        return mBaseFilterStage.propertyFilter.value({property});
+    }
+
+    Comparator getFilter(const QByteArrayList &properties) const
+    {
+        return mBaseFilterStage.propertyFilter.value(properties);
     }
 
     template <class T>
@@ -73,9 +79,15 @@ public:
         return getFilter(T::name);
     }
 
+    template <class T1, class T2, class... Rest>
+    Comparator getFilter() const
+    {
+        return getFilter({T1::name, T2::name, Rest::name...});
+    }
+
     bool hasFilter(const QByteArray &property) const
     {
-        return mBaseFilterStage.propertyFilter.contains(property);
+        return mBaseFilterStage.propertyFilter.contains({property});
     }
 
     template <class T>
@@ -94,7 +106,7 @@ public:
         return mId;
     }
 
-    void setBaseFilters(const QHash<QByteArray, Comparator> &filter)
+    void setBaseFilters(const QHash<QByteArrayList, Comparator> &filter)
     {
         mBaseFilterStage.propertyFilter = filter;
     }
@@ -104,7 +116,7 @@ public:
         mBaseFilterStage = filter;
     }
 
-    QHash<QByteArray, Comparator> getBaseFilters() const
+    QHash<QByteArrayList, Comparator> getBaseFilters() const
     {
         return mBaseFilterStage.propertyFilter;
     }
@@ -131,7 +143,12 @@ public:
 
     void filter(const QByteArray &property, const QueryBase::Comparator &comparator)
     {
-        mBaseFilterStage.propertyFilter.insert(property, comparator);
+        mBaseFilterStage.propertyFilter.insert({property}, comparator);
+    }
+
+    void filter(const QByteArrayList &properties, const QueryBase::Comparator &comparator)
+    {
+        mBaseFilterStage.propertyFilter.insert(properties, comparator);
     }
 
     void setType(const QByteArray &type)
@@ -373,6 +390,13 @@ public:
         return *this;
     }
 
+    template <typename T1, typename T2, typename... Rest>
+    Query &filter(const QueryBase::Comparator &comparator)
+    {
+        QueryBase::filter({T1::name, T2::name, Rest::name...}, comparator);
+        return *this;
+    }
+
     Query &filter(const QByteArray &id)
     {
         QueryBase::filter(id);
@@ -465,13 +489,13 @@ public:
     template <typename T>
     Query &resourceFilter(const ApplicationDomain::ApplicationDomainType &entity)
     {
-        mResourceFilter.propertyFilter.insert(T::name, Comparator(entity.identifier()));
+        mResourceFilter.propertyFilter.insert({T::name}, Comparator(entity.identifier()));
         return *this;
     }
 
     Query &resourceFilter(const QByteArray &name, const Comparator &comparator)
     {
-        mResourceFilter.propertyFilter.insert(name, comparator);
+        mResourceFilter.propertyFilter.insert({name}, comparator);
         return *this;
     }
 
@@ -531,13 +555,13 @@ public:
     template <typename T>
     SyncScope &resourceFilter(const ApplicationDomain::ApplicationDomainType &entity)
     {
-        mResourceFilter.propertyFilter.insert(T::name, Comparator(entity.identifier()));
+        mResourceFilter.propertyFilter.insert({T::name}, Comparator(entity.identifier()));
         return *this;
     }
 
     SyncScope &resourceFilter(const QByteArray &name, const Comparator &comparator)
     {
-        mResourceFilter.propertyFilter.insert(name, comparator);
+        mResourceFilter.propertyFilter.insert({name}, comparator);
         return *this;
     }
 
diff --git a/common/resourcefacade.cpp b/common/resourcefacade.cpp
index 7998692..90194d4 100644
--- a/common/resourcefacade.cpp
+++ b/common/resourcefacade.cpp
@@ -80,13 +80,13 @@ typename ApplicationDomain::SinkResource::Ptr readFromConfig<ApplicationDomain::
     return object;
 }
 
-static bool matchesFilter(const QHash<QByteArray, Query::Comparator> &filter, const ApplicationDomain::ApplicationDomainType &entity)
+static bool matchesFilter(const QHash<QByteArrayList, Query::Comparator> &filter, const ApplicationDomain::ApplicationDomainType &entity)
 {
     for (const auto &filterProperty : filter.keys()) {
-        if (filterProperty == ApplicationDomain::SinkResource::ResourceType::name) {
+        if (filterProperty[0] == ApplicationDomain::SinkResource::ResourceType::name) {
             continue;
         }
-        if (!filter.value(filterProperty).matches(entity.getProperty(filterProperty))) {
+        if (!filter.value(filterProperty).matches(entity.getProperty(filterProperty[0]))) {
             return false;
         }
     }
@@ -432,7 +432,7 @@ KAsync::Job<void> AccountFacade::remove(const Sink::ApplicationDomain::SinkAccou
     //Remove all identities
     job = job.then(Store::fetch<Identity>(Sink::Query{}.filter<Identity::Account>(account)))
         .each([] (const Identity::Ptr &identity) { return Store::remove(*identity); });
- 
+
     return job.then(LocalStorageFacade<Sink::ApplicationDomain::SinkAccount>::remove(account));
 }
 
diff --git a/common/storage/entitystore.cpp b/common/storage/entitystore.cpp
index 230dbc7..4fe7e3b 100644
--- a/common/storage/entitystore.cpp
+++ b/common/storage/entitystore.cpp
@@ -443,7 +443,7 @@ QVector<QByteArray> EntityStore::fullScan(const QByteArray &type)
     return keys.toList().toVector();
 }
 
-QVector<QByteArray> EntityStore::indexLookup(const QByteArray &type, const QueryBase &query, QSet<QByteArray> &appliedFilters, QByteArray &appliedSorting)
+QVector<QByteArray> EntityStore::indexLookup(const QByteArray &type, const QueryBase &query, QSet<QByteArrayList> &appliedFilters, QByteArray &appliedSorting)
 {
     if (!d->exists()) {
         SinkTraceCtx(d->logCtx) << "Database is not existing: " << type;
diff --git a/common/storage/entitystore.h b/common/storage/entitystore.h
index d79a0b5..ffa70b9 100644
--- a/common/storage/entitystore.h
+++ b/common/storage/entitystore.h
@@ -57,7 +57,7 @@ public:
     bool hasTransaction() const;
 
     QVector<QByteArray> fullScan(const QByteArray &type);
-    QVector<QByteArray> indexLookup(const QByteArray &type, const QueryBase &query, QSet<QByteArray> &appliedFilters, QByteArray &appliedSorting);
+    QVector<QByteArray> indexLookup(const QByteArray &type, const QueryBase &query, QSet<QByteArrayList> &appliedFilters, QByteArray &appliedSorting);
     QVector<QByteArray> indexLookup(const QByteArray &type, const QByteArray &property, const QVariant &value);
     void indexLookup(const QByteArray &type, const QByteArray &property, const QVariant &value, const std::function<void(const QByteArray &uid)> &callback);
     template<typename EntityType, typename PropertyType>
diff --git a/common/store.cpp b/common/store.cpp
index be2488a..0328c7f 100644
--- a/common/store.cpp
+++ b/common/store.cpp
@@ -117,11 +117,13 @@ QPair<typename AggregatingResultEmitter<typename DomainType::Ptr>::Ptr,  typenam
 
         //Filter resources by available content types (unless the query already specifies a capability filter)
         auto resourceFilter = query.getResourceFilter();
-        if (!resourceFilter.propertyFilter.contains(ApplicationDomain::SinkResource::Capabilities::name)) {
-            resourceFilter.propertyFilter.insert(ApplicationDomain::SinkResource::Capabilities::name, Query::Comparator{ApplicationDomain::getTypeName<DomainType>(), Query::Comparator::Contains});
+        if (!resourceFilter.propertyFilter.contains({ApplicationDomain::SinkResource::Capabilities::name})) {
+            resourceFilter.propertyFilter.insert({ApplicationDomain::SinkResource::Capabilities::name}, Query::Comparator{ApplicationDomain::getTypeName<DomainType>(), Query::Comparator::Contains});
         }
         resourceQuery.setFilter(resourceFilter);
-        resourceQuery.requestedProperties << resourceFilter.propertyFilter.keys();
+        for (auto const &properties :  resourceFilter.propertyFilter.keys()) {
+            resourceQuery.requestedProperties << properties;
+        }
 
         auto result = facade->load(resourceQuery, resourceCtx);
         auto emitter = result.second;
@@ -403,8 +405,8 @@ KAsync::Job<void> Store::synchronize(const Sink::SyncScope &scope)
 {
     auto resourceFilter = scope.getResourceFilter();
     //Filter resources by type by default
-    if (!resourceFilter.propertyFilter.contains(ApplicationDomain::SinkResource::Capabilities::name) && !scope.type().isEmpty()) {
-        resourceFilter.propertyFilter.insert(ApplicationDomain::SinkResource::Capabilities::name, Query::Comparator{scope.type(), Query::Comparator::Contains});
+    if (!resourceFilter.propertyFilter.contains({ApplicationDomain::SinkResource::Capabilities::name}) && !scope.type().isEmpty()) {
+        resourceFilter.propertyFilter.insert({ApplicationDomain::SinkResource::Capabilities::name}, Query::Comparator{scope.type(), Query::Comparator::Contains});
     }
     Sink::Query query;
     query.setFilter(resourceFilter);
diff --git a/common/typeindex.cpp b/common/typeindex.cpp
index 41821cb..6aa3796 100644
--- a/common/typeindex.cpp
+++ b/common/typeindex.cpp
@@ -53,6 +53,12 @@ static QByteArray getByteArray(const QVariant &value)
     return "toplevel";
 }
 
+template <typename T>
+static QByteArray padNumber(T number)
+{
+    static T uint_num_digits = (T)std::log10(std::numeric_limits<T>::max()) + 1;
+    return QByteArray::number(number).rightJustified(uint_num_digits, '0');
+}
 
 static QByteArray toSortableByteArrayImpl(const QDateTime &date)
 {
@@ -60,8 +66,7 @@ static QByteArray toSortableByteArrayImpl(const QDateTime &date)
     if (!date.isValid()) {
         return QByteArray::number(std::numeric_limits<unsigned int>::max());
     }
-    static unsigned int uint_num_digits = (unsigned int)std::log10(std::numeric_limits<unsigned int>::max()) + 1;
-    return QByteArray::number(std::numeric_limits<unsigned int>::max() - date.toTime_t()).rightJustified(uint_num_digits, '0');
+    return padNumber(std::numeric_limits<unsigned int>::max() - date.toTime_t());
 }
 
 static QByteArray toSortableByteArray(const QVariant &value)
@@ -99,6 +104,22 @@ QByteArray TypeIndex::sortedIndexName(const QByteArray &property) const
     return mType + ".index." + property + ".sorted";
 }
 
+QByteArray TypeIndex::sampledPeriodIndexName(const QByteArray &rangeBeginProperty, const QByteArray &rangeEndProperty) const
+{
+    return mType + ".index." + rangeBeginProperty + ".range." + rangeEndProperty;
+}
+
+static unsigned int bucketOf(const QVariant &value)
+{
+    switch (value.type()) {
+        case QMetaType::QDateTime:
+            return value.value<QDateTime>().date().toJulianDay() / 7;
+        default:
+            SinkError() << "Not knowing how to get the bucket of a" << value.typeName();
+            return {};
+    }
+}
+
 template <>
 void TypeIndex::addProperty<QByteArray>(const QByteArray &property)
 {
@@ -202,6 +223,41 @@ void TypeIndex::addPropertyWithSorting<ApplicationDomain::Reference, QDateTime>(
     addPropertyWithSorting<QByteArray, QDateTime>(property, sortProperty);
 }
 
+template <>
+void TypeIndex::addSampledPeriodIndex<QDateTime, QDateTime>(
+    const QByteArray &beginProperty, const QByteArray &endProperty)
+{
+    auto indexer = [=](bool add, const QByteArray &identifier, const QVariant &begin,
+                       const QVariant &end, Sink::Storage::DataStore::Transaction &transaction) {
+        SinkTraceCtx(mLogCtx) << "Adding entity to sampled period index";
+        const auto beginDate = begin.toDateTime();
+        const auto endDate = end.toDateTime();
+
+        auto beginBucket = bucketOf(beginDate);
+        auto endBucket   = bucketOf(endDate);
+
+        if (beginBucket > endBucket) {
+            SinkError() << "End bucket greater than begin bucket";
+            return;
+        }
+
+        Index index(sampledPeriodIndexName(beginProperty, endProperty), transaction);
+        for (auto bucket = beginBucket; bucket <= endBucket; ++bucket) {
+            QByteArray bucketKey = padNumber(bucket);
+            if (add) {
+                SinkTraceCtx(mLogCtx) << "Adding entity to bucket:" << bucketKey;
+                index.add(bucketKey, identifier);
+            } else {
+                SinkTraceCtx(mLogCtx) << "Removing entity from bucket:" << bucketKey;
+                index.remove(bucketKey, identifier);
+            }
+        }
+    };
+
+    mSampledPeriodProperties.insert({ beginProperty, endProperty });
+    mSampledPeriodIndexer.insert({ beginProperty, endProperty }, indexer);
+}
+
 void TypeIndex::updateIndex(bool add, const QByteArray &identifier, const Sink::ApplicationDomain::ApplicationDomainType &entity, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId)
 {
     for (const auto &property : mProperties) {
@@ -209,6 +265,12 @@ void TypeIndex::updateIndex(bool add, const QByteArray &identifier, const Sink::
         auto indexer = mIndexer.value(property);
         indexer(add, identifier, value, transaction);
     }
+    for (const auto &properties : mSampledPeriodProperties) {
+        const auto beginValue = entity.getProperty(properties.first);
+        const auto endValue   = entity.getProperty(properties.second);
+        auto indexer = mSampledPeriodIndexer.value(properties);
+        indexer(add, identifier, beginValue, endValue, transaction);
+    }
     for (const auto &property : mSortedProperties) {
         const auto value = entity.getProperty(property);
         auto indexer = mSortIndexer.value(property);
@@ -312,7 +374,38 @@ static QVector<QByteArray> sortedIndexLookup(Index &index, QueryBase::Comparator
     return keys;
 }
 
-QVector<QByteArray> TypeIndex::query(const Sink::QueryBase &query, QSet<QByteArray> &appliedFilters, QByteArray &appliedSorting, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId)
+static QVector<QByteArray> sampledIndexLookup(Index &index, QueryBase::Comparator filter)
+{
+    if (filter.comparator != Query::Comparator::Overlap) {
+        SinkWarning() << "Comparisons other than Overlap not supported on sampled period indexes";
+        return {};
+    }
+
+    QVector<QByteArray> keys;
+
+    auto bounds = filter.value.value<QVariantList>();
+
+    QByteArray lowerBound = toSortableByteArray(bounds[0]);
+    QByteArray upperBound = toSortableByteArray(bounds[1]);
+
+    QByteArray lowerBucket = padNumber(bucketOf(bounds[0]));
+    QByteArray upperBucket = padNumber(bucketOf(bounds[1]));
+
+    SinkTrace() << "Looking up from bucket:" << lowerBucket << "to:" << upperBucket;
+
+    index.rangeLookup(lowerBucket, upperBucket,
+        [&](const QByteArray &value) {
+            keys << value.data();
+        },
+        [bounds](const Index::Error &error) {
+            SinkWarning() << "Lookup error in index:" << error.message
+                          << "with bounds:" << bounds[0] << bounds[1];
+        });
+
+    return keys;
+}
+
+QVector<QByteArray> TypeIndex::query(const Sink::QueryBase &query, QSet<QByteArrayList> &appliedFilters, QByteArray &appliedSorting, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId)
 {
     const auto baseFilters = query.getBaseFilters();
     for (auto it = baseFilters.constBegin(); it != baseFilters.constEnd(); it++) {
@@ -325,11 +418,28 @@ QVector<QByteArray> TypeIndex::query(const Sink::QueryBase &query, QSet<QByteArr
         }
     }
 
+    for (auto it = baseFilters.constBegin(); it != baseFilters.constEnd(); it++) {
+        if (it.value().comparator == QueryBase::Comparator::Overlap) {
+            if (mSampledPeriodProperties.contains({it.key()[0], it.key()[1]})) {
+                Index index(sampledPeriodIndexName(it.key()[0], it.key()[1]), transaction);
+                const auto keys = sampledIndexLookup(index, query.getFilter(it.key()));
+                // The filter is not completely applied, we need post-filtering
+                // in the case the overlap period is not completely aligned
+                // with a week starting on monday
+                //appliedFilters << it.key();
+                SinkTraceCtx(mLogCtx) << "Sampled period index lookup on" << it.key() << "found" << keys.size() << "keys.";
+                return keys;
+            } else {
+                SinkWarning() << "Overlap search without sampled period index";
+            }
+        }
+    }
+
     for (auto it = mGroupedSortedProperties.constBegin(); it != mGroupedSortedProperties.constEnd(); it++) {
         if (query.hasFilter(it.key()) && query.sortProperty() == it.value()) {
             Index index(indexName(it.key(), it.value()), transaction);
             const auto keys = indexLookup(index, query.getFilter(it.key()));
-            appliedFilters << it.key();
+            appliedFilters.insert({it.key()});
             appliedSorting = it.value();
             SinkTraceCtx(mLogCtx) << "Grouped sorted index lookup on " << it.key() << it.value() << " found " << keys.size() << " keys.";
             return keys;
@@ -340,7 +450,7 @@ QVector<QByteArray> TypeIndex::query(const Sink::QueryBase &query, QSet<QByteArr
         if (query.hasFilter(property)) {
             Index index(sortedIndexName(property), transaction);
             const auto keys = sortedIndexLookup(index, query.getFilter(property));
-            appliedFilters << property;
+            appliedFilters.insert({property});
             SinkTraceCtx(mLogCtx) << "Sorted index lookup on " << property << " found " << keys.size() << " keys.";
             return keys;
         }
@@ -350,7 +460,7 @@ QVector<QByteArray> TypeIndex::query(const Sink::QueryBase &query, QSet<QByteArr
         if (query.hasFilter(property)) {
             Index index(indexName(property), transaction);
             const auto keys = indexLookup(index, query.getFilter(property));
-            appliedFilters << property;
+            appliedFilters.insert({property});
             SinkTraceCtx(mLogCtx) << "Index lookup on " << property << " found " << keys.size() << " keys.";
             return keys;
         }
diff --git a/common/typeindex.h b/common/typeindex.h
index 793dc1e..a8c0e10 100644
--- a/common/typeindex.h
+++ b/common/typeindex.h
@@ -73,10 +73,19 @@ public:
         mCustomIndexer << CustomIndexer::Ptr::create();
     }
 
+    template <typename Begin, typename End>
+    void addSampledPeriodIndex(const QByteArray &beginProperty, const QByteArray &endProperty);
+
+    template <typename Begin, typename End>
+    void addSampledPeriodIndex()
+    {
+        addSampledPeriodIndex<typename Begin::Type, typename End::Type>(Begin::name, End::name);
+    }
+
     void add(const QByteArray &identifier, const Sink::ApplicationDomain::ApplicationDomainType &entity, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId);
     void remove(const QByteArray &identifier, const Sink::ApplicationDomain::ApplicationDomainType &entity, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId);
 
-    QVector<QByteArray> query(const Sink::QueryBase &query, QSet<QByteArray> &appliedFilters, QByteArray &appliedSorting, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId);
+    QVector<QByteArray> query(const Sink::QueryBase &query, QSet<QByteArrayList> &appliedFilters, QByteArray &appliedSorting, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId);
     QVector<QByteArray> lookup(const QByteArray &property, const QVariant &value, Sink::Storage::DataStore::Transaction &transaction);
 
     template <typename Left, typename Right>
@@ -115,6 +124,7 @@ private:
     void updateIndex(bool add, const QByteArray &identifier, const Sink::ApplicationDomain::ApplicationDomainType &entity, Sink::Storage::DataStore::Transaction &transaction, const QByteArray &resourceInstanceId);
     QByteArray indexName(const QByteArray &property, const QByteArray &sortProperty = QByteArray()) const;
     QByteArray sortedIndexName(const QByteArray &property) const;
+    QByteArray sampledPeriodIndexName(const QByteArray &rangeBeginProperty, const QByteArray &rangeEndProperty) const;
     Sink::Log::Context mLogCtx;
     QByteArray mType;
     QByteArrayList mProperties;
@@ -122,9 +132,11 @@ private:
     QMap<QByteArray, QByteArray> mGroupedSortedProperties;
     //<Property, ResultProperty>
     QMap<QByteArray, QByteArray> mSecondaryProperties;
+    QSet<QPair<QByteArray, QByteArray>> mSampledPeriodProperties;
     QList<Sink::Indexer::Ptr> mCustomIndexer;
     Sink::Storage::DataStore::Transaction *mTransaction;
     QHash<QByteArray, std::function<void(bool, const QByteArray &identifier, const QVariant &value, Sink::Storage::DataStore::Transaction &transaction)>> mIndexer;
     QHash<QByteArray, std::function<void(bool, const QByteArray &identifier, const QVariant &value, Sink::Storage::DataStore::Transaction &transaction)>> mSortIndexer;
     QHash<QByteArray, std::function<void(bool, const QByteArray &identifier, const QVariant &value, const QVariant &sortValue, Sink::Storage::DataStore::Transaction &transaction)>> mGroupedSortIndexer;
+    QHash<QPair<QByteArray, QByteArray>, std::function<void(bool, const QByteArray &identifier, const QVariant &begin, const QVariant &end, Sink::Storage::DataStore::Transaction &transaction)>> mSampledPeriodIndexer;
 };
diff --git a/tests/querytest.cpp b/tests/querytest.cpp
index 36b6e90..b52ba96 100644
--- a/tests/querytest.cpp
+++ b/tests/querytest.cpp
@@ -59,7 +59,7 @@ private slots:
 
         Sink::QueryBase::Filter filter;
         filter.ids << "id";
-        filter.propertyFilter.insert("foo", QVariant::fromValue(QByteArray("bar")));
+        filter.propertyFilter.insert({"foo"}, QVariant::fromValue(QByteArray("bar")));
 
         Sink::Query query;
         query.setFilter(filter);
@@ -1617,6 +1617,163 @@ private slots:
             QCOMPARE(model->rowCount(), 4);
         }
     }
+
+    void eventsWithDates()
+    {
+        {
+            Event event("sink.dummy.instance1");
+            event.setExtractedStartTime(QDateTime::fromString("2018-05-23T12:00:00Z", Qt::ISODate));
+            event.setExtractedEndTime(QDateTime::fromString("2018-05-23T13:00:00Z", Qt::ISODate));
+            VERIFYEXEC(Sink::Store::create<Event>(event));
+        }
+        {
+            Event event("sink.dummy.instance1");
+            event.setExtractedStartTime(QDateTime::fromString("2018-05-23T13:00:00Z", Qt::ISODate));
+            event.setExtractedEndTime(QDateTime::fromString("2018-05-23T14:00:00Z", Qt::ISODate));
+            VERIFYEXEC(Sink::Store::create<Event>(event));
+        }
+        {
+            Event event("sink.dummy.instance1");
+            event.setExtractedStartTime(QDateTime::fromString("2018-05-23T14:00:00Z", Qt::ISODate));
+            event.setExtractedEndTime(QDateTime::fromString("2018-05-23T15:00:00Z", Qt::ISODate));
+            VERIFYEXEC(Sink::Store::create<Event>(event));
+        }
+        {
+            Event event("sink.dummy.instance1");
+            event.setExtractedStartTime(QDateTime::fromString("2018-05-23T12:00:00Z", Qt::ISODate));
+            event.setExtractedEndTime(QDateTime::fromString("2018-05-23T14:00:00Z", Qt::ISODate));
+            VERIFYEXEC(Sink::Store::create<Event>(event));
+        }
+        {
+            Event event("sink.dummy.instance1");
+            event.setExtractedStartTime(QDateTime::fromString("2018-05-24T12:00:00Z", Qt::ISODate));
+            event.setExtractedEndTime(QDateTime::fromString("2018-05-24T14:00:00Z", Qt::ISODate));
+            VERIFYEXEC(Sink::Store::create<Event>(event));
+        }
+        {
+            Event event("sink.dummy.instance1");
+            VERIFYEXEC(Sink::Store::create<Event>(event));
+        }
+
+        VERIFYEXEC(Sink::ResourceControl::flushMessageQueue("sink.dummy.instance1"));
+    }
+
+    void testOverlap()
+    {
+        eventsWithDates();
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Event::StartTime, Event::EndTime>(QueryBase::Comparator(
+                QVariantList{ QDateTime::fromString("2018-05-22T12:00:00Z", Qt::ISODate),
+                    QDateTime::fromString("2018-05-30T13:00:00Z", Qt::ISODate) },
+                QueryBase::Comparator::Overlap));
+            auto model = Sink::Store::loadModel<Event>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 5);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Event::StartTime, Event::EndTime>(QueryBase::Comparator(
+                QVariantList{ QDateTime::fromString("2018-05-22T12:30:00Z", Qt::ISODate),
+                    QDateTime::fromString("2018-05-22T12:31:00Z", Qt::ISODate) },
+                QueryBase::Comparator::Overlap));
+            auto model = Sink::Store::loadModel<Event>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 0);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Event::StartTime, Event::EndTime>(QueryBase::Comparator(
+                QVariantList{ QDateTime::fromString("2018-05-24T10:00:00Z", Qt::ISODate),
+                    QDateTime::fromString("2018-05-24T11:00:00Z", Qt::ISODate) },
+                QueryBase::Comparator::Overlap));
+            auto model = Sink::Store::loadModel<Event>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 0);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Event::StartTime, Event::EndTime>(QueryBase::Comparator(
+                QVariantList{ QDateTime::fromString("2018-05-23T12:30:00Z", Qt::ISODate),
+                    QDateTime::fromString("2018-05-23T12:31:00Z", Qt::ISODate) },
+                QueryBase::Comparator::Overlap));
+            auto model = Sink::Store::loadModel<Event>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 2);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Event::StartTime, Event::EndTime>(QueryBase::Comparator(
+                QVariantList{ QDateTime::fromString("2018-05-22T12:30:00Z", Qt::ISODate),
+                    QDateTime::fromString("2018-05-23T12:00:00Z", Qt::ISODate) },
+                QueryBase::Comparator::Overlap));
+            auto model = Sink::Store::loadModel<Event>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 2);
+        }
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.filter<Event::StartTime, Event::EndTime>(QueryBase::Comparator(
+                QVariantList{ QDateTime::fromString("2018-05-23T14:30:00Z", Qt::ISODate),
+                    QDateTime::fromString("2018-05-23T16:00:00Z", Qt::ISODate) },
+                QueryBase::Comparator::Overlap));
+            auto model = Sink::Store::loadModel<Event>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 1);
+        }
+
+    }
+
+    void testOverlapLive()
+    {
+        eventsWithDates();
+
+        {
+            Sink::Query query;
+            query.resourceFilter("sink.dummy.instance1");
+            query.setFlags(Query::LiveQuery);
+            query.filter<Event::StartTime, Event::EndTime>(QueryBase::Comparator(
+                QVariantList{ QDateTime::fromString("2018-05-22T12:00:00Z", Qt::ISODate),
+                    QDateTime::fromString("2018-05-30T13:00:00Z", Qt::ISODate) },
+                QueryBase::Comparator::Overlap));
+            auto model = Sink::Store::loadModel<Event>(query);
+            QTRY_VERIFY(model->data(QModelIndex(), Sink::Store::ChildrenFetchedRole).toBool());
+            QCOMPARE(model->rowCount(), 5);
+
+            Event event = Event::createEntity<Event>("sink.dummy.instance1");
+            event.setExtractedStartTime(QDateTime::fromString("2018-05-23T12:00:00Z", Qt::ISODate));
+            event.setExtractedEndTime(QDateTime::fromString("2018-05-23T13:00:00Z", Qt::ISODate));
+            VERIFYEXEC(Sink::Store::create<Event>(event));
+
+            Event event2 = Event::createEntity<Event>("sink.dummy.instance1");
+            event2.setExtractedStartTime(QDateTime::fromString("2018-05-33T12:00:00Z", Qt::ISODate));
+            event2.setExtractedEndTime(QDateTime::fromString("2018-05-33T13:00:00Z", Qt::ISODate));
+            VERIFYEXEC(Sink::Store::create<Event>(event2));
+
+            QTest::qWait(500);
+            QCOMPARE(model->rowCount(), 6);
+
+            VERIFYEXEC(Sink::Store::remove<Event>(event));
+            VERIFYEXEC(Sink::Store::remove<Event>(event2));
+
+            QTest::qWait(500);
+            QCOMPARE(model->rowCount(), 5);
+        }
+
+    }
+
 };
 
 QTEST_MAIN(QueryTest)