[DISCUSSION] Sorts being removed from subqueries

[maxburke]

Describe the bug

Referenced discussion: https://the-asf.slack.com/archives/C01QUFS30TD/p1745875862723149

Given this table:

> create table d1 (ul_node_id string);

It appears that sorts are being removed from inner expressions. For example, here is a query with a sort expression:

> explain SELECT "ul_node_id", encode(ul_node_id, 'base64') FROM d1   ORDER BY encode(ul_node_id, 'base64') ASC NULLS LAST;
+---------------+-------------------------------+
| plan_type     | plan                          |
+---------------+-------------------------------+
| physical_plan | ┌───────────────────────────┐ |
|               | │          SortExec         │ |
|               | │    --------------------   │ |
|               | │ encode(d1.ul_node_id,Utf8(│ |
|               | │   "base64"))@1 ASC NULLS  │ |
|               | │            LAST           │ |
|               | └─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐ |
|               | │       ProjectionExec      │ |
|               | │    --------------------   │ |
|               | │ encode(d1.ul_node_id,Utf8(│ |
|               | │        "base64")):        │ |
|               | │ encode(ul_node_id, base64)│ |
|               | │                           │ |
|               | │        ul_node_id:        │ |
|               | │         ul_node_id        │ |
|               | └─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐ |
|               | │       DataSourceExec      │ |
|               | │    --------------------   │ |
|               | │          bytes: 0         │ |
|               | │       format: memory      │ |
|               | │          rows: 0          │ |
|               | └───────────────────────────┘ |
|               |                               |
+---------------+-------------------------------+
1 row(s) fetched.

If I wrap it in a no-op CTE the SortExec stage disappears:

> explain WITH t0 AS (SELECT "ul_node_id", encode(ul_node_id, 'base64') FROM d1   ORDER BY encode(ul_node_id, 'base64') ASC NULLS LAST) SELECT  * FROM t0;
+---------------+-------------------------------+
| plan_type     | plan                          |
+---------------+-------------------------------+
| physical_plan | ┌───────────────────────────┐ |
|               | │       ProjectionExec      │ |
|               | │    --------------------   │ |
|               | │ encode(d1.ul_node_id,Utf8(│ |
|               | │        "base64")):        │ |
|               | │ encode(ul_node_id, base64)│ |
|               | │                           │ |
|               | │        ul_node_id:        │ |
|               | │         ul_node_id        │ |
|               | └─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐ |
|               | │       DataSourceExec      │ |
|               | │    --------------------   │ |
|               | │          bytes: 0         │ |
|               | │       format: memory      │ |
|               | │          rows: 0          │ |
|               | └───────────────────────────┘ |
|               |                               |
+---------------+-------------------------------+
1 row(s) fetched.

Manually hoisting out the ORDER BY from the CTE causes it to appear in the plan:

> explain WITH t0 AS (SELECT "ul_node_id", encode(ul_node_id, 'base64') FROM d1) SELECT * from t0   ORDER BY encode(ul_node_id, 'base64') ASC NULLS LAST;
+---------------+-------------------------------+
| plan_type     | plan                          |
+---------------+-------------------------------+
| physical_plan | ┌───────────────────────────┐ |
|               | │          SortExec         │ |
|               | │    --------------------   │ |
|               | │    encode(ul_node_id@0,   │ |
|               | │      base64) ASC NULLS    │ |
|               | │            LAST           │ |
|               | └─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐ |
|               | │       ProjectionExec      │ |
|               | │    --------------------   │ |
|               | │ encode(d1.ul_node_id,Utf8(│ |
|               | │        "base64")):        │ |
|               | │ encode(ul_node_id, base64)│ |
|               | │                           │ |
|               | │        ul_node_id:        │ |
|               | │         ul_node_id        │ |
|               | └─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐ |
|               | │       DataSourceExec      │ |
|               | │    --------------------   │ |
|               | │          bytes: 0         │ |
|               | │       format: memory      │ |
|               | │          rows: 0          │ |
|               | └───────────────────────────┘ |
|               |                               |
+---------------+-------------------------------+
1 row(s) fetched.

