@stefanvodita / @jpountz - Would love to get your thoughts on this optimization, and how we can leverage it in Lucene. In a nutshell, it solves the below problem:

Given a sorted non-overlapping set of intervals (Histogram buckets could be an example), it collects the matching documents count in single travel of PointsTree index, by skipping over the leafBlocks completely unless the values in leafBlock overlap with more than one interval. This ensures that the # leafBlocks actually traversed is bounded by the # buckets and remaining leafBlocks are collected in bulk. Hence it can very efficiently collect the doc counts, especially when the # documents / # buckets is pretty high.

Sorry, I only had a quick look. Is the opimisation here analogous to the one HistogramLeafCollector does with the skipper?

No, this approach is different from the skipper as it leverages PointValues instead of DocValues for computing the buckets

I didn't mean to imply that the two solutions are the same, apologies if that's how it came across.

Need some inputs from the community on how it can be plugged correctly into the HistogramCollector

Let me know if this doesn't answer the question @jainankitk, maybe you'd already gone through this and you were looking for a different answer.
I think you could start in HistogramCollector.getLeafCollector (code). Right now we throw an exception if the field we're using isn't doc values (code). You'd need a new branch for the case you want to implement and a new LeafCollector, similar to the ones already in the file. Having that would make it easier to think through the next steps.

At a higher level, I'm curious if you had a use-case in mind.

I didn't mean to imply that the two solutions are the same, apologies if that's how it came across.

Not at all. Even I was initially confused with skipper logic, only after spending some time realized this approach is slightly different. So, thanks for reiterating the question.

I think you could start in HistogramCollector.getLeafCollector (code). Right now we throw an exception if the field we're using isn't doc values (code).

Currently, Collector doesn't need to be aware of the Query itself. They are designed to collect individual docId or using DocIdStream from the scorer. But this CustomCollector, does not need the scorer to provide documents, but can BulkCollect documents, assuming MATCH_ALL or PointRangeQuery (where PointRangeQuery.field == histogram.field). Otherwise, it should fallback to traditional methods for collecting matching documents.

At a higher level, I'm curious if you had a use-case in mind.

This optimization can be applied to following use cases:

• Number of sale based on the price range (0-50, 50-100, 100-250,.....)
• Number of visits on website for each day in a month

Just as a data point, this change helped us improve date histogram latency from 5168 ms to 160 ms (~32x!!) for big5 workload in OpenSearch

I have updated the PR, and the code flow is like below now:

• HistogramCollector overrides the setWeight for accessing the underlying Query
• To keep things simple, just optimizing for MATCH_ALL_DOCS query and no deleted documents for now
• Optimized path is enabled only if pointTree is built for the field
• There are few other conditions for optimized path being enabled. Being conservative for now, and fallback to original.
• Add small unit test to verify working as expected

Will add few more unit tests, once I get some feedback on the code changes. Can also include small performance unit test that demonstrates, pointTree based collection is faster than the docValues based collector.

Interesting idea! I like that you integrated it transparently into the collector, so that users can benefit from it out of the box.

Thanks @jpountz for the review. Had some challenges with the integration initially, but seWeight method was pretty useful!

This is a nice optimization, using points (if the user indexed them) to carefully optimize counting of ranges.

@stefanvodita - Thanks for a prompt review. Addressed most of the review comments. Adding JMH benchmark instead of the not so useful performance test added earlier. The benchark results demonstrate significant increase in throughput with increasing # documents and bucket width (lesser buckets mean less low level traversal in point range tree and more documents collected in bulk):

Oooh those JMH benchy results are nice! Though, it's dangerous testing only on random data -- you can draw random conclusions/results. But it's better than no benchmark! Maybe we should add histogram faceting benchy to Lucene's nightly benchmarks?

Oooh those JMH benchy results are nice! Though, it's dangerous testing only on random data -- you can draw random conclusions/results. But it's better than no benchmark! Maybe we should add histogram faceting benchy to Lucene's nightly benchmarks?

Thanks @mikemccand for the feedback. Having histogram faceting benchmark in Lucene's nightly will be great! Created issue mikemccand/luceneutil#375 for following up on this.