You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@impala.apache.org by "Quanlong Huang (Code Review)" <ge...@cloudera.org> on 2026/07/16 14:48:34 UTC

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Quanlong Huang has uploaded this change for review. ( http://gerrit.cloudera.org:8080/24592


Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

A sort only reorders rows, so its output row count equals its child's
unless it applies a limit: TopN, Partitioned TopN, or a total sort
carrying a LIMIT. This extends HBO to support tracking and using
cardinality of such SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 - OrderKind: LEXICAL, ZORDER
 - LIMIT, OFFSET for non-PARTITIONED_TOPN
 - PerPartitionLimit and Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Skip local TopN since its cardinality usages assumes it's a per-instance
cardinality, but HBO tracks the summed cross-instance cardinality. Merge
TopN will skip its local TopN in constructing the child key string,
similar to final AggregationNode skips intermediate AggregationNodes.
This ensures the merge TopN's HBO key is identical to the single-node
plan's key.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/JoinNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
M tests/query_test/test_hbo.py
6 files changed, 439 insertions(+), 4 deletions(-)



  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/1
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 1
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 12: Code-Review+1


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 12
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Fri, 02 Oct 2026 10:43:02 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 6:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/23872/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Mon, 31 Aug 2026 14:40:22 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 10: Code-Review+1


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 10
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Tue, 08 Sep 2026 13:51:48 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 12:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/24242/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 12
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Tue, 29 Sep 2026 13:38:37 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 1:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/23267/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 1
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Thu, 16 Jul 2026 15:13:24 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 12:

(6 comments)

http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
File fe/src/main/java/org/apache/impala/planner/ExchangeNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java@441
PS11, Line 441: 
> I kinda feel like something is wrong here, overriding this.
That's a good point. It's a bit messy due to maintaining the literal meaning of isCardinalityPreserving(). Instead, we should rename it to ignoredInHboCardKey(). Then ExchangeNode can always return true in it.

PS12 removed these overrides.


http://gerrit.cloudera.org:8080/#/c/24592/4/fe/src/main/java/org/apache/impala/planner/JoinNode.java
File fe/src/main/java/org/apache/impala/planner/JoinNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/4/fe/src/main/java/org/apache/impala/planner/JoinNode.java@1096
PS4, Line 1096:   }
> Should we put this and subtreeHasJoin in PlanNode?  I think it's a little a
It's removed in later patch sets.


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java
File fe/src/main/java/org/apache/impala/planner/SortNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@269
PS11, Line 269:     PlanNode baseChild = getChild(0);
> Nit: heh, you were the one who taught me this:  Maybe change this to 
Done


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@285
PS11, Line 285:     }
> Nit: this preconditions should be above the "if" clause at line 282
Done


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@321
PS11, Line 321:       if (mergeParent_ instanceof ExchangeNode) {
> If the value changes only because its mutated, can we just keep the origina
We keep the original offset (originalOffset_) and we can use it here. But keeping and using the original limit will be tricky since getSortLimit() could return limitWithTies_ instead of limit_. We will still need a check like "mergeParent_ instanceof ExchangeNode" so not reducing the lines of changes.


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@474
PS11, Line 474:     }
> Nit and suggestion:
Done



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 12
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Tue, 29 Sep 2026 13:18:13 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

By default, a SortNode leaves the total row count unchanged. However,
when combined with a limit (TopN, Partitioned TopN, or a total sort with
a LIMIT), the output row count decreases. This extends HBO to support
tracking and using the cardinality of these limit-applying SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 -- Only true for RANK() with LIMIT pushdown.
 - OrderKind: LEXICAL, ZORDER
 - Limit and Offset:
 -- LIMIT, OFFSET for non-PARTITIONED_TOPN
 -- PerPartitionLimit for PARTITIONED_TOPN where OFFSET is always 0.
 - Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Local sort nodes in a distributed sort plan are skipped in the HBO key
string for two reasons:
 - to ensure SingleNodePlanner and DistributedPlanner use the same key
   string for the merge/final sort node, either a final Top-N or a
   merging-exchange.
 - Backend tracks the summed cross-instance cardinality for local sort
   nodes but the planner needs single instance cardinality which is the
   same as the cardinality of the final sort node.

