Plan changes between runs when an ORDER BY expression uses more than one column not in the SELECT list #27177

Describe the bug

When an ORDER BY expression refers to more than one column that isn't in the SELECT list, the planner adds those columns to a projection below the Sort, but their order changes from run to run. Query results are correct, but the logical and physical plans differ between runs of the same query, so EXPLAIN output isn't stable.

To Reproduce

In datafusion-cli:

CREATE TABLE t (a INT, b INT, c INT);
EXPLAIN VERBOSE SELECT a FROM t ORDER BY b + c;

Run it several times, each in a new datafusion-cli process. Over 16 runs on main (a616831), initial_logical_plan was:

Projection: t.a
  Sort: t.b + t.c ASC NULLS LAST
    Projection: t.a, t.b, t.c
      TableScan: t

in 8 runs, and had Projection: t.a, t.c, t.b in the other 8. The difference carries through to the physical plan: SortExec: expr=[b@1 + c@2 ASC NULLS LAST] in 8 runs and SortExec: expr=[b@2 + c@1 ASC NULLS LAST] in the other 8.

Expected behavior

The same query gives the same plan every time, for example with the missing columns added in the order they appear in the ORDER BY expression (t.b, t.c).

Additional context

The cause seems to be in LogicalPlanBuilder::sort_with_limit (datafusion/expr/src/logical_plan/builder.rs). It collects the sort columns missing from the input into an IndexSet, which keeps insertion order, but it fills it from Expr::column_refs(), which returns a std::collections::HashSet. HashSet iteration order is randomized per process, so when one sort expression refers to more than one missing column, they're inserted in a random order.

A possible fix is to collect the column references in the order they appear in the expression (for example with expr.apply straight into the IndexSet) instead of going through column_refs(). Would you prefer a local fix like that in sort_with_limit, or is it worth looking at other callers that iterate column_refs() where order matters?

I noticed this while working on #27118 (the fix for #26029). A regression test there checks EXPLAIN output, and the plan for its query kept changing between runs (11 vs 5 over 16 runs on the same build), so two lines of that test use <slt:ignore>.

Willingness to contribute

I would like to contribute a fix for this bug, but request guidance from the DataFusion community