[
https://issues.apache.org/jira/browse/IMPALA-8015?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Paul Rogers updated IMPALA-8015:
--------------------------------
Description:
TL;DR: the expression used to calculate the cardinality for a M:N (“generic”)
join is incorrect. Scroll to the end for the proposed fix. See IMPALA-8018 for
math details.
h4. Current Implementation
The code uses the following:
{code:java}
double lhsAdjNdv = slots.lhsNdv();
if (slots.lhsNumRows() > lhsCard) lhsAdjNdv *= lhsCard /
slots.lhsNumRows();
double rhsAdjNdv = slots.rhsNdv();
if (slots.rhsNumRows() > rhsCard) rhsAdjNdv *= rhsCard /
slots.rhsNumRows();
long joinCard = Math.round((lhsCard / Math.max(1, Math.max(lhsAdjNdv,
rhsAdjNdv))) *
rhsCard);
{code}
As noted in IMPALA-8014, the above attempts to adjust NDVs for the correlated
filter case.
Where:
* {{lhsCard}} is the output cardinality of the l (previous join) table or
{{|L'|}}
* {{rhsCard}} is the output cardinality of the r (scanned) table or {{|R'|}}
* {slots.lhsNdv()}} is the NDV of the left key or {{|L.k1|}}
* {slots.lnsNumRows()}} is the cardinality of the LHS table, or {{|L|}}
* {slots.rhsNdv()}} is the NDV of the right key or {{|R.k2|}}
* {slots.rnsNumRows()}} is the cardinality of the LHS table, or {{|R|}}
Translated to our notation:
{noformat}
adjNdv(L.k1) = |L.k1| * ( |L'| / |L| if |L| > |L'|, 1 otherwise )
adjNdv(R.k2) = |R.k2| * ( |R'| / |R| if |R| > |R'|, 1 otherwise )
|L’ ⋈ R’| = |L’| * |R’| / max(adjNdv(L.k1), adjNdv(R.k2))
{noformat}
We can make two simplifications:
* Since {{|X’| <= |X|}}, and when {{|X'| = |X|}} then {{|X’| / |X| = 1}} we
can drop the conditional term.
* Since {{|k| <= |X|}} and {{|X'|}} is positive, we can see that neither
{{adjNdv}} term can ever be less than one, so we can ignore the corresponding
{{max()}} in the code.
This gives:
{noformat}
adjNdv(L.k1) = |L.k1| * |L'| / |L|
adjNdv(R.k2) = |R.k2| * |R'| / |R|
|L’| * |R’|
|L’ ⋈ R’| = -------------------------------
max(adjNdv(L.k1), adjNdv(R.k2))
{noformat}
The meaning of the {{adjNdv}} values is that we reduce each NDV proportional to
the the number of rows selected. If we take the adjusted NDVs as the correct
values (but see below) the rest of the expression matches the derived
expression.
h4. Code Bug
However, it *does not* make sense to adjust the NDVs for the M:N case — the one
for which this code applies.
For example, suppose we start with 100 key values, and we select half the rows.
How many keys are left?
* If we start with 100 rows, then, yes, we do reduce the keys by half.
* But, if we start with 10,000 rows, removing half the rows still leaves 5,000
rows to hold our 100 keys.
The intuition is right: the number of matches should decrease if the scan
filter becomes more selective. But, that is exactly with the two scan term
({{|𝜎L|}} and {{|𝜎R|}} provide. It need not be done again for the keys.
The result of this bug that the code estimate will use NDVs that are too small,
producing estimates which are too large, which throws of join selection and
could degrade query performance if it leads to an inefficient plan.
That this attempted adjustment does not, in fact, work is not surprising. As
noted in S&S (section 3.1): “We do not know of any algorithm that *correctly*
takes into account both local predicates and join predicates.”
h4. Worked Example
Let's check with a detailed example:
* {{|L| = 10000}}
* {{|R| = 100}}
* {{|L’| = 3000}}
* {{|R’| = 50}}
* {{ndv(L.k1) = |L.k1| = 40}}
* {{ndv(R.k2) = |R.k2| = 20}}
Let's work this out intuitively first. The join is the normal cross join with
adjustments:
{noformat}
|L’ ⋈ R’| = |L| * |R| * adjustments
{noformat}
Adjustments:
* The left side scan returns only 30% of the total rows.
* The left hand has twice the key values of the right, so we have to discard
half of the left rows.
* Of the L keys with a match in R, it will match, on average, 100/20 = 5 rows.
* But half of R is filtered out, reducing the available matching rows.
And:
{noformat}
|L’ ⋈ R’| = (|L| / 2) * (|R| / 20 / 2)
= 10000 * 30% / 2 * 100 * / 20 / 2
= 1500 * 2.5
= 3750
{noformat}
Using the Equation 5 from IMPALA-8018 (which is Equation 2 in the S&S paper):
{noformat}
|L’| * |R’|
|L’ ⋈ R’| = -------------------
max(|L.k1|, |R.k2|)
= 3000 * 50 / max(40, 20)
= 3000 * 50 / 40
= 3750
{noformat}
Which works out.
Now let's check the code's expression:
{noformat}
adjNdv(L.k1) = |L.k1| * |L'| / |L|
= 40 * 3000 / 10,000
= 12
adjNdv(R.k2) = |R.k2| * |R'| / |R|
= 20 * 50 / 100
= 10
|L’| * |R’|
|L’ ⋈ R’| = -------------------------------
max(adjNdv(L.k1), adjNdv(R.k2))
= 3000 * 50 / max(12, 10)
= 150,000 / 12
= 12,500
{noformat}
Which does not quite work out, verifying the bug. Note that, as a result of the
bug, we overestimate the cardinality by 3 times.
h4. Proposed Fix
See IMPALA-8018 for the proposed fix for this and IMPALA-8014.
was:
TL;DR: the expression used to calculate the cardinality for a M:N (“generic”)
join is incorrect. Scroll to the end for the proposed fix. See IMPALA-8018 for
math details.
h4. Current Implementation
The code uses the following:
{code:java}
double lhsAdjNdv = slots.lhsNdv();
if (slots.lhsNumRows() > lhsCard) lhsAdjNdv *= lhsCard /
slots.lhsNumRows();
double rhsAdjNdv = slots.rhsNdv();
if (slots.rhsNumRows() > rhsCard) rhsAdjNdv *= rhsCard /
slots.rhsNumRows();
long joinCard = Math.round((lhsCard / Math.max(1, Math.max(lhsAdjNdv,
rhsAdjNdv))) *
rhsCard);
{code}
As noted in IMPALA-8014, the above attempts to adjust NDVs for the correlated
filter case.
Where:
* {{lhsCard}} is the output cardinality of the l (previous join) table or
{{|𝜎L|}}
* {{rhsCard}} is the output cardinality of the r (scanned) table or {{|𝜎R|}}
* {slots.lhsNdv()}} is the NDV of the left key or {{|L.k1|}}
* {slots.lnsNumRows()}} is the cardinality of the LHS table, or {{|L|}}
* {slots.rhsNdv()}} is the NDV of the right key or {{|R.k2|}}
* {slots.rnsNumRows()}} is the cardinality of the LHS table, or {{|R|}}
Translated to our notation:
{noformat}
adjNdv(L.k1) = |L.k1| * ( |𝜎L| / |L| if |L| > |𝜎L|, 1 otherwise )
adjNdv(R.k2) = |R.k2| * ( |𝜎R| / |R| if |R| > |𝜎R|, 1 otherwise )
|L’ ⋈ R’| = |L’| * |R’| / max(adjNdv(L.k1), adjNdv(R.k2))
{noformat}
We can make two simplifications:
* Since {{|X’| <= |X|}}, and when {{|𝜎X| = |X|}} then {{|X’| / |X| = 1}} we can
drop the conditional term.
* Since {{|k| <= |X|}} and {{|𝜎X|}} is positive, we can see that neither
{{adjNdv}} term can ever be less than one, so we can ignore the corresponding
{{max()}} in the code.
This gives:
{noformat}
adjNdv(L.k1) = |L.k1| * |𝜎L| / |L|
adjNdv(R.k2) = |R.k2| * |𝜎R| / |R|
|L’| * |R’|
|L’ ⋈ R’| = -------------------------------
max(adjNdv(L.k1), adjNdv(R.k2))
{noformat}
The meaning of the {{adjNdv}} values is that we reduce each NDV proportional to
the the number of rows selected. If we take the adjusted NDVs as the correct
values (but see below) the rest of the expression matches the derived
expression.
h4. Code Bug
However, it *does not* make sense to adjust the NDVs for the M:N case — the one
for which this code applies.
For example, suppose we start with 100 key values, and we select half the rows.
How many keys are left?
* If we start with 100 rows, then, yes, we do reduce the keys by half.
* But, if we start with 10,000 rows, removing half the rows still leaves 5,000
rows to hold our 100 keys.
The intuition is right: the number of matches should decrease if the scan
filter becomes more selective. But, that is exactly with the two scan term
({{|𝜎L|}} and {{|𝜎R|}} provide. It need not be done again for the keys.
The result of this bug that the code estimate will use NDVs that are too small,
producing estimates which are too large, which throws of join selection and
could degrade query performance if it leads to an inefficient plan.
That this attempted adjustment does not, in fact, work is not surprising. As
noted in S&S (section 3.1): “We do not know of any algorithm that *correctly*
takes into account both local predicates and join predicates.”
h4. Worked Example
Let's check with a detailed example:
* {{|L| = 10000}}
* {{|R| = 100}}
* {{|L’| = 3000}}
* {{|R’| = 50}}
* {{ndv(L.k1) = |L.k1| = 40}}
* {{ndv(R.k2) = |R.k2| = 20}}
Let's work this out intuitively first. The join is the normal cross join with
adjustments:
{noformat}
|L’ ⋈ R’| = |L| * |R| * adjustments
{noformat}
Adjustments:
* The left side scan returns only 30% of the total rows.
* The left hand has twice the key values of the right, so we have to discard
half of the left rows.
* Of the L keys with a match in R, it will match, on average, 100/20 = 5 rows.
* But half of R is filtered out, reducing the available matching rows.
And:
{noformat}
|L’ ⋈ R’| = (|L| / 2) * (|R| / 20 / 2)
= 10000 * 30% / 2 * 100 * / 20 / 2
= 1500 * 2.5
= 3750
{noformat}
Using the Equation 5 from IMPALA-8018 (which is Equation 2 in the S&S paper):
{noformat}
|L’| * |R’|
|L’ ⋈ R’| = -------------------
max(|L.k1|, |R.k2|)
= 3000 * 50 / max(40, 20)
= 3000 * 50 / 40
= 3750
{noformat}
Which works out.
Now let's check the code's expression:
{noformat}
adjNdv(L.k1) = |L.k1| * |𝜎L| / |L|
= 40 * 3000 / 10,000
= 12
adjNdv(R.k2) = |R.k2| * |𝜎R| / |R|
= 20 * 50 / 100
= 10
|L’| * |R’|
|L’ ⋈ R’| = -------------------------------
max(adjNdv(L.k1), adjNdv(R.k2))
= 3000 * 50 / max(12, 10)
= 150,000 / 12
= 12,500
{noformat}
Which does not quite work out, verifying the bug. Note that, as a result of the
bug, we overestimate the cardinality by 3 times.
h4. Proposed Fix
See IMPALA-8018 for the proposed fix for this and IMPALA-8014.
> Incorrect cardinality calculation for the generic case
> ------------------------------------------------------
>
> Key: IMPALA-8015
> URL: https://issues.apache.org/jira/browse/IMPALA-8015
> Project: IMPALA
> Issue Type: Bug
> Components: Frontend
> Affects Versions: Impala 3.1.0
> Reporter: Paul Rogers
> Assignee: Paul Rogers
> Priority: Major
>
> TL;DR: the expression used to calculate the cardinality for a M:N (“generic”)
> join is incorrect. Scroll to the end for the proposed fix. See IMPALA-8018
> for math details.
> h4. Current Implementation
> The code uses the following:
> {code:java}
> double lhsAdjNdv = slots.lhsNdv();
> if (slots.lhsNumRows() > lhsCard) lhsAdjNdv *= lhsCard /
> slots.lhsNumRows();
> double rhsAdjNdv = slots.rhsNdv();
> if (slots.rhsNumRows() > rhsCard) rhsAdjNdv *= rhsCard /
> slots.rhsNumRows();
> long joinCard = Math.round((lhsCard / Math.max(1, Math.max(lhsAdjNdv,
> rhsAdjNdv))) *
> rhsCard);
> {code}
> As noted in IMPALA-8014, the above attempts to adjust NDVs for the correlated
> filter case.
> Where:
> * {{lhsCard}} is the output cardinality of the l (previous join) table or
> {{|L'|}}
> * {{rhsCard}} is the output cardinality of the r (scanned) table or {{|R'|}}
> * {slots.lhsNdv()}} is the NDV of the left key or {{|L.k1|}}
> * {slots.lnsNumRows()}} is the cardinality of the LHS table, or {{|L|}}
> * {slots.rhsNdv()}} is the NDV of the right key or {{|R.k2|}}
> * {slots.rnsNumRows()}} is the cardinality of the LHS table, or {{|R|}}
> Translated to our notation:
> {noformat}
> adjNdv(L.k1) = |L.k1| * ( |L'| / |L| if |L| > |L'|, 1 otherwise )
> adjNdv(R.k2) = |R.k2| * ( |R'| / |R| if |R| > |R'|, 1 otherwise )
> |L’ ⋈ R’| = |L’| * |R’| / max(adjNdv(L.k1), adjNdv(R.k2))
> {noformat}
> We can make two simplifications:
> * Since {{|X’| <= |X|}}, and when {{|X'| = |X|}} then {{|X’| / |X| = 1}} we
> can drop the conditional term.
> * Since {{|k| <= |X|}} and {{|X'|}} is positive, we can see that neither
> {{adjNdv}} term can ever be less than one, so we can ignore the corresponding
> {{max()}} in the code.
> This gives:
> {noformat}
> adjNdv(L.k1) = |L.k1| * |L'| / |L|
> adjNdv(R.k2) = |R.k2| * |R'| / |R|
> |L’| * |R’|
> |L’ ⋈ R’| = -------------------------------
> max(adjNdv(L.k1), adjNdv(R.k2))
> {noformat}
> The meaning of the {{adjNdv}} values is that we reduce each NDV proportional
> to the the number of rows selected. If we take the adjusted NDVs as the
> correct values (but see below) the rest of the expression matches the derived
> expression.
> h4. Code Bug
> However, it *does not* make sense to adjust the NDVs for the M:N case — the
> one for which this code applies.
> For example, suppose we start with 100 key values, and we select half the
> rows. How many keys are left?
> * If we start with 100 rows, then, yes, we do reduce the keys by half.
> * But, if we start with 10,000 rows, removing half the rows still leaves
> 5,000 rows to hold our 100 keys.
> The intuition is right: the number of matches should decrease if the scan
> filter becomes more selective. But, that is exactly with the two scan term
> ({{|𝜎L|}} and {{|𝜎R|}} provide. It need not be done again for the keys.
> The result of this bug that the code estimate will use NDVs that are too
> small, producing estimates which are too large, which throws of join
> selection and could degrade query performance if it leads to an inefficient
> plan.
> That this attempted adjustment does not, in fact, work is not surprising. As
> noted in S&S (section 3.1): “We do not know of any algorithm that *correctly*
> takes into account both local predicates and join predicates.”
> h4. Worked Example
> Let's check with a detailed example:
> * {{|L| = 10000}}
> * {{|R| = 100}}
> * {{|L’| = 3000}}
> * {{|R’| = 50}}
> * {{ndv(L.k1) = |L.k1| = 40}}
> * {{ndv(R.k2) = |R.k2| = 20}}
> Let's work this out intuitively first. The join is the normal cross join with
> adjustments:
> {noformat}
> |L’ ⋈ R’| = |L| * |R| * adjustments
> {noformat}
> Adjustments:
> * The left side scan returns only 30% of the total rows.
> * The left hand has twice the key values of the right, so we have to discard
> half of the left rows.
> * Of the L keys with a match in R, it will match, on average, 100/20 = 5
> rows.
> * But half of R is filtered out, reducing the available matching rows.
> And:
> {noformat}
> |L’ ⋈ R’| = (|L| / 2) * (|R| / 20 / 2)
> = 10000 * 30% / 2 * 100 * / 20 / 2
> = 1500 * 2.5
> = 3750
> {noformat}
> Using the Equation 5 from IMPALA-8018 (which is Equation 2 in the S&S paper):
> {noformat}
> |L’| * |R’|
> |L’ ⋈ R’| = -------------------
> max(|L.k1|, |R.k2|)
> = 3000 * 50 / max(40, 20)
> = 3000 * 50 / 40
> = 3750
> {noformat}
> Which works out.
> Now let's check the code's expression:
> {noformat}
> adjNdv(L.k1) = |L.k1| * |L'| / |L|
> = 40 * 3000 / 10,000
> = 12
> adjNdv(R.k2) = |R.k2| * |R'| / |R|
> = 20 * 50 / 100
> = 10
> |L’| * |R’|
> |L’ ⋈ R’| = -------------------------------
> max(adjNdv(L.k1), adjNdv(R.k2))
> = 3000 * 50 / max(12, 10)
> = 150,000 / 12
> = 12,500
> {noformat}
> Which does not quite work out, verifying the bug. Note that, as a result of
> the bug, we overestimate the cardinality by 3 times.
> h4. Proposed Fix
> See IMPALA-8018 for the proposed fix for this and IMPALA-8014.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