To be specific, local sort node and final sort node shares the same HBO
key but only final sort node writes the HBO stats. The final sort node
can be a merging-exchange with SortInfo, LIMIT and OFFSET. Such
ExchangeNodes are not cardinality-preserving so we should generate HBO
key strings for them. To make all kinds of ExchangeNode delegate the HBO
key string generation to its child, i.e. regardless of whether it's
cardinality-preserving, this patch renames isCardinalityPreserving() to
ignoredInHboCardKey() so ExchangeNode can always return true in it.

To verify the cardinality of MERGING-EXCHANGE which only shown in
EXPLAIN output if explain_level >= 2, this patch extends
_run_hbo_explains() to support DISTRIBUTEDPLAN sections in the golden
test files.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Reviewed-on: http://gerrit.cloudera.org:8080/24592
Reviewed-by: Impala Public Jenkins <im...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
---
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
M fe/src/main/java/org/apache/impala/planner/JoinNode.java
M fe/src/main/java/org/apache/impala/planner/PlanNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/main/java/org/apache/impala/planner/TupleCacheNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-analytic-topn.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-offset-only-sort.test
M tests/query_test/test_hbo.py
12 files changed, 775 insertions(+), 42 deletions(-)

Approvals:
  Impala Public Jenkins: Looks good to me, approved; Verified

-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 14
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Aleksandr Efimov, Impala Public Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/24592

