Improve terms aggregation to perform the segment ordinal to global ordinal lookup post segment collection #5895

martijnvg · 2014-04-22T06:34:41Z

In case when there are not too many unique values it is better to do the segment ordinal to global ordinal lookup after segment results have been processed.

martijnvg · 2014-04-22T07:01:43Z

The initial commit adds an extra execution mode for terms aggregation (global_ordinals_low_cardinality) that performs the segment ordinal to global ordinal lookup post segment collection instead of looking up global ordinals on the fly (during segment collection). On low cardinality fields this basically cuts execution time down by half compared to using the default global_ordinal execution mode. (per hit one lookup takes place instead of two)

martijnvg · 2014-04-23T18:25:24Z

Merged the global_ordinals_low_cardinality execution mode in the GlobalOrdinalsStringTermsAggregator class and pick the post segment global ordinal lookup or on the fly global ordinal lookup based on the number of unique terms to number of unique documents ratio on a per segment basis.

jpountz · 2014-04-25T00:06:03Z

.../org/elasticsearch/search/aggregations/bucket/terms/GlobalOrdinalsStringTermsAggregator.java

+            // Ideally we want to know the amount of docs that are going to match... we don't know because the
+            // the aggs are executed with the main query and even if we knew for nested aggs it is even harder
+            // to know the the matching docs.
+            double postGlobalOrdinalResolvingRatio = segmentOrdinals.getNumOrds() / segmentOrdinals.getNumDocs(); // maybe multiple numDocs with a factor?


I think getNumOrds needs to be casted to a double?

jpountz · 2014-04-25T00:11:57Z

I'm concerned that this change conflicts a bit with #5873. For example, if you have a segment where ordinals are already global, #5873 would use them directly and this would be optimal.

On the other hand, this change would collect them into a separate structure and merge it with the global counts when the collection of the segment is terminated. Can we not collect into a different structure when ordinals are already global? (not sure how to detect it cleanly)

jpountz · 2014-04-25T00:14:34Z

Moreover, I liked better when this execution mode was in its own class since it might have different runtime properties (especially memory usage)?

jpountz · 2014-04-25T00:16:07Z

.../org/elasticsearch/search/aggregations/bucket/terms/GlobalOrdinalsStringTermsAggregator.java

