ORDER BY: one sort specification, keys beside the rows and one comparator #2720

Many merged pull requests fixed one ORDER BY case each. Read together, they trace back to five design choices. This issue proposes removing those causes instead of patching each case. It goes with #2717 (subqueries) and #2718 (set operations).

Why ORDER BY breaks

1. An ORDER BY item is resolved in several places. compileOrder (src/426orderby.js) handles positions, quoted names (Fix sorting for quoted column names in ORDER BY clause #2275) and parameters; compileSelect2 and compileSelectGroup2 (src/424select.js) each look the item up again for plain and grouped queries, the grouped one with its own maps (Fix ORDER BY on grouped source columns when SELECT uses aliases #2525, Review #2525 for code improvements: ORDER BY resolution in grouped queries #2630); queryfn3 (src/38query.js) does it twice more for set operations and skips expressions (Fix ORDER BY clause handling in multiple UNIONs #2188, Add SQL-99 compliant parenthesized SELECT support in UNION operations #2395, Review #2395 for code improvements: the first SELECT's ORDER BY and LIMIT are guessed at run time #2712); with SELECT * a position is resolved per row from that row's key order (Fix ORDER BY with numeric column references for SELECT * #2189, Review #2189 for code improvements: ORDER BY position with SELECT * is resolved per row #2693). Each place knows a different subset of the rules.
2. Sort keys travel inside the result rows. The value to sort on is stored on each row as $$$0, $$$1, … and removed afterwards through removeKeys. A key that is not removed in time takes part in comparisons: rows of a set operation compared unequal because of it (INTERSECT, EXCEPT and UNION compare rows wrongly when both SELECTs have their own ORDER BY #2610, Remove order keys before comparing rows in a set operation to close #2610 #2611), and set operations needed extra guards (Fix error with ORDER BY in INTERSECT/EXCEPT queries #2304, Review #2304 for code improvements: guards for a missing .query in set operations #2646).
3. The comparator is built as text with its own value rules. (a['$$$0']||'') turns NULL, undefined, 0 and '' into the same value, so NULL sorts between -1 and 1. .valueOf() is added only for columns declared as DATE, STRING or NUMBER. COLLATE NOCASE threw on numbers (Let ORDER BY ... COLLATE NOCASE sort numbers instead of throwing #2719). None of this is shared with =, MIN / MAX or DISTINCT (One comparison module with levels (dates compared by value, MAX/MIN on strings, one NULL order) #2595).
4. Each context that sorts has its own ORDER BY. The SELECT list, set operations, GROUP_CONCAT(… ORDER BY …) (only the direction is used, Add GROUP_CONCAT support for ORDER BY and SEPARATOR clauses #2418, GROUP_CONCAT(x ORDER BY y) sorts by x, not by y #2658, Review #2418 for code improvements: GROUP_CONCAT special-cased in the generic aggregate code #2660), window functions (OVER (ORDER BY …) is ignored, ROW_NUMBER() OVER (ORDER BY …) ignores the window's ORDER BY; PARTITION BY works only on already-sorted output #2591), and the function form at the top of compileOrder (SEARCH … ORDER BY()).
5. The text of an ORDER BY item is written by hand (toString() lost the direction until Fix missing ORDER BY direction when calling toString() on AST #970), the identity problem of Review #1197 for code improvements: toString() is used as the identity of an expression #2675.

Proposal

1. One sort specification. Each ORDER BY becomes a list of {expression, direction, nulls, collation}. One resolution step (the binding step of Subqueries: give each SELECT its own subqueries, one compiled form and a run context #2717) maps each item to an output column (by name, alias or position, with * expanded once per run at the latest), a group key, or an expression over the source row. Plain, grouped and set-operation queries (Set operations: parse UNION, INTERSECT and EXCEPT into a tree with their own ORDER BY and LIMIT #2718) use the same function.
2. Sort keys beside the rows, not in them. Compute the keys into a separate array (decorate, sort, undecorate). Nothing is added to the rows, so there is nothing to remove and nothing can leak into a comparison.
3. One comparator from the comparison module (One comparison module with levels (dates compared by value, MAX/MIN on strings, one NULL order) #2595). NULL placement by one rule (NULLS FIRST / NULLS LAST, default per dialect), collations as functions that apply only to text, dates by value whether or not the column is declared, one rule for numbers against text, and a stable sort. =, MIN / MAX, DISTINCT and set operations use the same module.
4. The same sort specification in every context. GROUP_CONCAT(… ORDER BY expr) sorts each group by its expression; window functions sort by partition and window order (ROW_NUMBER() OVER (ORDER BY …) ignores the window's ORDER BY; PARTITION BY works only on already-sorted output #2591, Review #2208 for code improvements: ROW_NUMBER() OVER (PARTITION BY) numbers the output rows #2702); SEARCH … ORDER BY() uses it too.
5. toString() written from the specification, so text and behaviour cannot drift apart (Review #1197 for code improvements: toString() is used as the identity of an expression #2675).

Test matrix

Item (name, alias, position, quoted name, expression, parameter) × query (plain, grouped, set operation, SELECT *, with a subquery) × values (numbers, text, dates, NULL, undefined, mixed) × options (ASC / DESC, NULLS FIRST / LAST, COLLATE NOCASE) × LIMIT / OFFSET, each compared with SQLite (#2593).

Order

1. Sort keys beside the rows and one comparator that keeps today's v4 rules. No behaviour change, except that cases which throw today stop throwing. 4.x.
2. One resolution step for plain, grouped and set-operation queries; fixes Review #2189 for code improvements: ORDER BY position with SELECT * is resolved per row #2693 and the expression gap in Review #2395 for code improvements: the first SELECT's ORDER BY and LIMIT are guessed at run time #2712. 4.x.
3. GROUP_CONCAT(… ORDER BY expr) on the same specification; fixes GROUP_CONCAT(x ORDER BY y) sorts by x, not by y #2658. 4.x.
4. NULL placement and value rules as SQLite, with a dialect keeping the v4 rules: 5.0, as listed in breaking.md ("ORDER BY with NULLs") and One comparison module with levels (dates compared by value, MAX/MIN on strings, one NULL order) #2595.
5. Window ordering: 5.0 (ROW_NUMBER() OVER (ORDER BY …) ignores the window's ORDER BY; PARTITION BY works only on already-sorted output #2591).

Related: #970, #2188, #2189, #2275, #2304, #2395, #2418, #2525, #2591, #2593, #2595, #2610, #2611, #2630, #2646, #2658, #2660, #2675, #2693, #2702, #2712, #2717, #2718, #2719.