[
https://issues.apache.org/jira/browse/IMPALA-12006?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17702173#comment-17702173
]
Aman Sinha commented on IMPALA-12006:
-------------------------------------
The overestimation occurs for both inner and outer joins. Changed the Jira
title to reflect that. I created a simplified example on TPC-H dataset:
{noformat}
create view v4 as
select a.o_clerk from orders a inner join
(select o_clerk, max(cast(o_orderdate as DATE)) max_date from orders where
o_orderdate < DATE '1998-01-01' group by o_clerk) t1
on a.o_clerk = t1.o_clerk AND a.o_orderdate = max_date;
explain select * from
orders a left outer join v4
on a.o_clerk = v4.o_clerk;
+--------------------------------------------------------------------------------------------+
| Explain String
|
+--------------------------------------------------------------------------------------------+
| Max Per-Host Resource Reservation: Memory=69.88MB Threads=9
|
| Per-Host Resource Estimates: Memory=778MB
|
|
|
| PLAN-ROOT SINK
|
| |
|
| 11:EXCHANGE [UNPARTITIONED]
|
| |
|
| 05:HASH JOIN [LEFT OUTER JOIN, PARTITIONED]
|
| | hash predicates: a.o_clerk = a.o_clerk
|
| | row-size=251B cardinality=2.24G
|
| |
|
| |--10:EXCHANGE [HASH(a.o_clerk)]
|
| | |
|
| | 04:HASH JOIN [INNER JOIN, BROADCAST]
|
| | | hash predicates: a.o_orderdate = max(CAST(o_orderdate AS DATE)),
a.o_clerk = o_clerk |
| | | runtime filters: RF000 <- max(CAST(o_orderdate AS DATE)), RF001 <-
o_clerk |
| | | row-size=80B cardinality=1.50M
|
| | |
|
| | |--08:EXCHANGE [BROADCAST]
|
| | | |
|
| | | 07:AGGREGATE [FINALIZE]
|
| | | | output: max:merge(CAST(o_orderdate AS DATE))
|
| | | | group by: o_clerk
|
| | | | row-size=31B cardinality=1.01K
|
| | | |
|
| | | 06:EXCHANGE [HASH(o_clerk)]
|
| | | |
|
| | | 03:AGGREGATE [STREAMING]
|
| | | | output: max(CAST(o_orderdate AS DATE))
|
| | | | group by: o_clerk
|
| | | | row-size=31B cardinality=1.01K
|
| | | |
|
| | | 02:SCAN HDFS [tpch.orders]
|
| | | HDFS partitions=1/1 files=1 size=162.56MB
|
| | | predicates: o_orderdate < DATE '1998-01-01'
|
| | | row-size=49B cardinality=150.00K
|
| | |
|
| | 01:SCAN HDFS [tpch.orders a]
|
| | HDFS partitions=1/1 files=1 size=162.56MB
|
| | runtime filters: RF000 -> a.o_orderdate, RF001 -> a.o_clerk
|
| | row-size=49B cardinality=1.50M
|
| |
|
| 09:EXCHANGE [HASH(a.o_clerk)]
|
| |
|
| 00:SCAN HDFS [tpch.orders a]
|
| HDFS partitions=1/1 files=1 size=162.56MB
|
| row-size=171B cardinality=1.50M
|
+--------------------------------------------------------------------------------------------+
tpch> select count(*) from
> orders a left outer join v4
> on a.o_clerk = v4.o_clerk;
+----------+
| count(*) |
+----------+
| 2009241 |
+----------+
{noformat}
So the estimated cardinality of the top Left Outer Join is 2.24B. Actual
cardinality is 2M, so an overestimation by 3 orders of magnitude. I
deliberately chose o_clerk as the join key since that has lots of duplicates.
Here's the NDV stats for orders.o_clerk:
{noformat}
+-----------------+---------------+------------------+--------+----------+---------------+--------+---------+
| Column | Type | #Distinct Values | #Nulls | Max Size | Avg
Size | #Trues | #Falses |
+-----------------+---------------+------------------+--------+----------+---------------+--------+---------+
| o_clerk | STRING | 1006 | 0 | 15 | 15.0
| -1 | -1 |
{noformat}
> Outer/inner join cardinality highly overestimated
> -------------------------------------------------
>
> Key: IMPALA-12006
> URL: https://issues.apache.org/jira/browse/IMPALA-12006
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
> Affects Versions: Impala 4.2.0
> Reporter: Aman Sinha
> Assignee: Aman Sinha
> Priority: Major
>
> In one of the use cases, we have seen the cardinality estimate for left outer
> join highly overestimated. The plan is complex and only a partial output is
> shown below (with the column names anonymized):
> {noformat}
> 57:HASH JOIN [LEFT OUTER JOIN, BROADCAST]
> | hash-table-id=121
> | hash predicates: a.id = a.id
> | fk/pk conjuncts: none
> | mem-estimate=0B mem-reservation=0B spill-buffer=2.00MB
> thread-reservation=0
> | tuple-ids=4N,3,6N,8N,9N,11N,14N,16N,19N,21N,24N,26N,29N,31N
> row-size=2.63KB cardinality=3.90T
> | in pipelines: 06(GETNEXT), 26(OPEN)
> |
> |--F1253:PLAN FRAGMENT hosts=13 instances=13
> | | Per-Instance Resources: mem-estimate=1.10GB mem-reservation=204.00MB
> thread-reservation=1
> | JOIN BUILD
> | | join-table-id=121 plan-id=122 cohort-id=25
> | | build expressions: a.id
> | | mem-estimate=1.08GB mem-reservation=204.00MB spill-buffer=2.00MB
> thread-reservation=0
> | |
> | 1758:EXCHANGE [BROADCAST]
> | | mem-estimate=20.87MB mem-reservation=0B thread-reservation=0
> | | tuple-ids=29,31 row-size=85B cardinality=9.56M
> | | in pipelines: 26(GETNEXT)
> | |
> ...
> ...
> ...
> 56:HASH JOIN [LEFT OUTER JOIN, BROADCAST]
> | hash predicates: ifnull(a.id, a.id) = a.id
> | fk/pk conjuncts: assumed fk/pk
> | mem-estimate=0B mem-reservation=0B spill-buffer=2.00MB
> thread-reservation=0
> | tuple-ids=4N,3,6N,8N,9N,11N,14N,16N,19N,21N,24N,26N row-size=2.55KB
> cardinality=14.97G
> | in pipelines: 06(GETNEXT), 22(OPEN)
> {noformat}
> Note that the left input of the join is estimated as 14.97G rows, right input
> as 9.56M rows but the LOJ estimate is 3.9T rows. We need to investigate why
> that is so and fix it. The NDV of the based column involved in the join is
> 36661 but in the lower join there are functions involved in the join
> condition.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