+            // the aggs are executed with the main query and even if we knew for nested aggs it is even harder
+            // to know the the matching docs.
+            double postGlobalOrdinalResolvingRatio = segmentOrdinals.getNumOrds() / segmentOrdinals.getNumDocs(); // maybe multiple numDocs with a factor?
+            if (postGlobalOrdinalResolvingRatio <= 0.9) { // TODO: make configurable


0.9 looks high given that it is supposed to be used on low-cardinality fields?

I'm also wondering if we should apply this strategy if any of the segments matches this criterion. This way we wouldn't need the f (segmentDocCounts != null) condition in collect anymore?

I agree that 0.9 is on the high side as well. I was playing around with this threshold and I did see a small improvement even for high cardinality fields, but for those fields the additional memory usage caused by segmentCounts should also be taken into account, so we must set this to a lower value

martijnvg · 2014-04-25T04:28:20Z

Initially I put this enhancement into a different execution hint and I moved it into global_ordinals hint for the following reasons:

I would have ended up with two more execution modes: global_ordinals_low_cardinality and global_ordinals_low_cardinalty_hash and I don't like that too much.
The most important reason for me is that during parsing automatically selecting the right impl seems more difficult (in TermsAggregatorFactory). For example I think that valuesSource.metaData().maxAtomicUniqueValuesCount() is too rough. In the setNextReader() method in the aggregator we have more fine grained statistics (from Ordinals.Docs and Scorer), that can make a better decision what should be used.

So maybe we should be more conservative when using this post segment collection global ordinal resolving to be sure that segmentCounts bigarray isn't taking too much memory. We can lower the threshold to 0.5 and include an upper bound of unique values (this what determines the memory cost of segmentCounts) from where we fallback to on the fly global ordinal resolving.

update: We can in the TermsAggregatorFactory iterate over all atomic readers and fetch the Ordinals.Docs to figure out what strategy is better? In that case I'm ok with putting this in post segment collection global ordinals lookup in a different strategy.

On the other hand, this change would collect them into a separate structure and merge it with the global counts when the collection of the segment is terminated. Can we not collect into a different structure when ordinals are already global? (not sure how to detect it cleanly)

I think this can be detected. If the globalOrdinals field is on instance GlobalOrdinalMapping then we can fallback to normal collection (setting segmentCounts to null). This enhancement must work together with the #5873 optimization.

jpountz · 2014-04-25T10:24:02Z

I tried to think more about when to use this execution mode:

it can only be used on leaf aggregators,
if you are currently doing a terms under terms aggregation, we currently use the global_ordinals_hash mode in order to not allocate memory for every possible bucket. But if we start doing the same with this execution mode, the LongHash is probably going to kill the speedup that we gained from collecting segment ordinals.

So in the end, it looks to me like this new execution mode would be safe/useful on single-level terms aggregations? (which might still be quite common)

update: We can in the TermsAggregatorFactory iterate over all atomic readers and fetch the Ordinals.Docs to figure out what strategy is better?

+1

I think this can be detected. If the globalOrdinals field is on instance GlobalOrdinalMapping

I tend to dislike instanceof checks since it tends to be fragile. For example, if we get a second class impl that exposes global ordinals, this will break. :(

Use segment maxOrd and global maxOrd to detected if global ordinals lookup needs to be performed

martijnvg · 2014-04-25T17:49:25Z

Updated the PR to have a dedicated global_ordinals_low_cardinality implementation instead merging this enhancement into global_ordinals implementation.

I tend to dislike instanceof checks since it tends to be fragile. For example, if we get a second class impl that exposes global ordinals, this will break. :(

I replaced that with if (globalOrdinals.maxOrd() != segmentOrdinals.maxOrd()).

jpountz · 2014-04-25T19:46:19Z

.../org/elasticsearch/search/aggregations/bucket/terms/GlobalOrdinalsStringTermsAggregator.java

+                mapSegmentCountsToGlobalCounts();
+                Releasables.close(segmentDocCounts);
+                segmentDocCounts = null;
+            }


Should it be done in postCollect instead?

…Collect Compute maxOrd in factory if global ordinals is going to be used. Use maxOrd to pick GLOBAL_ORDINALS or GLOBAL_ORDINALS_LOW_CARDINALITY For GLOBAL_ORDINALS and GLOBAL_ORDINALS_LOW_CARDINALITY use maxOrd as bucket count

martijnvg · 2014-04-27T13:16:27Z

Thanks for reviewing this @jpountz! I Updated PR with the following changes:

Moved mapSegmentCountsToGlobalCounts() check for last segment to postCollect
segmentOrdinals in GLOBAL_ORDINALS_LOW_CARDINALITY impl instantiated with maxOrd.
Compute maxOrd in TermsAggregatorFactory if global ordinals is going to be used.
Use maxOrd to pick GLOBAL_ORDINALS or GLOBAL_ORDINALS_LOW_CARDINALITY
For GLOBAL_ORDINALS and GLOBAL_ORDINALS_LOW_CARDINALITY use maxOrd as estimated bucket count

jpountz · 2014-04-27T20:55:29Z

src/main/java/org/elasticsearch/search/aggregations/support/ValuesSource.java

@@ -159,6 +161,8 @@ public void setNeedsGlobalOrdinals(boolean needsGlobalOrdinals) {}

            public abstract BytesValues.WithOrdinals globalBytesValues();

+            public abstract long maxOrd(IndexSearcher indexSearcher);


Should it be called globalMaxOrd?

Yes, it should, I'll change that.

jpountz · 2014-04-27T21:02:49Z

LGTM

…dinality fields. Instead of resolving the global ordinal for each hit on the fly, resolve the global ordinals during post collect. On fields with not so many unique values, that can reduce the number of global ordinals significantly. Closes #5895 Closes #5854

martijnvg changed the title ~~Perform the segment ordinal to global ordinal lookup post segment collection~~ Improve terms aggregation to perform the segment ordinal to global ordinal lookup post segment collection Apr 22, 2014

jpountz reviewed Apr 25, 2014
View reviewed changes

martijnvg added 2 commits April 26, 2014 00:12

Initial version of resolving global ordinals post segment collection.

f453762

Reverted back the dedicated low cardinality global ordinals terms aggs.

3854bf4

Use segment maxOrd and global maxOrd to detected if global ordinals lookup needs to be performed

martijnvg added v2.0.0 labels Apr 25, 2014

jpountz reviewed Apr 25, 2014
View reviewed changes

jpountz reviewed Apr 27, 2014
View reviewed changes

martijnvg closed this in f3219f7 Apr 29, 2014

clintongormley added the :Analytics/Aggregations Aggregations label Jun 7, 2015

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve terms aggregation to perform the segment ordinal to global ordinal lookup post segment collection #5895

Improve terms aggregation to perform the segment ordinal to global ordinal lookup post segment collection #5895

martijnvg commented Apr 22, 2014

martijnvg commented Apr 22, 2014

martijnvg commented Apr 23, 2014

jpountz Apr 25, 2014

jpountz commented Apr 25, 2014

jpountz commented Apr 25, 2014

jpountz Apr 25, 2014

jpountz Apr 25, 2014

martijnvg Apr 25, 2014

martijnvg commented Apr 25, 2014

jpountz commented Apr 25, 2014

martijnvg commented Apr 25, 2014

jpountz Apr 25, 2014

martijnvg commented Apr 27, 2014

jpountz Apr 27, 2014

martijnvg Apr 28, 2014

jpountz commented Apr 27, 2014

		@@ -159,6 +161,8 @@ public void setNeedsGlobalOrdinals(boolean needsGlobalOrdinals) {}

		public abstract BytesValues.WithOrdinals globalBytesValues();

		public abstract long maxOrd(IndexSearcher indexSearcher);

Improve terms aggregation to perform the segment ordinal to global ordinal lookup post segment collection #5895

Improve terms aggregation to perform the segment ordinal to global ordinal lookup post segment collection #5895

Conversation

martijnvg commented Apr 22, 2014

martijnvg commented Apr 22, 2014

martijnvg commented Apr 23, 2014

jpountz Apr 25, 2014

Choose a reason for hiding this comment

jpountz commented Apr 25, 2014

jpountz commented Apr 25, 2014

jpountz Apr 25, 2014

Choose a reason for hiding this comment

jpountz Apr 25, 2014

Choose a reason for hiding this comment

martijnvg Apr 25, 2014

Choose a reason for hiding this comment

martijnvg commented Apr 25, 2014

jpountz commented Apr 25, 2014

martijnvg commented Apr 25, 2014

jpountz Apr 25, 2014

Choose a reason for hiding this comment

martijnvg commented Apr 27, 2014

jpountz Apr 27, 2014

Choose a reason for hiding this comment

martijnvg Apr 28, 2014

Choose a reason for hiding this comment

jpountz commented Apr 27, 2014