Paul Rogers created IMPALA-8035:
-----------------------------------
Summary: Planner estimate incorrect for non-equi-join case
Key: IMPALA-8035
URL: https://issues.apache.org/jira/browse/IMPALA-8035
Project: IMPALA
Issue Type: Bug
Components: Frontend
Affects Versions: Impala 3.1.0
Reporter: Paul Rogers
Assignee: Paul Rogers
The code in {{JoinNode.getJoinCardinality()}} makes a bold (and incorrect)
assumption:
{code:java}
if (eqJoinConjunctSlots.isEmpty()) {
// There are no eligible equi-join conjuncts. Optimistically assume FK/PK
with a
// join selectivity of 1.
return probeCard;
}
{code}
Suppose we have a join of the form:
{code:sql}
SELECT * FROM t1, t2
{code}
Or
{code:sql}
SELECT *
FROM t1, t2
WHERE t1.a > t2.b
{code}
The code assumes that each t1 row will match just one t2 row, which seems very
unlikely.
In fact, there are well-known algorithms to estimate this case. The first
example is a Cartesian product with cardinality {{|T1| * |T2|}}.
The second uses the selectivity of the expression:
{noformat}
|T1 ⋈ T2| = |T1| * |T2| * sel(T1.a > T2.b)
{noformat}
Without a histogram, we cannot obtain an accurate estimation of the cardinality
(but see IMPALA-8032). But, we can assume that there is some reduction, else
the user would not have included the clause. Most systems assume a value of 0.1
or 0.45 for inequality. See IMPALA-7601 and [Ramakrishnan and
Gehrke|http://pages.cs.wisc.edu/~dbbook/openAccess/Minibase/optimizer/costformula.html].
However, as noted in IMPALA-7601, we don’t accurately estimate the selectivity
of inequalities, so work is needed there also.
The reason that this bug does not cause problems for users is that, presumably,
most real-world queries use eqi-joins. However, some kinds of analysis queries
use other predicates, and Impala should support these use cases.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
