feat(postgres): infer whether a statement's order is total by colinhacks · Pull Request #163 · colinhacks/reylo

colinhacks · 2026-11-03T04:13:36Z

Reylo now infers, on Postgres, whether a statement's ORDER BY makes its rows' order total: its sort keys hold every column of a unique key of the rows it sorts, so no two rows of any result tie and the order is the same on every run. Anything that compares two results of the same query by position needs that, and can now require it.

The analysis carries ordered: true; every built module sets query["~standard"].query.ordered to true, and its declared type carries the literal true there, so a driver's signature can refuse a query whose order is not total. It is absent otherwise, and absent for a result of cardinality one, maybeOne or none, as key is. MySQL, SQLite and DuckDB report none yet.

The rule

The sort keys must hold every column of one of these keys:

a result key (the rules of feat(postgres): infer the result key of a statement #160), each column an output column the ORDER BY names by position, by output name, or as the FROM's column the select list holds; this covers group by, distinct on, and a union without all, whose ORDER BY works on output columns;
a unique key of a FROM item's rows, a table's or one a view, a with query or a subquery keeps from its statement, each column a table's valid NOT NULL column passed through unchanged, selected or not, where every other item meets one row at most per row of that item and no outer join null-extends it (no LATERAL subquery); or one such key of every item together.

Every sort key must hold a value that is the same on every run over the same data: a table's column passed through, or an expression of such columns that calls nothing volatile, no window function, no subquery and no aggregate whose value turns on its rows' order (string_agg, array_agg, floating-point sum); otherwise rows that do not tie may still move between runs. A sort key counts toward the key only under its column's own ordering: not one written with using or collate, not an expression, and not a string under a nondeterministic collation, or one whose collation the engine does not read. A bare name is an output column's before a FROM column's, as Postgres reads ORDER BY, and one only a * expands to is the FROM's column of that name. A limit or offset keeps the order total. No ORDER BY, no total order.

Checks

The oracle checks every run of a statement it says is ordered: no two rows in a row may tie on every sort key (the same text, or both NULL). A sort key that is no output column is read from a copy of the statement that also selects it (cardinality::sort_probe, which adds each such sort expression to the select list), run on the same values. Fed analyses that falsely claim a total order, it fails six of the eight statements in total_order. The other two have no tie in the seeded data.
A new case, oracle/cases/total_order, covers ordering by a primary key, a non-unique column alone and then the key, a key not selected, to-one and to-many joins, a nullable side's key, group by, distinct on, union and union all, no ORDER BY, limit, offset, a view, a with query, a subquery, a nondeterministic collation, collate, an expression, an alias and a position. Printed lines end in ordered where the order is total; seven existing lines gain it.
Unit tests in engine/postgres/src/cardinality.rs; loader tests that a built module declares and carries ordered, and that a signature requiring ordered: true takes such a query and refuses another.
The rule is documented under Cardinality on the Postgres page, and the skill says how to get a total order.

The Vercel preview fails on every main commit since #152, unrelated to this change.

vercel · 2026-11-03T04:13:41Z

The latest updates on your projects. Learn more about Vercel for GitHub.

Project	Deployment	Actions	Updated
reylo	8000 Ready	Preview	Nov 3, 2026 5:25pm UTC

pullfrog

✅ No new issues found.

Reviewed changes

I reviewed the whole PR: the new total-order inference in the Postgres engine, the oracle's check of it, how the flag reaches the Standard Query and its declared type, and the docs.

Engine rule: cardinality::total_order takes a sort over a result key's output columns, under a type with no collation or a table column with a deterministic collation, or a FROM item's NOT NULL unique key that every other item is determined from. It only runs on SELECTs whose cardinality is many.
Catalog: Catalog::not_null comes from the prefetched relations' valid, inheritance-wide NOT NULL flags. It reuses #160's key query, which already drops deferrable indexes, traditional inheritance parents, non-default equality opclasses and indexes whose collation disagrees with their column's.
Oracle: sort_probe re-selects sort keys that are not output columns, and ties fails a run where two adjacent rows tie on every sort key. A statement claimed as ordered that the probe cannot read is reported as a problem rather than skipped.
Run time and types: the loader emits ordered: true and standardQuery carries it. mapper-server.ts is the only place that writes declarations, and it intersects "~standard": { query: { ordered: true } } so a driver's signature can require it. A type-level test covers this.
Docs: there is a "Total order" rule under Cardinality on the Postgres page, a matching line in the skill, and the site's captures are regenerated.

I checked the soundness edges against the code:

using and collate sort keys
an output name that shadows an input column
* positions
null-extended and LATERAL anchors
set-returning functions in FROM and in the select list
set operations, group by and distinct on
views, WITH queries and subqueries, whose keys come from output_keys with NULL-equal semantics, so the extra NOT NULL requirement there only makes the rule stricter

I found nothing unsound.

^{｜ View workflow run ｜ Using claude-opus-5-5 ｜ 𝕏}

Copilot

🟡 Changes recommended

The ordering analysis incorrectly guarantees cross-run stability for volatile sorts such as random(), violating the documented ordering guarantee for positional consumers.

3 open issues

What changed in this PR

Adds Postgres total-order inference alongside result-key inference, exposing ordered: true through generated query types and Standard Query metadata for consumers that compare results by position.

Changes:

Infers total ordering from result keys and qualifying source-table keys.
Propagates ordering metadata through the engine, loader, runtime, and generated declarations.
Adds oracle checks, regression cases, loader tests, and documentation.

File	Description
`tests/standard-query.test.ts`	Tests runtime metadata and type-level requirements.
`tests/compiled.test.ts`	Checks generated declarations and runtime ordering flags.
`src/standard-query.ts`	Exposes optional `ordered: true` metadata.
`src/mapper-server.ts`	Declares literal ordering metadata for SQL modules.
`src/loader.ts`	Includes ordering metadata in generated modules.
`src/index.ts`	Passes query-definition ordering into the runtime.
`src/execute.ts`	Adds ordering to the runtime module type.
`src/engine-core.ts`	Adds ordering to the analysis interface.
`skills/using-reylo/SKILL.md`	Explains ordering for positional comparisons.
`site/scripts/capture-types.ts`	Captures ordering in documentation declarations.
`site/lib/sql-modules.json`	Refreshes captured types and adds the ordering example.
`site/content/docs/postgres.mdx`	Documents total-order rules and usage.
`oracle/src/seed.rs`	Checks adjacent rows for tied sort keys.
`oracle/src/main.rs`	Prints inferred ordering in oracle results.
`oracle/cases/total_order/view.sql`	Covers ordering through a view.
`oracle/cases/total_order/view_key_not_selected.sql`	Covers an unselected view key.
`oracle/cases/total_order/unique_not_selected.sql`	Covers an unselected unique key.
`oracle/cases/total_order/union.sql`	Covers ordered duplicate-eliminating unions.
`oracle/cases/total_order/union_all.sql`	Covers unions that retain duplicates.
`oracle/cases/total_order/to_one_left_join.sql`	Covers a to-one outer join.
`oracle/cases/total_order/to_one_join.sql`	Covers a key-preserving inner join.
`oracle/cases/total_order/to_many_join.sql`	Covers ordering that leaves joined rows tied.
`oracle/cases/total_order/to_many_both_keys.sql`	Covers ordering by both joined keys.
`oracle/cases/total_order/subquery.sql`	Covers key propagation through a subquery.
`oracle/cases/total_order/setup.sql`	Defines tables, keys, a view, and a collation.
`oracle/cases/total_order/position.sql`	Covers positional ORDER BY references.
`oracle/cases/total_order/offset_param.sql`	Covers ordering with parameterized offset.
`oracle/cases/total_order/nullable_unique.sql`	Covers nullable unique columns.
`oracle/cases/total_order/nullable_side_key.sql`	Covers a null-extended join key.
`oracle/cases/total_order/nondeterministic.sql`	Covers nondeterministic collation rejection.
`oracle/cases/total_order/non_unique.sql`	Covers non-unique sorting alone.
`oracle/cases/total_order/non_unique_then_key.sql`	Covers a unique tiebreaker.
`oracle/cases/total_order/no_order.sql`	Covers queries without ORDER BY.
`oracle/cases/total_order/limited.sql`	Covers order preservation with LIMIT.
`oracle/cases/total_order/key_not_selected.sql`	Covers hidden sort keys.
`oracle/cases/total_order/group_by.sql`	Covers ordering by a grouping key.
`oracle/cases/total_order/group_by_count.sql`	Covers non-unique aggregate ordering.
`oracle/cases/total_order/expression.sql`	Covers expression-based key rejection.
`oracle/cases/total_order/explicit_collation.sql`	Covers explicit collation with a valid tiebreaker.
`oracle/cases/total_order/explicit_collation_only.sql`	Covers explicit collation without a tiebreaker.
`oracle/cases/total_order/expected.txt`	Records expected ordering inference.
`oracle/cases/total_order/distinct_on.sql`	Covers ordering of DISTINCT ON results.
`oracle/cases/total_order/cte.sql`	Covers keys retained by a WITH query.
`oracle/cases/total_order/by_unique_desc.sql`	Covers descending unique-key sorting.
`oracle/cases/total_order/by_primary_key.sql`	Covers primary-key sorting.
`oracle/cases/total_order/alias_name.sql`	Covers output-alias precedence.
`oracle/cases/result_key/expected.txt`	Adds ordering to existing result-key expectations.
`oracle/cases/param_keys/expected.txt`	Adds ordering to parameterized-sort expectations.
`oracle/cases/joins/expected.txt`	Adds ordering to existing join expectations.
`engine/sqlite/src/sqlite.rs`	Leaves ordering unreported for SQLite.
`engine/postgres/src/postgres.rs`	Collects NOT NULL facts and invokes ordering inference.
`engine/postgres/src/extension.rs`	Reads ordering from extension responses.
`engine/postgres/src/cardinality.rs`	Implements ordering inference, probes, and unit tests.
`engine/mysql/src/mysql.rs`	Leaves ordering unreported for MySQL.
`engine/duckdb/src/duckdb.rs`	Leaves ordering unreported for DuckDB.
`engine/core/src/api.rs`	Serializes ordering when true.
`engine/core/src/analysis.rs`	Defaults bare analyses to no ordering claim.

_{Review effort: Balanced}

colinhacks · 2026-11-03T04:40:13Z

+    if select_keys(s, trust, catalog, columns).iter().any(|key| key.iter().all(|at| sorted_at.contains(at))) {
+        return true;


Right: a total order has to be the same order on every run, not just free of ties. Fixed in the latest commit. Every sort key must now be stable: a table's column passed through, or an output column whose entry is one, or an expression of such columns that calls nothing volatile, no window function, no subquery, no function a user shadows, and no aggregate whose value turns on the order of its rows (array_agg, string_agg, the JSON aggregates, floating-point sum/avg and the like, unless the call orders them). This holds wherever the key stands in the ORDER BY, and through output aliases and derived columns, since a WITH query's or subquery's computed column has no table column behind it. count(*) stays stable. Oracle statements volatile_first, window_first and aggregate_order_sensitive now report no order; aggregate_count does.

colinhacks · 2026-11-03T04:40:17Z

+                let Some(name) = c.fields.first().and_then(field_name) else { return (None, None) };
+                let mut named = columns.iter().enumerate().filter(|(_, (n, _))| n == name).map(|(i, _)| i);
+                match (named.next(), named.next()) {
+                    (Some(at), None) => return (Some(at), held(at)),


Fixed. A bare ORDER BY name that only a * expands to is now read as the FROM's column of that name, while an entry with that alias or implicit name still wins, as Postgres reads it. select * from users order by email is now ordered (oracle star_name, plus a unit test). A position past a * still counts only where the type has no collation or the FROM's key covers it, which is conservative.

colinhacks · 2026-11-03T04:40:20Z

+        for (k, e) in added.into_iter().enumerate() {
+            let target = protobuf::ResTarget { name: format!("reylo_sort_{k}"), val: Some(Box::new(e)), ..Default::default() };
+            s.target_list.push(protobuf::Node { node: Some(NodeEnum::ResTarget(Box::new(target))) });
+        }


Fixed: the copy's added columns now take the first reylo_sort_<n> that no output column and no name in the ORDER BY has. probe_alias.sql (select title as reylo_sort_0 from posts order by id, reylo_sort_0) runs and checks cleanly, and a unit test covers it.

pullfrog

Important

The new stability check still lets two kinds of order-sensitive aggregates through, so a few statements can claim ordered: true when their order can change from run to run.

Reviewed changes

I reviewed 657a5db, which requires every sort key to hold the same value on every run, and fixes how bare ORDER BY names resolve.

Stable sort keys: stable_sort_key / stable_output / stable_expression reject any sort key, anywhere in the ORDER BY, that has a volatile call, a window function, a subquery, a non-built-in function, or an ORDER_SENSITIVE aggregate with no ORDER BY of its own. The key's columns must also pass through to a table's.
Name resolution: output_named checks a bare name against both columns and named_entry. An alias whose position disagrees is treated as ambiguous. A name that only a * supplies is read as the FROM's column (star_name.sql).
Probe names: sort_probe now picks reylo_sort_N names that no output column or sort key already uses (probe_alias.sql).
Cases and docs: six new total_order statements cover these rules, and the Postgres page now names random(), window functions and string_agg.

The rest of the change looks sound to me. Every place where a sort key falls outside what the engine reads (past a *, over VALUES or a function, using) now fails, which only ever withholds ordered.

^{｜ Fix all ➔ ｜ Fix 👍s ➔ ｜ View workflow run ｜ Using claude-opus-5-5 ｜ 𝕏}

pullfrog

Important

Both earlier findings are fixed. One sibling of the SQL/JSON gap is still open: json_array(select …) can still make a statement claim ordered: true.

Reviewed changes

I reviewed c2ec870, which closes the two order-sensitive aggregate gaps from the last review. The TypeScript hunks in the range-diff (row / columns) come from the rebase onto main, not from this PR.

No agg_order exemption: an ORDER_SENSITIVE aggregate is now never a stable sort key, even with its own ORDER BY. aggregate_own_order.sql, a unit test, the doc comment and the Postgres page all cover this.
SQL/JSON aggregates: stable_expression rejects any JsonArrayAgg / JsonObjectAgg node, and the two names that never matched are gone from ORDER_SENSITIVE. json_arrayagg.sql and a unit test cover this.

^{｜ Fix all ➔ ｜ Fix 👍s ➔ ｜ View workflow run ｜ Using claude-opus-5-5 ｜ 𝕏}

pullfrog

ℹ️ No new issues in this push. The json_array(select …) thread from the last review is still open, and there is one informational note below.

Reviewed changes

Most of what changed since c2ec870 is the rebase onto main at 9e2abf7: the Cardinality enum and at_most_one from #162, and ~standard.query.columns / output from #165. The rest is a57455d.

Uncollated types by kind: total_order now uses uncollated(&Type) on the type descriptor's TyKind instead of the UNCOLLATED list of catalog names. I checked it against pgtypes.rs::base_type, and no type that has a collation maps to those kinds. Enums (now Text with values), money, inet and bit no longer count as uncollated, but that only makes the rule stricter.
One ~standard intersection: mapper-server.ts and capture-types.ts now write columns and ordered into a single "~standard": { query: { … } } member. The declaration tests in compiled.test.ts and standard-query.test.ts assert the merged line.
Captures and expected lines: the oracle's expected.txt files are reblessed for at_most_one and jsonb, and site/lib/sql-modules.json is regenerated.

ℹ️ The docs' dynamic-sort example no longer gets `ordered: true`

After the regenerated capture, the Postgres sort_users.sql and search_posts.sql on the inference page (03-inference.mdx) no longer carry ordered: true. They used to, but that was a stale capture. Both sort by case when input.sort = … end over a one-row with input as (select :sort::text …). stable_expression accepts a column only if from.base traces it to a table's column, and input.sort is computed from a parameter, so it fails. Writing the parameter straight into the ORDER BY (param_keys/case_chooses.sql) still gets ordered. This only makes the rule stricter, so the PR can merge as it is. Still, the pattern the docs recommend for a dynamic sort can't be marked as a total order.

Technical details

# Parameter-derived CTE columns are not stable sort keys

## Affected sites
- engine/postgres/src/cardinality.rs:2553-2559 — `stable_expression` requires every column read to pass `from.base`, which a WITH query's column computed from a parameter (`select $1::text as sort`) never does
- site/content/sections/03-inference.mdx:290, :309 — `sort_users.sql` / `search_posts.sql`, the docs' dynamic-sort idiom, now captured without `ordered`

## Required outcome
- Decide whether a column of a WITH query or subquery whose entry is itself a stable expression (parameters, constants, table columns) counts as stable, so the documented `with input as (select :sort …)` idiom keeps `ordered: true`; or accept the false negative.

## Open questions for the human
- Is losing `ordered` on the docs' own dynamic-sort pattern acceptable for this PR, or should it be handled here or in a follow-up?

^{｜ Fix it ➔ ｜ View workflow run ｜ Using claude-opus-5-5 ｜ 𝕏}

pullfrog

Important

stable_column now looks inside LATERAL subquery bodies. There, a column of a sibling FROM item is never checked, so a sort key whose value changes between runs can still yield ordered: true.

Reviewed changes

I reviewed 2c10da3, the only commit since ea8d935. It fixes the open json_array(select …) thread (now resolved) and answers the earlier note about dynamic sorts.

JsonArrayQueryConstructor: stable_expression now rejects the raw json_array(select …) node as it rejects a SubLink. json_array_query.sql and a unit test cover it.
Derived columns read through their entry: a new stable_column accepts a WITH query's or subquery's column when that column's entry in its own statement is a stable expression, so a parameter counts (with input as (select :sort::text as sort)). parameter_sort.sql and unit tests cover it, and the docs' sort_users.sql capture has ordered: true again. search_posts.sql still does not, because its input is a jsonb_to_record function, which through does not read. That only withholds ordered, so it is safe.

^{｜ Fix all ➔ ｜ Fix 👍s ➔ ｜ View workflow run ｜ Using claude-opus-5-5 ｜ 𝕏}

The analysis carries `ordered` where the ORDER BY's sort keys hold a unique key of the rows it sorts, so no two rows tie and the order is the same on every run. The oracle checks each run for ties, reading a sort key that is no output column from a copy that selects it.

A sort key whose value may change from run to run (a volatile call, a window function, an aggregate that turns on its rows' order) leaves the order unproven. A name a `*` expands to is the FROM's column, and the oracle's added sort columns take names nothing else has.

A WITH query's or subquery's column whose entry is itself the same on every run, such as a parameter, is a stable sort key, so a dynamic sort over `with input as (select :sort …)` keeps its total order. A `json_array(select …)` is a query of its own and never stable.

pullfrog

✅ No new issues found. The LATERAL-subquery finding from the last review is fixed, and its thread is resolved.

Reviewed changes

Since 9dc5855, the b DD4F ranch was rebased onto main at 9784278 and gained one commit, 7366b8f.

No reading through a LATERAL entry: stable_column now returns false for a Source::Subquery(_, true) item before it calls from.through. A LATERAL subquery's column therefore counts as stable only when from.base passes it through to a table's column. The same guard also covers a LATERAL item nested inside a non-lateral subquery's body, because the recursion goes through stable_column again.
Coverage: the earlier counterexample is now a unit test and oracle/cases/total_order/lateral_sibling.sql, both expected not to be ordered.

^{｜ View workflow run ｜ Using claude-opus-5-5 ｜ 𝕏}

Copilot AI balanced review requested due to automatic review settings November 3, 2026 04:13

Copilot started reviewing on behalf of colinhacks November 3, 2026 04:14

View session

pullfrog Bot reviewed Nov 3, 2026

View reviewed changes

Copilot AI reviewed Nov 3, 2026

View reviewed changes

pullfrog Bot reviewed Nov 3, 2026

View reviewed changes

Comment thread engine/postgres/src/cardinality.rs Resolved

Comment thread engine/postgres/src/cardinality.rs Resolved

colinhacks force-pushed the total-order branch from 657a5db to c2ec870 Compare November 3, 2026 07:01

pullfrog Bot reviewed Nov 3, 2026

View reviewed changes

Comment thread engine/postgres/src/cardinality.rs Resolved

colinhacks force-pushed the total-order branch from c2ec870 to a57455d Compare November 3, 2026 16:11

pullfrog Bot reviewed Nov 3, 2026

View reviewed changes

colinhacks force-pushed the total-order branch from a57455d to ea8d935 Compare November 3, 2026 16:22

pullfrog Bot reviewed Nov 3, 2026

View reviewed changes

Comment thread engine/postgres/src/cardinality.rs Resolved

colinhacks force-pushed the total-order branch from 2c10da3 to 9dc5855 Compare November 3, 2026 17:08

colinhacks added 8 commits November 3, 2026 09:14

feat: declare a total order on the standard query

6dd84ac

docs(postgres): document the total order

b176580

fix(postgres): never order totally by an order-sensitive aggregate

4cc8dad

test: carry the total order through the rebuilt declarations

09570a9

fix(postgres): read no sort value through a lateral subquery's entry

7366b8f

colinhacks force-pushed the total-order branch from 9dc5855 to 7366b8f Compare November 3, 2026 17:24

pullfrog Bot reviewed Nov 3, 2026

View reviewed changes

colinhacks merged commit 9a44da5 into main Nov 3, 2026
15 checks passed

colinhacks deleted the total-order branch November 3, 2026 17:30

Navigation Menu

Repository navigation

feat(postgres): infer whether a statement's order is total - #163

feat(postgres): infer whether a statement's order is total#163
colinhacks merged 8 commits into
mainfrom
total-order

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

		if select_keys(s, trust, catalog, columns).iter().any(\|key\| key.iter().all(\|at\| sorted_at.contains(at))) {
		return true;

Conversation

Uh oh!

The rule

Checks

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

🟡 Changes recommended

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

ℹ️ The docs' dynamic-sort example no longer gets ordered: true

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

ℹ️ The docs' dynamic-sort example no longer gets `ordered: true`