Alpha

These pages are built from main, turborel 0.0.0. Anything may change from one build to the next: SQL, API, protocol and files alike.

Optimizer Rules and Statistics

The planner takes plug-ins at two places. An optimizer rule rewrites the logical plan of each statement as it is planned. Statistics cross both ways. A storage engine or an index method tells the planner what it knows of its rows, and a plug-in asks the database what it keeps of a table, a column or an index. What each costs is a count of calls. A rule costs one call a pass of every statement planned. An engine's or an index's statistics cost one call when first asked, and one each time they go stale. A plug-in asking for statistics costs one round trip a question. Whether that is worth it is the operator's choice.

The examples run with the example plug-in, its manifest declaring these objects.

OPTIMIZER RULE CONTRADICTION PHASE BOUND;
OPTIMIZER RULE ERRING;
STORAGE ENGINE FILES;
INDEX METHOD SORTED SUPPORTS (EQUALITY, RANGE);
PROCEDURE SKEW(VARCHAR(128), VARCHAR(128)) MODIFIES SQL DATA;
CREATE EXTENSION EXAMPLE;
CREATE TABLE T (A INTEGER, B INTEGER);
INSERT INTO T VALUES (1, 1), (2, 2), (3, 3), (4, 0), (5, 1), (6, 2), (7, 3), (8, 0);
OK
OK
OK

Optimizer rules

An optimizer rule is kind 37. It is declared with the phase it runs in and the passes it makes at most.

OPTIMIZER RULE <name> [ PHASE { BOUND | REWRITTEN } ] [ PASSES <count> ]

A rule of PHASE BOUND rewrites the plan as bound, before the built-in rules. A rule of PHASE REWRITTEN, the default, rewrites the plan they made, before the physical planner orders its joins and chooses its paths. The rules of a phase run in the order of their extensions' names, then in the order their manifest declares them. Each runs a pass at a time until it answers no change, or until its PASSES (1 unless written) or OPTIMIZER.MAX_PASSES is reached.

A pass is one CALL of operation 1, REWRITE. Its payload is the plan in the plan form, and its RESULT a byte 0 for no change or a byte 1 and the plan rewritten. The example's CONTRADICTION finds a filter no row passes, a column above one literal and below another, and makes it an empty VALUES. EXPLAIN names it among the rules that fired, and no table is read.

EXPLAIN SELECT A FROM T WHERE A > 5 AND A < 3;
 PLAN
---------------------------------------------------------
 -- bound:
 Project T.A
   Filter T.A > 5 AND T.A < 3
     Scan ANN.T
 -- rules: EXAMPLE.CONTRADICTION, EXAMPLE.ERRING skipped
 -- optimized:
 Project #0
   Values
 -- physical:
 Project #0
   Values
(11 rows)

A rule is an optimization, so its failure fails nothing. A rule whose call fails, runs past PLUGINS.CALL_TIMEOUT_MS, or gives a plan that is not valid is skipped for the statement, every pass it made undone. EXPLAIN names it skipped, and the statement completes with the warning SQLSTATE 01T02 (Appendix A). The example's ERRING always fails.

EXPLAIN SELECT A FROM T WHERE A > 6;
 PLAN
---------------------------------------
 -- bound:
 Project T.A
   Filter T.A > 6
     Scan ANN.T
 -- rules: EXAMPLE.ERRING skipped
 -- optimized:
 Project T.A
   Filter T.A > 6
     Scan ANN.T
 -- physical:
 Project T.A
   Filter T.A > 6  (est. rows=3)
     SeqScan ANN.T  (rows=8, cost=7.2)
(13 rows)

A prepared statement keeps its plan, so it makes no call when run again. The subqueries a statement runs again for each row are planned once with it, and a rule sees them as kept expressions.

The plan form

The plan form is format 1, apart from the planner's own types, so a program built against one release rewrites another's plans. A plan is a tree of nodes. Each node has an operator code, the planner's id of it (0 for a node a rule made), whether it is kept, its output columns each with its name and type, the planner's estimates of its rows and of a row's width, a body, and its inputs.

plan:   format u32 (1) | node
node:   op u8 | id u32 | kept u8 | columns: count u32 | (name str | type str)...
        | rows f64 | width f64 | body | inputs: count u32 | node...
