[
https://issues.apache.org/jira/browse/CALCITE-7687?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Etienne Pelissier updated CALCITE-7687:
---------------------------------------
Description:
{{[RelMdSelectivity#getSelectivity|https://github.com/apache/calcite/blob/0211999427e294114db8f6b58cad95870cc13ccb/core/src/main/java/org/apache/calcite/rel/metadata/RelMdSelectivity.java#L178](Aggregate
rel, RelMetadataQuery mq, @Nullable RexNode predicate)}} method:
{code:java}
public @Nullable Double getSelectivity(Aggregate rel, RelMetadataQuery mq,
@Nullable RexNode predicate) {
...
RelOptUtil.splitFilters(
rel.getGroupSet(), // [2]
predicate,
pushable,
notPushable);
final RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
RexNode childPred =
RexUtil.composeConjunction(rexBuilder, pushable, true);
// [1]
Double selectivity = mq.getSelectivity(rel.getInput(), childPred);
...
}
{code}
and
{{{}[RelMdDistinctRowCount#getDistinctRowCount|https://github.com/apache/calcite/blob/0211999427e294114db8f6b58cad95870cc13ccb/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java#L168](Aggregate
rel, RelMetadataQuery mq, ImmutableBitSet groupKey, @Nullable RexNode
predicate){}}}:
{code:java}
public @Nullable Double getDistinctRowCount(Aggregate rel, RelMetadataQuery
mq,
ImmutableBitSet groupKey, @Nullable RexNode predicate) {
...
RelOptUtil.splitFilters(
ImmutableBitSet.range(rel.getGroupCount()),
predicate,
pushable,
notPushable);
final RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
RexNode childPreds =
RexUtil.composeConjunction(rexBuilder, pushable, true);
// set the bits as they correspond to the child input
ImmutableBitSet.Builder childKey = ImmutableBitSet.builder();
RelMdUtil.setAggChildKeys(groupKey, rel, childKey);
// [1]
Double distinctRowCount =
mq.getDistinctRowCount(rel.getInput(), childKey.build(), childPreds);
...
}
{code}
both currently pass down the predicate to their input [1] without considering
any possible translation, since an {{Aggregate}} derives its row type as
{{(group keys..., aggregate calls...)}} and so its output field {{i}} is input
field {{{}groupSet.nth(i\){}}}; hence when the Aggregate's input analyzes the
predicate, it can end up reading a different column from the one the predicate
names. Note that in the second method the group key beside it *is* translated,
by {{{}RelMdUtil.setAggChildKeys{}}}.
Unlike CALCITE-4414 the consequence is silent rather than an exception:
{{splitFilters}} only pushes conjuncts whose references are contained in the
bitmap it is given, so the index that reaches the input is always valid, it
simply names another field. The estimate does not change either as long as the
input keys only off {{{}SqlKind{}}}, which stock {{RelMdUtil.guessSelectivity}}
does. It becomes a wrong estimate for a table that supplies a
{{BuiltInMetadata.Selectivity.Handler}} or a
{{BuiltInMetadata.DistinctRowCount.Handler}} through
{{{}RelOptTable#unwrap{}}}, the hook added by CALCITE-4223 so that engines can
derive selectivity from column statistics. In the tests attached to the first
two comments such a handler is asked about column {{c}} and answers with column
{{{}b{}}}'s null fraction.
Note I: in a similar situation, {{RelMdSelectivity#getSelectivity(Project)}}
uses {{RelOptUtil.pushPastProject}} and
{{RelMdSelectivity#getSelectivity(Calc)}} uses {{RelOptUtil.pushPastCalc}}
(added by CALCITE-4414) to convert the predicate before passing it to the
input. There is no equivalent {{{}RelOptUtil.pushPastAggregate{}}}, which is
plausibly why these two overloads were missed.
Note II: in the first code snippet above, {{splitFilters}} is called at [2]
with {{{}rel.getGroupSet(){}}}, which holds *input* indices, while
{{predicate}} is expressed over the {*}output{*}; {{RelMdDistinctRowCount}}
passes {{ImmutableBitSet.range(rel.getGroupCount())}} for the same purpose, so
the two disagree. A predicate on a genuine group key can therefore be refused,
and a predicate on an aggregate call can be pushed — in the second test {{IS
NULL($2)}} on {{COUNT($0)}} is answered with a column's null fraction.
was:
This is the same defect as CALCITE-4414, but in the {{Aggregate}} overloads,
which were not swept [when that issue was
fixed|https://github.com/apache/calcite/commit/b4e399cb35224d8c8d55f02b7cf2b9649a3b28a4]
for {{Calc}} in 1.27.0.
An {{Aggregate}} derives its row type as {{{}(group keys..., agg calls...){}}},
so output field {{i}} is input field {{{}groupSet.nth(i\){}}}. Two metadata
handlers forward a predicate expressed over the aggregate's *output* to the
aggregate's *input* without applying that translation.
*Minimal repros covering both handlers are in the comments of this ticket.*
h3. 1. [RelMdSelectivity#getSelectivity(Aggregate,
...)|https://github.com/apache/calcite/blob/7939fa2163467205726764fb2e575f8b289c1b8b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdSelectivity.java#L178]
{code:java}
RelOptUtil.splitFilters(rel.getGroupSet(), predicate, pushable, notPushable);
RexNode childPred = RexUtil.composeConjunction(rexBuilder, pushable, true);
// childPred not translated
Double selectivity = mq.getSelectivity(rel.getInput(), childPred);{code}
Two independent problems.
*(a) No translation.* Exactly as in
[CALCITE-4414|https://github.com/apache/calcite/commit/b4e399cb35224d8c8d55f02b7cf2b9649a3b28a4].
Compare {{{}getSelectivity(Project, ...){}}}, which calls
{{RelOptUtil.pushPastProject}} before recursing, and {{{}getSelectivity(Calc,
...){}}}, which calls {{RelOptUtil.pushPastCalc}} since
[CALCITE-4414|https://github.com/apache/calcite/commit/b4e399cb35224d8c8d55f02b7cf2b9649a3b28a4].
*(b) Wrong pushability* *bitmap.* {{predicate}} is in output index space, but
{{rel.getGroupSet() }}holds *input* indices, so {{splitFilters}} compares the
two spaces against one another. The correct bitmap is
{{{}ImmutableBitSet.range(rel.getGroupCount()){}}}, which is what
{{RelMdDistinctRowCount}} already uses for the same purpose, so the two
handlers currently disagree.
h3. 2. [RelMdDistinctRowCount#getDistinctRowCount(Aggregate,
...)|https://github.com/apache/calcite/blob/7939fa2163467205726764fb2e575f8b289c1b8b/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java#L168]
{code:java}
RelOptUtil.splitFilters(
ImmutableBitSet.range(rel.getGroupCount()), predicate, pushable, notPushable);
RexNode childPreds = RexUtil.composeConjunction(rexBuilder, pushable, true);
// set the bits as they correspond to the child input
RelMdUtil.setAggChildKeys(groupKey, rel, childKey);
// childPreds not translated
Double distinctRowCount = mq.getDistinctRowCount(rel.getInput(),
childKey.build(), childPreds);{code}
One problem.
*(a) No translation.*
h3. 3. Symptom
Unlike CALCITE-4414, which threw {{{}ArrayIndexOutOfBoundsException{}}}, this
is silent.
{{splitFilters}} only pushes conjuncts whose refs are inside the bitmap, so the
pushed index is always valid: it just names a different column.
That is harmless while the handler below keys only off {{SqlKind
(RelMdUtil.guessSelectivity)}} , which is why it has gone unnoticed.
It becomes a *wrong estimate* for any table supplying a
{{BuiltInMetadata.Selectivity.Handler}} through {{{}RelOptTable.unwrap{}}}.
h3. 4. Suggested fix
[{{FlinkRelMdUtil.splitPredicateOnAgg}}|https://github.com/apache/flink/blob/12197ea92a5667073bc0c6810e526a39979d835c/flink-table/flink-table-planner/src/main/scala/org/apache/flink/table/planner/plan/utils/FlinkRelMdUtil.scala#L556]
already addresses both problems:
{code:java}
RelOptUtil.splitFilters(ImmutableBitSet.range(0, numOfGroupKey), predicate,
pushable, notPushable)
val adjustments = new Array[Int](aggOutputFields.size)
grouping.zipWithIndex.foreach { case (bit, index) => adjustments(index) = bit -
index }
pushCondition.accept(new RelOptUtil.RexInputConverter(
rexBuilder, aggOutputFields, aggInputFields, adjustments)){code}
{{RexInputConverter}} is already used this way by both {{Union}} handlers. A
{{RelOptUtil.pushPastAggregate}} helper alongside {{pushPastProject}} /
{{pushPastCalc}} would let both handlers share one implementation.
h3. 5. Downstream impact
*Drill* - most exposed:
[{{DrillRelMdSelectivity#getScanSelectivity}}|https://github.com/apache/drill/blob/23bc6619705fe4f625a4dbe68e0044bd8dead73b/exec/java-exec/src/main/java/org/apache/drill/exec/planner/cost/DrillRelMdSelectivity.java#L117]
consults per-column statistics, so this is a wrong estimate rather than a
differently-wrong constant. Neither Drill handler overrides {{{}Aggregate{}}}.
*Hive* - neither handler overrides {{{}Aggregate{}}}.
*Kylin* - {{{}DefaultRelMetadataProvider{}}}, no custom handlers.
*Flink* - unaffected (fix above).
> RelMdSelectivity and RelMdDistinctRowCount for Aggregate can propagate a
> predicate with wrong references
> --------------------------------------------------------------------------------------------------------
>
> Key: CALCITE-7687
> URL: https://issues.apache.org/jira/browse/CALCITE-7687
> Project: Calcite
> Issue Type: Bug
> Components: core
> Affects Versions: 1.42.0
> Reporter: Etienne Pelissier
> Assignee: Etienne Pelissier
> Priority: Minor
> Labels: in-progress, pull-request-available
>
> {{[RelMdSelectivity#getSelectivity|https://github.com/apache/calcite/blob/0211999427e294114db8f6b58cad95870cc13ccb/core/src/main/java/org/apache/calcite/rel/metadata/RelMdSelectivity.java#L178](Aggregate
> rel, RelMetadataQuery mq, @Nullable RexNode predicate)}} method:
> {code:java}
> public @Nullable Double getSelectivity(Aggregate rel, RelMetadataQuery mq,
> @Nullable RexNode predicate) {
> ...
> RelOptUtil.splitFilters(
> rel.getGroupSet(), // [2]
> predicate,
> pushable,
> notPushable);
> final RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
> RexNode childPred =
> RexUtil.composeConjunction(rexBuilder, pushable, true);
> // [1]
> Double selectivity = mq.getSelectivity(rel.getInput(), childPred);
> ...
> }
> {code}
> and
> {{{}[RelMdDistinctRowCount#getDistinctRowCount|https://github.com/apache/calcite/blob/0211999427e294114db8f6b58cad95870cc13ccb/core/src/main/java/org/apache/calcite/rel/metadata/RelMdDistinctRowCount.java#L168](Aggregate
> rel, RelMetadataQuery mq, ImmutableBitSet groupKey, @Nullable RexNode
> predicate){}}}:
> {code:java}
> public @Nullable Double getDistinctRowCount(Aggregate rel, RelMetadataQuery
> mq,
> ImmutableBitSet groupKey, @Nullable RexNode predicate) {
> ...
> RelOptUtil.splitFilters(
> ImmutableBitSet.range(rel.getGroupCount()),
> predicate,
> pushable,
> notPushable);
> final RexBuilder rexBuilder = rel.getCluster().getRexBuilder();
> RexNode childPreds =
> RexUtil.composeConjunction(rexBuilder, pushable, true);
> // set the bits as they correspond to the child input
> ImmutableBitSet.Builder childKey = ImmutableBitSet.builder();
> RelMdUtil.setAggChildKeys(groupKey, rel, childKey);
> // [1]
> Double distinctRowCount =
> mq.getDistinctRowCount(rel.getInput(), childKey.build(), childPreds);
> ...
> }
> {code}
> both currently pass down the predicate to their input [1] without considering
> any possible translation, since an {{Aggregate}} derives its row type as
> {{(group keys..., aggregate calls...)}} and so its output field {{i}} is
> input field {{{}groupSet.nth(i\){}}}; hence when the Aggregate's input
> analyzes the predicate, it can end up reading a different column from the one
> the predicate names. Note that in the second method the group key beside it
> *is* translated, by {{{}RelMdUtil.setAggChildKeys{}}}.
> Unlike CALCITE-4414 the consequence is silent rather than an exception:
> {{splitFilters}} only pushes conjuncts whose references are contained in the
> bitmap it is given, so the index that reaches the input is always valid, it
> simply names another field. The estimate does not change either as long as
> the input keys only off {{{}SqlKind{}}}, which stock
> {{RelMdUtil.guessSelectivity}} does. It becomes a wrong estimate for a table
> that supplies a {{BuiltInMetadata.Selectivity.Handler}} or a
> {{BuiltInMetadata.DistinctRowCount.Handler}} through
> {{{}RelOptTable#unwrap{}}}, the hook added by CALCITE-4223 so that engines
> can derive selectivity from column statistics. In the tests attached to the
> first two comments such a handler is asked about column {{c}} and answers
> with column {{{}b{}}}'s null fraction.
> Note I: in a similar situation, {{RelMdSelectivity#getSelectivity(Project)}}
> uses {{RelOptUtil.pushPastProject}} and
> {{RelMdSelectivity#getSelectivity(Calc)}} uses {{RelOptUtil.pushPastCalc}}
> (added by CALCITE-4414) to convert the predicate before passing it to the
> input. There is no equivalent {{{}RelOptUtil.pushPastAggregate{}}}, which is
> plausibly why these two overloads were missed.
> Note II: in the first code snippet above, {{splitFilters}} is called at [2]
> with {{{}rel.getGroupSet(){}}}, which holds *input* indices, while
> {{predicate}} is expressed over the {*}output{*}; {{RelMdDistinctRowCount}}
> passes {{ImmutableBitSet.range(rel.getGroupCount())}} for the same purpose,
> so the two disagree. A predicate on a genuine group key can therefore be
> refused, and a predicate on an aggregate call can be pushed — in the second
> test {{IS NULL($2)}} on {{COUNT($0)}} is answered with a column's null
> fraction.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
