Column shared by two CTEs resolves nondeterministically to one of them

[funcpp]

Found while reviewing #12's second half (#23). Same class as the ordering bug fixed in #21, but this one changes the answer, not just the order of results.

1. A column present in two CTEs resolves to a coin flip

WITH a AS (SELECT x FROM s1), b AS (SELECT x FROM s2)
SELECT x FROM a JOIN b ON a.x = b.x

20 runs of the same binary on 927025d:

10   x  ←  s1.x    (direct)
10   x  ←  s2.x    (direct)

Both are reported as ColumnOrigin::Concrete — a claim that the column provably comes from that table. x is genuinely ambiguous between the two CTEs, so neither answer is right; the correct result is Ambiguous, or Concrete only once a catalog settles it.

This is worse than #21: there the set of mappings was stable and only their order moved. Here the lineage itself differs between runs, and a consumer that caches or diffs results sees a real table change identity.

2. Ambiguous.candidates ordering also varies

SELECT x FROM t1 JOIN t2 ON t1.id = t2.id JOIN t3 ON t1.id = t3.id

10 runs produced 5 distinct orderings:

3   [t1, t2, t3]
3   [t3, t1, t2]
2   [t2, t1, t3]
1   [t1, t3, t2]
1   [t3, t2, t1]

This one is cosmetic by comparison, but it reaches CatalogProvider::resolve_column, so a provider that picks by position rather than by name gets a different answer per run.

Cause

ScopeTree stores bindings in a hash map, and both accessors flatten it straight into a Vec:

• sqllineage/src/graph/scope.rs:14 — bindings: HashMap<String, Binding>
• sqllineage/src/graph/scope.rs:103 — immediate_bindings
• sqllineage/src/graph/scope.rs:112 — visible_bindings

Iteration order therefore follows the per-process random hash seed. resolve_from_bindings then walks that Vec and returns from inside the loop at the first CTE or derived table that has the column:

sqllineage/src/resolve/mod.rs:451

for (_, binding) in bindings {
    match binding {
        Binding::Cte(s) | Binding::DerivedTable(s) => {
            if graph.scopes.output_columns(*s).iter().any(|c| c.name == name) {
                return resolve_through_scope(name, *s, graph, resolved, incoming, visited);
            }
        }
        Binding::Table(t) => table_candidates.push(t.clone()),
    }
}

So whichever CTE the hash map happens to yield first wins. Physical tables accumulate into table_candidates instead of returning early, which is why #2 shows as ordering rather than as a changed answer — but that Vec inherits the same random order.

Shape of a fix

Two parts, and the second is the load-bearing one:

1. Deterministic binding order. Preserve insertion order — either an order-preserving map, or a Vec<(String, Binding)> alongside the map for iteration while the map stays for lookup. Note visible_bindings also relies on nearest-scope-wins shadowing, which must survive the change.

2. Stop returning early. Collect every scope binding that publishes the column instead of taking the first. Then:

   • exactly one match → Concrete (today's behavior when unambiguous)
   • two or more → Ambiguous, which fix: stop claiming a table for columns that resolve to none #23 defined as "a real choice between at least two known relations"
   • none, and no physical candidate → Unresolved, also from fix: stop claiming a table for columns that resolve to none #23

Ordering alone would make the bug reproducible but keep it wrong — it would just pick the same wrong CTE every time. The early return is the actual defect.

Worth checking while in there: whether a CTE match should outrank a physical-table candidate at all, since today a CTE that has the column short-circuits before any physical table is even considered.

Regression test

A deterministic result cannot be tested by a single run. #21 established the pattern — assert the expected result, and confirm the test fails against the unfixed code across repeated runs (that one failed 14/15 pre-fix). The same applies here.