klsince commented on code in PR #9667:
URL: https://github.com/apache/pinot/pull/9667#discussion_r1008553250
##########
pinot-core/src/main/java/org/apache/pinot/core/startree/operator/StarTreeFilterOperator.java:
##########
@@ -223,108 +200,150 @@ private BaseFilterOperator getFilterOperator() {
@Nullable
private StarTreeResult traverseStarTree() {
MutableRoaringBitmap matchingDocIds = new MutableRoaringBitmap();
- Set<String> remainingPredicateColumns = new HashSet<>();
- Map<String, IntSet> matchingDictIdsMap = new HashMap<>();
+ Set<String> globalRemainingPredicateColumns = Collections.emptySet();
+ boolean globalRemainingPredicateColumnsSet = false;
StarTree starTree = _starTreeV2.getStarTree();
List<String> dimensionNames = starTree.getDimensionNames();
StarTreeNode starTreeRootNode = starTree.getRoot();
// Use BFS to traverse the star tree
- Queue<SearchEntry> queue = new ArrayDeque<>();
- queue.add(new SearchEntry(starTreeRootNode,
_predicateEvaluatorsMap.keySet(), _groupByColumns));
- SearchEntry searchEntry;
- while ((searchEntry = queue.poll()) != null) {
- StarTreeNode starTreeNode = searchEntry._starTreeNode;
+ Queue<StarTreeNode> queue = new LinkedList<>();
+ queue.add(starTreeRootNode);
+ // Use null to mark the end of the current level
+ queue.add(null);
+ int childDimensionId = 0;
+ Set<String> remainingPredicateColumns = new
HashSet<>(_predicateEvaluatorsMap.keySet());
+ Set<String> remainingGroupByColumns = new HashSet<>(_groupByColumns);
+ IntSet matchingDictIds = null;
+ while (!queue.isEmpty()) {
+ StarTreeNode starTreeNode = queue.poll();
+ if (starTreeNode == null) {
+ // Previous level finished
+ if (queue.isEmpty()) {
+ break;
+ } else {
+ String childDimension = dimensionNames.get(childDimensionId++);
+ remainingPredicateColumns.remove(childDimension);
+ remainingGroupByColumns.remove(childDimension);
+ matchingDictIds = null;
+ queue.add(null);
+ continue;
+ }
+ }
// If all predicate columns and group-by columns are matched, we can use
aggregated document
- if (searchEntry._remainingPredicateColumns.isEmpty() &&
searchEntry._remainingGroupByColumns.isEmpty()) {
+ if (remainingPredicateColumns.isEmpty() &&
remainingGroupByColumns.isEmpty()) {
matchingDocIds.add(starTreeNode.getAggregatedDocId());
- } else {
- // For leaf node, because we haven't exhausted all predicate columns
and group-by columns, we cannot use
- // the aggregated document. Add the range of documents for this node
to the bitmap, and keep track of the
- // remaining predicate columns for this node
- if (starTreeNode.isLeaf()) {
- matchingDocIds.add((long) starTreeNode.getStartDocId(),
starTreeNode.getEndDocId());
-
remainingPredicateColumns.addAll(searchEntry._remainingPredicateColumns);
- } else {
- // For non-leaf node, proceed to next level
- String nextDimension =
dimensionNames.get(starTreeNode.getChildDimensionId());
+ continue;
+ }
- // If we have predicates on next level, add matching nodes to the
queue
- if (searchEntry._remainingPredicateColumns.contains(nextDimension)) {
- Set<String> newRemainingPredicateColumns = new
HashSet<>(searchEntry._remainingPredicateColumns);
- newRemainingPredicateColumns.remove(nextDimension);
+ // For leaf node, because we haven't exhausted all predicate columns and
group-by columns, we cannot use
+ // the aggregated document. Add the range of documents for this node to
the bitmap, and keep track of the
+ // remaining predicate columns for this node
+ if (starTreeNode.isLeaf()) {
+ matchingDocIds.add((long) starTreeNode.getStartDocId(),
starTreeNode.getEndDocId());
+ // Only set the global remaining predicate columns once because we
traverse the tree with BFS, so the first leaf
+ // node always have all the
Review Comment:
ah got it. I was having a B-tree in mind while reading this part 🤣
--
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]