to look at the new patch set (#7).

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

By default, a SortNode leaves the total row count unchanged. However,
when combined with a limit (TopN, Partitioned TopN, or a total sort with
a LIMIT), the output row count decreases. This extends HBO to support
tracking and using the cardinality of these limit-applying SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 -- Only true for RANK() with LIMIT pushdown.
 - OrderKind: LEXICAL, ZORDER
 - Limit and Offset:
 -- LIMIT, OFFSET for non-PARTITIONED_TOPN
 -- PerPartitionLimit for PARTITIONED_TOPN where OFFSET is always 0.
 - Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Local sort nodes in a distributed sort plan are skipped in the HBO key
string for two reasons:
 - to ensure SingleNodePlanner and DistributedPlanner use the same key
   string for the merge/final sort node, either a final Top-N or a
   merging-exchange.
 - Backend tracks the summed cross-instance cardinality for local sort
   nodes but the planner needs single instance cardinality which is the
   same as the cardinality of the final sort node.

To be specific, local sort node and final sort node shares the same HBO
key but only final sort node writes the HBO stats. The final sort node
can be a merging-exchange with SortInfo, LIMIT and OFFSET. Such
ExchangeNodes are not cardinality-preserving and reuse the corresponding
sort node's HBO key string.

To verify the cardinality of MERGING-EXCHANGE which only shown in
EXPLAIN output if explain_level >= 2, this patch extends
_run_hbo_explains() to support DISTRIBUTEDPLAN sections in the golden
test files.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-analytic-topn.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-offset-only-sort.test
M tests/query_test/test_hbo.py
8 files changed, 761 insertions(+), 25 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/7
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 7
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Steve Carlin (Code Review)" <ge...@cloudera.org>.
Steve Carlin has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 11:

(6 comments)

http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
File fe/src/main/java/org/apache/impala/planner/ExchangeNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/ExchangeNode.java@441
PS11, Line 441:   public String generateHboKeyString(THboStatsType statsType,
I kinda feel like something is wrong here, overriding this.

This is just like the parent version without the "isCardinalityPreserving()".  

So I get why this is special, but I'm thinking there should be another method used in the parent, like "shouldGenerateHbo()", so that this isn't overridden (also applies to appendScanInputStats).  Then, the parent "shouldGenerateHbo()" returns "isCardinalityPreserving()" by default, and the "shouldGenerateHbo()" in this class is overridden to be "true", since that's what makes the ExchangeNode special.


http://gerrit.cloudera.org:8080/#/c/24592/4/fe/src/main/java/org/apache/impala/planner/JoinNode.java
File fe/src/main/java/org/apache/impala/planner/JoinNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/4/fe/src/main/java/org/apache/impala/planner/JoinNode.java@1096
PS4, Line 1096:       return generateFlattenJoinGroupKeyString(statsType, strategy);
Should we put this and subtreeHasJoin in PlanNode?  I think it's a little awkward to have AggregationNode and SortNode call a method in JoinNode directly.


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java
File fe/src/main/java/org/apache/impala/planner/SortNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@269
PS11, Line 269:     while ((baseChild instanceof SortNode
Nit: heh, you were the one who taught me this:  Maybe change this to 
    while ((baseChild instanceof SortNode sortChild && sortChild.info_ == info_)
        || baseChild instanceof ExchangeNode) {


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@285
PS11, Line 285:     Preconditions.checkState(children_.size() == 1);
Nit: this preconditions should be above the "if" clause at line 282


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@321
PS11, Line 321:       if (mergeParent_ instanceof ExchangeNode) {
If the value changes only because its mutated, can we just keep the original value here?  Or is that value lost because the PlanNode is reconstructed?


http://gerrit.cloudera.org:8080/#/c/24592/11/fe/src/main/java/org/apache/impala/planner/SortNode.java@474
PS11, Line 474:     } else {
Nit and suggestion:

I see this clear is at the top of "tryUpdate..."

But would it be better to put this clear code in PlanNode.computeStats()?  Or would this cause issues?



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 11
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Wed, 23 Sep 2026 18:02:49 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Aleksandr Efimov, Steve Carlin, Impala Public Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/24592

to look at the new patch set (#12).

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

By default, a SortNode leaves the total row count unchanged. However,
when combined with a limit (TopN, Partitioned TopN, or a total sort with
a LIMIT), the output row count decreases. This extends HBO to support
tracking and using the cardinality of these limit-applying SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 -- Only true for RANK() with LIMIT pushdown.
 - OrderKind: LEXICAL, ZORDER
 - Limit and Offset:
 -- LIMIT, OFFSET for non-PARTITIONED_TOPN
 -- PerPartitionLimit for PARTITIONED_TOPN where OFFSET is always 0.
 - Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Local sort nodes in a distributed sort plan are skipped in the HBO key
string for two reasons:
 - to ensure SingleNodePlanner and DistributedPlanner use the same key
   string for the merge/final sort node, either a final Top-N or a
   merging-exchange.
 - Backend tracks the summed cross-instance cardinality for local sort
   nodes but the planner needs single instance cardinality which is the
   same as the cardinality of the final sort node.

To be specific, local sort node and final sort node shares the same HBO
key but only final sort node writes the HBO stats. The final sort node
can be a merging-exchange with SortInfo, LIMIT and OFFSET. Such
ExchangeNodes are not cardinality-preserving so we should generate HBO
key strings for them. To make all kinds of ExchangeNode delegate the HBO
key string generation to its child, i.e. regardless of whether it's
cardinality-preserving, this patch renames isCardinalityPreserving() to
ignoredInHboCardKey() so ExchangeNode can always return true in it.

To verify the cardinality of MERGING-EXCHANGE which only shown in
EXPLAIN output if explain_level >= 2, this patch extends
_run_hbo_explains() to support DISTRIBUTEDPLAN sections in the golden
test files.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
M fe/src/main/java/org/apache/impala/planner/JoinNode.java
M fe/src/main/java/org/apache/impala/planner/PlanNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/main/java/org/apache/impala/planner/TupleCacheNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-analytic-topn.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-offset-only-sort.test
M tests/query_test/test_hbo.py
12 files changed, 775 insertions(+), 42 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/12
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 12
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 8:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/23912/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 8
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Thu, 03 Sep 2026 15:54:12 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 8:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1352
PS6, Line 1352:       analyticFragment.addPlanRoot(upperTopN);
> Yes - the local Top-N in the new hbo-analytic-topn.test. It runs below the 
This is harmless since the local sort node's per-instance cardinality matches the final sort node's. Unlike createOrderByFragment() where we add its OFFSET to its LIMIT so we need to invoke computeStats() for childSortNode again.

Added the comment in SortNode.computeStats() since this comment is now removed.


http://gerrit.cloudera.org:8080/#/c/24592/7/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/7/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1381
PS7, Line 1381:       if (node.isPartitionedTopN()) {
> parentSortNode is assigned in both branches and never read now - the setTop
Oops, fixed this bug and added testDistributedTopNWithTiesStorePath to cover this.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 8
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Thu, 03 Sep 2026 15:33:05 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 13: Verified+1


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 13
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Wed, 07 Oct 2026 04:40:02 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Aleksandr Efimov, Impala Public Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/24592

to look at the new patch set (#8).

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

By default, a SortNode leaves the total row count unchanged. However,
when combined with a limit (TopN, Partitioned TopN, or a total sort with
a LIMIT), the output row count decreases. This extends HBO to support
tracking and using the cardinality of these limit-applying SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 -- Only true for RANK() with LIMIT pushdown.
 - OrderKind: LEXICAL, ZORDER
 - Limit and Offset:
 -- LIMIT, OFFSET for non-PARTITIONED_TOPN
 -- PerPartitionLimit for PARTITIONED_TOPN where OFFSET is always 0.
 - Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Local sort nodes in a distributed sort plan are skipped in the HBO key
string for two reasons:
 - to ensure SingleNodePlanner and DistributedPlanner use the same key
   string for the merge/final sort node, either a final Top-N or a
   merging-exchange.
 - Backend tracks the summed cross-instance cardinality for local sort
   nodes but the planner needs single instance cardinality which is the
   same as the cardinality of the final sort node.

To be specific, local sort node and final sort node shares the same HBO
key but only final sort node writes the HBO stats. The final sort node
can be a merging-exchange with SortInfo, LIMIT and OFFSET. Such
ExchangeNodes are not cardinality-preserving and reuse the corresponding
sort node's HBO key string.

To verify the cardinality of MERGING-EXCHANGE which only shown in
EXPLAIN output if explain_level >= 2, this patch extends
_run_hbo_explains() to support DISTRIBUTEDPLAN sections in the golden
test files.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-analytic-topn.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-offset-only-sort.test
M tests/query_test/test_hbo.py
8 files changed, 779 insertions(+), 23 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/8
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 8
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1352
PS6, Line 1352:       lowerTopN.setTopNMergeParent(upperTopN);
`lowerTopN` has already run `init()` and `computeStats()` before this split, while it was still considered a final TopN, so it can already hold the final HBO cardinality with `hasHboCard_ = true`. The exchange is then initialized from that value before this relationship is set. Assigning `topNMergeParent_` here only changes future `computeStats()` and storage decisions; nothing recomputes the lower node or the exchange. The final plan can therefore keep `(from HBO)` on the local TopN and use the merged whole-query cardinality as its local/exchange estimate, contrary to the final-node-only rule in `SortNode.computeStats()`.

Could we mark the lower TopN before the exchange is initialized, or recompute lower → exchange → upper after setting the relationship? Please add a split analytic TopN test with an HBO hit that verifies the lower node does not retain the HBO annotation/cardinality and the exchange uses the recomputed estimate.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Mon, 31 Aug 2026 17:10:12 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 5:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1294
PS5, Line 1294:       lowerTopN.setTopNMergeInput(true);
> The recompute drops the HBO cardinality but not hasHboCard_ - nothing ever 
The reset is covered by the merged IMPALA-15236. Let's keep the cardinality discussion in the PS6 thread at line 1352.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Sun, 06 Sep 2026 07:16:49 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Aleksandr Efimov, Impala Public Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/24592

to look at the new patch set (#9).

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

By default, a SortNode leaves the total row count unchanged. However,
when combined with a limit (TopN, Partitioned TopN, or a total sort with
a LIMIT), the output row count decreases. This extends HBO to support
tracking and using the cardinality of these limit-applying SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 -- Only true for RANK() with LIMIT pushdown.
 - OrderKind: LEXICAL, ZORDER
 - Limit and Offset:
 -- LIMIT, OFFSET for non-PARTITIONED_TOPN
 -- PerPartitionLimit for PARTITIONED_TOPN where OFFSET is always 0.
 - Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Local sort nodes in a distributed sort plan are skipped in the HBO key
string for two reasons:
 - to ensure SingleNodePlanner and DistributedPlanner use the same key
   string for the merge/final sort node, either a final Top-N or a
   merging-exchange.
 - Backend tracks the summed cross-instance cardinality for local sort
   nodes but the planner needs single instance cardinality which is the
   same as the cardinality of the final sort node.

To be specific, local sort node and final sort node shares the same HBO
key but only final sort node writes the HBO stats. The final sort node
can be a merging-exchange with SortInfo, LIMIT and OFFSET. Such
ExchangeNodes are not cardinality-preserving and reuse the corresponding
sort node's HBO key string.

To verify the cardinality of MERGING-EXCHANGE which only shown in
EXPLAIN output if explain_level >= 2, this patch extends
_run_hbo_explains() to support DISTRIBUTEDPLAN sections in the golden
test files.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-analytic-topn.test
A testdata/workloads/functional-query/queries/QueryTest/hbo-offset-only-sort.test
M tests/query_test/test_hbo.py
8 files changed, 779 insertions(+), 23 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/9
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 9
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 7:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1352
PS6, Line 1352:       analyticFragment.addPlanRoot(upperTopN);
> `lowerTopN` has already run `init()` and `computeStats()` before this split
We can add lowerTopN.computeStats() here to clear the HBO cardinality. But I think this is better than the estimate. Or is there a case that we'd better drop the HBO cardinality?

Updated the comments and added the test.


http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/SortNode.java
File fe/src/main/java/org/apache/impala/planner/SortNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/SortNode.java@233
PS6, Line 233:   public void setSortMergeParent(PlanNode p) { mergeParent_ = p; }
> `OFFSET` without `LIMIT` is still cardinality-changing here. For a legal TO
Nice catch! We should handle the case of OFFSET without LIMIT.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 7
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Wed, 02 Sep 2026 13:21:22 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 7:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/7/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/7/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1381
PS7, Line 1381:       SortNode parentSortNode;
parentSortNode is assigned in both branches and never read now - the setTopNMergeParent() call that used it is gone in PS7. The new check in the SortNode constructor does not cover this branch: both merge Top-Ns are built on exchNode rather than on the sort, so childSortNode keeps mergeParent_ null. It is no longer a merge input, so it takes an HBO cardinality and stores its own run. Both nodes then store under the same key, and the local one stores the cross-instance sum - the collision from the line 1390 thread. No plan under functional-planner has a Top-N with ties below an UNPARTITIONED exchange, so no golden shows this. Was dropping the call deliberate?



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 7
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Wed, 02 Sep 2026 19:05:05 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 5:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1390
PS5, Line 1390:     childSortNode.computeStats(ctx_.getRootAnalyzer());
> In the non-ties path childSortNode is not marked as merge input, so this co
Fixed in PS8. The local sort is marked as a merge input before stats are recomputed, so only the merge node stores HBO stats. Tests cover the store path and original LIMIT/OFFSET key.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Thu, 03 Sep 2026 16:43:45 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 9:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/23925/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 9
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Sun, 06 Sep 2026 01:58:44 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 7:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/7/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/7/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1381
PS7, Line 1381:       SortNode parentSortNode;
> parentSortNode is assigned in both branches and never read now - the setTop
PS9 marks the local sort as a merge input. testDistributedTopNWithTiesStorePath checks that it no longer writes HBO stats.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 7
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Sun, 06 Sep 2026 07:23:00 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/SortNode.java
File fe/src/main/java/org/apache/impala/planner/SortNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/SortNode.java@233
PS6, Line 233:     return !(hasLimit() || isTypeTopN() || isPartitionedTopN());
`OFFSET` without `LIMIT` is still cardinality-changing here. For a legal TOTAL sort such as `ORDER BY bool_col OFFSET 5`, `createOrderByFragment()` clears the local offset but does not call `setTopNMergeParent()` because that call is under `hasLimit`. The local sort therefore delegates its HBO key to the scan. The merging exchange delegates to the same key and stores N-5 rows, while the scan stores N. `HistoricalStats` considers them the same run, so one value replaces the other. In a single-node plan, ignoring the offset also gives a parent the same child key with and without `OFFSET`, although the input cardinality differs.

Could we include `offset_ > 0` in `isCardinalityPreserving()`, mark the local sort as a merge input for either LIMIT or OFFSET, and only track merging exchanges that have a LIMIT or a non-zero offset? Please also add distributed OFFSET-only and single-node parent regression tests.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Mon, 31 Aug 2026 16:44:21 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 6:

(2 comments)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1352
PS6, Line 1352:       lowerTopN.setTopNMergeParent(upperTopN);
> We can add lowerTopN.computeStats() here to clear the HBO cardinality. But 
Yes - the local Top-N in the new hbo-analytic-topn.test. It runs below the HASH exchange, so each instance keeps its own top 5 per group, and it emits at least as many rows as the merge Top-N returns. The golden gives it cardinality=50, which is the merged count, and the exchange between them takes its cardinality and its memory estimate from that number.

It holds 50 only because it read HBO before the split, and nothing recomputes it afterwards. Should the comment here say that keeping it is deliberate? The isSortMergeInput() check in computeStats() skips HBO for a merge input, so the plan disagrees with it.


http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/SortNode.java
File fe/src/main/java/org/apache/impala/planner/SortNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/SortNode.java@233
PS6, Line 233:     return !(hasLimit() || isTypeTopN() || isPartitionedTopN());
> Nice catch! We should handle the case of OFFSET without LIMIT.
Covered in PS7. originalOffset_ keeps isCardinalityPreserving() false after the offset moves to the exchange, and setMergeInfo() marks the local sort whether or not there is a limit. hbo-offset-only-sort.test covers the OFFSET-only plan.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Wed, 02 Sep 2026 19:04:58 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 13:

Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/14225/ DRY_RUN=false


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 13
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Wed, 07 Oct 2026 00:06:52 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Steve Carlin (Code Review)" <ge...@cloudera.org>.
Steve Carlin has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 12: Code-Review+2

Giving a +2 since this seems to have gotten a thorough review from two of us.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 12
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Mon, 05 Oct 2026 19:08:34 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Impala Public Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/24592

to look at the new patch set (#3).

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

A sort only reorders rows, so its output row count equals its child's
unless it applies a limit: TopN, Partitioned TopN, or a total sort
carrying a LIMIT. This extends HBO to support tracking and using
cardinality of such SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 - OrderKind: LEXICAL, ZORDER
 - LIMIT, OFFSET for non-PARTITIONED_TOPN
 - PerPartitionLimit and Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Skip local TopN since its cardinality usages assumes it's a per-instance
cardinality, but HBO tracks the summed cross-instance cardinality. Merge
TopN will skip its local TopN in constructing the child key string,
similar to final AggregationNode skips intermediate AggregationNodes.
This ensures the merge TopN's HBO key is identical to the single-node
plan's key.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExprCanonicalizer.java
M fe/src/main/java/org/apache/impala/planner/JoinNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
M tests/query_test/test_hbo.py
8 files changed, 445 insertions(+), 25 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/3
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 2:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/23312/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 2
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Mon, 20 Jul 2026 01:28:37 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1352
PS6, Line 1352:       lowerTopN.setTopNMergeParent(upperTopN);
> `lowerTopN` has already run `init()` and `computeStats()` before this split
I'd soften "harmless" here. ExchangeNode copies the local Top-N cardinality and divides it by getNumNodes() for the queue memory estimate, so it uses it as a total. With two senders each returning five rows for the same ten groups and no ties, 100 rows cross the exchange while the final Top-N returns 50.

My suggestion to recompute doesn't solve this either: the non-HBO estimate can have the same problem. Could we document this approximation and track the exchange costing separately?



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Sun, 06 Sep 2026 07:15:27 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 3:

Build Failed 

https://jenkins.impala.io/job/gerrit-code-review-checks/23410/ : Initial code review checks failed. See linked job for details on the failure.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 3
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Tue, 28 Jul 2026 09:13:02 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Impala Public Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/24592

to look at the new patch set (#2).

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

A sort only reorders rows, so its output row count equals its child's
unless it applies a limit: TopN, Partitioned TopN, or a total sort
carrying a LIMIT. This extends HBO to support tracking and using
cardinality of such SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 - OrderKind: LEXICAL, ZORDER
 - LIMIT, OFFSET for non-PARTITIONED_TOPN
 - PerPartitionLimit and Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Skip local TopN since its cardinality usages assumes it's a per-instance
cardinality, but HBO tracks the summed cross-instance cardinality. Merge
TopN will skip its local TopN in constructing the child key string,
similar to final AggregationNode skips intermediate AggregationNodes.
This ensures the merge TopN's HBO key is identical to the single-node
plan's key.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/AggregationNode.java
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExprCanonicalizer.java
M fe/src/main/java/org/apache/impala/planner/JoinNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
M tests/query_test/test_hbo.py
8 files changed, 446 insertions(+), 25 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/2
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 2
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 5:

(2 comments)

Went through PS5. The key layout (TIES, order directions, per-partition limits) and the operand qualification for sorts over joins look right, and HboKeyStringTest covers the identity distinctions that matter (ordering column, ASC/DESC, ties, partitioned top-n over a join). Two comments on the distributed local-TopN side.

Note on the base: PS5 sits on 24426 PS12, and PS13/14 of 24426 reworked the JoinNode helpers this patch extends (buildHboOperandQualifierMap dropped its statsType/strategy params), so the upcoming rebase will need to reconcile buildHboInputQualifierMap with that refactor.

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1294
PS5, Line 1294:       lowerTopN.setTopNMergeInput(true);
The recompute drops the HBO cardinality but not hasHboCard_ - nothing ever clears that flag (PlanNode.java:1100 is its only write), so when init() picked up a match, the lower TopN's explain keeps annotating the freshly recomputed estimate with '(from HBO)'. The ties childSortNode marked at line 1367 hits the same thing through the computeStats() at the end of createOrderByFragment(). Clearing the flag in setTopNMergeInput(), or resetting it at the top of tryUpdateCardinalityFromHbo(), would keep the annotation truthful.

On the TODO: reusing the final TopN's HBO number here would understate the local output - sum over instances of min(limit, instance_rows) >= min(limit, total_rows) - so recomputing looks right to me.


http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1390
PS5, Line 1390:     childSortNode.computeStats(ctx_.getRootAnalyzer());
In the non-ties path childSortNode is not marked as merge input, so this computeStats() keeps it HBO-tracked, and at toThrift it writes stats under the same key the logical sort used during single-node planning (for offset=0 the limit propagates unchanged). What gets stored is the cross-instance sum of per-instance limited outputs: with I instances all reaching the limit, num_rows = I*N recorded under the LIMIT:N key. Reads survive today only because tryUpdateCardinalityFromHbo() caps the matched value at the node's own limit, so cardinality_ lands back on N - but the stored runs are inflated, and anything consuming the matched row count without a cap (a future stats type, or surfacing the raw matched value) inherits I*N.

Two follow-ups: (1) is leaving this path unmarked intentional? The commit message's 'skip local TopN since HBO tracks the summed cross-instance cardinality' rationale seems to apply here as much as to the ties/partitioned paths. (2) With offset > 0 the rewrite to (limit+offset, offset=0) means the LIMIT:N|OFFSET:M key that single-node planning looks up is never written by distributed executions, so offset queries can only match here, after the rewrite - worth a comment or a test if that is by design.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 5
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Mon, 17 Aug 2026 08:45:21 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Hello Aleksandr Efimov, Impala Public Jenkins, 

I'd like you to reexamine a change. Please visit

    http://gerrit.cloudera.org:8080/24592

to look at the new patch set (#6).

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................

IMPALA-15189: Support HBO for SortNode cardinality

By default, a SortNode leaves the total row count unchanged. However,
when combined with a limit (TopN, Partitioned TopN, or a total sort with
a LIMIT), the output row count decreases. This extends HBO to support
tracking and using the cardinality of these limit-applying SortNodes.

The HBO key string of a SortNode consists of
 - Type: TOTAL, PARTIAL, TOPN, PARTITIONED_TOPN
 - IncludeTies: true/false for Top-N
 -- Only true for RANK() with LIMIT pushdown.
 - OrderKind: LEXICAL, ZORDER
 - Limit and Offset:
 -- LIMIT, OFFSET for non-PARTITIONED_TOPN
 -- PerPartitionLimit for PARTITIONED_TOPN where OFFSET is always 0.
 - Partition Exprs for PARTITIONED_TOPN
 - Order Exprs
 - Child key

Local sort nodes in a distributed sort plan are skipped in the HBO key
string for two reasons:
 - to ensure SingleNodePlanner and DistributedPlanner use the same key
   string for the merge/final sort node, either a final Top-N or a
   merging-exchange.
 - Backend tracks the summed cross-instance cardinality for local sort
   nodes but the planner needs single instance cardinality which is the
   same as the cardinality of the final sort node.

To be specific, local sort node and final sort node shares the same HBO
key but only final sort node writes the HBO stats. The final sort node
can be a merging-exchange with SortInfo, LIMIT and OFFSET. Such
ExchangeNodes are not cardinality-preserving and reuse the corresponding
sort node's HBO key string.

Testing
 - Added FE tests on HBO key strings
 - Added e2e tests

Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
---
M fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
M fe/src/main/java/org/apache/impala/planner/ExchangeNode.java
M fe/src/main/java/org/apache/impala/planner/PlanNode.java
M fe/src/main/java/org/apache/impala/planner/SortNode.java
M fe/src/test/java/org/apache/impala/planner/HboKeyStringTest.java
A testdata/workloads/functional-query/queries/QueryTest/hbo-agg-on-topn-sort.test
M tests/query_test/test_hbo.py
7 files changed, 528 insertions(+), 4 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/92/24592/6
-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 6:

(2 comments)

Thanks for the comments! Rebased onto the latest join patch and addressed comments.

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1294
PS5, Line 1294:       // Make sure the childFragment's output is partitioned as required by the sortNode.
> The recompute drops the HBO cardinality but not hasHboCard_ - nothing ever 
Nice catch! We should reset hasHboCard_ in tryUpdateCardinalityFromHbo(). I'll leave this to IMPALA-15236 since that patch has done this and will be merged first.

For the TODO, I think the planner wants per-instance cardinality for local sort nodes. But even the per-instance cardinality could be different in local sort node and final sort node. PS6 assumes they are close so share the HBO key string for them. We might need to revisit this.


http://gerrit.cloudera.org:8080/#/c/24592/5/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1390
PS5, Line 1390:                 ctx_.getNextNodeId(), exchNode, childSortNode.getSortInfo(),
> In the non-ties path childSortNode is not marked as merge input, so this co
That's a good point. We should handle the plain distributed sort plan as well. In this case, the merging-exchange acts as the final sort node. We should track and use HBO stats there and skip the local sort node.

Also added OFFSET to the test.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Mon, 31 Aug 2026 14:15:55 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 7:

Build Successful 

https://jenkins.impala.io/job/gerrit-code-review-checks/23899/ : Initial code review checks passed. Use gerrit-verify-dryrun-external or gerrit-verify-dryrun to run full precommit tests.


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 7
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Wed, 02 Sep 2026 13:45:27 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 13: Code-Review+2


-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 13
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Steve Carlin <sc...@cloudera.com>
Gerrit-Comment-Date: Wed, 07 Oct 2026 00:06:52 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Quanlong Huang (Code Review)" <ge...@cloudera.org>.
Quanlong Huang has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 10:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1352
PS6, Line 1352:       analyticFragment.addPlanRoot(upperTopN);
> I'd soften "harmless" here. ExchangeNode copies the local Top-N cardinality
Since it's an existing issue, let's track it separately. Thanks for filing IMPALA-15326 for this!



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 10
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Tue, 08 Sep 2026 11:27:50 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Aleksandr Efimov (Code Review)" <ge...@cloudera.org>.
Aleksandr Efimov has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 6:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java
File fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java:

http://gerrit.cloudera.org:8080/#/c/24592/6/fe/src/main/java/org/apache/impala/planner/DistributedPlanner.java@1352
PS6, Line 1352:       lowerTopN.setTopNMergeParent(upperTopN);
> `lowerTopN` has already run `init()` and `computeStats()` before this split
Agreed, IMPALA-15326 tracks the exchange estimate separately.



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 6
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Aleksandr Efimov <dz...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Reviewer: Quanlong Huang <hu...@gmail.com>
Gerrit-Comment-Date: Tue, 08 Sep 2026 13:51:05 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-15189: Support HBO for SortNode cardinality

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/24592 )

Change subject: IMPALA-15189: Support HBO for SortNode cardinality
......................................................................


Patch Set 1:

(2 comments)

gerrit-auto-critic failed. You can reproduce it locally using command:

  python3 bin/jenkins/critique-gerrit-review.py --dryrun

To run it, you might need a virtual env with Python3's venv installed.

http://gerrit.cloudera.org:8080/#/c/24592/1/fe/src/main/java/org/apache/impala/planner/SortNode.java
File fe/src/main/java/org/apache/impala/planner/SortNode.java:

http://gerrit.cloudera.org:8080/#/c/24592/1/fe/src/main/java/org/apache/impala/planner/SortNode.java@307
PS1, Line 307:     // Order-by sequence is significant, so keep it as-is (do not sort). 
line has trailing whitespace


http://gerrit.cloudera.org:8080/#/c/24592/1/tests/query_test/test_hbo.py
File tests/query_test/test_hbo.py:

http://gerrit.cloudera.org:8080/#/c/24592/1/tests/query_test/test_hbo.py@299
PS1, Line 299: 
flake8: W292 no newline at end of file



-- 
To view, visit http://gerrit.cloudera.org:8080/24592
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ib829887a91593bee124d56e661e714575fe3be97
Gerrit-Change-Number: 24592
Gerrit-PatchSet: 1
Gerrit-Owner: Quanlong Huang <hu...@gmail.com>
Gerrit-Reviewer: Impala Public Jenkins <im...@cloudera.com>
Gerrit-Comment-Date: Thu, 16 Jul 2026 14:50:37 +0000
Gerrit-HasComments: Yes