[
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
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.
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
>
> 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)
