[GitHub] [pinot] klsince commented on a diff in pull request #9667: Improve star-tree to use star-node when the predicate matches all the non-star nodes

[GitBox]

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: 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