[
https://issues.apache.org/jira/browse/IMPALA-14601?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18117314#comment-18117314
]
ASF subversion and git services commented on IMPALA-14601:
----------------------------------------------------------
Commit a64de029b8d20b25497f8fbe093c4ed6e536cae0 in impala's branch
refs/heads/master from stiga-huang
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=a64de029b ]
IMPALA-14601: Support HBO for JoinNode cardinality
This extends HBO to support tracking and using cardinality of JoinNodes.
Only frontend changes are needed.
HBO Key String
--------------
The HBO key string for a JoinNode consists of the following info:
- JoinOp, e.g. LEFT_OUTER_JOIN, LEFT_SEMI_JOIN, LEFT_ANTI_JOIN, etc.
- LIMIT
- Join conjuncts.
- Optional WHERE conjuncts.
- HBO key strings of the left and right children.
Right-handed joins like RIGHT_OUTER_JOIN are inverted in the HBO key
string so a plan and its inverted counterpart hash identically. For
instance, these two JoinNodes have the same HBO key string:
LeftOuterJoin RightOuterJoin
/ \ / \
A B B A
For INNER/CROSS joins that the join order doesn't impact the final
cardinality, the HBO key string is optimized to be independent with the
join order. For each of such JoinNode, a maximal contiguous group of
such joins are collected and flatten into sorted operand strings in the
HBO key string. Then added all the conjuncts. For instance, the
following two plans would have the same HBO key string in the top level
JoinNode:
InnerJoin InnerJoin
/ \ / \
InnerJoin C InnerJoin B
/ \ / \
A B A C
This patch also renames the HBO key string fields to use Camel names,
and adds a util method in PlanNode to start generating HBO key string
with the optional LIMIT.
Canonicalization
----------------
Conjuncts are canonicalized in the same way as in HdfsScanNode and
AggregationNode, except that column names are qualified using a
canonicalized alias "op<idx>" where idx is the index of the operand in
the sorted operand list. E.g. the following two queries have the same
conjunct string:
select count(*) from alltypes a join alltypestiny b on a.id = b.int_col;
select count(*) from alltypestiny a join alltypes b on a.id = b.int_col;
But their canonicalized conjunct strings are different:
1) op0.id = op1.int_col
2) op1.id = op0.int_col
Note that alltypes is operand 0 and alltypestiny is operand 1.
When an AggregationNode is on top of a JoinNode, these operand strings
are also used in canonicalizing aggregation expressions to distinguish
which tuple the column comes from. E.g. for the following query:
select t1.int_col, t2.int_col, t3.int_col, count(*)
from functional.alltypes t1
join functional.alltypestiny t2 on t1.id = t2.id
left join functional.alltypessmall t3 on t1.id = t3.id
group by t1.int_col, t2.int_col, t3.int_col
The query plan with the operand strings ("op0.0", "op0.1", "op1"):
Agg
|
LeftJoin
/ \
InnerJoin(op0) t3(op1)
/ \
t1(op0.0) t2(op0.1)
The GroupBy columns will be canonicalized as "op0.0.int_col",
"op0.1.int_col", "op1.int_col".
Testing
- Added FE tests on the HBO key strings.
- Added e2e tests.
Assisted-by: Opus 4.8 (Claude Code)
Change-Id: I70b655ae7027d0d9eb8e9fae9ba2e1b7ad9876b4
Reviewed-on: http://gerrit.cloudera.org:8080/24426
Reviewed-by: Impala Public Jenkins <[email protected]>
Tested-by: Impala Public Jenkins <[email protected]>
> HBO for computing JoinNode cardinality
> --------------------------------------
>
> Key: IMPALA-14601
> URL: https://issues.apache.org/jira/browse/IMPALA-14601
> Project: IMPALA
> Issue Type: New Feature
> Components: Backend, Frontend
> Reporter: Quanlong Huang
> Assignee: Quanlong Huang
> Priority: Critical
>
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