Code Operator Body
1 SCAN table str, then each column's statistics, distinct f64, nulls f64, u8 0 or u8 1 and its least and greatest values
2 FILTER condition
3 PROJECT count u32, expressions
4 JOIN kind u8 (0 cross, 1 left, 2 right, 3 full, 4 semi, 5 anti, of the left's columns alone), u8 0, or u8 1 and its condition
5 AGGREGATE kept alone
6 SORT count u32, each column u32, descending u8, nulls first u8
7 LIMIT kept alone
8 DISTINCT nothing
9 SET op u8 (1 union, 2 except, 3 intersect), all u8
10 VALUES count u32 rows, each count u32 expressions
11 to 18 SYSTEM, RECURSIVE, WORK TABLE, TRANSITION, UNNEST, WINDOW, RECOGNIZE, POLYMORPHIC kept alone

A kept node has a label str as its body, for people. Its body is the planner's, and the rule may move it to another place but not open it. Its inputs stay open, and each must give the columns and types it gave. A recursive query and a polymorphic table function keep their inputs too.

Code Expression Body
1 COLUMN index u32 of the input's columns, the two of a join one row
2 LITERAL type str, a value of protocol 1
3 CALL name str, count u32, arguments
4 OPERATOR op u8, count u32, operands
5 CAST type str, operand
6 OPAQUE id u32, count u32, the columns it reads

The operators are 1 AND, 2 OR, 3 NOT, 4 =, 5 <>, 6 <, 7 >, 8 <=, 9 >=, 10 IS NULL, 11 IS NOT NULL, 12 +, 13 -, 14 *, 15 / and 16 negation. A type is a <data type> as SQL writes it, empty where the planner does not know it, and a number not known is negative. A function is named by CALL only where its name finds it alone. An expression the form cannot say is OPAQUE, as a subquery, a CASE or a LIKE. A rule may name its columns again, as other columns of the same row, and may move it, but may not open it or use it twice.

The planner checks the plan it is given back. Each node must have the inputs its operator takes, each column must be one of its input's, each table one the catalog holds, and each kept node and opaque expression one it was given, used once. Each function must take its arguments, each comparison must be of comparable types, and each condition must be BOOLEAN. The plan must give the columns and types it gave. That the plan returns the same rows is the rule's own contract, which the planner cannot check.

Statistics for the planner

A storage engine answers operation 8, STATISTICS, of a table's locator, and an index method operation 9 of an index's.

table:   u8 0 (none) | u8 1 | rows f64 | width f64 | refresh u64 | count u32 | column...
column:  distinct f64 | nulls f64 | u8 0, or u8 1 | least value | greatest value
         | count u32 | histogram bound values... | u8 0, or u8 1 | most f64 | median f64 | p90 f64 | p99 f64
         | count u32 | (common value | share f64)...
index:   u8 0 (none) | u8 1 | entries f64 | distinct keys f64 | pages f64 | refresh u64

A histogram's values are its bounds, ascending, each bucket between two of them holding as many values. The frequencies are how many times the most repeated value appears, and the median, 90th and 99th percentile of the repetitions. The common values are the values many rows hold, each with the share of the table's rows it holds, and the histogram then describes the other values; a program that keeps none sends a count of 0. The first time the planner asks, the program is asked, and its answer is kept, so later questions cost no call. It is asked again at the planner's next question once the rows or entries written since reach refresh, and when the table is analyzed (Database::analyze). An answer of none, or a call that fails, is kept as none until then, and the planner takes its defaults, as of a program that answers no statistics. The example's FILES counts each column's distinct values, so the planner estimates an equality on a column of four values over 64 rows at 16.

CREATE TABLE F (K INTEGER, V INTEGER) USING FILES;
INSERT INTO F SELECT X.B, 10 * X.A + Y.A FROM T AS X, T AS Y;
COMMIT;
EXPLAIN SELECT V FROM F WHERE K = 1;
OK
OK
OK
 PLAN
-----------------------------------------
 -- bound:
 Project F.V
   Filter F.K = 1
     Scan ANN.F
 -- rules: EXAMPLE.ERRING skipped
 -- optimized:
 Project F.V
   Filter F.K = 1
     Scan ANN.F
 -- physical:
 Project F.V
   Filter F.K = 1  (est. rows=16)
     SeqScan ANN.F  (rows=64, cost=64.0)
(13 rows)

An index method's distinct keys estimate an equality on all its columns, and its pages a probe's descent.

Statistics a plug-in asks

While a call runs, its program may send STATISTICS, type 11, and the database answers STATISTICSDONE, type 12, or ERROR.

STATISTICS      call u64 | u8 1 table | name str
                         | u8 2 column | table name str | column name str
                         | u8 3 index | name str
STATISTICSDONE  call u64 | table statistics, of a table or a column, or index statistics

A table is written SCHEMA.TABLE. A column's answer is its table's, with that column alone. The answer is what the newest state of the database keeps, the statistics the planner reads. A table that was not analyzed, or whose engine keeps none, answers none. A procedure or table function asks by its user's privileges, checked by a query of the table that reads no row. Another kind runs as the server, so it may ask of any table. A question of a table there is not, or one the user may not read, is answered ERROR. An optimizer rule needs to ask nothing, as each scan of its plan form holds its table's statistics.

The example's SKEW writes the rows and distinct values the database keeps of a column into SEEN.

CREATE TABLE SEEN (N DOUBLE PRECISION, D DOUBLE PRECISION);
COMMIT;
CALL SKEW('ANN.F', 'K');
SELECT * FROM SEEN;
OK
OK
OK
                        N |                        D
--------------------------+--------------------------
                    6.4E1 |                      4E0
(1 row, with a warning: SQLSTATE 01T02)

The SDK

Rule::rewrite(cx, form) gives the form rewritten, or none (Plugin::rule). The form's types are turborel_plugin::plan, and its reading and writing are the SDK's. Engine::statistics(locator) and IndexMethod::statistics(locator) answer the planner, a TableAnswer or an IndexAnswer, and answer none unless written. A call asks the database with Cx::table_statistics, Cx::column_statistics and Cx::index_statistics.