[
https://issues.apache.org/jira/browse/IMPALA-8048?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Zoltán Borók-Nagy updated IMPALA-8048:
--------------------------------------
Epic Link: IMPALA-12674
> Improve join cardinality estimation: urn model, NDV tracking, etc.
> ------------------------------------------------------------------
>
> Key: IMPALA-8048
> URL: https://issues.apache.org/jira/browse/IMPALA-8048
> Project: IMPALA
> Issue Type: Improvement
> Components: Frontend
> Affects Versions: Impala 3.1.0
> Reporter: Paul Rogers
> Priority: Major
>
> Work is underway on a number of JIRA tickets to improve cardinality
> estimates. That work is constrained by the possible need to back-port to
> prior releases. As a result, the changes are made within the existing context
> to minimize the impact.
> The current model makes a number of naive assumptions, however, that should
> be addressed in a second batch of changes which will entail a wider code
> impact.
> h4. Adopt the Urn Model for NDV Estimation.
> Suppose we have a table alumni(name, sex, class) with values such as:
> {noformat}
> John Smith, M, 2008
> Jane Doe, F, 1993
> ...
> {noformat}
> We have 50 years of data, 1000 rows per year, or 50K rows. We have these
> stats:
> {noformat}
> |alumni| = 50K
> |name| = 49K
> |sex| = 2
> |class| = 50
> {noformat}
> We have the following query which fills in the graduation date for each class:
> {code:sql}
> select * from alumni, grad_dates where sex='F' where alumni.class =
> grad_dates.class
> {code}
> Focusing just on the alumni table, how many classes will be available to
> match? That is, what is {{|class'|}}, the NDV of the name field after
> accounting for the affect of the predicate {{sex='F'}}.
> Today we work it out with a linear model as follows:
> {code}
> sel(sex = 'F') = 1/|F| = 1/2 = 0.5
> |sex'| = |sex| * sel(sex = 'F') = 2 * 0.5 = 1
> |class'| = |class| * sel(sex = 'F') = 50 * 0.5 = 25
> {code}
> The math works for the {{sex}} field: the correct adjusted NDV is 1.
> What about for {{class}}? Since the predicate eliminated half the rows, it
> eliminated half the class values. But, this can't be right. Surely women
> graduated in all classes. What went wrong?
> The problem is the linear assumption. As shown in the [SwamiI and
> Schiefer|https://pdfs.semanticscholar.org/2735/672262940a23cfce8d4cc1e25c0191de7da7.pdf]
> paper, Section 5, the correct estimation technique is the urn model. See the
> paper for details. Using that model:
> {noformat}
> |x'| = (1 - (1 - 1/|x|)^|T')
> |alumni'| = |alumni| * sel(sex = 'F') = 50K * .5 = 25K
> |class'| = |class| * (1 - (1 - 1/50) ^ 25K) = 50
> {noformat}
> That is, as the cardinality of the selected table grows larger, the
> probability reaches 1 that other, non-correlated values will still appear.
> This, though we remove half the rows, all the classes are still represented.
> h4. Per-Tuple Column NDV Tracking
> At present, after the current round of changes, we use a linear model to
> estimate column NDV after filtering, and use the same model for all columns.
> If we adopt the urn model, then we must treat columns separately. In the
> above, we do *not* want to apply the urn model to the {{sex}} column. Why? We
> already know its cardinality from the filter predicate. Don't want to replace
> it with an estimated urn-model value. This problem is more acute if you
> consider a range predicate, such as those used on partitions: {{class >
> 2009}}.
> To make the above work, we have to track NDV per column. That is, the scan
> node must provide a list of columns and their NDVs after scanning. Columns
> mentioned in a predicate have their NDVs estimated from selectivity. All
> other columns have their NDVs estimated from the urn model. (There are
> several ways to implement this; the point is that some columns must be
> singled out for special treatment.)
> h4. Proper Join-to-Table Join Column NDVs
> The NDV adjustment model says that, to compute the join cardinality, we need
> the adjusted column cardinality (NDV). When joining one table to another, it
> is clear how to adjust the column NDVs for each table: each is done according
> to the rules spelled out above.
> A complexity arises, however, when we want to join three tables: we have ((A
> ⋈ B) ⋈ C). How do we adjust the NDVs for the columns created by the (A ⋈ B)
> join? If we simply adjust the NDV of table columns using a common selectivity
> (as done in the simple linear model), then we are correct for the columns
> from one table, but wrong for columns from the other. Why? The two table had
> different selectivities applied, we can't reduce them to a common number.
> The solution is the per-column adjusted NDV tracking: we'd know to apply one
> set of adjustments for columns from the left table, another for the right.
> This requires additional data structures in each plan node.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscr...@impala.apache.org
For additional commands, e-mail: issues-all-h...@impala.apache.org
