You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "zihanx (via GitHub)" <gi...@apache.org> on 2026/03/31 23:30:18 UTC
[I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
zihanx opened a new issue, #15905:
URL: https://github.com/apache/lucene/issues/15905
## Description:
Following up on the recently merged ReaderUtil.partitionByLeaf API (https://github.com/apache/lucene/pull/15507), we're planning a second task to build a generic utility class for efficiently retrieving doc-values for an int[] of global doc IDs.
The doc-values retriever would:
- Take an `IndexReader`, `int[] globalDocIds`, and `DoubleValuesSource[]` (or abstract LeafVisitor factory)
- Take an Executor/TaskExecutor for concurrent per-leaf retrieval
- Return values in 1:1 correspondence with the input doc ID order
This requires a scatter/gather pattern:
- Scatter: Partition global doc IDs by leaf (using `partitionByLeaf`)
- Map: Retrieve doc-values per leaf (concurrent)
- Gather: Reassemble results back to original input order
The current `partitionByLeaf(ScoreDoc[], leaves)` API doesn't track original positions, so we can't reassemble results in input order. We need ordinal tracking.
## Design options:
1. Two separate APIs (current prototype):
```
// Existing - no ordinals (for callers who don't need gather and only take in ScoreDoc[])
public static int[][] partitionByLeaf(ScoreDoc[] hits, List<LeafReaderContext> leaves)
// New - with ordinals for scatter/gather
public record PartitionedHits(int[][] docIdsByLeaf, int[] ordinals) {}
public static PartitionedHits partitionByLeafWithOrdinals(int[] globalDocIds, List<LeafReaderContext> leaves)
// Private - helper method for duplicate partition logic
private static int[][] partitionSortedDocIds(int[] sortedDocIds, List<LeafReaderContext> leaves)
```
Pros: Clear intent, no wasted compute, type-safe
Cons: Two entry points
2. Single API with boolean flag:
```
public record PartitionedHits(int[][] docIdsByLeaf, int[] ordinals) {}
public static PartitionedHits partitionByLeaf(..., boolean includeOrdinals)
```
Pros: Single entry point
Cons: ordinals is null when not requested, still need to handle different input types (ScoreDoc[] vs int[])
3. Always return ordinals:
```
public static PartitionedHits partitionByLeaf(int[] globalDocIds, List<LeafReaderContext> leaves)
```
Pros: Simplest API
Cons: Wastes compute for callers who don't need ordinals
## Questions for the community:
1. Should we add an `int[]` input method? The merged PR only has `ScoreDoc[]` input
([last PR comment](https://github.com/apache/lucene/pull/15803#discussion_r2960596460)), but the scatter/gather use case needs raw doc IDs.
2. Which API design is preferred for ordinal tracking? Or any better ideas?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "zihanx (via GitHub)" <gi...@apache.org>.
zihanx commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-4185424929
Thanks @gsmiller for the feedback and the benchmark! Really appreciate your help!
To answer your questions:
1. `ScoreDoc[] v.s. int[]`: For the doc-retriever use case, the API should be a generic class that takes `int[] globalDocIds` as input not `ScoreDoc[]`. @mikemccand originally described the retriever class as:
> A generic (reusable to open source) utility class to retrieve doc-values (DoubleValuesSource) for an int[] of global docids to return. API could be simple-ish, taking an open IndexReader, the int[] globalHits, and maybe DoubleValuesSource[]... Or, so other things (stored fields maybe) are supported, the API could be a bit more abstract, and caller passes in some sort of LeafVisitor factory lambda-a-jigger thingy
@mikemccand can you please help confirm this is the intended design? If so, even with Option 3, we'd still need two APIs (one for `ScoreDoc[]`, one for `int[]`), which is essentially Option 1 (or we could say even worse because option 1 would not introduce overhead).
2. Overhead: Agree, the overhead might be noise compare to other work being done.
I think right now the problem we need to solve is what input type does the ordinal-tracking API need?
Our current state only has one api: `partitionByLeaf(ScoreDoc[], leaves) → int[][]`, we still need to decide `ScoreDoc[]`/`int[]` input.
If we need `int[]` as the input for retriever class, I'm leaning towards option 1, which seems cleanest: two APIs with different input types and different return types based on use case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "zihanx (via GitHub)" <gi...@apache.org>.
zihanx commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-5298258736
Closing this out. The API landed in #16496 (merged to `main`).
**Outcome:** `ReaderUtil.partitionByLeaf(int[], leaves)` now returns a `PartitionedHits(int[][] docIdsByLeaf, int[][] ordinalsByLeaf)` record. The per-leaf ordinals record each doc ID's original position in the input array. Only one API is needed.
**Design result:**
- Took `int[]` instead of `ScoreDoc[]`.
- Consolidated to a single API rather than separate with/without-ordinals methods. A JMH benchmark showed ordinal tracking is essentially free, thanks to a packed-long sort: each `(docId, ordinal)` is packed into a `long` (docId high 32 bits, ordinal low 32) and sorted with the primitive `Arrays.sort(long[])`. Callers that don't need ordinals just ignore `ordinalsByLeaf()`.
Thanks @gsmiller for the design input and review!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "zihanx (via GitHub)" <gi...@apache.org>.
zihanx closed issue #15905: ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern
URL: https://github.com/apache/lucene/issues/15905
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "zihanx (via GitHub)" <gi...@apache.org>.
zihanx commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-5222461356
Thanks for the feedback, @gsmiller !
I've opened #16496 with the `partitionByLeaf` redesign and the new `partitionByLeafWithOrdinals` variant. It's scoped to just the ReaderUtil API + tests. We will follow up the doc-values retriever that motivates the ordinals in a separate PR. Would appreciate a review when you have a chance. Thanks again!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-5209454058
Sorry for the long delay. I was away for a few months. I think this all sounds reasonable. I think I'm still slightly partial to a single API that includes the ordinals since I suspect the additional cost of tracking the ordinals probably isn't huge in an overall system, but at the same time, I acknowledge the desire to optimize where possible. So I think it's a fair approach to have the two APIs. We probably want to position them (via their javadoc) as one providing a subset of the functionality but being optimized for situations where the caller doesn't care about the ordinals? Look forward to seeing the PR!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-4183884261
I have a few thoughts but I'm more curious what others think. As a disclaimer I work with Zihan on Amazon's product search, but I'm not particularly close to this project (so I'll probably ask silly questions) :)
1. Between the first two options, I think two separate methods is the way to go (option 1). Adding a boolean to control behavior (option 2) has a bit of a bad smell IMO.
2. Is there a reason you want the newly-proposed `partitionByLeafWithOrdinals` method to take `int[]` instead of `ScoreDoc[]` as input (in option 1)? There's a bit of asymmetry that might be worth fleshing out. It feels like these two methods are conflating whether-or-not the caller has ScoreDoc[] or int[] as input _and_ whether-or-not they need "ordinal tracking." This sort of carries into option 3 too. If you went with that approach, would you use ScoreDoc[] as input (as the current API does), or would you need to change it to int[]?
3. Would option 3 be as simple as leveraging [IntroSorter](https://github.com/apache/lucene/blob/0fcf9c825f1f76588040f592d7f893899cc715cd/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java#L39) to sort the docIDs and ordinals as parallel arrays [1]? I wonder how much overhead it would actually introduce to do this over the current Arrays#sort approach. I kind of think we should try this first and see if it actually results in a meaningful performance difference. So I think I'm in favor of starting with option 3. If there really is a meaningful performance impact, I'd be in favor of option 1 (but sorting out the discussion of ScoreDoc[] vs. int[] as input).
[1] Something like...
```
new IntroSorter() {
int pivot;
@Override
protected int compare(int i, int j) {
return Integer.compare(sortedDocIds[i], sortedDocIds[j]);
}
@Override
protected void swap(int i, int j) {
int tmp = sortedDocIds[i];
sortedDocIds[i] = sortedDocIds[j];
sortedDocIds[j] = tmp;
tmp = ordinals[i];
ordinals[i] = ordinals[j];
ordinals[j] = tmp;
}
@Override
protected void setPivot(int i) {
pivot = sortedDocIds[i];
}
@Override
protected int comparePivot(int j) {
return Integer.compare(pivot, sortedDocIds[j]);
}
}.sort(0, sortedDocIds.length);
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-4185954654
With-respect-to `ScoreDoc[]` vs. `int[]`, I agree with what you're saying about Option 1 vs. Option 3. Ultimately, I'm slightly concerned we're going to end up with four methods proposed by the end of this that model the different combinations of ScoreDoc[] and int[] as input across ordinals or no-ordinals :). Maybe it was a mistake to move from int[] to ScoreDoc[] in the previous API design. If int[] really is the more generic version of this, maybe the right thing is to ask callers to deal with translating their ScoreDoc[] to int[]. I think the earlier premise was that the common use-case was for callers to have ScoreDoc[], so it made sense to not expect them to translate. But stepping back a little, maybe we should consider this decision separately?
Just to make things complicated though (sorry!), did you consider an alternative approach that would just return ordinals as int[][]? So instead of sorting the actual ScoreDoc[] or int[] input, we'd provide ordinal references back into the original data. Maybe an example would be easier:
```
ScoreDoc[] hits = {new ScoreDoc(42, ..), new ScoreDoc(7, ..), new ScoreDoc(100, ..), new ScoreDoc(23, ..)};
int[][] ordinalsByLeaf = ReaderUtil.partitionByLeaf(hits, leaves);
// Suppose leaf 0 covers docs 0-49, leaf 1 covers docs 50-99, leaf 2 covers 100+
// ordinalsByLeaf[0] = {1, 3, 0} → hits[1]=doc7, hits[3]=doc23, hits[0]=doc42 (sorted within leaf)
// ordinalsByLeaf[1] = {}
// ordinalsByLeaf[2] = {2} → hits[2]=doc100
```
So this handles both the current use-case and the scatter-gather use-case I think in a single method? (Different topic on whether-or-not you need two versions for accepting ScoreDoc[] vs. accepting int[]). I think this will still underperform similarly as Option 3 based on the benchmarking I did earlier though. You still couldn't use Arrays#sort directly; you'd need need something like IntroSorter, and sorting would have to do two array dereferences to access each element for comparison (i.e., `hits[ordinalsByLeaf[i]]`). But maybe it avoids some data copying? It might be worth adding to the jmh benchmark I created just to see...
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-4184071194
Hmm... actually option 3 might be worse than I thought. I put together a micro-benchmark (#15933) and keeping track of the parallel ordinal array adds quite a bit of overhead. Here's the raw output of the benchmark:
```
Benchmark (numDocIds) (numLeaves) Mode Cnt Score Error Units
PartitionByLeafBenchmark.arraysSortOnly 100 5 thrpt 15 1213.898 ± 23.702 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 100 50 thrpt 15 1146.033 ± 30.084 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 100 200 thrpt 15 849.219 ± 10.757 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 1000 5 thrpt 15 84.469 ± 0.637 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 1000 50 thrpt 15 65.685 ± 3.071 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 1000 200 thrpt 15 88.932 ± 5.194 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 10000 5 thrpt 15 5.031 ± 0.394 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 10000 50 thrpt 15 5.562 ± 0.467 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 10000 200 thrpt 15 5.691 ± 0.560 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 100000 5 thrpt 15 0.265 ± 0.008 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 100000 50 thrpt 15 0.265 ± 0.007 ops/ms
PartitionByLeafBenchmark.arraysSortOnly 100000 200 thrpt 15 0.265 ± 0.007 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 100 5 thrpt 15 911.904 ± 31.288 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 100 50 thrpt 15 866.220 ± 22.404 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 100 200 thrpt 15 690.300 ± 17.029 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 1000 5 thrpt 15 63.449 ± 3.054 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 1000 50 thrpt 15 64.223 ± 2.953 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 1000 200 thrpt 15 69.654 ± 0.704 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 10000 5 thrpt 15 3.443 ± 0.234 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 10000 50 thrpt 15 3.471 ± 0.283 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 10000 200 thrpt 15 3.200 ± 0.322 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 100000 5 thrpt 15 0.174 ± 0.006 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 100000 50 thrpt 15 0.174 ± 0.005 ops/ms
PartitionByLeafBenchmark.introSortWithOrdinals 100000 200 thrpt 15 0.166 ± 0.011 ops/ms
```
And a summary of the results:
| numDocIds | numLeaves | Arrays.sort (ops/ms) | IntroSorter+ordinals (ops/ms) | Overhead |
|-----------|-----------|---------------------|-------------------------------|----------|
| 100 | 5 | 1214 | 912 | ~25% |
| 100 | 50 | 1146 | 866 | ~24% |
| 100 | 200 | 849 | 690 | ~19% |
| 1,000 | 5 | 84 | 63 | ~25% |
| 1,000 | 50 | 66 | 64 | ~3% |
| 1,000 | 200 | 89 | 70 | ~22% |
| 10,000 | 5 | 5.0 | 3.4 | ~32% |
| 10,000 | 50 | 5.6 | 3.5 | ~38% |
| 10,000 | 200 | 5.7 | 3.2 | ~44% |
| 100,000 | 5 | 0.265 | 0.174 | ~34% |
| 100,000 | 50 | 0.265 | 0.174 | ~34% |
| 100,000 | 200 | 0.265 | 0.166 | ~37% |
That said... I wonder how much we'd care about this in practice? This operation would probably be done once in the handling of a given search, and I suspect the difference in performance here would really show up in a meaningful way relative to the other work being done. But maybe I'm wrong? I dunno. WDYT?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [I] ReaderUtil.partitionByLeaf API design: ordinal tracking for scatter/gather pattern [lucene]
Posted by "zihanx (via GitHub)" <gi...@apache.org>.
zihanx commented on issue #15905:
URL: https://github.com/apache/lucene/issues/15905#issuecomment-4464273677
Sorry for the long delay circling back to this. And thanks again @gsmiller for the detailed feedback!
- On `ScoreDoc[]` vs `int[]`
I agree that the four-method explosion is the thing to avoid, and it sounds reasonable to move `partitionByLeaf` to `int[]` input. Our previous decision is based on the fact that no one requires low level `int[]` input and `ScoreDoc[]` is already sufficient. But now the retriever needs `int[]`, and the partitioning logic only ever looks at docId, and `ScoreDoc[]` introduces things that the operation ignores. Asking `ScoreDoc[]` callers to do a small translation seems fair.
- On the `int[][] ordinalsByLeaf` alternative
I really like the elegance of the single-method shape, but it still introduces overhead for user's who don't need ordinal tracking. And at retrieval time it adds indirection as well.
So I'd propose using two methods, both int[] input, deprecating our previous `ScoreDoc[]` input for `partitionByLeaf`:
```
// No ordinals
public static int[][] partitionByLeaf(int[] globalDocIds, List<LeafReaderContext> leaves)
// With ordinals
public record PartitionedHits(int[][] docIdsByLeaf, int[][] ordinalsByLeaf) {}
public static PartitionedHits partitionByLeafWithOrdinals( int[] globalDocIds, List<LeafReaderContext> leaves)
```
If this sounds reasonable, I'm happy to put up a PR first to switch `partitionByLeaf` from `ScoreDoc[]` to `int[]` input, and then build on this issue once that's in.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org