Skip to content

Instantly share code, notes, and snippets.

@buremba

buremba/partialindex.md

Last active August 29, 2015 14:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save buremba/becd46dc40b920fc073f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save buremba/becd46dc40b920fc073f to your computer and use it in GitHub Desktop.
Download ZIP
hazelcast partial index
Raw
partialindex.md

#Partial Index Implementation

A partial index is a type of index built over a subset of a map; the subset is defined by a conditional expression (called the predicate of the partial index). The index contains entries for only those table rows that satisfy the predicate. A major motivation for partial indexes is to avoid indexing common values. Since a query searching for a common value (one that accounts for more than a few percent of all the map entries) will not use the index anyway, there is no point in keeping those rows in the index at all. This reduces the size of the index, which will speed up queries that do use the index. It will also speed up many write operations (IMap.put, IMap.set etc.) because the index does not need to be updated in all cases. (benchmarks) 1

[Wikipedia] (http://en.wikipedia.org/wiki/Partial_index)

[Postgresql] (http://www.postgresql.org/docs/8.0/static/indexes-partial.html)

[In case you may want to look at some related unit tests] (https://github.com/buremba/hazelcast/blob/index-features/hazelcast/src/test/java/com/hazelcast/query/impl/IndexServiceQueryTest.java)

Since indexes and the actual data already live on memory, indexing is much more different than persistent databases. When users have more than a few indexes and use complex predicates for queries, it becomes more expensive to query the index and merge the results. (See hazelcast/hazelcast#3253) Many users use similar type of queries and partial indexes provides much more better performance for their queries.

Also on a heavy load system, the number of indexes directly affects the performance of IMap.put and IMap.set. Since indexes internally use ConcurrentHashMap and ConcurrentSkipListSet (for SortedIndexStore) adding new entries to these indexes requires some cpu resource (also storage) and partial indexes uses much less storage depending on the predicate of index so they're much more preferable compared to normal indexes.

#New Features

  • Partial Indexes

  • IndexStats implementation in IMap.getLocalMapStats() (I implemented it in this PR because I need it for testing)

##Changes

  • Added predicate attribute to index tag in XMLConfig. Currently it's evaluated as SqlPredicate but we can add support for class reference of predicate that will be used in index.
  • Implemented IndexStats to IMap.getLocalMapStats(). Currently It uses AtomicLongArray for storing usage counts and a ReentrantReadWriteLock for safely replacing AtomicLongArray. I tried to find the best memory-efficient solution, if someone can review IndexStats implementation, I would appreciate it.
  • Created ConnectorPredicate, AttributePredicate interfaces for differentiating predicates.
  • The number of lines in Predicates class exceeded 1.4k with the new changes so I had to move all predicates to com.hazelcast.query.impl.predicate package.
  • Changed the way QueryContext works. Previously it were mapping predicate to index comparing which attribute they use. Now, it lazily plans which predicate will use which index. Predicates usually use QueryPlan.getPlan which returns an instance of QueryContext.QueryPlan.
  • Moved AndResultSet, OrResultSet, MultiResultSet and FilterResultSet to com.hazelcast.query.impl.resultset package.
  • I had to change the way SqlPredicate and PredicateBuilder works. SqlPredicate.createPredicate is a static method that returns a compiled predicate and PredicateBuilder is not longer a Predicate, users must call PredicateBuilder.build method in order to get the actual Predicate instance. I have a question about this change. 1.
  • AndPredicate and OrPredicate constructors changed. Previously it was possible to create an AndPredicate that contains only one predicate; however it doesn't really make sense and and(equal(null, 1)).equals(equal(null, 1)) returns false even though they're actually same predicates.

##Process

When the user adds a new index using IMap.addIndex(attribute, isOrdered, Predicate), the predicate is stored in Index and when Index.saveEntryIndex is called by RecordStore.saveIndex it tests the predicate on the entry and indexes it if passes.

When the user performs a query using IMap.entrySet(Predicate), IMap.keySet(Predicate) or IMap.values(Predicate), IndexService.query creates an instance of QueryContext and calls predicate.filter(queryContext) method. queryContext lazily plans the query when queryContext.getPlan() is called.

The query planner in queryContext simply adds the indexes to a PriorityQueue that can be used for the query and ranks them based on number of same predicates between index predicate and query predicate. Then it tries to find the best plan for the query.

The tricky part in this scenario is comparing the predicates. We need to safely determine whether an index's predicate is a subset of query or not. between("attr1", 1, 10) and between("attr1", 1, 5) is a subset of and(between("attr1", 1, 10), between("attr2", 1, 10)) but they're not a subset of or(between("attr1", 1, 10), between("attr2", 1, 10)). We use ConnectorPredicate.isSubset and Predicate.in for this purpose.

##Questions

  • Partial indexes assumes that the predicate is a condition that filters entries. However PagingPredicate is not a filter predicate so what should we do about it? Should we create an interface called FilterPredicate for other predicates or just throw an exception when user use PagingPredicate for the condition of index?
  • Currently there are two ConnectorPredicate: AndPredicate and OrPredicate. SqlBuilder and PredicateBuilder implements Predicate interface but actually they're just predicate wrappers that contains only one predicate. When a user passes SqlPredicate to a query method, we need to get the actual predicate instance since ConnectorPredicate.subtract needs to compare the classes of predicates in order to perform the operation. I actually spent 2 days in order to find a good solution that doesn't involve such big changes but it's just became more and more complex. They're designed to work with Predicate.apply and IndexAwarePredicate.filter methods but comparing predicates (subset, contains, subtract operations) is much more complex and confusing when they implement Predicate. If you have a good solution that doesn't involve these big changes, I would gladly implement it.

##Future Work

  • Support for destroying indexes.
  • Make LikePredicate, ILikePredicate and RegexPredicate (is it possible?) IndexAwarePredicate.
  • A FieldExtractor for indexes would be great. (can be used for composite keys, custom functions etc.)

I wrote more than 20 tests for index store, index query, index mapconfig and new features of predicates. Still it needs to tested because there are much more use cases of queries.

##Benchmarks

Performing complex queries on indexes vs not indexed map. (3.3-EA2): (source code: https://github.com/ahmetmircik/hazelcast/tree/bench2)


Number of indexes: 0
Map has 600000
600000 items inserted in 53833ms
Indexed predicate count: 3
Query avg time of 10 queries was : 297.8 ms
Max time of 10 queries was : 572.0 ms
Query variance of 10 queries was : 16835.066666666666
Query STD of 10 queries was: 129.75001605651795

Query Time: 0 159 index: null
Indexed predicate count: 8
Query avg time of 10 queries was : 230.0 ms
Max time of 10 queries was : 246.0 ms
Query variance of 10 queries was : 174.88888888888889
Query STD of 10 queries was: 13.224556283251582

Indexed predicate count: 13
Query avg time of 10 queries was : 176.1 ms
Max time of 10 queries was : 195.0 ms
Query variance of 10 queries was : 97.65555555555558
Query STD of 10 queries was: 9.882082551545276

Indexed predicate count: 20
Query avg time of 10 queries was : 179.6 ms
Max time of 10 queries was : 189.0 ms
Query variance of 10 queries was : 64.4888888888889
Query STD of 10 queries was: 8.030497424748289

Indexed predicate count: 25
Query avg time of 10 queries was : 174.5 ms
Max time of 10 queries was : 186.0 ms
Query variance of 10 queries was : 28.5
Query STD of 10 queries was: 5.338539126015656


Number of indexes: 18
Map has 600000
600000 items inserted in 201868ms

Indexed predicate count: 3
Query avg time of 10 queries was : 1873.4 ms
Max time of 10 queries was : 6415.0 ms
Query variance of 10 queries was : 2623203.6
Query STD of 10 queries was: 1619.6306986470713

Indexed predicate count: 8
Query avg time of 10 queries was : 2807.6 ms
Max time of 10 queries was : 2910.0 ms
Query variance of 10 queries was : 3911.8222222222216
Query STD of 10 queries was: 62.54456189168025

Indexed predicate count: 13
Query avg time of 10 queries was : 2333.8 ms
Max time of 10 queries was : 2421.0 ms
Query variance of 10 queries was : 3081.9555555555553
Query STD of 10 queries was: 55.51536323897697

Indexed predicate count: 20
Query avg time of 10 queries was : 2334.1 ms
Max time of 10 queries was : 2403.0 ms
Query variance of 10 queries was : 2365.4333333333334
Query STD of 10 queries was: 48.63572075474294

Indexed predicate count: 25
Query avg time of 10 queries was : 2374.1 ms
Max time of 10 queries was : 2468.0 ms
Query variance of 10 queries was : 4301.211111111111
Query STD of 10 queries was: 65.58361922851705

Using partial index vs normal index:

imap.addIndex("media_id", false, Predicates.notEqual("inactive", false));
insertRandomItems(15000);
Predicate p = Predicates.and(Predicates.between("media_id", 1, 1000), Predicates.notEqual("inactive", false));
imap.values(p);

Map has 600000
600000 items inserted in 47117ms
Indexed predicate count: 2
Query avg time of 10 queries was : 38.1 ms
Max time of 10 queries was : 51.0 ms
Query variance of 10 queries was : 207.2111111111111
Query STD of 10 queries was: 22.53838550655989

imap.addIndex("media_id", false);
insertRandomItems(15000);
Predicate p = Predicates.and(Predicates.between("media_id", 1, 1000), Predicates.notEqual("inactive", false));
imap.values(p);

Map has 600000
600000 items inserted in 60769ms
Indexed predicate count: 2
Query avg time of 10 queries was : 62.1 ms
Max time of 10 queries was : 144.0 ms
Query variance of 10 queries was : 386.7666666666667
Query STD of 10 queries was: 26.934186330221678

Performing complex queries when using partial index vs normal index:

EntryObject eo = new PredicateBuilder().getEntryObject();
PredicateBuilder p0 = eo
        .isNot("disabled_for_upload")
        .and(eo.get("media_id").notEqual(-1))
        .and(eo.get("qc_approval_media_state").notEqual(22))
        .and(eo.get("proxy_creation_state").equal(14))
        .and(eo.get("content_approval_media_state").notEqual(18))
        .and(eo.isNot("inactive"));

eo = new PredicateBuilder().getEntryObject();
PredicateBuilder p1 = eo
        .get("quality_check_state").equal(12)
        .and(eo.get("clock_approval_media_state").notEqual(42))
        .and(eo.get("class_approval_media_state").notEqual(72));

imap.addIndex("quality_check_state", false, p0);
insertRandomItems(15000);
imap.values(Predicates.and(p1, p0));

Map has 600000
600000 items inserted in 61152ms
Query avg time of 10 queries was : 138.1 ms
Max time of 10 queries was : 131.0 ms
Query variance of 10 queries was : 35.0
Query STD of 10 queries was: 22.53838550655989

EntryObject eo = new PredicateBuilder().getEntryObject();
PredicateBuilder p0 = eo
        .isNot("disabled_for_upload")
        .and(eo.get("media_id").notEqual(-1))
        .and(eo.get("qc_approval_media_state").notEqual(22))
        .and(eo.get("proxy_creation_state").equal(14))
        .and(eo.get("content_approval_media_state").notEqual(18))
        .and(eo.isNot("inactive"));

eo = new PredicateBuilder().getEntryObject();
PredicateBuilder p1 = eo
        .get("quality_check_state").equal(12)
        .and(eo.get("clock_approval_media_state").notEqual(42))
        .and(eo.get("class_approval_media_state").notEqual(72));

// searched attributes are indexed
imap.addIndex("disabled_for_upload", false);
imap.addIndex("media_id", false);
imap.addIndex("proxy_creation_state", false);
imap.addIndex("content_approval_media_state", false);
imap.addIndex("inactive", false);
imap.addIndex("quality_check_state", false);
imap.addIndex("clock_approval_media_state", false);
insertRandomItems(15000);
imap.values(Predicates.and(p1, p0));

Map has 600000
600000 items inserted in 90632ms
Query avg time of 10 queries was : 214.1 ms
Max time of 10 queries was : 292.776867676687666 ms
Query variance of 10 queries was : 57.0
Query STD of 10 queries was: 42.35528452352523

Since I'm not really an expert on this area, if someone can review pull request I would appreciate it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment