You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by GitBox <gi...@apache.org> on 2022/10/26 22:33:54 UTC
[GitHub] [pinot] Jackie-Jiang opened a new pull request, #9667: Improve star-tree to use star-node when the predicate matches all the non-star nodes
Jackie-Jiang opened a new pull request, #9667:
URL: https://github.com/apache/pinot/pull/9667
When the predicate matches all the non-star nodes under a branch, we can use the star-node if it exists and the dimension is not included in the group-by
--
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
[GitHub] [pinot] Jackie-Jiang merged pull request #9667: Improve star-tree to use star-node when the predicate matches all the non-star nodes
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang merged PR #9667:
URL: https://github.com/apache/pinot/pull/9667
--
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
[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
Posted by 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
[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
Posted by GitBox <gi...@apache.org>.
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-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
[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
Posted by 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
[GitHub] [pinot] codecov-commenter commented on pull request #9667: Improve star-tree to use star-node when the predicate matches all the non-star nodes
Posted by GitBox <gi...@apache.org>.
codecov-commenter commented on PR #9667:
URL: https://github.com/apache/pinot/pull/9667#issuecomment-1292896809
# [Codecov](https://codecov.io/gh/apache/pinot/pull/9667?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) Report
> Merging [#9667](https://codecov.io/gh/apache/pinot/pull/9667?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (fef4114) into [master](https://codecov.io/gh/apache/pinot/commit/46aa54139fcbdab36851dcc2c4349d8ccfe3da79?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (46aa541) will **decrease** coverage by `0.00%`.
> The diff coverage is `94.28%`.
```diff
@@ Coverage Diff @@
## master #9667 +/- ##
============================================
- Coverage 28.20% 28.19% -0.01%
Complexity 53 53
============================================
Files 1933 1934 +1
Lines 103909 103947 +38
Branches 15771 15773 +2
============================================
+ Hits 29307 29312 +5
- Misses 71728 71758 +30
- Partials 2874 2877 +3
```
| Flag | Coverage Δ | |
|---|---|---|
| integration1 | `25.99% <94.28%> (+0.07%)` | :arrow_up: |
| integration2 | `24.68% <8.57%> (-0.05%)` | :arrow_down: |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#carryforward-flags-in-the-pull-request-comment) to find out more.
| [Impacted Files](https://codecov.io/gh/apache/pinot/pull/9667?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) | Coverage Δ | |
|---|---|---|
| [...core/startree/operator/StarTreeFilterOperator.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9zdGFydHJlZS9vcGVyYXRvci9TdGFyVHJlZUZpbHRlck9wZXJhdG9yLmphdmE=) | `88.88% <94.28%> (+1.56%)` | :arrow_up: |
| [...g/apache/pinot/server/api/resources/ErrorInfo.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3Qtc2VydmVyL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9zZXJ2ZXIvYXBpL3Jlc291cmNlcy9FcnJvckluZm8uamF2YQ==) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [.../raw/BaseRawFloatSingleColumnDistinctExecutor.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9xdWVyeS9kaXN0aW5jdC9yYXcvQmFzZVJhd0Zsb2F0U2luZ2xlQ29sdW1uRGlzdGluY3RFeGVjdXRvci5qYXZh) | `0.00% <0.00%> (-77.78%)` | :arrow_down: |
| [...t/server/api/resources/DefaultExceptionMapper.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3Qtc2VydmVyL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9zZXJ2ZXIvYXBpL3Jlc291cmNlcy9EZWZhdWx0RXhjZXB0aW9uTWFwcGVyLmphdmE=) | `0.00% <0.00%> (-75.00%)` | :arrow_down: |
| [.../raw/RawFloatSingleColumnDistinctOnlyExecutor.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9xdWVyeS9kaXN0aW5jdC9yYXcvUmF3RmxvYXRTaW5nbGVDb2x1bW5EaXN0aW5jdE9ubHlFeGVjdXRvci5qYXZh) | `0.00% <0.00%> (-29.63%)` | :arrow_down: |
| [.../apache/pinot/controller/util/TableSizeReader.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29udHJvbGxlci9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29udHJvbGxlci91dGlsL1RhYmxlU2l6ZVJlYWRlci5qYXZh) | `76.22% <0.00%> (-18.86%)` | :arrow_down: |
| [...pinot/controller/util/CompletionServiceHelper.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29udHJvbGxlci9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29udHJvbGxlci91dGlsL0NvbXBsZXRpb25TZXJ2aWNlSGVscGVyLmphdmE=) | `72.22% <0.00%> (-16.67%)` | :arrow_down: |
| [.../filter/predicate/InPredicateEvaluatorFactory.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9vcGVyYXRvci9maWx0ZXIvcHJlZGljYXRlL0luUHJlZGljYXRlRXZhbHVhdG9yRmFjdG9yeS5qYXZh) | `42.85% <0.00%> (-11.28%)` | :arrow_down: |
| [...pache/pinot/core/util/SortedRangeIntersection.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS91dGlsL1NvcnRlZFJhbmdlSW50ZXJzZWN0aW9uLmphdmE=) | `66.66% <0.00%> (-8.70%)` | :arrow_down: |
| [.../pinot/server/api/resources/TableSizeResource.java](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-cGlub3Qtc2VydmVyL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9zZXJ2ZXIvYXBpL3Jlc291cmNlcy9UYWJsZVNpemVSZXNvdXJjZS5qYXZh) | `80.00% <0.00%> (-8.00%)` | :arrow_down: |
| ... and [45 more](https://codecov.io/gh/apache/pinot/pull/9667/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) | |
:mega: We’re building smart automated test selection to slash your CI/CD build times. [Learn more](https://about.codecov.io/iterative-testing/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation)
--
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
[GitHub] [pinot] Jackie-Jiang commented on pull request #9667: Improve star-tree to use star-node when the predicate matches all the non-star nodes
Posted by GitBox <gi...@apache.org>.
Jackie-Jiang commented on PR #9667:
URL: https://github.com/apache/pinot/pull/9667#issuecomment-1293871550
@siddharthteotia The current star-tree integration test can cover this, but will refactor the traverseStarTree and integration test a little bit
--
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
[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
Posted by 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 review, 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