Multiple calls to the same `volatile` function do not produce different answers

[alamb]

Describe the bug

When I call a function like random() twice I expect to get different values, but I only get a single value

To Reproduce

❯ select random() r1, random() r2;
+--------------------+--------------------+
| r1                 | r2                 |
+--------------------+--------------------+
| 0.5798857099939392 | 0.5798857099939392 |
+--------------------+--------------------+
1 row in set. Query took 0.002 seconds.

Expected behavior

I expect the values from the two different calls to random() to be different

Additional context

The explain plan shows what is wrong:

❯ explain select random() r1, random() r2;
+---------------+--------------------------------------------------------------------+
| plan_type     | plan                                                               |
+---------------+--------------------------------------------------------------------+
| logical_plan  | Projection: random() AS random() AS r1, random() AS random() AS r2 |
|               |   Projection: random() AS random()                                 |
|               |     EmptyRelation                                                  |
| physical_plan | ProjectionExec: expr=[random()@0 as r1, random()@0 as r2]          |
|               |   ProjectionExec: expr=[random()]                                  |
|               |     PlaceholderRowExec                                             |
|               |                                                                    |
+---------------+--------------------------------------------------------------------+

And explain verbose shows the problem is introduced in logical_plan after common_sub_expression_eliminate:

❯ explain verbose select random() r1, random() r2;
+------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------+
| plan_type                                                  | plan                                                                                                                          |
+------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------+
| initial_logical_plan                                       | Projection: random() AS r1, random() AS r2                                                                                    |
|                                                            |   EmptyRelation                                                                                                               |
| logical_plan after inline_table_scan                       | SAME TEXT AS ABOVE                                                                                                            |
....
                                                                                               |
| logical_plan after eliminate_cross_join                    | SAME TEXT AS ABOVE                                                                                                            |
| logical_plan after common_sub_expression_eliminate         | Projection: random() AS random() AS r1, random() AS random() AS r2                                                            |
|                                                            |   Projection: random() AS random()                                                                                            |
|                                                            |     EmptyRelation

[alamb]

Interestingly 2a69244 gets the right answers;

$ git checkout 2a692446f46ef96f48eb9ba19231e9576be9ff5a
$ cd datafusion-cli
$ cargo run
...

DataFusion CLI v33.0.0
❯ select random() r1, random() r2;
+--------------------+--------------------+
| r1                 | r2                 |
+--------------------+--------------------+
| 0.9618989885434452 | 0.8635457246459088 |
+--------------------+--------------------+
1 row in set. Query took 0.025 seconds.

It looks like push_down_projection undoes the optimization somehow

Details

