You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "gortiz (via GitHub)" <gi...@apache.org> on 2025/09/04 15:42:00 UTC
[PR] Support descending iterators to optimize order by desc [pinot]
gortiz opened a new pull request, #16755:
URL: https://github.com/apache/pinot/pull/16755
This PR improves https://github.com/apache/pinot/issues/8837
The main idea is to break the _ascending only_ invariant on docid iterators and support both ascending and descending. Due to how the code is right now, in order to do that we need to modify several operators. Then in SelectionPlanNode, if the order is descending, we call `ProjectorOperator.withOrder(false)`, which either returns:
- A new ProjectorOperator whose order is descending, in which case we use SelectionPartiallyOrderedByLinearOperator, which is similar to the old SelectionPartiallyOrderedByAscOperator.
- Or fails with UnsupportedOperationException, in which case we call the same old SelectionPartiallyOrderedByDescOperator we used before, which has a higher cost.
A prelimilary benchmark returns (on my M1) the following data, which is significantly better than the current state. I still need to verify that everything works as expected, so I'm opening this as a draft
```
Benchmark (_asc) (_limit) (_numRows) (_primaryRepetitions) (_scenario) Mode Cnt Score Error Units
BenchmarkOrderByQueries.sortedPartially true 1500 1500000 1 EXP(0.5) avgt 1.521 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr true 1500 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedPartially true 1500 1500000 1000 EXP(0.5) avgt 3.853 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr true 1500 1500000 1000 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedPartially true 150000 1500000 1 EXP(0.5) avgt 35.481 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr true 150000 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedPartially true 150000 1500000 1000 EXP(0.5) avgt 59.138 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr true 150000 1500000 1000 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedPartially false 1500 1500000 1 EXP(0.5) avgt 1.900 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr false 1500 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedPartially false 1500 1500000 1000 EXP(0.5) avgt 2.388 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr false 1500 1500000 1000 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedPartially false 150000 1500000 1 EXP(0.5) avgt 37.283 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr false 150000 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedPartially false 150000 1500000 1000 EXP(0.5) avgt 53.551 ms/op
BenchmarkOrderByQueries.sortedPartially:jfr false 150000 1500000 1000 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally true 1500 1500000 1 EXP(0.5) avgt 0.694 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr true 1500 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally true 1500 1500000 1000 EXP(0.5) avgt 2.983 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr true 1500 1500000 1000 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally true 150000 1500000 1 EXP(0.5) avgt 14.721 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr true 150000 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally true 150000 1500000 1000 EXP(0.5) avgt 15.271 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr true 150000 1500000 1000 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally false 1500 1500000 1 EXP(0.5) avgt 0.629 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr false 1500 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally false 1500 1500000 1000 EXP(0.5) avgt 0.462 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr false 1500 1500000 1000 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally false 150000 1500000 1 EXP(0.5) avgt 28.011 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr false 150000 1500000 1 EXP(0.5) avgt NaN ---
BenchmarkOrderByQueries.sortedTotally false 150000 1500000 1000 EXP(0.5) avgt 21.024 ms/op
BenchmarkOrderByQueries.sortedTotally:jfr false 150000 1500000 1000 EXP(0.5) avgt NaN ---
```
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Support descending iterators to optimize order by desc [pinot]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #16755:
URL: https://github.com/apache/pinot/pull/16755#discussion_r2322607775
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIterator.java:
##########
@@ -27,55 +27,94 @@
* <p>It keeps calling {@link BlockDocIdIterator#advance(int)} to gather the common matching document ids from all child
* BlockDocIdIterators until one of them hits the end.
*/
-public final class AndDocIdIterator implements BlockDocIdIterator {
+public class AndDocIdIterator implements BlockDocIdIterator {
public final BlockDocIdIterator[] _docIdIterators;
- private int _nextDocId = 0;
+ protected int _nextDocId;
- public AndDocIdIterator(BlockDocIdIterator[] docIdIterators) {
+ private AndDocIdIterator(BlockDocIdIterator[] docIdIterators) {
_docIdIterators = docIdIterators;
}
+ public static AndDocIdIterator create(BlockDocIdIterator[] docIdIterators, boolean asc) {
+ return asc ? new Asc(docIdIterators) : new Desc(docIdIterators);
+ }
+
@Override
- public int next() {
- int maxDocId = _nextDocId;
- int maxDocIdIndex = -1;
+ public int advance(int targetDocId) {
+ _nextDocId = targetDocId;
+ return next();
+ }
+
+ @Override
+ public void close() {
+ for (BlockDocIdIterator it : _docIdIterators) {
+ it.close();
+ }
+ }
+
+ /// Starting from [#_nextDocId], returns the next common matching document id from all child BlockDocIdIterators or
+ /// Constants.EOF if there is no more common matching document id.
+ ///
+ /// Although the state of [#_nextDocId] is not updated, iterators will be advanced, so this method have side effects.
+ protected int findNextCommonMatch() {
+ // CandidateId is the next did to try.
+ // It is initialized to the current _nextDocId and updated using advance() calls on the child iterators.
+ int candidateId = _nextDocId;
+ // The index in _docIdIterators that returned the candidateId from advance() call.
+ // Initialized to -1 to indicate that no iterator has returned the candidateId yet.
+ int candidateIdIndex = -1;
int numDocIdIterators = _docIdIterators.length;
+ // The index of the next iterator to test. It can be reset to 0 when a new candidateId is found.
int index = 0;
while (index < numDocIdIterators) {
- if (index == maxDocIdIndex) {
+ if (index == candidateIdIndex) {
// Skip the index with the max document id
index++;
continue;
}
- int docId = _docIdIterators[index].advance(maxDocId);
- if (docId != Constants.EOF) {
- if (docId == maxDocId) {
- index++;
- } else {
- // The current iterator does not contain the maxDocId, update maxDocId and advance all other iterators
- maxDocId = docId;
- maxDocIdIndex = index;
- index = 0;
- }
- } else {
- closeIterators();
+ // docId is the next docId from the current iterator that matches
+ int docId = _docIdIterators[index].advance(candidateId);
+ if (docId == Constants.EOF) { // this iterator is exhausted. Given we are an and we know there are no more matches
+ close();
return Constants.EOF;
}
+ if (docId == candidateId) { // The current iterator contains the candidateId, move to the next iterator
+ index++;
+ } else {
+ // The current iterator does not contain the candidateId, update candidateId
+ // and reset index to advance other iterators
+ candidateId = docId;
+ candidateIdIndex = index;
+ index = 0;
+ }
}
- _nextDocId = maxDocId;
- return _nextDocId++;
+ return candidateId;
}
- @Override
- public int advance(int targetDocId) {
- _nextDocId = targetDocId;
- return next();
+ public static class Asc extends AndDocIdIterator {
+ public Asc(BlockDocIdIterator[] docIdIterators) {
+ super(docIdIterators);
+ _nextDocId = 0;
+ }
+
+ @Override
+ public int next() {
+ _nextDocId = findNextCommonMatch();
+ return _nextDocId++;
+ }
}
- private void closeIterators() {
- for (BlockDocIdIterator it : _docIdIterators) {
- it.close();
+ public static class Desc extends AndDocIdIterator {
+ public Desc(BlockDocIdIterator[] docIdIterators) {
+ super(docIdIterators);
+ _nextDocId = Integer.MAX_VALUE;
}
}
+
+ @Override
+ public int next() {
+ _nextDocId = findNextCommonMatch();
+ return _nextDocId--;
Review Comment:
The `next()` method at line 117-118 is outside of any class definition. This appears to be a structural error where the `Desc` class definition is incomplete, leaving this method floating outside the class.
```suggestion
@Override
public int next() {
_nextDocId = findNextCommonMatch();
return _nextDocId--;
}
```
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Support descending iterators to optimize order by desc [pinot]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #16755:
URL: https://github.com/apache/pinot/pull/16755#discussion_r2325002781
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/CombinedFilterOperator.java:
##########
@@ -61,8 +61,16 @@ public String toExplainString() {
@Override
protected BlockDocIdSet getTrues() {
Tracing.activeRecording().setNumChildren(2);
- BlockDocIdSet mainFilterDocIdSet = _mainFilterOperator.nextBlock().getNonScanFilterBLockDocIdSet();
+ BlockDocIdSet mainFilterDocIdSet = _mainFilterOperator.nextBlock().getNonScanFilterBlockDocIdSet();
Review Comment:
Method name has a typo: 'BLockDocIdSet' should be 'BlockDocIdSet'.
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/MVScanDocIdIterator.java:
##########
@@ -258,4 +243,44 @@ public void close() {
_readerContext.close();
}
}
+
+ public static class Asc extends MVScanDocIdIterator {
+ public Asc(PredicateEvaluator predicateEvaluator, DataSource dataSource, int numDocs) {
+ super(predicateEvaluator, dataSource, numDocs);
+ }
+
+ @Override
+ public int next() {
+ while (_nextDocId < _numDocs) {
+ int nextDocId = _nextDocId++;
+ // TODO: The performance can be improved by batching the docID lookups similar to how it's done in
+ // SVScanDocIdIterator
+ boolean doesValueMatch = _valueMatcher.doesValueMatch(nextDocId);
+ if (doesValueMatch) {
+ return nextDocId;
+ }
+ }
+ close();
+ return Constants.EOF;
+ }
+ }
+
Review Comment:
The `Desc` class constructor is missing its class declaration. The code shows a constructor body without the proper class definition.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Support descending iterators to optimize order by desc [pinot]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #16755:
URL: https://github.com/apache/pinot/pull/16755#discussion_r2322607845
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/MVScanDocIdIterator.java:
##########
@@ -258,4 +243,45 @@ public void close() {
_readerContext.close();
}
}
+
+ public static class Asc extends MVScanDocIdIterator {
+ public Asc(PredicateEvaluator predicateEvaluator, DataSource dataSource, int numDocs) {
+ super(predicateEvaluator, dataSource, numDocs);
+ }
+
+ @Override
+ public int next() {
+ while (_nextDocId < _numDocs) {
+ int nextDocId = _nextDocId++;
+ // TODO: The performance can be improved by batching the docID lookups similar to how it's done in
+ // SVScanDocIdIterator
+ boolean doesValueMatch = _valueMatcher.doesValueMatch(nextDocId);
+ if (doesValueMatch) {
+ return nextDocId;
+ }
+ }
+ close();
+ return Constants.EOF;
+ }
+ }
+
+ public static class Desc extends MVScanDocIdIterator {
+ public Desc(PredicateEvaluator predicateEvaluator, DataSource dataSource, int numDocs) {
+ super(predicateEvaluator, dataSource, numDocs);
Review Comment:
The `Desc` constructor doesn't initialize `_nextDocId` to start from the end of the document range like the ascending version does. It should set `_nextDocId = numDocs - 1` to properly iterate in descending order.
```suggestion
super(predicateEvaluator, dataSource, numDocs);
_nextDocId = numDocs - 1;
```
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapBasedFilterOperator.java:
##########
@@ -79,4 +83,9 @@ public List<Operator> getChildOperators() {
public String toExplainString() {
return EXPLAIN_NAME;
}
+
+ @Override
+ protected BaseFilterOperator reverse() {
+ return new BitmapBasedFilterOperator(_docIds, _ascending, _numDocs, !_ascending);
Review Comment:
The constructor call at line 89 passes `_ascending` as the second parameter (exclusive) and `!_ascending` as the fourth parameter (ascending). This creates a logical inconsistency where the exclusive flag equals the ascending flag, which doesn't match the expected behavior.
```suggestion
return new BitmapBasedFilterOperator(_docIds, !_exclusive, _numDocs, !_ascending);
```
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Support descending iterators to optimize order by desc [pinot]
Posted by "gortiz (via GitHub)" <gi...@apache.org>.
gortiz commented on code in PR #16755:
URL: https://github.com/apache/pinot/pull/16755#discussion_r2324978933
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/BitmapBasedFilterOperator.java:
##########
@@ -79,4 +83,9 @@ public List<Operator> getChildOperators() {
public String toExplainString() {
return EXPLAIN_NAME;
}
+
+ @Override
+ protected BaseFilterOperator reverse() {
+ return new BitmapBasedFilterOperator(_docIds, _ascending, _numDocs, !_ascending);
Review Comment:
This is an error, but the solution is not what is recommended.
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
Re: [PR] Support descending iterators to optimize order by desc [pinot]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #16755:
URL: https://github.com/apache/pinot/pull/16755#discussion_r2322607888
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/SortedDocIdIterator.java:
##########
@@ -28,57 +28,114 @@
* The {@code SortedDocIdIterator} is the iterator for SortedDocIdSet to iterate over a list of matching document id
* ranges from a sorted column.
*/
-public final class SortedDocIdIterator implements BlockDocIdIterator {
- private final List<IntPair> _docIdRanges;
- private final int _numRanges;
+public abstract class SortedDocIdIterator implements BlockDocIdIterator {
+ protected final List<IntPair> _docIdRanges;
+ protected final int _numRanges;
- private int _currentRangeId = 0;
- private int _nextDocId;
+ protected int _currentRangeId;
+ protected int _nextDocId;
- public SortedDocIdIterator(List<IntPair> docIdRanges) {
+ private SortedDocIdIterator(List<IntPair> docIdRanges) {
_docIdRanges = docIdRanges;
_numRanges = _docIdRanges.size();
_nextDocId = docIdRanges.get(0).getLeft();
}
+ public static SortedDocIdIterator create(List<IntPair> docIdRanges, boolean ascending) {
+ return ascending ? new Asc(docIdRanges) : new Desc(docIdRanges);
+ }
+
public List<IntPair> getDocIdRanges() {
return _docIdRanges;
}
- @Override
- public int next() {
- IntPair currentRange = _docIdRanges.get(_currentRangeId);
- if (_nextDocId <= currentRange.getRight()) {
- // Next document id is within the current range
- return _nextDocId++;
- }
- if (_currentRangeId < _numRanges - 1) {
- // Move to the next range
- _currentRangeId++;
- _nextDocId = _docIdRanges.get(_currentRangeId).getLeft();
- return _nextDocId++;
- } else {
- return Constants.EOF;
+ private static class Asc extends SortedDocIdIterator {
+ private Asc(List<IntPair> docIdRanges) {
+ super(docIdRanges);
+ _currentRangeId = 0;
+ _nextDocId = 0;
Review Comment:
Line 56 sets `_nextDocId = 0` but it should be set to `docIdRanges.get(0).getLeft()` to properly initialize to the start of the first range, consistent with the parent constructor logic.
```suggestion
_nextDocId = docIdRanges.get(0).getLeft();
```
--
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: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org