gazagnaire.org
SQL frontend over the catalog engine
1(*---------------------------------------------------------------------------
2 Copyright (c) 2025 Thomas Gazagnaire. All rights reserved.
3 SPDX-License-Identifier: ISC
4 ---------------------------------------------------------------------------*)
5
6(** Storage-agnostic SQL query executor.
7
8 Operates over a {!catalog} that exposes a table's column names and rows, so
9 the evaluation logic (comparisons, [LIKE], joins, ordering) is independent
10 of the storage backend and can be tested in isolation. The catalog speaks
11 the engine core's {!Catalog.Value.t} -- so a storage adapter need not know
12 the SQL frontend's value type -- and the executor converts at that boundary.
13*)
14
15type catalog = {
16 columns : string -> string list;
17 (** Column names of a table, in declared order. *)
18 rows : string -> Catalog.Value.t list list;
19 (** Rows of a table, each aligned to {!columns}. *)
20 rows_rowid : string -> (int64 option * Catalog.Value.t list) list;
21 (** Each row paired with its rowid, or [None] for a row source without one
22 (a view, a derived table, [VALUES]) -- lets the executor resolve the
23 implicit [rowid]/[oid]/[_rowid_] column of a full table scan. *)
24 index_scan :
25 string ->
26 (string * Catalog.Value.t) list ->
27 (string * Catalog.Value.t list list) option;
28 (** [index_scan table eqs] returns [Some (index_name, rows)] when an index
29 on [table] serves the column-equality bindings [eqs], or [None] for a
30 full {!rows} scan. The rows are still re-filtered, so this is a pure
31 optimisation. *)
32 index_for : string -> string list -> string option;
33 (** [index_for table cols] names a unique index on [table] all of whose
34 columns are among [cols] -- the structural counterpart of
35 {!index_scan}, used by {!explain}. *)
36 collation : string -> string -> string option;
37 (** [collation table col] is [col]'s declared [COLLATE] sequence
38 (uppercase) on [table], or [None] for the default binary / a derived
39 source. *)
40}
41
42val of_catalog : Catalog.t -> catalog
43(** [of_catalog cat] adapts a {!Catalog.t} to the SQL frontend's read/explain
44 view. Backends such as Irmin or Parquet can implement {!Catalog.Spi.S},
45 build a catalog handle, and pass it through this adapter before calling
46 {!Engine.run_select}. *)
47
48val number_params : Ast.stmt -> Ast.stmt
49(** [number_params stmt] assigns each [?] placeholder its zero-based index in
50 left-to-right source order. *)
51
52type binding = string * (string * Ast.value) list
53(** One named row fragment, [(alias, [(column, value); ...])]. A [binding list]
54 passed as [?scope] is an outer environment placed at the tail of the row's
55 own bindings, so inner columns shadow it for unqualified names but a
56 qualified [alias.col] still resolves. Used for correlated subqueries (the
57 enclosing row) and for a trigger's [OLD]/[NEW] rows. *)
58
59val set_cat_subquery_runner :
60 (catalog ->
61 (string * (string * Ast.value) list) list ->
62 Ast.select ->
63 Ast.value array ->
64 Ast.value list list) ->
65 unit
66(** [set_cat_subquery_runner] is install the runner used for every SELECT [eval]
67 reaches -- a scalar / [IN] / [EXISTS] subquery, a FROM-subquery, a CTE body,
68 a recursive-CTE arm -- given the enclosing-row {!type-catalog}, the outer
69 scope, the subquery, and the params, returning its rows.
70 {!Engine.run_select} (the catalog-VM engine) installs itself here on load;
71 without it a SELECT raises a clear error. *)
72
73val from_bindings :
74 ?scope:binding list ->
75 catalog ->
76 Ast.value array ->
77 Ast.from_clause ->
78 Ast.join list ->
79 binding list list
80(** [from_bindings cat params from joins] is the join-row environments of a bare
81 [FROM from joins] (no projection, no WHERE), each a [binding list] usable as
82 an outer [~scope]. Drives [UPDATE ... FROM]. [?scope] adds outer bindings.
83*)
84
85val materialize_ctes : catalog -> Ast.value array -> Ast.cte list -> catalog
86(** [materialize_ctes cat params ctes] runs each [WITH] table expression
87 (semi-naive evaluation for a recursive one) and binds its rows into [cat]
88 under its name, returning the extended catalog. Lets a [WITH] on
89 [UPDATE]/[DELETE] put its CTEs in scope for the statement's subqueries. *)
90
91val resolve_collations : catalog -> Ast.select -> Ast.select
92(** [resolve_collations] is make each base-table column's declared [COLLATE]
93 sequence explicit in [s]'s comparisons and ORDER BY keys (wrapping the
94 column in a [Collate] node by sqlite3's left-operand rule), so the collation
95 machinery honours it. The engine applies this before lowering, so a compiled
96 scan over a collated column compares under the collation rather than by
97 binary value. *)
98
99val resolve_where_aliases : catalog -> Ast.select -> Ast.select
100(** [resolve_where_aliases] is substitute a select-list alias referenced in
101 [s]'s WHERE or ORDER BY with the aliased expression -- so
102 [SELECT a AS x FROM t WHERE x > 1] resolves [x] (an alias is only
103 substituted when it does not name a real source column, which shadows it,
104 matching sqlite3). The engine applies this before lowering so a compiled
105 scan resolves the alias too. *)
106
107val substitute_scope :
108 catalog -> binding list -> Ast.select -> Ast.select option
109(** [substitute_scope cat scope s] replaces each free (correlated) column of
110 subquery [s] -- one bound by neither its own FROM nor a deeper scope -- with
111 its value from [scope] (the enclosing row), turning a correlated subquery
112 into an uncorrelated one a caller can run on its own. [None] when [s] is too
113 tangled for the simple rule (a FROM-subquery, a nested subquery, or a
114 window). *)
115
116val hoist_subqueries :
117 run:(Ast.select -> Ast.value list list) -> catalog -> Ast.select -> Ast.select
118(** [hoist_subqueries] is replace each uncorrelated scalar / [IN (SELECT ...)] /
119 [EXISTS] subquery in [s]'s scalar-expression positions (select list, WHERE,
120 GROUP BY, HAVING, ORDER BY, join ON) with its materialised value -- a
121 literal, or an [IN] value list. A correlated subquery (one referencing an
122 enclosing query's columns) is left intact. [run] materialises an
123 uncorrelated subquery to its rows; the engine passes a runner that executes
124 it on the catalog VM. The register VM has no subquery opcode, so it calls
125 this to compile the outer query of an uncorrelated subquery rather than fall
126 back. Sound because an uncorrelated subquery is constant. *)
127
128val resolve_ordinals : catalog -> Ast.select -> Ast.select
129(** [resolve_ordinals] is rewrite [s]'s ORDER BY and GROUP BY so a 1-based
130 output-column ordinal ([ORDER BY 2] / [GROUP BY 2]) becomes the expression
131 of that output column. The engine applies this before lowering so a compiled
132 ORDER BY/GROUP BY ordinal works too. *)
133
134val select_columns : catalog -> Ast.select -> string list
135(** [select_columns cat s] is the output column names of [s]: each item's alias,
136 else a bare column's name, else [columnN]; [*] expands the source table's
137 columns. Used to name the columns of a [CREATE TABLE ... AS] target. *)
138
139val is_aggregate_query : Ast.select -> bool
140(** [is_aggregate_query s] is whether [s] aggregates at all -- it groups, has
141 HAVING, or a select column folds an aggregate. A LIMIT/OFFSET cannot be
142 pushed into the scan of such a query (the aggregate folds every row first),
143 so a fast path must recognise and skip it. *)
144
145val aggregate_compilable : Ast.select -> bool
146(** [aggregate_compilable] is whether [s] is an aggregate/GROUP BY select that
147 {!aggregate_scan} can run: it groups or aggregates or has HAVING and uses no
148 window function. The scan carries the implicit rowid column, so an aggregate
149 over [rowid] (e.g. [count(rowid)]) compiles. *)
150
151val window_compilable : Ast.select -> bool
152(** [window_compilable] is whether [s] has a window function over a [rowid]-free
153 projection, so its (filtered, joined) source rows can be scanned by the
154 register VM and then post-processed by {!aggregate_scan} (which reaches
155 {!window_project}). *)
156
157val aggregate_scan :
158 catalog ->
159 Ast.value array ->
160 Ast.select ->
161 (string * string list) list ->
162 Ast.value list list ->
163 Ast.value list list
164(** [aggregate_scan cat params s segments rows] runs an aggregate/GROUP BY [s]
165 from its already-scanned source [rows]: it builds the row environments and
166 runs the grouping, aggregation, HAVING, ORDER BY, DISTINCT, and
167 OFFSET/LIMIT. [segments] is the join's tables in FROM order as
168 [(alias, cols)]; each row is the concatenation of those tables' columns in
169 that order and is sliced back into one binding per table (a single-table
170 aggregate is a one-element [segments]). Lets the register VM do the scan and
171 reuse this aggregation. *)
172
173val combine_compound :
174 catalog ->
175 Ast.value array ->
176 Ast.select ->
177 Ast.value list list ->
178 (Ast.set_op * Ast.value list list) list ->
179 Ast.value list list
180(** [combine_compound cat params s base_rows compound_rows] combines a compound
181 select's already-computed arm rows -- [base_rows] for the leading arm,
182 [(op, rows)] per following arm: fold the set operators, apply [s]'s ORDER BY
183 over the output columns, then OFFSET/LIMIT. Lets a caller produce each arm's
184 rows itself (via the register VM) and reuse this orchestration. *)
185
186val explain : catalog -> Ast.select -> string
187(** [explain cat select] describes the access path the executor takes, one line
188 per table ([SCAN t] or [SEARCH t USING INDEX i]). Structural -- the same
189 index decision the engine makes, independent of parameter values. *)
190
191val is_agg : string -> Ast.expr list -> bool
192(** [is_agg name args] is whether [name] (with that argument count) is an
193 aggregate -- [count]/[sum]/[avg]/..., or [min]/[max] with at most one
194 argument. An aggregate is folded over a group, not applied per row. *)
195
196val eval_const :
197 ?scope:binding list -> catalog -> Ast.value array -> Ast.expr -> Ast.value
198(** [eval_const cat params e] evaluates [e] with no table row in scope, for
199 [INSERT ... VALUES] tuples. A column reference raises [Failure] unless it
200 resolves in [?scope] (a trigger's OLD/NEW rows). *)
201
202val row_matches :
203 ?scope:binding list ->
204 ?rowid:int64 ->
205 catalog ->
206 Ast.value array ->
207 string ->
208 string list ->
209 Ast.expr option ->
210 Ast.value list ->
211 bool
212(** [row_matches cat params table cols where vals] is whether the row [vals] of
213 [table] (aligned to [cols]) satisfies [where]. [None] matches every row.
214 Used to select the rows a [DELETE] removes. [?scope] adds outer bindings;
215 [?rowid] is the row's rowid, so [where] may reference the implicit rowid
216 column. *)
217
218val eval_in_row :
219 ?scope:binding list ->
220 ?rowid:int64 ->
221 catalog ->
222 Ast.value array ->
223 string ->
224 string list ->
225 Ast.value list ->
226 Ast.expr ->
227 Ast.value
228(** [eval_in_row cat params table cols vals e] evaluates [e] against the single
229 [table] row [vals] (aligned to [cols]) -- the right-hand side of an
230 [UPDATE ... SET] assignment, which may reference the row's columns. [?scope]
231 adds outer bindings (a trigger's OLD/NEW rows); [?rowid] is the row's rowid,
232 so [e] may reference the implicit rowid column. *)
233
234val eval_upsert :
235 ?scope:binding list ->
236 catalog ->
237 Ast.value array ->
238 table:string ->
239 cols:string list ->
240 current:Ast.value list ->
241 excluded:Ast.value list ->
242 Ast.expr ->
243 Ast.value
244(** [eval_upsert cat params ~table ~cols ~current ~excluded e] evaluates an
245 [UPSERT] [DO UPDATE] expression with the conflicting row's [current] values
246 in scope under [table] and the would-be-inserted [excluded] values under the
247 [excluded] pseudo-table (both aligned to [cols]). *)
248
249val returning_rows :
250 catalog ->
251 Ast.value array ->
252 table:string ->
253 cols:string list ->
254 Ast.result_col list ->
255 Ast.value list list ->
256 Ast.value list list
257(** [returning_rows cat params ~table ~cols returning rows] projects a
258 [RETURNING] column list over each affected [row] of [table] ([cols] are the
259 table's column names, aligned to [row]); [*] expands to the whole row. *)