[
https://issues.apache.org/jira/browse/CALCITE-7757?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Darpan Lunagariya (e6data) updated CALCITE-7757:
------------------------------------------------
Labels: rel (was: )
> 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: rel
>
> 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.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
