[
https://issues.apache.org/jira/browse/IMPALA-15127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18106186#comment-18106186
]
ASF subversion and git services commented on IMPALA-15127:
----------------------------------------------------------
Commit eab0a04de5ea7674173ca08ef55e2ef7a6701a50 in impala's branch
refs/heads/master from stiga-huang
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=eab0a04de ]
IMPALA-15127: Support HBO for UnionNode cardinality
This extends HBO to support tracking and using cardinality of
UnionNodes. Only FE changes are needed.
HBO Key String
--------------
The HBO key string of a UnionNode consits of the optional LIMIT, the
canonicalized const operands, and the key strings of its children.
To make the HBO key string consistent for different operand orders,
the children are sorted by their concatenated and sorted scan table
names. E.g. an operand with only one table scan in its subtree uses the
table name as the sort key, an operand with multiple table scans uses a
sort key like "tbl1,tbl2,tbl3".
In case when two operands have the same set of table scans, we use the
original order in query for simplicity. Another query that flips their
order will have a different HBO key, which misses the HBO stats. Such
cases are rare in practice, so we keep them unoptimized.
Historical Runs Matching
------------------------
If the HBO key strings match, we pick one from the list of historical
runs corresponding to that key.
UnionNode is the first HBO-supported node type that has multiple
children so we need to extend the existing matching mechanism to
supports matching multiple scan nodes.
Each UnionNode collects all the leaf scan input stats inside its subtree
in pre-order traversal. The order of visiting its children is the same
as the operand order used in the HBO key string.
While matching a historical run, element-wise comparison of all
TScanInputStats entries is performed to ensure they are similar
respectively. Take the following UnionNode runs as an example. The
children (sorted) are ScanNodes A, B, C.
UnionNode UnionNode
/ | \ / | \
A B C A' B' C'
The matching requires similar(A, A') && similar(B, B') && similar(C, C').
Similarity of a scan node pair is checked in the following way:
- If both sides have valid input_rows (come from HMS numRows stats),
compare row count.
- If either input_rows is missing,
- For EXPR_REWRITE, an exact catalog version match means similar.
if catalog versions differ, compare input file sizes.
- For other strategies, catalog version is not a reliable signal,
so compare input file sizes only.
Note that the hash key matching already ensures table names and
conjuncts are matched. It's done before finding the historical run so we
don't need to compare table names or conjuncts here.
For UnionNodes that have only constant operands, there are no scan input
stats. The corresponding HBO value list will have at most one item since
the HBO key matching already ensures the constants are identical.
Testing
- Added FE tests for HBO key strings.
- Added FE tests to matching historical runs.
- Added e2e tests on all UNION types.
Assisted-by: Opus 4.8 (Claude Code)
Change-Id: Ie228f530bdcb171d3b717966673164bf9a4c45c8
Reviewed-on: http://gerrit.cloudera.org:8080/24556
Reviewed-by: Impala Public Jenkins <[email protected]>
Tested-by: Impala Public Jenkins <[email protected]>
> HBO for computing UnionNode cardinality
> ---------------------------------------
>
> Key: IMPALA-15127
> URL: https://issues.apache.org/jira/browse/IMPALA-15127
> Project: IMPALA
> Issue Type: New Feature
> Components: Frontend
> Reporter: Quanlong Huang
> Assignee: Quanlong Huang
> Priority: Major
>
> The HBO hash string of UnionNode should match different operand orders if the
> operands are the same.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
