gortiz commented on code in PR #16789: URL: https://github.com/apache/pinot/pull/16789#discussion_r2358236389
########## pinot-core/src/main/java/org/apache/pinot/core/operator/BaseDocIdSetOperator.java: ########## @@ -0,0 +1,64 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.pinot.core.operator; + +import javax.annotation.Nullable; +import org.apache.pinot.core.operator.blocks.DocIdSetBlock; + + +/// The base class for operators that produce [DocIdSetBlock]. Review Comment: We are trying to use the new Markdown Javadoc (introduced in Java 25, but already supported in most IDEs) in new classes. It usually produce an easier to read documentation ########## pinot-core/src/main/java/org/apache/pinot/core/operator/BitmapDocIdSetOperator.java: ########## @@ -32,51 +33,50 @@ * <p>Should call {@link #nextBlock()} multiple times until it returns <code>null</code> (already exhausts all the * documents) or already gathered enough documents (for selection queries). */ -public class BitmapDocIdSetOperator extends BaseOperator<DocIdSetBlock> { +public class BitmapDocIdSetOperator extends BaseDocIdSetOperator { private static final String EXPLAIN_NAME = "DOC_ID_SET_BITMAP"; - - // TODO: Consider using BatchIterator to fill the document ids. Currently BatchIterator only reads bits for one - // container instead of trying to fill up the buffer with bits from multiple containers. If in the future - // BatchIterator provides an API to fill up the buffer, switch to BatchIterator. - private final IntIterator _intIterator; + @Nullable + private IntIteratorDocIdSetOperator _docIdIteratorOperator = null; private final int[] _docIdBuffer; + private final ImmutableBitmapDataProvider _docIds; + private final DidOrder _didOrder; - public BitmapDocIdSetOperator(ImmutableBitmapDataProvider bitmap) { - _intIterator = bitmap.getIntIterator(); - _docIdBuffer = new int[DocIdSetPlanNode.MAX_DOC_PER_CALL]; + public BitmapDocIdSetOperator(ImmutableBitmapDataProvider docIds, int[] docIdBuffer, DidOrder didOrder) { + _docIds = docIds; + _docIdBuffer = docIdBuffer; + _didOrder = didOrder; } - public BitmapDocIdSetOperator(ImmutableBitmapDataProvider bitmap, int numDocs) { - _intIterator = bitmap.getIntIterator(); - _docIdBuffer = new int[Math.min(numDocs, DocIdSetPlanNode.MAX_DOC_PER_CALL)]; + public static BitmapDocIdSetOperator ascending(ImmutableBitmapDataProvider docIds) { + return ascending(docIds, new int[DocIdSetPlanNode.MAX_DOC_PER_CALL]); } - public BitmapDocIdSetOperator(IntIterator intIterator, int[] docIdBuffer) { - _intIterator = intIterator; - _docIdBuffer = docIdBuffer; + public static BitmapDocIdSetOperator ascending(ImmutableBitmapDataProvider docIds, int numDocs) { + return ascending(docIds, new int[Math.min(numDocs, DocIdSetPlanNode.MAX_DOC_PER_CALL)]); } - public BitmapDocIdSetOperator(ImmutableBitmapDataProvider bitmap, int[] docIdBuffer) { - _intIterator = bitmap.getIntIterator(); - _docIdBuffer = docIdBuffer; + public static BitmapDocIdSetOperator ascending(ImmutableBitmapDataProvider docIds, int[] docIdBuffer) { + return new BitmapDocIdSetOperator(docIds, docIdBuffer, DidOrder.ASC); + } + + public static BitmapDocIdSetOperator descending(ImmutableBitmapDataProvider docIds, int numDocs) { + return descending(docIds, new int[Math.min(numDocs, DocIdSetPlanNode.MAX_DOC_PER_CALL)]); + } + + public static BitmapDocIdSetOperator descending(ImmutableBitmapDataProvider bitmap, int[] docIdBuffer) { + return new BitmapDocIdSetOperator(bitmap, docIdBuffer, DidOrder.ASC); Review Comment: Nice catch! I think I introduced that error when I changed this attribute from boolean to enum ########## pinot-core/src/main/java/org/apache/pinot/core/operator/DescDocIdSetOperator.java: ########## @@ -0,0 +1,133 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.pinot.core.operator; + +import com.google.common.base.Preconditions; +import java.util.Collections; +import java.util.List; +import org.apache.pinot.core.common.BlockDocIdIterator; +import org.apache.pinot.core.common.BlockDocIdSet; +import org.apache.pinot.core.common.Operator; +import org.apache.pinot.core.operator.blocks.DocIdSetBlock; +import org.apache.pinot.core.operator.dociditerators.BitmapBasedDocIdIterator; +import org.apache.pinot.core.operator.filter.BaseFilterOperator; +import org.apache.pinot.core.plan.DocIdSetPlanNode; +import org.apache.pinot.segment.spi.Constants; +import org.apache.pinot.spi.trace.Tracing; +import org.roaringbitmap.IntIterator; +import org.roaringbitmap.RoaringBitmap; +import org.roaringbitmap.RoaringBitmapWriter; + + +public class DescDocIdSetOperator extends BaseDocIdSetOperator { + private static final String EXPLAIN_NAME = "DOC_ID_SET"; Review Comment: Changed to REVERSE_DOC_ID_SET in 4146e4113817026004b8b919fda125104a2eb7e7 ########## pinot-core/src/main/java/org/apache/pinot/core/operator/DescDocIdSetOperator.java: ########## @@ -0,0 +1,133 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.pinot.core.operator; + +import com.google.common.base.Preconditions; +import java.util.Collections; +import java.util.List; +import org.apache.pinot.core.common.BlockDocIdIterator; +import org.apache.pinot.core.common.BlockDocIdSet; +import org.apache.pinot.core.common.Operator; +import org.apache.pinot.core.operator.blocks.DocIdSetBlock; +import org.apache.pinot.core.operator.dociditerators.BitmapBasedDocIdIterator; +import org.apache.pinot.core.operator.filter.BaseFilterOperator; +import org.apache.pinot.core.plan.DocIdSetPlanNode; +import org.apache.pinot.segment.spi.Constants; +import org.apache.pinot.spi.trace.Tracing; +import org.roaringbitmap.IntIterator; +import org.roaringbitmap.RoaringBitmap; +import org.roaringbitmap.RoaringBitmapWriter; + + +public class DescDocIdSetOperator extends BaseDocIdSetOperator { + private static final String EXPLAIN_NAME = "DOC_ID_SET"; + + private static final ThreadLocal<int[]> THREAD_LOCAL_DOC_IDS = + ThreadLocal.withInitial(() -> new int[DocIdSetPlanNode.MAX_DOC_PER_CALL]); + + private final BaseFilterOperator _filterOperator; + private final int _maxSizeOfDocIdSet; + + private BlockDocIdSet _blockDocIdSet; + private int _currentDocId = 0; + private IntIterator _reverseIterator; + + public DescDocIdSetOperator(BaseFilterOperator filterOperator, int maxSizeOfDocIdSet) { + Preconditions.checkArgument(maxSizeOfDocIdSet > 0 && maxSizeOfDocIdSet <= DocIdSetPlanNode.MAX_DOC_PER_CALL); + _filterOperator = filterOperator; + _maxSizeOfDocIdSet = maxSizeOfDocIdSet; + } + + @Override + protected DocIdSetBlock getNextBlock() { + if (_reverseIterator == null) { + initializeBitmap(); + } + + if (_currentDocId == Constants.EOF) { + return null; + } + + Tracing.ThreadAccountantOps.sample(); + + int pos = 0; + int[] docIds = THREAD_LOCAL_DOC_IDS.get(); + for (int i = 0; i < _maxSizeOfDocIdSet && _reverseIterator.hasNext(); i++) { + _currentDocId = _reverseIterator.next(); + docIds[pos++] = _currentDocId; + } + if (pos > 0) { + return new DocIdSetBlock(docIds, pos); + } else { + return null; + } + } + + private void initializeBitmap() { + _blockDocIdSet = _filterOperator.nextBlock().getBlockDocIdSet(); + BlockDocIdIterator iterator = _blockDocIdSet.iterator(); + if (iterator instanceof BitmapBasedDocIdIterator) { + _reverseIterator = ((BitmapBasedDocIdIterator) iterator).getDocIds().getReverseIntIterator(); + } else { + RoaringBitmapWriter<RoaringBitmap> writer = RoaringBitmapWriter.writer().get(); + int docId = iterator.next(); + while (docId != Constants.EOF) { + writer.add(docId); + docId = iterator.next(); + } + _reverseIterator = writer.get().getReverseIntIterator(); + } + } + + @Override + public String toExplainString() { + return EXPLAIN_NAME; + } + + @Override + public List<Operator> getChildOperators() { + return Collections.singletonList(_filterOperator); Review Comment: Done in e8005b1bab0bcb37af899c5367e4e4c2985aae77 ########## pinot-core/src/main/java/org/apache/pinot/core/operator/BitmapDocIdSetOperator.java: ########## @@ -32,51 +33,50 @@ * <p>Should call {@link #nextBlock()} multiple times until it returns <code>null</code> (already exhausts all the * documents) or already gathered enough documents (for selection queries). */ -public class BitmapDocIdSetOperator extends BaseOperator<DocIdSetBlock> { +public class BitmapDocIdSetOperator extends BaseDocIdSetOperator { private static final String EXPLAIN_NAME = "DOC_ID_SET_BITMAP"; - - // TODO: Consider using BatchIterator to fill the document ids. Currently BatchIterator only reads bits for one - // container instead of trying to fill up the buffer with bits from multiple containers. If in the future - // BatchIterator provides an API to fill up the buffer, switch to BatchIterator. - private final IntIterator _intIterator; + @Nullable + private IntIteratorDocIdSetOperator _docIdIteratorOperator = null; private final int[] _docIdBuffer; + private final ImmutableBitmapDataProvider _docIds; + private final DidOrder _didOrder; - public BitmapDocIdSetOperator(ImmutableBitmapDataProvider bitmap) { - _intIterator = bitmap.getIntIterator(); - _docIdBuffer = new int[DocIdSetPlanNode.MAX_DOC_PER_CALL]; + public BitmapDocIdSetOperator(ImmutableBitmapDataProvider docIds, int[] docIdBuffer, DidOrder didOrder) { + _docIds = docIds; + _docIdBuffer = docIdBuffer; + _didOrder = didOrder; } - public BitmapDocIdSetOperator(ImmutableBitmapDataProvider bitmap, int numDocs) { - _intIterator = bitmap.getIntIterator(); - _docIdBuffer = new int[Math.min(numDocs, DocIdSetPlanNode.MAX_DOC_PER_CALL)]; + public static BitmapDocIdSetOperator ascending(ImmutableBitmapDataProvider docIds) { + return ascending(docIds, new int[DocIdSetPlanNode.MAX_DOC_PER_CALL]); } - public BitmapDocIdSetOperator(IntIterator intIterator, int[] docIdBuffer) { - _intIterator = intIterator; - _docIdBuffer = docIdBuffer; + public static BitmapDocIdSetOperator ascending(ImmutableBitmapDataProvider docIds, int numDocs) { + return ascending(docIds, new int[Math.min(numDocs, DocIdSetPlanNode.MAX_DOC_PER_CALL)]); } - public BitmapDocIdSetOperator(ImmutableBitmapDataProvider bitmap, int[] docIdBuffer) { - _intIterator = bitmap.getIntIterator(); - _docIdBuffer = docIdBuffer; + public static BitmapDocIdSetOperator ascending(ImmutableBitmapDataProvider docIds, int[] docIdBuffer) { + return new BitmapDocIdSetOperator(docIds, docIdBuffer, DidOrder.ASC); + } + + public static BitmapDocIdSetOperator descending(ImmutableBitmapDataProvider docIds, int numDocs) { + return descending(docIds, new int[Math.min(numDocs, DocIdSetPlanNode.MAX_DOC_PER_CALL)]); + } + + public static BitmapDocIdSetOperator descending(ImmutableBitmapDataProvider bitmap, int[] docIdBuffer) { + return new BitmapDocIdSetOperator(bitmap, docIdBuffer, DidOrder.ASC); } @Override protected DocIdSetBlock getNextBlock() { - int bufferSize = _docIdBuffer.length; - int index = 0; - while (index < bufferSize && _intIterator.hasNext()) { - _docIdBuffer[index++] = _intIterator.next(); - } - if (index > 0) { - return new DocIdSetBlock(_docIdBuffer, index); - } else { - return null; + if (_docIdIteratorOperator == null) { + IntIterator iterator = _didOrder == DidOrder.ASC ? _docIds.getIntIterator() : _docIds.getReverseIntIterator(); + _docIdIteratorOperator = new IntIteratorDocIdSetOperator(iterator, _docIdBuffer, _didOrder); Review Comment: The reason to create `IntIteratorDocIdSetOperator` is that in order to reverse a `BitmapDocIdSetOperator` we need to have the bitmap. But in master we have the `BitmapDocIdSetOperator(IntIterator intIterator, int[] docIdBuffer)` that is used from `ExpressionScanDocIdIterator`. We can keep the same code here and make `BitmapDocIdSetOperator`, keep that constructor, make `_docIds` nullable and fail on `BitmapDocIdSetOperator.withOrder` if `_docIds` is null. But in my opinion that makes the code more difficult to understand. This approach is also cleaner given it makes sense for a `BitmapDocIdSetOperator` to keep a bitmap while it also makes sense to have a `DocIdSetOperator` backed by an int iterator ########## pinot-core/src/main/java/org/apache/pinot/core/operator/SegmentBlockOperator.java: ########## @@ -0,0 +1,42 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.pinot.core.operator; + +import org.apache.pinot.core.common.Block; +import org.apache.pinot.core.common.Operator; + + +/// An operator that is bound to a specific segment. Review Comment: About the name of the class, I think you are right: The current name is misleading. But I don't think `ReversibleDocScanOperator` has some issues as well: 1. On #16755, which I hope we will end up merging, this interface will be implemented by more operators (including BaseFilterOperator). 2. These operators may or may not be reversible. 3. The key part is that these operators are ordered by did, either ascending, descending or both. I'm renaming the interface as DidOrderedOperator in 65d0b20b4f8397ec06812016519e7c7c14848dc5 ########## pinot-core/src/main/java/org/apache/pinot/core/operator/SegmentBlockOperator.java: ########## @@ -0,0 +1,42 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.pinot.core.operator; + +import org.apache.pinot.core.common.Block; +import org.apache.pinot.core.common.Operator; + + +/// An operator that is bound to a specific segment. Review Comment: The problem with that is that some operators may be at the same time descending and ascending, so `isReverseOrder()` doesn't imply `isNormalOrder` (or whatever we would call it). This is important because, for example, in `SelectionPartiallyOrderedByLinearOperator` we have a precondition verifying whether the operator and the order are compatible. I also find these enums easier to read when using on calls than the old alternative using booleans. ########## pinot-core/src/main/java/org/apache/pinot/core/operator/AscDocIdSetOperator.java: ########## @@ -32,11 +32,12 @@ /** - * The <code>DocIdSetOperator</code> takes a filter operator and returns blocks with set of the matched document Ids. + * The <code>AscendingDocIdSetOperator</code> takes a filter operator and returns blocks with set of the matched + * document Ids. * <p>Should call {@link #nextBlock()} multiple times until it returns <code>null</code> (already exhausts all the * matched documents) or already gathered enough documents (for selection queries). */ -public class DocIdSetOperator extends BaseOperator<DocIdSetBlock> { +public class AscDocIdSetOperator extends BaseDocIdSetOperator { Review Comment: Done in 0ed5804dcb269415fb641abe2cca1e55552cbe1a ########## pinot-core/src/main/java/org/apache/pinot/core/plan/SelectionPlanNode.java: ########## @@ -120,6 +122,34 @@ public Operator<SelectionResultsBlock> run() { return new SelectionOrderByOperator(_indexSegment, _queryContext, expressions, projectOperator); } + private BaseProjectOperator<?> getSortedByProject(List<ExpressionContext> expressions, int maxDocsPerCall, + List<OrderByExpressionContext> orderByExpressions) { + BaseProjectOperator<?> projectOperator = + new ProjectPlanNode(_segmentContext, _queryContext, expressions, maxDocsPerCall).run(); + + boolean asc = orderByExpressions.get(0).isAsc(); + if (!asc + && reverseOptimizationEnabled(_queryContext) + && !projectOperator.isCompatibleWith(SegmentBlockOperator.DidOrder.DESC)) { + try { + return projectOperator.withOrder(SegmentBlockOperator.DidOrder.DESC); + } catch (IllegalArgumentException | UnsupportedOperationException e) { + // This happens when the operator cannot provide the required order between blocks + // Fallback to SelectionOrderByOperator + return projectOperator; + } + } + return projectOperator; + } + + private boolean reverseOptimizationEnabled(QueryContext queryContext) { Review Comment: Don't you think QueryOptionsUtil is too overloaded with methods like this one that probably are only going to be used by a single class? I think it is better to keep it where we are using it and in case we end up reading the query option from other places we can move it to QueryOptionsUtil ########## pinot-tools/src/main/java/org/apache/pinot/tools/SortedColumnQuickstart.java: ########## @@ -0,0 +1,187 @@ +/** + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.pinot.tools; + +import com.fasterxml.jackson.databind.ObjectMapper; +import java.io.File; +import java.io.FileWriter; +import java.io.IOException; +import java.nio.file.Path; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Random; +import java.util.UUID; +import java.util.function.LongSupplier; +import java.util.stream.IntStream; +import java.util.stream.Stream; +import org.apache.pinot.segment.spi.AggregationFunctionType; +import org.apache.pinot.segment.spi.index.startree.AggregationFunctionColumnPair; +import org.apache.pinot.spi.config.table.FieldConfig; +import org.apache.pinot.spi.config.table.StarTreeIndexConfig; +import org.apache.pinot.spi.config.table.TableConfig; +import org.apache.pinot.spi.config.table.TableType; +import org.apache.pinot.spi.data.FieldSpec; +import org.apache.pinot.spi.data.Schema; +import org.apache.pinot.spi.data.readers.GenericRow; +import org.apache.pinot.spi.utils.builder.TableConfigBuilder; +import org.apache.pinot.tools.admin.PinotAdministrator; + +/// Notice: In order to run this quickstart, you need to run the SortedTable main method once to +/// generate the content in the pinot-tools/target/classes/examples/batch/sorted folder. +public class SortedColumnQuickstart extends Quickstart { Review Comment: As a developer, these specific quickstarts are very useful when I need to try out some implementations. For example, while we could merge MultistageEngineQuickStart and ColocatedJoinQuickStart, I find it more useful to have them isolated, as ColocatedJoinQuickStart starts orders of magnitude faster than MultistageEngineQuickStart, given that it doesn't need to load as many tables or execute as many queries. The order-by-benchmark also uses this class to create a similar dataset. -- 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-unsubscr...@pinot.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@pinot.apache.org For additional commands, e-mail: commits-h...@pinot.apache.org
