Darpan Lunagariya (e6data) created CALCITE-7757:
---------------------------------------------------
Summary: 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)
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. 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. 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. 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. 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. 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.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