❯ explain verbose select random() r1, random() r2;
+------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------+
| plan_type                                                  | plan                                                                                                                      |
+------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------+
| initial_logical_plan                                       | Projection: random() AS r1, random() AS r2                                                                                |
|                                                            |   EmptyRelation                                                                                                           |
| logical_plan after inline_table_scan                       | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after type_coercion                           | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after count_wildcard_rule                     | SAME TEXT AS ABOVE                                                                                                        |
| analyzed_logical_plan                                      | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_nested_union                  | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after unwrap_cast_in_comparison               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after replace_distinct_aggregate              | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_join                          | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after decorrelate_predicate_subquery          | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after scalar_subquery_to_join                 | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after extract_equijoin_predicate              | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after merge_projection                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after rewrite_disjunctive_predicate           | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_duplicated_expr               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_filter                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_cross_join                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after common_sub_expression_eliminate         | Projection: random() AS random() AS r1, random() AS random() AS r2                                                        |
|                                                            |   Projection: random() AS random()                                                                                        |
|                                                            |     EmptyRelation                                                                                                         |
| logical_plan after eliminate_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after propagate_empty_relation                | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_one_union                     | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after filter_null_join_keys                   | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_outer_join                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_filter                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after single_distinct_aggregation_to_group_by | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after unwrap_cast_in_comparison               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after common_sub_expression_eliminate         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_projection                    | Projection: random() AS random() AS r1, random() AS random() AS r2                                                        |
|                                                            |   EmptyRelation                                                                                                           |
| logical_plan after eliminate_projection                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_nested_union                  | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after unwrap_cast_in_comparison               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after replace_distinct_aggregate              | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_join                          | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after decorrelate_predicate_subquery          | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after scalar_subquery_to_join                 | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after extract_equijoin_predicate              | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after merge_projection                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after rewrite_disjunctive_predicate           | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_duplicated_expr               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_filter                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_cross_join                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after common_sub_expression_eliminate         | Projection: random() AS random() AS random() AS r1, random() AS random() AS random() AS r2                                |
|                                                            |   Projection: random() AS random()                                                                                        |
|                                                            |     EmptyRelation                                                                                                         |
| logical_plan after eliminate_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after propagate_empty_relation                | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_one_union                     | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after filter_null_join_keys                   | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_outer_join                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_filter                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after single_distinct_aggregation_to_group_by | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after unwrap_cast_in_comparison               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after common_sub_expression_eliminate         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_projection                    | Projection: random() AS random() AS random() AS r1, random() AS random() AS random() AS r2                                |
|                                                            |   EmptyRelation                                                                                                           |
| logical_plan after eliminate_projection                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_nested_union                  | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after unwrap_cast_in_comparison               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after replace_distinct_aggregate              | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_join                          | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after decorrelate_predicate_subquery          | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after scalar_subquery_to_join                 | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after extract_equijoin_predicate              | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after merge_projection                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after rewrite_disjunctive_predicate           | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_duplicated_expr               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_filter                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_cross_join                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after common_sub_expression_eliminate         | Projection: random() AS random() AS random() AS random() AS r1, random() AS random() AS random() AS random() AS r2        |
|                                                            |   Projection: random() AS random()                                                                                        |
|                                                            |     EmptyRelation                                                                                                         |
| logical_plan after eliminate_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after propagate_empty_relation                | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_one_union                     | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after filter_null_join_keys                   | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after eliminate_outer_join                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_filter                        | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after single_distinct_aggregation_to_group_by | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after simplify_expressions                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after unwrap_cast_in_comparison               | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after common_sub_expression_eliminate         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_projection                    | Projection: random() AS random() AS random() AS random() AS r1, random() AS random() AS random() AS random() AS r2        |
|                                                            |   EmptyRelation                                                                                                           |
| logical_plan after eliminate_projection                    | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan after push_down_limit                         | SAME TEXT AS ABOVE                                                                                                        |
| logical_plan                                               | Projection: random() AS random() AS random() AS random() AS r1, random() AS random() AS random() AS random() AS r2        |
|                                                            |   EmptyRelation                                                                                                           |
| initial_physical_plan                                      | ProjectionExec: expr=[random() as r1, random() as r2]                                                                     |
|                                                            |   EmptyExec: produce_one_row=true                                                                                         |
|                                                            |                                                                                                                           |
| initial_physical_plan_with_stats                           | ProjectionExec: expr=[random() as r1, random() as r2], statistics=[Rows=Exact(1), Bytes=Exact(16), [(Col[0]:),(Col[1]:)]] |
|                                                            |   EmptyExec: produce_one_row=true, statistics=[Rows=Exact(1), Bytes=Exact(8), []]                                         |
|                                                            |                                                                                                                           |
| physical_plan after OutputRequirements                     | OutputRequirementExec                                                                                                     |
|                                                            |   ProjectionExec: expr=[random() as r1, random() as r2]                                                                   |
|                                                            |     EmptyExec: produce_one_row=true                                                                                       |
|                                                            |                                                                                                                           |
| physical_plan after aggregate_statistics                   | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after join_selection                         | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after LimitedDistinctAggregation             | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after EnforceDistribution                    | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after CombinePartialFinalAggregate           | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after EnforceSorting                         | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after coalesce_batches                       | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after OutputRequirements                     | ProjectionExec: expr=[random() as r1, random() as r2]                                                                     |
|                                                            |   EmptyExec: produce_one_row=true                                                                                         |
|                                                            |                                                                                                                           |
| physical_plan after PipelineChecker                        | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after LimitAggregation                       | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan after ProjectionPushdown                     | SAME TEXT AS ABOVE                                                                                                        |
| physical_plan                                              | ProjectionExec: expr=[random() as r1, random() as r2]                                                                     |
|                                                            |   EmptyExec: produce_one_row=true                                                                                         |
|                                                            |                                                                                                                           |
| physical_plan_with_stats                                   | ProjectionExec: expr=[random() as r1, random() as r2], statistics=[Rows=Exact(1), Bytes=Exact(16), [(Col[0]:),(Col[1]:)]] |
|                                                            |   EmptyExec: produce_one_row=true, statistics=[Rows=Exact(1), Bytes=Exact(8), []]                                         |
|                                                            |                                                                                                                           |
+------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------+
109 rows in set. Query took 0.011 seconds.
``` 

</p>
</details> 

[alamb]

This appears to have been exposed in #8340 from @jonahgao and @haohuaijin (the bug has existed for quite a while, but previously it got "undone" by projection pushdown):

• 3f6ff22 CORRECT
• d771f26 WRONG

For some reason I don't understand, something about #8340 seems to expose us to this bug downstream in IOx

[viirya]

The correctness relying on the order of optimization rules is somehow flaky and easily to be broken. I think we should disallow volatile expressions to be targets of common subexpr elimination at the beginning: #8520

[alamb]

The correctness relying on the order of optimization rules is somehow flaky and easily to be broken. I think we should disallow volatile expressions to be targets of common subexpr elimination at the beginning: #8520

I agree -- thank you @viirya -- I will review that PR shortly