Something went wrong. Try again.
My own corner of monopam
Something went wrong. Try again.
16 kB · 318 lines
OCaml
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319(*--------------------------------------------------------------------------- Copyright (c) 2025 Thomas Gazagnaire. All rights reserved. SPDX-License-Identifier: ISC ---------------------------------------------------------------------------*)
(** SQL query execution over any store.
[Query] runs queries over a {!catalog}, which gives the columns and rows of each table, so comparisons, [LIKE], joins and ordering do not depend on the store and can be tested alone. The catalog uses {!Catalog.Value.t}, and [Query] converts to and from {!Ast.value}. *)
type catalog = { columns : string -> string list; (** [columns name] is the column names of the table [name], in declaration order. *) rows : string -> Catalog.Value.t list list; (** [rows name] is the rows of [name], each aligned to {!columns}. *) rows_rowid : string -> (int64 option * Catalog.Value.t list) list; (** [rows_rowid name] is the rows of [name] with their rowids, or [None] for a source without one, such as a view, a derived table or [VALUES]. *) has_rowid : string -> bool; (** [has_rowid name] is [true] iff the relation [name] has an implicit rowid. A plain table has one; a view, a [WITHOUT ROWID] table, a [VALUES] list and a materialised CTE do not, so [rowid] is an unknown column there. *) index_scan : string -> (string * Catalog.Value.t) list -> (string * Catalog.Value.t list list) option; (** [index_scan table eqs] is [Some (path, rows)] if an index on [table] serves the column equalities [eqs], and [None] for a full scan. The caller filters the rows again, so it only saves work. [path] names the access as {!best_index_for} does. *) best_index_for : string -> string list -> Catalog.Spi.access_path option; (** [best_index_for table cols] is the best access path for an equality on [cols] in [table], the one that binds the most key columns. The planner costs it and {!explain} prints it. *) affinity : string -> string -> Catalog.Value_ops.affinity option; (** [affinity table col] is the affinity of the declared type of [col], or [None] for a relation without a schema, such as a derived table or a view. The planner follows a chain of equalities only between columns with the same affinity. *) row_count : string -> upto:int -> int; (** [row_count table ~upto] is the number of rows of [table], counted up to [upto]. The planner uses it to choose between an index seek and a hash. A relation that is not a table returns [upto]. *) collation : string -> string -> string option; (** [collation table col] is the declared [COLLATE] sequence of [col], in upper case, or [None] for BINARY and for a derived source. *) table_function : string -> (string list * (Catalog.Value.t list -> Catalog.Value.t list list)) option; (** [table_function name] is [Some (columns, rows)] for a table-valued function of the backend, such as the [pragma_*] functions, with [rows args] its rows for the arguments [args]. [None] leaves [name] to {!Func}. *) scalar_function : string -> (Catalog.Value.t list -> Catalog.Value.t) option; (** [scalar_function name] is [Some f] for a scalar function of the backend, with [f args] its value. The backend provides the functions whose value depends on the connection, such as [last_insert_rowid()] and the change counters. [None] leaves [name] to {!Func}. *) subquery : catalog -> (string * (string * Catalog.Value.t) list) list -> Ast.select -> Catalog.Value.t array -> Catalog.Value.t list list; (** [subquery cat scope s params] is the rows of [s] over [cat], with the outer scope [scope]. It runs every select reached from the catalog: a scalar, [IN] or [EXISTS] subquery, a [FROM] subquery, a CTE body, and the parts of a recursive CTE. [cat] may be a derived catalog that hides a relation. The builder of the catalog chooses it, so a backend can count what its runner reads. *) subquery_memo : (Ast.select, Catalog.Value.t list list) Hashtbl.t; (** The rows already computed for correlated subqueries, keyed by the subquery with its correlated columns replaced by values. Outer rows with the same values share one run. Each catalog needs its own table. *) recursion_cap : int; (** The rows a recursive CTE may produce over this catalog before it is refused with [Failure], positive. A derived catalog keeps the cap of the catalog it derives from. *)}(** The type for catalogs. *)
val default_recursion_cap : int(** [default_recursion_cap] is the cap on a recursive CTE a catalog takes when its caller names none, the one {!of_catalog} and {!Engine.catalog} apply. *)
val of_catalog : ?recursion_cap:int -> subquery: (catalog -> (string * (string * Catalog.Value.t) list) list -> Ast.select -> Catalog.Value.t array -> Catalog.Value.t list list) -> Catalog.t -> catalog(** [of_catalog ?recursion_cap ~subquery cat] is the catalog of [cat], with [subquery] as its runner, usually from {!Engine.run_select}, and [recursion_cap] (default [1_000_000]) as its {!field-recursion_cap}. @raise Invalid_argument if [recursion_cap] is not positive. A backend such as Irmin or Parquet implements {!Catalog.Spi.S} and adapts it here. The catalog has no functions of its own. *)
val table_function : catalog -> string -> Ast.value list -> string list * Ast.value list list(** [table_function cat name args] is [(columns, rows)] for the table-valued function [name] applied to [args]: the one of the backend ({!field-table_function}) if it has one, and the one of {!Func} otherwise.
@raise Catalog.Error.Prepare if neither has [name]. *)
val call : catalog -> ?coll:Catalog.Collation.t -> string -> Ast.value list -> Ast.value(** [call cat ~coll name args] is the scalar function [name] applied to [args]: the one of the backend ({!field-scalar_function}) if it has one, and [Func.apply ~coll name args] otherwise. Every evaluator calls functions through it.
@raise Catalog.Error.Prepare as {!Func.apply} does. *)
val check_calls : ?explain:bool -> catalog -> Ast.select -> unit(** [check_calls ~explain cat s] accepts [s] if every call in its select list, [WHERE], [GROUP BY], [HAVING], [ORDER BY] and join conditions names a function that {!val-call} accepts with that number of arguments, or raises. As in sqlite3, calls are checked when the statement is prepared, so a bad name fails even over an empty table. A function of the backend accepts any number of arguments. Aggregate calls and subqueries are checked elsewhere. [explain] (defaults to [false]) accepts unknown names but still checks argument counts, as sqlite3 does for [EXPLAIN].
@raise Catalog.Error.Prepare as {!Func.apply} does: ["no such function: f"] for an unknown name, and ["wrong number of arguments to function f()"] for a wrong count. A built-in scalar function at the head of a window fails with ["f() may not be used as a window function"], and a window function called without one with {!Func.window_misuse}'s sentence. *)
val resolve_env : catalog -> Resolve.env(** [resolve_env cat] is the schema of [cat] as {!Resolve} reads it, without rows, indexes or runner. *)
val within_build_budget : Catalog.Value.t list list -> bool(** [within_build_budget rows] is [true] iff a hash over [rows] stays within {!Catalog.Join.budget}. It stops counting at the first row past the budget.*)
type binding = string * (string * Ast.value) list(** The type for named rows, [(alias, [(column, value); ...])]. A [scope] is an outer list of bindings, after those of the row, so an inner column hides an outer one of the same unqualified name, and [alias.col] still reaches it. It holds the enclosing row of a correlated subquery, or the [OLD] and [NEW] rows of a trigger. *)
val reads_table : string -> Ast.select -> bool(** [reads_table name s] is [true] iff [s] reads the relation [name], without regard to case, in its [FROM], a join, a compound arm, a nested [WITH] body or a subquery. *)
val materialize_ctes : catalog -> Ast.value array -> Ast.cte list -> catalog(** [materialize_ctes cat params ctes] is [cat] with the rows of each [WITH] table of [ctes] bound under its name, a recursive one computed by semi-naive evaluation. It serves the [WITH] of an [UPDATE] or a [DELETE]. *)
val flatten_ctes : catalog -> Ast.select -> Ast.select(** [flatten_ctes cat s] is [s] with each [WITH] table that one [FROM] reads exactly once merged into that reader: the table of the body takes the name of the CTE, and the [WHERE] of the body joins the [WHERE] of the reader, so an index can serve it. As in sqlite3 ([flattenSubquery], src/select.c), the body must read one plain table and have no aggregate, [DISTINCT], compound, recursion, window, [LIMIT], [OFFSET] or [ORDER BY]. Other CTEs stay for {!materialize_ctes}. *)
type membership = { states : Catalog.Value_ops.affinity option; (** The affinity of the compared column, combined with the affinity of the left operand as for a comparison (src/expr.c). *) rows : Catalog.Value.t list option; (** The first column of the rows of an uncorrelated subquery, which the register VM compiles as a list. [None] for a correlated subquery, which runs for each outer row. *)}(** The type for the right-hand side of [x IN (SELECT ...)], from which {!Lower.query} builds the membership. *)
val opaque_membership : membership(** [opaque_membership] states no affinity and holds no rows. *)
val membership : run:(Ast.select -> Ast.value list list) -> catalog -> Ast.select -> membership(** [membership ~run cat sub] is the affinity of the compared column of [sub] and, if [sub] is uncorrelated, the values of that column, computed with [run] and cached in [cat]. *)
val lift_outer_aggregates : Resolve.env -> Ast.select -> Ast.select(** [lift_outer_aggregates env s] is [s] with each aggregate a subquery of its select list, [HAVING] or [ORDER BY] computes over [s]'s columns alone made [s]'s, as sqlite3 attributes it: [s] then reads its aggregates off a grouped select over its sources. A select with no such aggregate is [s] itself.
@raise Catalog.Error.Prepare on such an aggregate in [s]'s [WHERE], [GROUP BY] or a join condition, and, as not supported, in a compound select, beside a window function or beside a [*] over a [NATURAL] or [USING] join. *)
val hoist_subqueries : run:(Ast.select -> Ast.value list list) -> catalog -> Ast.select -> Ast.select(** [hoist_subqueries ~run cat s] is [s] with each uncorrelated scalar or [EXISTS] subquery in its select list, [WHERE], [GROUP BY], [HAVING], [ORDER BY] and join conditions replaced by its value, computed with [run]. An uncorrelated subquery is constant, and the register VM, which has no subquery instruction, can then compile [s]. A literal [v IN (SELECT c ...)] over an uncorrelated subquery that only narrows its sources is replaced by true where a row with [c = v] exists, which an index on [c] answers with a seek. Correlated subqueries stay, and {!membership} handles the other [IN (SELECT ...)]. *)
val is_aggregate_query : Ast.select -> bool(** [is_aggregate_query s] is [true] iff [s] has a [GROUP BY], a [HAVING] or an aggregate in its select list. Its [LIMIT] cannot move into the scan. *)
val aggregate_compilable : Ast.select -> bool(** [aggregate_compilable s] is [true] iff [s] aggregates and has no window ({!select_windows}), so the register VM runs it as a grouped query. An aggregate over [rowid], such as [count(rowid)], compiles. *)
val window_compilable : Ast.select -> bool(** [window_compilable s] is [true] iff [s] has a window function, does not aggregate and does not project [rowid], so the register VM scans it and {!Window.scan} computes the windows. *)
val window_over_groups : Ast.select -> bool(** [window_over_groups s] is [true] iff [s] aggregates and has a window function, which runs over the grouped rows. {!Engine.run_select} runs such a select; a backend should pass it there. *)
val is_agg_expr : Ast.expr -> bool(** [is_agg_expr e] is [true] iff [e] is an aggregate call, with or without [DISTINCT], [FILTER] or [ORDER BY] inside the call. It does not look into the operands of [e]. *)
val window_exprs : Ast.result_col list -> Ast.expr list(** [window_exprs cols] is the distinct [Window] nodes of [cols], in order of first appearance. It does not look into a [Window] node. *)
val select_windows : Ast.select -> Ast.expr list(** [select_windows s] is the distinct [Window] nodes [s] computes, in order of first appearance: those of its select list, then those only its [ORDER BY] names (lang_select.html section 2). *)
val set_op : ?colls:Catalog.Collation.t option list -> Ast.set_op -> Ast.value list list -> Ast.value list list -> Ast.value list list(** [set_op ~colls op left right] combines the rows of two compound arms. [UNION ALL] keeps every row in order. [UNION], [EXCEPT] and [INTERSECT] give distinct rows in key order, as sqlite3 does with an index on the row. [colls] is the collating sequence of each column ({!Resolve.compound_collations}); [None] or a missing entry is BINARY. Of rows with equal keys, the first one is kept. *)
val facts : catalog -> Plan.facts(** [facts cat] is what the planner knows of [cat]: its columns and affinities, its best index for an equality, the size of a relation, and what its seeks can do. A seek key is a constant or a column of an outer row, and a row found by a seek has no rowid. *)
val plan : catalog -> Ast.select -> Plan.t(** [plan cat s] is the access path of each source of [s] and the order of the loop, [Plan.v] of {!facts}. {!Engine.run_select} runs this plan and {!explain} prints it. It uses the query as written, without parameter values or subquery results. The [WITH] tables of [s] are bound ({!materialize_ctes}) for their columns only; their rows are not computed.*)
val plan_sources : catalog -> Ast.select -> Plan.access list(** [plan_sources cat s] is the accesses of [plan cat s], in scan order: the [FROM] source, then each join operand. *)
(** The type for the value a seek binds a key column to: a value known before the loop, or [Outer (i, j)], column [j] of the cursor at scan position [i] where the loop stands when the seek rewinds. *)type seek_key = Value of Ast.value | Outer of int * int
val seek_keys : catalog -> Ast.value array -> Plan.access -> (string * seek_key) list option(** [seek_keys cat params access] is each key column of the seek [access] with the value it binds, a constant, parameter or closed subquery evaluated over [params]. It is [None], and the caller reads the whole relation, if [access] is not a seek or a key has no single value, such as an unbound parameter or an IN list. The rows {!field-index_scan} answers have no rowid, so {!plan} uses no seek for a query that reads one. *)
val explain : catalog -> Ast.select -> string(** [explain cat select] is {!plan} of [select], after the rewrites the engine applies, as one line per source in scan order, such as [SCAN t] or [SEARCH t USING INDEX i]. It first checks the names with {!Resolve.check_columns} and with {!check_calls} under [~explain:true].
@raise Catalog.Error.Prepare for a name that resolves to no column. @raise Failure for a source naming a relation the store has not got. *)
val is_agg : string -> Ast.expr list -> bool(** [is_agg name args] is [true] iff [name] with the arguments [args] is an aggregate, such as [count], [sum] or [avg], or [min] and [max] with at most one argument. *)
val is_rowid_name : string -> bool(** [is_rowid_name n] is [true] iff [n] is [rowid], [oid] or [_rowid_], without regard to case (lang_createtable.html section 2.6). A declared column of that name comes first. *)