Bulk operations for LongValues and Sorted[Set]DocValues [LUCENE-8178]

[asfimport]

One-by-one DocValues iteration by advanceExact and nextOrd/ordValue is really slow for bulk operations like facetting. Reading and unpacking integers in blocks is substantially faster but DocValues for now can be queried only for single document.

To apply document-based bulk processing DocIdSetIterator matches have to be splitted to sequential docID runs and remapped to underlying LongValues positions.
After this transformation relatively large linear scans can be performed over packed integers.

 

To do this two new interfaces

1. LongValuesCollector (collectValue(long index, long value)).
2. OrdStatsCollector (collectOrd(long ord), collectMissing(int count)).

and three new functions are introduced

1. LongValues.forRange(long begin, long end, LongValuesCollector collector)
2. SortedDocValues.forEach(DocIdSetIterator disi, OrdStatsConsumer collector)
3. SortedSetDocValues.forEach(DocIdSetIterator disi, OrdStatsConsumer collector)

with reference implementations.

Optimized versions of these functions are provided for:

1. DirectReader for non-32/64 bits per value cases (using PackedInts.Decoder).
2. Lucene70DocValuesProducer getSorted and getSortedSet (both sparse and dense).

 

Measured Solr facetting performance boost is up to 2 - 2.5x on real index.
Patch for Solr DocValuesFacets is also provided as separate file.

 

Implementation notes:

• OrdStatsCollector does not accept document id because it will ruin performance for SortedSetDocValues due to excessive position lookups.
• This patch is fully compatible with Lucene 7.0 DocValues format.

---

Migrated from LUCENE-8178 by Nikolay Khitrin (@khitrin), 2 votes, updated Feb 20 2018
Attachments: graph.png, LUCENE-8178.patch, LUCENE-8178-for-solr.patch

[asfimport]

Adrien Grand (@jpountz) (migrated from JIRA)

I understand how it can make things faster, but I'm a bit on the fence due to how specialized it is (it seems to focus on faceting on MatchAllDocsQuery on an index with not too many deletions) vs. the number of additional APIs.

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

I agree, I think decode done in bulk shouldn't be an api detail. it should be just like the postings lists.

[asfimport]

Nikolay Khitrin (@khitrin) (migrated from JIRA)

@jpountz, yes, I've mainly tested it on matchall case and non-random queries (like date ranges) and after your point I've performed small stress test for different random samplings using `RandomSortField` from Solr (image attached: not quite accurate, warmup excluded, several low-time points below main clouds seems to be ramp-up phase – quasi single thread time). Unfortunately, there is a regression on less-than-half random portions of document set.

I will try to find a way to reduce this penalty for random cuts (like many deletions).

@rmuir, I didn't found suitable API for terminal operations involving DocValues (sorting, top-n selection, faceting, etc – when query phase is done and no filtering will be performed on DISI), so I have a timid idea about it.