[ 
https://issues.apache.org/jira/browse/SPARK-62042?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Xi Liang updated SPARK-62042:
-----------------------------
    Affects Version/s: 3.0.3
                       3.1.3
          Description: 
Nested column aliasing ({{NestedColumnAliasing}} and 
{{GeneratorNestedColumnAliasing}}, applied by {{ColumnPruning}}) replaces a 
nested field access with an alias that it evaluates in a new {{Project}} below 
an operator. It does this for a non-deterministic access too. The optimizer may 
change which values a non-deterministic expression returns, but not how many 
times it is evaluated: the scaladoc of {{Expression.deterministic}} says "The 
non-deterministic expressions should not change in number and order." A query's 
select list is evaluated once per row of its input, but the alias is evaluated 
once per row of the operator's input. When the operator repeats input rows, as 
a join, an explode or a sample with replacement does, every output row built 
from one input row then shares one evaluation.

This can be seen without randomness. In the queries below, each row reads 
{{monotonically_increasing_id()}} twice in one select list: as {{m}}, and as 
{{v}} through an access of {{s.arr}}, whose element i has {{x}} = i. As 
written, the query evaluates both once per row of the select list's input. By 
its documentation, {{monotonically_increasing_id()}} puts the partition ID in 
the upper 31 bits and the record number within the partition in the lower 33 
bits, so two calls evaluated for the same row return the same value, whatever 
the partitioning. {{% 1000}} maps both the same way and keeps the index in 
0..999, and {{s.arr}} is never null, so the index is evaluated on every row. So 
every row should have v = m. On master, with AQE on and off:

{code:sql}
CREATE TABLE t1 USING parquet AS
SELECT 1 AS id,
  named_struct('arr', transform(sequence(0, 999), i -> named_struct('x', i, 
'y', i)), 'e', 0) AS s,
  sequence(1, 1000) AS seq;
CREATE TABLE t2 USING parquet AS SELECT 1 AS id FROM range(1000);

-- 1000 joined rows: (rows, rows with v != m)
SELECT count(*), sum(CASE WHEN v != m THEN 1 ELSE 0 END) FROM (SELECT 
s.arr[CAST(monotonically_increasing_id() % 1000 AS INT)].x AS v, 
CAST(monotonically_increasing_id() % 1000 AS INT) AS m FROM t1 JOIN t2 ON t1.id 
= t2.id);
-- expected: 1000, 0
-- actual:   1000, 999

-- 1000 exploded rows: (rows, rows with v != m, sum(n)); the query also reads n 
(see below)
SELECT count(*), sum(CASE WHEN v != m THEN 1 ELSE 0 END), sum(n) FROM (SELECT 
s.arr[CAST(monotonically_increasing_id() % 1000 AS INT)].x AS v, 
CAST(monotonically_increasing_id() % 1000 AS INT) AS m, n FROM t1 LATERAL VIEW 
explode(seq) g AS n);
-- expected: 1000, 0, 500500
-- actual:   1000, 999, 500500
{code}

The access in {{v}} is evaluated once, for the one row of {{t1}}, below the 
join or the explode, so {{v}} is the same in every row while {{m}} counts up. 
The nonzero counts in this ticket come from local runs and depend on the 
partitioning; any nonzero count shows the bug.

The same queries on released versions (pyspark from PyPI) and with nested 
column aliasing turned off by its confs, with AQE on and off; each cell is the 
number of rows, out of 1000, with v != m:

||Run||join||explode||
|2.4.8|0|0|
|3.0.3|0|999|
|3.1.3, 4.0.0 and 4.3.0|999|999|
|4.3.0 with {{spark.sql.optimizer.nestedSchemaPruning.enabled}} and 
{{spark.sql.optimizer.expression.nestedPruning.enabled}} off|0|0|

The explode case dates from SPARK-27707 (3.0.0), which made {{ColumnPruning}} 
alias nested field accesses below a {{Generate}}; 2.4.8 has no nested column 
aliasing. The join case dates from SPARK-31736 (3.1.0), which made nested 
column aliasing work through a join. 4.1.0 and 4.2.0 have the same 
{{NestedColumnAliasing.canAlias}} (the check that decides whether an access may 
be aliased) and the same lists of operators that nested column aliasing aliases 
below as 4.0.0 and 4.3.0, by reading the code; they were not run, and 3.2.x to 
3.5.x were not run either.

The bug also shows as a random pick from a nested array that returns the same 
element in every output row. Over the same tables, on master, 4.0.0 and 4.3.0, 
with AQE on and off:

{code:sql}
-- 1000 joined rows, each picking a random element of s.arr: (rows, distinct 
values)
SELECT count(*), count(DISTINCT v) FROM (SELECT s.arr[CAST(rand(0) * 1000 AS 
INT)].x AS v FROM t1 JOIN t2 ON t1.id = t2.id);
-- expected: 1000, about 632
-- actual:   1000, 1

-- 1000 exploded rows, each picking a random element of s.arr
SELECT count(*), count(DISTINCT v), sum(n) FROM (SELECT s.arr[CAST(rand(0) * 
1000 AS INT)].x AS v, n FROM t1 LATERAL VIEW explode(seq) g AS n);
-- expected: 1000, about 632, 500500
-- actual:   1000, 1, 500500
{code}

1000 random picks from 1000 values give about 632 distinct values on average.

The optimized plan of the random-pick join query's subquery evaluates the 
access below the join, once for the one row of {{t1}}:

{code}
Project [_extract_x#240 AS v#237]
+- Join Inner, (id#135 = id#138)
   :- Filter isnotnull(id#135)
   :  +- Project [id#135, s#136.arr[cast((rand(0) * 1000.0) as int)].x AS 
_extract_x#240]
   :     +- Relation spark_catalog.default.t1[id#135,s#136,seq#137] parquet
   +- Filter isnotnull(id#138)
      +- Relation spark_catalog.default.t2[id#138] parquet
{code}

On master, these also give one distinct value: {{shuffle(s.arr, 0)\[0\].x}} 
over the join (1000 rows), a random index into a top-level array column (below, 
1000 rows) and a sample with replacement (below, 1016 rows).

{code:sql}
CREATE TABLE t4 USING parquet AS SELECT 1 AS id, transform(sequence(0, 999), i 
-> named_struct('b', i, 'c', i)) AS a;
SELECT count(*), count(DISTINCT v) FROM (SELECT a[CAST(rand(0) * 1000 AS 
INT)].b AS v FROM t4 JOIN t2 ON t4.id = t2.id);
{code}

{code:scala}
spark.table("t1").sample(withReplacement = true, fraction = 1000.0, seed = 0)
  .selectExpr("s.arr[CAST(rand(0) * 1000 AS INT)].x AS v")
  .selectExpr("count(*)", "count(DISTINCT v)")
{code}

The join case needs {{spark.sql.optimizer.nestedSchemaPruning.enabled}} 
(default true): with it off, the random-pick join query gives 630 distinct 
values. The explode case needs 
{{spark.sql.optimizer.nestedSchemaPruning.enabled}} or 
{{spark.sql.optimizer.expression.nestedPruning.enabled}} (also default true): 
with only {{spark.sql.optimizer.nestedSchemaPruning.enabled}} off, the 
random-pick explode query still gives 1 distinct value. The explode case also 
needs the query to read the generator output {{n}}: without {{n}} in the 
subquery's select list (and without {{sum(n)}}), the random-pick explode query 
gives 630 distinct values. By reading the code, {{ColumnPruning}} has an 
earlier case for a {{Project}} above a {{Generate}} that does not read all of 
the {{Generate}}'s output; it matches such a {{Project}} on every iteration, so 
{{GeneratorNestedColumnAliasing}} never sees it.


  was:
Nested column aliasing ({{NestedColumnAliasing}} and 
{{GeneratorNestedColumnAliasing}}, applied by {{ColumnPruning}}) replaces a 
nested field access with an alias that it evaluates in a new {{Project}} below 
an operator. It does this for a non-deterministic access too. A query's select 
list is evaluated once per row of its input, so a non-deterministic expression 
in it should give each row its own value, but the alias is evaluated once per 
row of the operator's input. When the operator repeats input rows, as a join, 
an explode or a sample with replacement does, every output row built from one 
input row then gets the same value.

On master, and on 4.0.0 and 4.3.0 (pyspark from PyPI), with AQE on and off:

{code:sql}
CREATE TABLE t1 USING parquet AS
SELECT 1 AS id,
  named_struct('arr', transform(sequence(0, 999), i -> named_struct('x', i, 
'y', i)), 'e', 0) AS s,
  sequence(1, 1000) AS seq;
CREATE TABLE t2 USING parquet AS SELECT 1 AS id FROM range(1000);

-- 1000 joined rows, each picking a random element of s.arr
SELECT count(*), count(DISTINCT v) FROM (SELECT s.arr[CAST(rand(0) * 1000 AS 
INT)].x AS v FROM t1 JOIN t2 ON t1.id = t2.id);
-- expected: 1000, about 632
-- actual:   1000, 1

-- 1000 exploded rows, each picking a random element of s.arr (the query also 
reads n; see below)
SELECT count(*), count(DISTINCT v), sum(n) FROM (SELECT s.arr[CAST(rand(0) * 
1000 AS INT)].x AS v, n FROM t1 LATERAL VIEW explode(seq) g AS n);
-- expected: 1000, about 632, 500500
-- actual:   1000, 1, 500500

-- control: the same random pick from seq, an array of integers; seq[...] has 
no struct
-- field access, so nested column aliasing leaves it alone
SELECT count(*), count(DISTINCT v) FROM (SELECT seq[CAST(rand(0) * 1000 AS 
INT)] AS v FROM t1 JOIN t2 ON t1.id = t2.id);
-- actual: 1000, 630
{code}

1000 random picks from 1000 values give about 632 distinct values on average; 
with seed 0, the control gives 630. The exact counts in this ticket come from 
local runs and can differ with the partitioning; the signal is one value versus 
about 632.

The optimized plan of the first query's subquery evaluates the access below the 
join, once for the one row of {{t1}}:

{code}
Project [_extract_x#240 AS v#237]
+- Join Inner, (id#135 = id#138)
   :- Filter isnotnull(id#135)
   :  +- Project [id#135, s#136.arr[cast((rand(0) * 1000.0) as int)].x AS 
_extract_x#240]
   :     +- Relation spark_catalog.default.t1[id#135,s#136,seq#137] parquet
   +- Filter isnotnull(id#138)
      +- Relation spark_catalog.default.t2[id#138] parquet
{code}

Other accesses and operators behave the same. On master, over {{t1}}, {{t2}} 
and a new table {{t4}}, each of these gives one distinct value:

{code:sql}
-- 1000 rows
SELECT s.arr[CAST(monotonically_increasing_id() % 1000 AS INT)].x AS v FROM t1 
JOIN t2 ON t1.id = t2.id;
-- 1000 rows
SELECT shuffle(s.arr, 0)[0].x AS v FROM t1 JOIN t2 ON t1.id = t2.id;
CREATE TABLE t4 USING parquet AS SELECT 1 AS id, transform(sequence(0, 999), i 
-> named_struct('b', i, 'c', i)) AS a;
-- a random index into the top-level array column a: 1000 rows
SELECT a[CAST(rand(0) * 1000 AS INT)].b AS v FROM t4 JOIN t2 ON t4.id = t2.id;
{code}

{code:scala}
// a sample with replacement: 1016 rows
spark.table("t1").sample(withReplacement = true, fraction = 1000.0, seed = 0)
  .selectExpr("s.arr[CAST(rand(0) * 1000 AS INT)].x AS v")
{code}

The join case needs {{spark.sql.optimizer.nestedSchemaPruning.enabled}} 
(default true): with it off, the join query gives 630 distinct values. The 
explode case needs {{spark.sql.optimizer.nestedSchemaPruning.enabled}} or 
{{spark.sql.optimizer.expression.nestedPruning.enabled}} (also default true): 
with only {{spark.sql.optimizer.nestedSchemaPruning.enabled}} off, the explode 
query still gives 1, and with both off, 630. The explode case also needs the 
query to read the generator output {{n}}: without {{n}} in the subquery's 
select list, the explode query gives 630. By reading the code, 
{{ColumnPruning}} has an earlier case for a {{Project}} above a {{Generate}} 
that does not read all of the {{Generate}}'s output; it matches such a 
{{Project}} on every iteration, so {{GeneratorNestedColumnAliasing}} never sees 
it.

4.1.0 and 4.2.0 have the same {{NestedColumnAliasing.canAlias}} and the same 
lists of operators that nested column aliasing aliases below, by reading the 
code; they were not run. The join case dates from SPARK-31736 (3.1.0), which 
made nested column aliasing work through a join. The changes that introduced 
the explode and sample cases were not looked up, and 3.x was not run.



> Exclude non-deterministic nested field accesses from nested column aliasing
> ---------------------------------------------------------------------------
>
>                 Key: SPARK-62042
>                 URL: https://issues.apache.org/jira/browse/SPARK-62042
>             Project: Spark
>          Issue Type: Bug
>          Components: SQL
>    Affects Versions: 3.0.3, 3.1.3, 4.1.0, 4.0.0, 4.2.0, 4.3.0, 5.0.0
>            Reporter: Xi Liang
>            Priority: Major
>              Labels: correctness, pull-request-available
>
> Nested column aliasing ({{NestedColumnAliasing}} and 
> {{GeneratorNestedColumnAliasing}}, applied by {{ColumnPruning}}) replaces a 
> nested field access with an alias that it evaluates in a new {{Project}} 
> below an operator. It does this for a non-deterministic access too. The 
> optimizer may change which values a non-deterministic expression returns, but 
> not how many times it is evaluated: the scaladoc of 
> {{Expression.deterministic}} says "The non-deterministic expressions should 
> not change in number and order." A query's select list is evaluated once per 
> row of its input, but the alias is evaluated once per row of the operator's 
> input. When the operator repeats input rows, as a join, an explode or a 
> sample with replacement does, every output row built from one input row then 
> shares one evaluation.
> This can be seen without randomness. In the queries below, each row reads 
> {{monotonically_increasing_id()}} twice in one select list: as {{m}}, and as 
> {{v}} through an access of {{s.arr}}, whose element i has {{x}} = i. As 
> written, the query evaluates both once per row of the select list's input. By 
> its documentation, {{monotonically_increasing_id()}} puts the partition ID in 
> the upper 31 bits and the record number within the partition in the lower 33 
> bits, so two calls evaluated for the same row return the same value, whatever 
> the partitioning. {{% 1000}} maps both the same way and keeps the index in 
> 0..999, and {{s.arr}} is never null, so the index is evaluated on every row. 
> So every row should have v = m. On master, with AQE on and off:
> {code:sql}
> CREATE TABLE t1 USING parquet AS
> SELECT 1 AS id,
>   named_struct('arr', transform(sequence(0, 999), i -> named_struct('x', i, 
> 'y', i)), 'e', 0) AS s,
>   sequence(1, 1000) AS seq;
> CREATE TABLE t2 USING parquet AS SELECT 1 AS id FROM range(1000);
> -- 1000 joined rows: (rows, rows with v != m)
> SELECT count(*), sum(CASE WHEN v != m THEN 1 ELSE 0 END) FROM (SELECT 
> s.arr[CAST(monotonically_increasing_id() % 1000 AS INT)].x AS v, 
> CAST(monotonically_increasing_id() % 1000 AS INT) AS m FROM t1 JOIN t2 ON 
> t1.id = t2.id);
> -- expected: 1000, 0
> -- actual:   1000, 999
> -- 1000 exploded rows: (rows, rows with v != m, sum(n)); the query also reads 
> n (see below)
> SELECT count(*), sum(CASE WHEN v != m THEN 1 ELSE 0 END), sum(n) FROM (SELECT 
> s.arr[CAST(monotonically_increasing_id() % 1000 AS INT)].x AS v, 
> CAST(monotonically_increasing_id() % 1000 AS INT) AS m, n FROM t1 LATERAL 
> VIEW explode(seq) g AS n);
> -- expected: 1000, 0, 500500
> -- actual:   1000, 999, 500500
> {code}
> The access in {{v}} is evaluated once, for the one row of {{t1}}, below the 
> join or the explode, so {{v}} is the same in every row while {{m}} counts up. 
> The nonzero counts in this ticket come from local runs and depend on the 
> partitioning; any nonzero count shows the bug.
> The same queries on released versions (pyspark from PyPI) and with nested 
> column aliasing turned off by its confs, with AQE on and off; each cell is 
> the number of rows, out of 1000, with v != m:
> ||Run||join||explode||
> |2.4.8|0|0|
> |3.0.3|0|999|
> |3.1.3, 4.0.0 and 4.3.0|999|999|
> |4.3.0 with {{spark.sql.optimizer.nestedSchemaPruning.enabled}} and 
> {{spark.sql.optimizer.expression.nestedPruning.enabled}} off|0|0|
> The explode case dates from SPARK-27707 (3.0.0), which made {{ColumnPruning}} 
> alias nested field accesses below a {{Generate}}; 2.4.8 has no nested column 
> aliasing. The join case dates from SPARK-31736 (3.1.0), which made nested 
> column aliasing work through a join. 4.1.0 and 4.2.0 have the same 
> {{NestedColumnAliasing.canAlias}} (the check that decides whether an access 
> may be aliased) and the same lists of operators that nested column aliasing 
> aliases below as 4.0.0 and 4.3.0, by reading the code; they were not run, and 
> 3.2.x to 3.5.x were not run either.
> The bug also shows as a random pick from a nested array that returns the same 
> element in every output row. Over the same tables, on master, 4.0.0 and 
> 4.3.0, with AQE on and off:
> {code:sql}
> -- 1000 joined rows, each picking a random element of s.arr: (rows, distinct 
> values)
> SELECT count(*), count(DISTINCT v) FROM (SELECT s.arr[CAST(rand(0) * 1000 AS 
> INT)].x AS v FROM t1 JOIN t2 ON t1.id = t2.id);
> -- expected: 1000, about 632
> -- actual:   1000, 1
> -- 1000 exploded rows, each picking a random element of s.arr
> SELECT count(*), count(DISTINCT v), sum(n) FROM (SELECT s.arr[CAST(rand(0) * 
> 1000 AS INT)].x AS v, n FROM t1 LATERAL VIEW explode(seq) g AS n);
> -- expected: 1000, about 632, 500500
> -- actual:   1000, 1, 500500
> {code}
> 1000 random picks from 1000 values give about 632 distinct values on average.
> The optimized plan of the random-pick join query's subquery evaluates the 
> access below the join, once for the one row of {{t1}}:
> {code}
> Project [_extract_x#240 AS v#237]
> +- Join Inner, (id#135 = id#138)
>    :- Filter isnotnull(id#135)
>    :  +- Project [id#135, s#136.arr[cast((rand(0) * 1000.0) as int)].x AS 
> _extract_x#240]
>    :     +- Relation spark_catalog.default.t1[id#135,s#136,seq#137] parquet
>    +- Filter isnotnull(id#138)
>       +- Relation spark_catalog.default.t2[id#138] parquet
> {code}
> On master, these also give one distinct value: {{shuffle(s.arr, 0)\[0\].x}} 
> over the join (1000 rows), a random index into a top-level array column 
> (below, 1000 rows) and a sample with replacement (below, 1016 rows).
> {code:sql}
> CREATE TABLE t4 USING parquet AS SELECT 1 AS id, transform(sequence(0, 999), 
> i -> named_struct('b', i, 'c', i)) AS a;
> SELECT count(*), count(DISTINCT v) FROM (SELECT a[CAST(rand(0) * 1000 AS 
> INT)].b AS v FROM t4 JOIN t2 ON t4.id = t2.id);
> {code}
> {code:scala}
> spark.table("t1").sample(withReplacement = true, fraction = 1000.0, seed = 0)
>   .selectExpr("s.arr[CAST(rand(0) * 1000 AS INT)].x AS v")
>   .selectExpr("count(*)", "count(DISTINCT v)")
> {code}
> The join case needs {{spark.sql.optimizer.nestedSchemaPruning.enabled}} 
> (default true): with it off, the random-pick join query gives 630 distinct 
> values. The explode case needs 
> {{spark.sql.optimizer.nestedSchemaPruning.enabled}} or 
> {{spark.sql.optimizer.expression.nestedPruning.enabled}} (also default true): 
> with only {{spark.sql.optimizer.nestedSchemaPruning.enabled}} off, the 
> random-pick explode query still gives 1 distinct value. The explode case also 
> needs the query to read the generator output {{n}}: without {{n}} in the 
> subquery's select list (and without {{sum(n)}}), the random-pick explode 
> query gives 630 distinct values. By reading the code, {{ColumnPruning}} has 
> an earlier case for a {{Project}} above a {{Generate}} that does not read all 
> of the {{Generate}}'s output; it matches such a {{Project}} on every 
> iteration, so {{GeneratorNestedColumnAliasing}} never sees it.



--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to