Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Coherence SIG: Advanced usage of indexes

aragozin
November 08, 2011

Coherence SIG: Advanced usage of indexes

Slidedeck from presentation at Oracle Coherence SIG,London 4 Nov 2011

aragozin

November 08, 2011
Tweet

More Decks by aragozin

Other Decks in Technology

Transcript

  1. Presentation overview • Structure of Coherence index • How IndexAwareFilter

    works • Multiple indexes in same query • Custom index provider API (since 3.6) • Embedding Apache Lucene into data grid
  2. Creation of index QueryMap.addIndex( ValueExtractor extractor, boolean ordered, Comparator comparator)

    Attribute extractor, used to identify index later Index configuration
  3. Using of query API public interface QueryMap extends Map {

    Set keySet(Filter f); Set entrySet(Filter f); Set entrySet(Filter f, Comparator c); ... } public interface InvocableMap extends Map { Map invokeAll(Filter f, EntryProcessor agent); Object aggregate(Filter f, EntryAggregator agent); ... }
  4. Indexes at storage node extractor index extractor index extractor index

    Indexes Backing map Named cache backend SimpleMapIndex Reverse map Forward map val key key key key val key key val key key key val key val key val
  5. Indexes at storage node • All indexes created on cache

    are stored in map • Reverse map is used to speed up filters • Forward map is used to speed up aggregators Custom extractors should obey equals/hashCode contract! QueryMap.Entry.extract(…) is using index, if available
  6. Indexes at storage node  Index structures are stored in

    heap • and may consume a lot of memory  For partitioned scheme • keys in index are binary blobs, • regular object, otherwise  Indexes will keep your key in heap even if you use off heap backing map  Single index for all primary partitions of cache on single node
  7. How filters use indexes? interface IndexAwareFilter extends EntryFilter { int

    calculateEffectiveness(Map im, Set keys); Filter applyIndex(Map im, Set keys); } • applyIndex(…) is called by cache service on top level filter • calculateEffectiveness(…) may be called by compound filter on nested filters • each node executes index individually • For complex queries execution plan is calculated ad hoc, each compound filter calculates plan for nested filters
  8. Example: equalsFilter Filter execution (call to applyIndex() )  Lookup

    for matching index using extractor instance as key  If index found,  lookup index reverse map for value  intersect provided candidate set with key set from reverse map  return null – candidate set is accurate, no object filtering required  else (no index found)  return this – all entries from candidate set should be deserialized and evaluated by filter
  9. Multiple indexes in same query Example: ticker=IBM & side=B new

    AndFilter( new EqualsFilter(“getTicker”, “IBM”), new EqualsFilter(“getSide”, „B‟)) Execution plan • call applyIndex(…) on first nested filter – only entries with ticker IBM are retained in candidate set • call applyIndex(…) on second nested filter – only entries with side=B are retained in candidate set • return candidate set
  10. Index performance PROs • using of inverted index • no

    deserialization overhead CONs • very simplistic cost model in index planner • candidate set is stored in hash tables (intersections/unions may be expensive) • high cardinality attributes may cause problems
  11. Compound indexes Example: ticker=IBM & side=B  Index per attribute

    new AndFilter( new EqualsFilter(“getTicker”, “IBM”), new EqualsFilter(“getSide”, „B‟))  Index for compound attribute new EqualsFilter( new MultiExtractor(“getTicker, getSide”), Arrays.asList(new Object[]{“IBM”, „B‟})) For index to be used, filter’s extractor should match extractor used to create index!
  12. Ordered indexes vs. unordered 19.23 1.63 1.37 0.61 0.72 1.19

    0.1 1 10 100 Term count = 100k Term count = 10k Term count = 2k Filter execution time (ms) Unordered Ordered
  13. Custom indexes since 3.6 interface IndexAwareExtractor extends ValueExtractor { MapIndex

    createIndex( boolean ordered, Comparator comparator, Map indexMap, BackingMapContext bmc); MapIndex destroyIndex(Map indexMap); }
  14. Ingredients of customs index • Custom index extractor • Custom

    index class (extends MapIndex) • Custom filter, aware of custom index + • Thread safe implementation • Handle both binary and object keys gracefully • Efficient insert (index is updates synchronously)
  15. Why custom indexes? Custom index implementation is free to use

    any advanced data structure tailored for specific queries. • NGram index – fast substring based lookup • Apache Lucene index – full text search • Time series index – managing versioned data
  16. Using Apache Lucene in grid Why? • Full text search

    / rich queries • Zero index maintenance PROs • Index partitioning by Coherence • Faster execution of many complex queries CONs • Slower updates • Text centric
  17. Lucene example Step 1. Create document extractor // First, we

    need to define how our object will map // to field in Lucene document LuceneDocumentExtractor extractor = new LuceneDocumentExtractor(); extractor.addText("title", new ReflectionExtractor("getTitle")); extractor.addText("author", new ReflectionExtractor("getAuthor")); extractor.addText("content", new ReflectionExtractor("getContent")); extractor.addText("tags", new ReflectionExtractor("getSearchableTags")); Step 2. Create index on cache // next create LuceneSearchFactory helper class LuceneSearchFactory searchFactory = new LuceneSearchFactory(extractor); // initialize index for cache, this operation actually tells coherence // to create index structures on all storage enabled nodes searchFactory.createIndex(cache);
  18. Lucene example Now you can use Lucene queries // now

    index is ready and we can search Coherence cache // using Lucene queries PhraseQuery pq = new PhraseQuery(); pq.add(new Term("content", "Coherence")); pq.add(new Term("content", "search")); // Lucene filter is converted to Coherence filter // by search factory cache.keySet(searchFactory.createFilter(pq));
  19. Lucene example You can even combine it with normal filters

    // You can also combine normal Coherence filters // with Lucene queries long startDate = System.currentTimeMillis() - 1000 * 60 * 60 * 24; // last day long endDate = System.currentTimeMillis(); BetweenFilter dateFilter = new BetweenFilter("getDateTime", startDate, endDate); Filter pqFilter = searchFactory.createFilter(pq); // Now we are selecting objects by Lucene query and apply // standard Coherence filter over Lucene result set cache.keySet(new AndFilter(pqFilter, dateFilter));
  20. Lucene search performance 0.72 0.71 1.10 1.09 3.30 1.80 1.16

    1.18 4.38 4.39 1.93 1.96 2.38 2.38 0.67 7.23 1.49 7.77 8.81 8.75 1.53 8.66 15.96 15.96 11.15 11.12 52.59 8.74 0.5 5 50 A1=x & E1=y E1=x & A1=y D1=x & E1=y E1=x & D1=y E1=x & E2=y E1=x & E2=Y & E3=z D1=w & E1=x & E2=Y & E3=z E1=x & E2=Y & E3=z & D1=w A2 in [n..m] & E1=x & E2=Y & E3=z E1=x & E2=Y & E3=z & A2 in [n..m] D1 in *v1…, v10+ & E1=x & E2=Y & E3=z E1=x & E2=Y & E3=z & D1 in *v1…, v10+ H1=a & E1=x & E2=Y & E3=z E1=x & E2=Y & E3=z & H1=a Filter execution time (ms) Lucene Coherence
  21. Time series index Special index for managing versioned data Getting

    last version for series k select * from versions where series=k and version = (select max(version) from versions where key=k) Series key Entry id Timestamp Payload Entry key Entry value Cache entry
  22. Time series index Series inverted index Series key Series key

    Series key Series key Series key HASHTABLE Timestamp Entry ref Timestamp Entry ref Timestamp Entry ref Timestamp inverted subindex ORDER