[
https://issues.apache.org/jira/browse/DRILL-5254?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Kunal Khatua updated DRILL-5254:
--------------------------------
Labels: performance tuning (was: )
Fix Version/s: (was: 1.10.0)
Future
Moving this to Future target although it has been marked as _Resolved_ with a
_Won't_ _Fix_ resolution.
Applying _performance_ and _tuning_ labels for tracking purposes.
> Enhance default reduction factors in optimizer
> ----------------------------------------------
>
> Key: DRILL-5254
> URL: https://issues.apache.org/jira/browse/DRILL-5254
> Project: Apache Drill
> Issue Type: Improvement
> Affects Versions: 1.9.0
> Reporter: Paul Rogers
> Assignee: Paul Rogers
> Labels: performance, tuning
> Fix For: Future
>
>
> Drill uses Calcite for query parsing and optimization. Drill uses Calcite's
> default selectivity (reduction factor) rules to compute the number of rows
> removed by a filter.
> The default rules appear to be overly aggressive in estimating reductions. In
> a production use case, an input with 4 billion rows was estimated to return
> just 40K rows from a filter. That is, the filter estimated a 1/1,000,000
> reduction in rows. As it turns out, the actual reduction was closer to 1/2.
> The result was that the planner compared the expected 40K rows against
> another input of 2.5 million rows, and decided the 40K rows would be best on
> the build side of a hash join. When confronted with the actual 3 billion
> rows, the hash join ran out of memory.
> The moral of the story is that, in Drill, it is worth being conservative when
> planning for memory-intensive operations.
> The (sanitized) filter is the following, annotated with (a guess at) the
> default reduction factors in each term:
> {code}
> col1_s20 in ('Value1','Value2','Value3','Value4',
> 'Value5','Value6','Value7','Value8','Value9') -- 25%
> AND col2_i <=3 -- 25%
> AND col3_s1 = 'Y' -- 15%
> AND col4_s1 = 'Y' -- 15%
> AND col5_s6 not like '%str1%' -- 25%
> AND col5_s6 not like '%str2%' -- 25%
> AND col5_s6 not like '%str3%' -- 25%
> AND col5_s6 not like '%str4%' -- 25%
> {code}
> Total reduction is something like:
> {code}
> .25 * .25 * .15 ^ 2 * .25 ^ 4 = 0.000005
> {code}
> Filter estimation is a known hard problem. In general, one needs statistics
> and other data, and even then the estimates are just guesses.
> Still it is possible to ensure that the defaults are at least unbiased. That
> is if we assume that the probability of A LIKE B being 25%, then the
> probability of A NOT LIKE B should be 75%, not also 25%.
> This JIRA suggests creating an experimental set of defaults based on the
> "core" Calcite defaults, but with other reduction factors derived using the
> laws of probability. In particular:
> || Operator || Revised || Explanation || Calcite Default
> | = | 0.15 | Default in Calcite | 0.15
> | <> | 0.85 | 1 - p(=) | 0.5
> | < | 0.425 | p(<>) / 2 | 0.5
> | > | 0.425 | p(<>) / 2 | 0.5
> | <= | 0.575 | p(<) + p(=) | 0.5
> | >= | 0.575 | p(>) + p(=) | 0.5
> | LIKE | 0.25 | Default in Calcite | 0.25
> | NOT LIKE | 0.75 | 1 - p(LIKE) | 0.25
> | NOT NULL | 0.90 | Default in Calcite | 0.90
> | IS NULL | 0.10 | 1 - p(NOT NULL) | 0.25
> | val IS TRUE | 0.5 | 1 / 2 | 0.25
> | val IS FALSE | 0.5 | 1 / 2 | 0.25
> | val IS NOT TRUE | 0.55 | (1 + p(NULL)) / 2 | 0.25
> | val IS NOT FALSE | 0.55 | (1 + p(NULL)) / 2 | 0.25
> | expr IS TRUE | Varies | p(expr) | 0.25
> | expr IS FALSE | Varies | 1 - p(expr) | 0.25
> | expr IS NOT TRUE | Varies | p(expr IS FALSE) | 0.25
> | expr IS NOT FALSE | Varies | p(expr IS TRUE) | 0.25
> | A OR B | Varies | min(p(A) + p(B), 0.5) | 0.5
> | A AND B | Varies | p(A ^ B) = p(A) * p(B) | Same
> | IN (a) | 0.15 | p(=) | 0.25
> | x IN (a, b, c, ...) | Varies | p(x = a v x = b v x = c v ...) | 0.25
> | NOT A | Varies | 1 - p(A) | 0.25
> | BETWEEN a AND b | 0.33 | p(<= ^ >=) | 0.25
> | NOT BETWEEN a AND b | 0.67 | 1 - p(BETWEEN) | 0.25
> The Calcite defaults were identified by inspection and verified by tests. The
> Calcite rules make sense if one considers conditional probability: that the
> user applied a particular expression to the data with the expectation that
> given that data set, the expression matches 25% of the rows.
> The probability of the IS NOT TRUE statement assumes the presence of nulls,
> while IS TRUE does not. This is an example of conditional probability. If the
> user asks if something is TRUE, we can assume that they are nor worried about
> nulls. If they ask if it is NOT FALSE, the only justification for such syntax
> is to include nulls. Since we assume nulls (when present) make up 10% of
> data, in such a case, half the non-null data is true, half is false.
> Note that, in the proposed implementation, each expression in an IS TRUE or
> similar clause is considered as a constant. That is, the following deliver
> different reduction factors:
> {code}
> a = 10
> (a = 10) IS TRUE
> {code}
> One could argue that the second should give the selectivity for "a = 10", but
> the code (at present) treats this the same as "b IS TRUE" where b just
> happens to be "a = 10".
> The rule for OR caps the reduction factor at 0.5 per standard practice. We
> assume values are independent, so the reduction is simply the sum of the
> individual items. (If data consists of "a", "b", "c" and "d", then p("a") =
> 25% and p("a" | "b" | "c" | "d" ) = 100%.
> The rule for BETWEEN arises because Calcite (or Drill?) rewrites {{a BETWEEN
> b AND c}} as {{a >= b AND a <= c}}.
> With the revised rules, the example WHERE reduction becomes:
> {code}
> col1_s20 in ('Value1','Value2','Value3','Value4',
> 'Value5','Value6','Value7','Value8','Value9') -- 50%
> AND col2_i <=3 -- 57%
> AND col3_s1 = 'Y' -- 15%
> AND col4_s1 = 'Y' -- 15%
> AND col5_s6 not like '%str1%' -- 85%
> AND col5_s6 not like '%str2%' -- 85%
> AND col5_s6 not like '%str3%' -- 85%
> AND col5_s6 not like '%str4%' -- 85%
> .5 * .57 * .15^2 * .85^4 = 0.003
> {code}
> The new rules are not a panacea: they are still just guesses. However, they
> are unbiased guesses based on the rules of probability which result in more
> conservative reductions of filters. The result may be better plans in queries
> with large conjunctions (large number of expressions AND'ed together.)
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
