xiangfu0 commented on code in PR #19879:
URL: https://github.com/apache/pinot/pull/19879#discussion_r4289848583
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/query/LinearSelectionOrderByOperator.java:
##########
@@ -234,7 +312,105 @@ private void concatList(StringBuilder sb, List<?> list) {
@Override
protected SelectionResultsBlock getNextBlock() {
- return new SelectionResultsBlock(createDataSchema(),
fetch(_listBuilderSupplier), _comparator, _queryContext);
+ List<Object[]> rows = fetch(_listBuilderSupplier);
+ if (!_lateMaterialize) {
+ return new SelectionResultsBlock(createDataSchema(), rows, _comparator,
_queryContext);
+ }
+ return fetchRemainingExpressions(rows);
+ }
+
+ /// Fills the output expressions that were not projected during the scan,
for the rows that survived the limit.
+ ///
+ /// The rows are visited in doc-id order because that is the order
[BitmapDocIdSetOperator#ascending] returns, while
+ /// `rows` keeps the result order. Both views hold the same row arrays, so
filling one fills the other.
+ private SelectionResultsBlock fetchRemainingExpressions(List<Object[]> rows)
{
+ int numExpressions = _expressions.size();
+ List<ExpressionContext> nonOrderByExpressions =
_expressions.subList(_numOrderByExpressions, numExpressions);
+ int numNonOrderByExpressions = nonOrderByExpressions.size();
+
+ int numRows = rows.size();
+ Object[][] rowsByDocId = rows.toArray(new Object[numRows][]);
+ Arrays.sort(rowsByDocId, Comparator.comparingInt(row -> (int)
row[_numOrderByExpressions]));
+ RoaringBitmap docIds = new RoaringBitmap();
Review Comment:
The alignment of `rowsByDocId` with the ascending bitmap iteration quietly
relies on every surviving row having a distinct doc id. That holds today, but
if a future change ever let two rows share a doc id the bitmap would dedupe and
the trailing rows would be left unfilled. A one-line `assert
docIds.getCardinality() == numRows;` here would make that assumption fail
loudly instead of silently misaligning.
##########
pinot-core/src/main/java/org/apache/pinot/core/plan/SelectionPlanNode.java:
##########
@@ -88,17 +88,38 @@ public Operator<SelectionResultsBlock> run() {
maxDocsPerCall = Math.min(limit + _queryContext.getOffset(),
DocIdSetPlanNode.MAX_DOC_PER_CALL);
}
- BaseProjectOperator<?> projectOperator = getSortedByProject(expressions,
maxDocsPerCall, orderByExpressions);
+ // Whether the scan can iterate in query order, and so stop once the
list builder is full. Ascending always
+ // can; descending only when reverse iteration is permitted, because
DocIdSetPlanNode only produces an
+ // ascending DocIdSetOperator. getSortedByProject below performs the
actual switch and decides for real; this
+ // is a conservative prediction, and being wrong only costs the
optimization, never correctness.
boolean asc = orderByExpressions.get(0).isAsc();
+ boolean canIterateInQueryOrder =
+ asc ||
QueryOptionsUtils.isReverseOrderAllowed(_queryContext.getQueryOptions());
+
+ // Projecting only the order-by expressions and fetching the rest for
the rows that survive the limit pays off
+ // only when the scan cannot stop at the limit. The linear operator
stops as soon as the list builder is full,
+ // which with a fully sorted order-by prefix is after limit+offset
documents, so there is nothing to save
+ // there. The descending operator has to read the whole match set
because there is no descending cursor.
+ boolean scanBoundedByLimit = canIterateInQueryOrder &&
sortedColumnsPrefixSize == orderByExpressions.size();
+ boolean lateMaterialize = expressions.size() > numOrderByExpressions &&
!scanBoundedByLimit
Review Comment:
The gate has no guard on limit size. When `limit + offset` reaches the
match-set size, late materialization reads the same number of entries as the
eager path but adds a whole extra pass: a bitmap build, a sort, an array copy,
and a second decode/transform over every surviving row. With the option
defaulting to on, a large-`LIMIT` export/pagination query could regress. Worth
either a limit/selectivity guard here or shipping default-off until benchmarked.
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/query/LinearSelectionOrderByOperator.java:
##########
@@ -234,7 +312,105 @@ private void concatList(StringBuilder sb, List<?> list) {
@Override
protected SelectionResultsBlock getNextBlock() {
- return new SelectionResultsBlock(createDataSchema(),
fetch(_listBuilderSupplier), _comparator, _queryContext);
+ List<Object[]> rows = fetch(_listBuilderSupplier);
+ if (!_lateMaterialize) {
+ return new SelectionResultsBlock(createDataSchema(), rows, _comparator,
_queryContext);
+ }
+ return fetchRemainingExpressions(rows);
+ }
+
+ /// Fills the output expressions that were not projected during the scan,
for the rows that survived the limit.
+ ///
+ /// The rows are visited in doc-id order because that is the order
[BitmapDocIdSetOperator#ascending] returns, while
+ /// `rows` keeps the result order. Both views hold the same row arrays, so
filling one fills the other.
+ private SelectionResultsBlock fetchRemainingExpressions(List<Object[]> rows)
{
+ int numExpressions = _expressions.size();
+ List<ExpressionContext> nonOrderByExpressions =
_expressions.subList(_numOrderByExpressions, numExpressions);
+ int numNonOrderByExpressions = nonOrderByExpressions.size();
+
+ int numRows = rows.size();
+ Object[][] rowsByDocId = rows.toArray(new Object[numRows][]);
+ Arrays.sort(rowsByDocId, Comparator.comparingInt(row -> (int)
row[_numOrderByExpressions]));
+ RoaringBitmap docIds = new RoaringBitmap();
+ for (Object[] row : rowsByDocId) {
+ docIds.add((int) row[_numOrderByExpressions]);
+ }
+
+ Set<String> columns = new HashSet<>();
+ for (ExpressionContext expression : nonOrderByExpressions) {
+ expression.getColumns(columns);
+ }
+ Map<String, DataSource> dataSourceMap = new HashMap<>();
+ for (String column : columns) {
+ dataSourceMap.put(column, _indexSegment.getDataSource(column,
_queryContext.getSchema()));
Review Comment:
This uses the `getDataSource(column, schema)` overload, which is a new
dependency on `_queryContext.getSchema()` being populated on the scan path (the
eager path resolves columns through the project operator instead). Could you
confirm the schema is always non-null here, e.g. for virtual/derived columns on
the server side, so this can't NPE?
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/query/LinearSelectionOrderByOperator.java:
##########
@@ -124,39 +159,76 @@ public IndexSegment getIndexSegment() {
public ExecutionStatistics getExecutionStatistics() {
long numEntriesScannedInFilter =
_projectOperator.getExecutionStatistics().getNumEntriesScannedInFilter();
int numDocsScanned = getNumDocsScanned();
- long numEntriesScannedPostFilter = (long) numDocsScanned *
_projectOperator.getNumColumnsProjected();
+ long numEntriesScannedPostFilter =
+ (long) numDocsScanned * _projectOperator.getNumColumnsProjected() +
_numEntriesScannedPostFilterLate;
int numTotalDocs = _indexSegment.getSegmentMetadata().getTotalDocs();
return new ExecutionStatistics(numDocsScanned, numEntriesScannedInFilter,
numEntriesScannedPostFilter,
numTotalDocs);
}
+ /// Number of expressions the project operator actually produces: all of
them, or just the order-by prefix when
+ /// materialising late.
+ protected int getNumProjectedExpressions() {
+ return _columnContexts.length;
+ }
+
+ protected BlockValSet[] newBlockValSets() {
+ return new BlockValSet[getNumProjectedExpressions()];
+ }
+
protected IntFunction<Object[]> fetchBlock(ValueBlock valueBlock,
BlockValSet[] blockValSets) {
- int numExpressions = _expressions.size();
+ int numProjected = getNumProjectedExpressions();
- for (int i = 0; i < numExpressions; i++) {
+ for (int i = 0; i < numProjected; i++) {
ExpressionContext expression = _expressions.get(i);
blockValSets[i] = valueBlock.getBlockValueSet(expression);
}
RowBasedBlockValueFetcher blockValueFetcher = new
RowBasedBlockValueFetcher(blockValSets);
- if (!_nullHandlingEnabled) {
- return blockValueFetcher::getRow;
+ RoaringBitmap[] nullBitmaps;
+ if (_nullHandlingEnabled) {
+ nullBitmaps = new RoaringBitmap[numProjected];
+ for (int i = 0; i < numProjected; i++) {
+ nullBitmaps[i] = blockValSets[i].getNullBitmap();
+ }
+ } else {
+ nullBitmaps = null;
}
- RoaringBitmap[] nullBitmaps = new RoaringBitmap[numExpressions];
- for (int i = 0; i < numExpressions; i++) {
- nullBitmaps[i] = blockValSets[i].getNullBitmap();
+
+ if (!_lateMaterialize) {
+ if (nullBitmaps == null) {
+ return blockValueFetcher::getRow;
+ }
+ return (docId) -> {
+ Object[] row = blockValueFetcher.getRow(docId);
+ applyNulls(row, nullBitmaps, docId);
+ return row;
+ };
}
- return (docId) -> {
- Object[] row = blockValueFetcher.getRow(docId);
- for (int colId = 0; colId < nullBitmaps.length; colId++) {
- if (nullBitmaps[colId] != null && nullBitmaps[colId].contains(docId)) {
- row[colId] = null;
- }
+
+ // Leave room for the expressions fetched after the limit is applied, and
carry the doc id in the first of those
+ // slots so the fetch knows which documents to read. That slot is
overwritten by the first fetched value.
+ int numExpressions = _expressions.size();
+ int[] docIds = valueBlock.getDocIds();
+ return (rowId) -> {
+ Object[] row = new Object[numExpressions];
+ blockValueFetcher.getRow(rowId, row, 0);
+ if (nullBitmaps != null) {
+ applyNulls(row, nullBitmaps, rowId);
}
+ row[_numOrderByExpressions] = docIds[rowId];
return row;
};
}
+ private static void applyNulls(Object[] row, RoaringBitmap[] nullBitmaps,
int rowId) {
Review Comment:
Small readability nit: the parameter is named `rowId` (and the sibling
lambda at line 213 calls it `rowId` too) but it actually holds a block-local
position, not a doc id. Since an off-by-one here is exactly the kind of bug
this code has to avoid, a name like `rowIdInBlock` would make the intent
clearer.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
