[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 <gi...@apache.org>]

klsince commented on code in PR #9667:
URL: https://github.com/apache/pinot/pull/9667#discussion_r1008539148


##########
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:
   sry for the late comment, the comment seems not completed. 
   
   not so sure but I'd assume `remainingPredicateColumns` wouldn't change after BFS traversal reaches the leaf level. If so, it seems like no need to track those columns in another globalRemainingPredicateColumns? 
   
   
   



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