[
https://issues.apache.org/jira/browse/CALCITE-7757?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Darpan Lunagariya (e6data) updated CALCITE-7757:
------------------------------------------------
Description:
h2. Summary
{{RelMdFunctionalDependency}} currently infers functional dependencies that do
not always hold under SQL null, grouping, ordinal, and value-equality semantics.
{{AggregateRemoveDuplicateKeysRule}} consumes this metadata and can
consequently remove a necessary grouping key, changing query results.
h2. Correctness problems
# *Outer-join equality dependencies* — {{LEFT}} and {{RIGHT}} joins must not
infer bidirectional functional dependencies from equality predicates when null
generation invalidates one direction.
# *Dependencies from null-generated inputs* — Outer joins must not blindly
preserve functional dependencies from the null-generated input because null
padding can invalidate them.
# *Incorrect Aggregate ordinal mapping* — Aggregate input group ordinals must
be mapped to packed output positions before exposing their functional
dependencies.
# *Equality-derived dependencies for approximate numerics* — Equality
predicates involving {{FLOAT}} or {{DOUBLE}} must not produce functional
dependencies when SQL equality and grouping equality differ.
# *Unsafe derived-expression dependencies* — Determinism alone is insufficient
for removing derived grouping expressions; unsafe scalar and nested types must
be rejected.
# *Grouping-set aggregate dependencies* — Grouping columns must not be assumed
to determine aggregate results when grouping sets can produce identical
null-padded keys.
# *Projected TableScan ordinals* — Table keys expressed in base-table ordinals
must not be applied directly to projected or reordered {{TableScan}} output
columns.
# *Unsafe generic unary-node passthrough* — Unknown single-input relational
nodes must not automatically inherit input functional dependencies because they
may change schema, values, or cardinality.
# *Join offsets with system fields* — Functional-dependency ordinals for join
inputs must account for system fields prefixed to the output, including semi
and anti joins.
# *Equality-derived dependencies for collated values* — Equality using a custom
collator can consider strings equal even when Enumerable grouping distinguishes
their Java keys, making the inferred dependency unsafe.
was:
h2. Summary
{{RelMdFunctionalDependency}} currently infers functional dependencies that do
not always hold under SQL null, grouping, ordinal, and value-equality semantics.
{{AggregateRemoveDuplicateKeysRule}} consumes this metadata and can
consequently remove a necessary grouping key, changing query results.
h2. Correctness problems
h3. 1. Outer-join equality dependencies
{{LEFT}} and {{RIGHT}} joins are handled like {{INNER}} joins. Equality
predicates currently create bidirectional dependencies even though
null-generated columns do not generally determine preserved-side columns.
For example:
{code:sql}
SELECT d.deptno, e.deptno, COUNT(*)
FROM emp e
LEFT JOIN dept d ON e.deptno = d.deptno
GROUP BY d.deptno, e.deptno
{code}
For unmatched rows, {{d.deptno}} is always {{NULL}}, but {{e.deptno}} can have
different values. Therefore:
{code}
d.deptno -> e.deptno
{code}
does not hold.
Even the opposite direction is not generally safe when the join has additional
predicates, because rows with the same preserved-side equality key may be
matched or unmatched.
h3. 2. Dependencies from the null-generated input
This problem does not depend on deriving a functional dependency from the join
condition.
{{RelMdFunctionalDependency}} first obtains the dependencies of both join
inputs. For a {{LEFT JOIN}}, it currently copies all dependencies from the
right input into the join result. However, null padding can invalidate a
dependency that was valid within the right input.
Consider:
{code:sql}
SELECT r.a, r.y, COUNT(*) AS c
FROM (VALUES (1), (2)) AS l(z)
LEFT JOIN (
SELECT z, a, COALESCE(a, 1) AS y
FROM (VALUES (1, CAST(NULL AS INTEGER))) AS v(z, a)
) AS r
ON l.z = r.z
GROUP BY r.a, r.y
{code}
Before the join, the right-side Project establishes {{r.a -> r.y}} because
{{r.y}} is the deterministic expression {{COALESCE(r.a, 1)}}.
The {{LEFT JOIN}} produces:
{code}
l.z=1: matched row -> r.a=NULL, r.y=1
l.z=2: unmatched row -> r.a=NULL, r.y=NULL
{code}
After null padding, both rows have the same value of {{r.a}} but different
values of {{r.y}}. Therefore {{r.a -> r.y}} no longer holds in the join result.
h3. 3. Incorrect Aggregate ordinal mapping
{{RelMdFunctionalDependency}} carries {{Aggregate}} input ordinals into the
{{Aggregate}} output without mapping the input {{groupSet}} indices to packed
output positions.
For example, after {{AggregateProjectMergeRule}}:
{code}
Aggregate input groupSet: {1, 2, 3}
Aggregate output key positions: {0, 1, 2}
{code}
An input dependency such as {{1 -> 2}} can therefore be incorrectly interpreted
as an output dependency between positions {{1}} and {{2}}. This can cause an
unrelated grouping column to be removed.
For example, given:
{code:sql}
SELECT a, b, c, COUNT(*)
FROM (
VALUES
(0, 1, 1, 10),
(0, 1, 1, 20)
) AS t(z, a, b, c)
WHERE a = b
GROUP BY a, b, c
{code}
The correct result contains two groups:
{code}
a=1, b=1, c=10, count=1
a=1, b=1, c=20, count=1
{code}
The incorrect rewrite removes {{c}} and produces one group with {{count=2}}.
h3. 4. Equality-derived dependencies for approximate numeric types
Filter and Join equality conditions infer bidirectional functional dependencies
without checking operand types.
For {{DOUBLE}}, SQL considers {{0.0 = -0.0}} true, while grouping can
distinguish the two values.
For example:
{code:sql}
SELECT x, y, COUNT(*)
FROM (
VALUES
(CAST(0 AS DOUBLE), CAST(0 AS DOUBLE)),
(CAST(0 AS DOUBLE), -CAST(0 AS DOUBLE))
) AS t(x, y)
WHERE x = y
GROUP BY x, y
{code}
The original query produces two groups with {{COUNT\(\*\) = 1}}. If {{y}} is
removed based on the inferred dependency {{x -> y}}, the rewritten query
produces one group with {{COUNT\(\*\) = 2}}.
Equality-derived dependencies therefore require conservative type and
equality-semantics checks.
h3. 5. Derived-expression dependencies require stronger safety checks
Project metadata currently assumes that a deterministic expression is
functionally determined by its referenced columns.
For safe types, this allows valid rewrites such as {{GROUP BY col, col + 2}} to
{{GROUP BY col}}
However, determinism alone does not guarantee that values considered equal for
grouping produce grouping-equivalent derived values.
At minimum, the implementation must conservatively handle:
* {{FLOAT}}
* {{DOUBLE}}
* {{INTERVAL}}
* Nested occurrences of those types
* Collated values
* Custom types with non-trivial equality semantics
* Open-ended container types whose runtime values may contain unsafe types
The required condition is stronger than determinism:
{code}
base values are grouping-equivalent
implies
derived values are grouping-equivalent
{code}
h2. Expected behavior
{{RelMdFunctionalDependency}} should only report dependencies that remain valid
under the relational expression's:
* Null-generation semantics
* Input-to-output ordinal mapping
* SQL equality semantics
* Grouping equality semantics
* Expression stability and type semantics
{{AggregateRemoveDuplicateKeysRule}} must leave the plan unchanged when a
dependency cannot be proven safely.
h2. Acceptance criteria
* Add functional-dependency metadata tests covering all five cases.
* Add {{AggregateRemoveDuplicateKeysRule}} wrong-result regression tests.
* Handle {{LEFT}} and {{RIGHT}} joins symmetrically and conservatively.
* Do not automatically preserve all dependencies from a null-generated input.
* Correctly map {{Aggregate}} input group ordinals to output positions.
* Add equality-compatibility checks for Filter and Join equality-derived
dependencies.
* Add recursive type-safety checks for derived-expression dependencies.
* Preserve valid existing optimizations, including:
{code}
GROUP BY col, col + 2
->
GROUP BY col
{code}
for types where the transformation is safe.
> RelMdFunctionalDependency can infer unsound dependencies and cause incorrect
> query results
> ------------------------------------------------------------------------------------------
>
> Key: CALCITE-7757
> URL: https://issues.apache.org/jira/browse/CALCITE-7757
> Project: Calcite
> Issue Type: Bug
> Components: core
> Affects Versions: 1.42.0
> Reporter: Darpan Lunagariya (e6data)
> Assignee: Darpan Lunagariya (e6data)
> Priority: Major
> Labels: pull-request-available
>
> h2. Summary
> {{RelMdFunctionalDependency}} currently infers functional dependencies that
> do not always hold under SQL null, grouping, ordinal, and value-equality
> semantics.
> {{AggregateRemoveDuplicateKeysRule}} consumes this metadata and can
> consequently remove a necessary grouping key, changing query results.
> h2. Correctness problems
> # *Outer-join equality dependencies* — {{LEFT}} and {{RIGHT}} joins must not
> infer bidirectional functional dependencies from equality predicates when
> null generation invalidates one direction.
> # *Dependencies from null-generated inputs* — Outer joins must not blindly
> preserve functional dependencies from the null-generated input because null
> padding can invalidate them.
> # *Incorrect Aggregate ordinal mapping* — Aggregate input group ordinals must
> be mapped to packed output positions before exposing their functional
> dependencies.
> # *Equality-derived dependencies for approximate numerics* — Equality
> predicates involving {{FLOAT}} or {{DOUBLE}} must not produce functional
> dependencies when SQL equality and grouping equality differ.
> # *Unsafe derived-expression dependencies* — Determinism alone is
> insufficient for removing derived grouping expressions; unsafe scalar and
> nested types must be rejected.
> # *Grouping-set aggregate dependencies* — Grouping columns must not be
> assumed to determine aggregate results when grouping sets can produce
> identical null-padded keys.
> # *Projected TableScan ordinals* — Table keys expressed in base-table
> ordinals must not be applied directly to projected or reordered {{TableScan}}
> output columns.
> # *Unsafe generic unary-node passthrough* — Unknown single-input relational
> nodes must not automatically inherit input functional dependencies because
> they may change schema, values, or cardinality.
> # *Join offsets with system fields* — Functional-dependency ordinals for join
> inputs must account for system fields prefixed to the output, including semi
> and anti joins.
> # *Equality-derived dependencies for collated values* — Equality using a
> custom collator can consider strings equal even when Enumerable grouping
> distinguishes their Java keys, making the inferred dependency unsafe.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