To Reproduce

No response

Expected behavior

No response

Additional context

No response

[comphead]

Simpler test case

ORDER BY in outer query

> explain select x.* from (select 1 a union all select null) x order by a nulls last;
+---------------+------------------------------------------------------------+
| plan_type     | plan                                                       |
+---------------+------------------------------------------------------------+
| physical_plan | ┌───────────────────────────┐                              |
|               | │  SortPreservingMergeExec  │                              |
|               | │    --------------------   │                              |
|               | │      a ASC NULLS LAST     │                              |
|               | └─────────────┬─────────────┘                              |
|               | ┌─────────────┴─────────────┐                              |
|               | │         UnionExec         ├──────────────┐               |
|               | └─────────────┬─────────────┘              │               |
|               | ┌─────────────┴─────────────┐┌─────────────┴─────────────┐ |
|               | │       ProjectionExec      ││       ProjectionExec      │ |
|               | │    --------------------   ││    --------------------   │ |
|               | │            a: 1           ││          a: NULL          │ |
|               | └─────────────┬─────────────┘└─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐┌─────────────┴─────────────┐ |
|               | │     PlaceholderRowExec    ││     PlaceholderRowExec    │ |
|               | └───────────────────────────┘└───────────────────────────┘ |
|               |                                                            |
+---------------+------------------------------------------------------------+
1 row(s) fetched. 
Elapsed 0.009 seconds.

should be the same as ORDER BY in CTE

> explain select x.* from (select 1 a union all select null order by a nulls last) x;
+---------------+------------------------------------------------------------+
| plan_type     | plan                                                       |
+---------------+------------------------------------------------------------+
| physical_plan | ┌───────────────────────────┐                              |
|               | │         UnionExec         ├──────────────┐               |
|               | └─────────────┬─────────────┘              │               |
|               | ┌─────────────┴─────────────┐┌─────────────┴─────────────┐ |
|               | │       ProjectionExec      ││       ProjectionExec      │ |
|               | │    --------------------   ││    --------------------   │ |
|               | │            a: 1           ││          a: NULL          │ |
|               | └─────────────┬─────────────┘└─────────────┬─────────────┘ |
|               | ┌─────────────┴─────────────┐┌─────────────┴─────────────┐ |
|               | │     PlaceholderRowExec    ││     PlaceholderRowExec    │ |
|               | └───────────────────────────┘└───────────────────────────┘ |
|               |                                                            |
+---------------+------------------------------------------------------------+
1 row(s) fetched. 
Elapsed 0.008 seconds.

But it is not. Sort is gone

[maxburke]

I bisected this to commit 02eab80

[maxburke]

I'm getting the results I expect if I revert the changes from that commit ^ in this file: datafusion/sql/src/relation/mod.rs (ie: remove the call to optimize_subquery_sort)

[comphead]

I'm getting the results I expect if I revert the changes from that commit ^ in this file: datafusion/sql/src/relation/mod.rs (ie: remove the call to optimize_subquery_sort)

Thanks for narrowing down

[ozankabak]

I remember that we discussed this before and the conclusion that this is actually valid behavior. Quoting from Wikipedia:

ORDER BY is the only way to sort the rows in the result set. Without this clause, the relational database system may return the rows in any order. If an ordering is required, the ORDER BY must be provided in the SELECT statement sent by the application. Although some database systems allow the specification of an ORDER BY clause in subqueries or view definitions, the presence there has no effect on the final result-set order, but makes sense when combined with a result offset clause or a fetch first clause. A view is a logical relational table, and the relational model mandates that a table is a set of rows, implying no sort order whatsoever.

IIRC the SQL standard defines things way. Granted, a lot of people do not like this behavior and find it surprising, but it is not wrong AFAICT -- and a lot of DBs behave this way.

Personally, I think the behavior is not surprising in @comphead's example, but it is somewhat surprising in @maxburke's example. For users that don't like the standard behavior, maybe we can add a configuration flag to DF that they can switch, which would make the optimize_subquery_sort function respect subqueries.

I am removing the bug and regression tags for now -- we can reclassify as such if we find out I'm mistaken.