Set operations: parse UNION, INTERSECT and EXCEPT into a tree with their own ORDER BY and LIMIT #2718

Many merged pull requests fixed one set operation case each (UNION, UNION ALL, INTERSECT, EXCEPT). Read together, they trace back to six design choices. This issue proposes removing those causes instead of patching each case. It is the set operation counterpart of #2717 (subqueries).

Why set operations break

1. A set operation is a property of the first SELECT. A UNION B EXCEPT C is stored as A.union = B, B.except = C: a chain hanging off the first SELECT. The chain evaluates right to left (Fix multiple EXCEPT problem #202, Evaluate UNION / EXCEPT / INTERSECT chains left to right to close #202 #2582), there is no place for precedence (does INTERSECT bind tighter?), and the first SELECT is both one branch and the whole statement.
2. The statement's ORDER BY / LIMIT and the first branch's sit on the same object. The grammar needs several SELECT variants to tell them apart (SelectWithoutOrderOrLimit, ParenthesizedSelect, UnionableSelect, LPAR Select RPAR UnionClause OrderClause LimitClause; Fix ORDER BY clause handling in multiple UNIONs #2188, Add SQL-99 compliant parenthesized SELECT support in UNION operations #2395, Implement SQL-99 compliant parenthesized SELECT support for UNION with ORDER BY #2417). Where the parser loses track, queryfn3 guesses (unionBranchHasOrder), and the guess is wrong in (SELECT ... LIMIT 1) UNION ALL SELECT ... applies the LIMIT to the whole result #2711.
3. Sorting a union adds hidden keys to the rows. Sort keys ($$$0, …) are added to each row before the sort and removed after it. Rows are compared as whole objects for UNION, INTERSECT and EXCEPT, so a leftover key makes equal rows differ (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). The block that adds the keys exists twice and skips expressions without an error (Review #2395 for code improvements: the first SELECT's ORDER BY and LIMIT are guessed at run time #2712).
4. Run state is written to the compiled query. Clearing orderfn and limit after the first use made the second run differ (Set operation with ORDER BY / LIMIT on the first SELECT gives a different result from the second run #2605, fixed in Keep ORDER BY / LIMIT of the first SELECT in a set operation on every run to close #2605 #2608).
5. Each branch needs its own subquery list (Fix UNION ALL with subquery in NOT IN clause #2404, Fix UNION with nested SELECT #2518): the subquery design in Subqueries: give each SELECT its own subqueries, one compiled form and a run context #2717.
6. Rows are compared in more than one way. doDistinct builds a text key from the values; the set operations deep-compare objects. Distinct and set results can disagree on dates, NULL vs undefined, and leftover keys.

Proposal

1. Parse into a tree, as the SQL standard writes it:

   Query     := Body [ORDER BY …] [LIMIT … OFFSET …]
   Body      := Term { (UNION | EXCEPT) [ALL] Term }
   Term      := Primary { INTERSECT [ALL] Primary }
   Primary   := SelectCore | '(' Query ')'
   

   ORDER BY and LIMIT belong to the Query node where they were written: a parenthesised (SELECT … LIMIT 1) keeps its own, the statement keeps its own, and nothing is guessed. One rule per level replaces the SELECT variants. Precedence and associativity are decided in one place, so the open question in Evaluate UNION / EXCEPT / INTERSECT chains left to right to close #202 #2582 (standard SQL or SQLite) becomes one choice in the grammar.

2. Evaluate bottom-up, on tuples. Each node returns rows as values in column order plus the column names of its leftmost SELECT. UNION, INTERSECT, EXCEPT and DISTINCT share one key function from the comparison module (One comparison module with levels (dates compared by value, MAX/MIN on strings, one NULL order) #2595), so no sort key or stray property can affect a comparison. Rows become objects only at the end. ORDER BY on a Query node resolves names and positions against that node's output columns at compile time; that is also where an expression that is not an output column gets an error, as in SQLite, instead of being ignored.

3. The compiled plan stays unchanged after compiling. Run state goes into a run context, as in Subqueries: give each SELECT its own subqueries, one compiled form and a run context #2717.

4. Each Primary owns its subqueries, as in Subqueries: give each SELECT its own subqueries, one compiled form and a run context #2717.

#2313 (HTML table source) is not a set operation problem; #2277 adds a test.

Test matrix

Operator (UNION, UNION ALL, INTERSECT, EXCEPT, with and without CORRESPONDING) × parentheses around each branch or none × ORDER BY / LIMIT on none, the first branch, the last branch, the statement, or several × chain length two or three × mixed operators (precedence) × a subquery inside a branch. Each result compared with SQLite (#2593). #2711 is one cell of this table.

Order

1. The tree, keeping v4's right-to-left order. No behaviour change; fixes (SELECT ... LIMIT 1) UNION ALL SELECT ... applies the LIMIT to the whole result #2711. 4.x.
2. Tuples and one key function for set operations and DISTINCT. 4.x, with the matrix as the safety net; dates compared by value follows the 5.0 comparison decision (One comparison module with levels (dates compared by value, MAX/MIN on strings, one NULL order) #2595).
3. Run context, shared with Subqueries: give each SELECT its own subqueries, one compiled form and a run context #2717.
4. Left to right with standard precedence: 5.0 (Evaluate UNION / EXCEPT / INTERSECT chains left to right to close #202 #2582), with a dialect keeping the v4 order.

Related: #202, #2188, #2374, #2395, #2404, #2417, #2518, #2582, #2593, #2595, #2605, #2608, #2610, #2611, #2711, #2712, #2717.