[GitHub] [pinot] Jackie-Jiang 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>]

Jackie-Jiang commented on code in PR #9667:
URL: https://github.com/apache/pinot/pull/9667#discussion_r1008549704


##########
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:
   Some branches might reach their leaf before other branches, and we will remove some predicate columns later when traversing branches not reaching leaf yet. We need to store all the remaining predicate columns to get the correct query result



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