SQL database (P38)
Strata is a SQL database written for this prototype in plain JavaScript, with no dependencies at run time. It runs in the page. The console opens with a small shop loaded: customers, products, orders and their lines.
The SQL it reads
Strata reads SQL as SQLite reads it. Tables have types, primary keys, NOT NULL, UNIQUE, DEFAULT and CHECK. Indexes can be on columns or on expressions. A SELECT can join tables in every way, right and full outer joins included. Its subqueries can be scalar, IN or EXISTS, and can read the row of the query around them. It can group with GROUP BY and HAVING, combine results with UNION, INTERSECT and EXCEPT, use WITH and WITH RECURSIVE, and compute window functions over frames of rows or ranges. INSERT can resolve a conflict with OR IGNORE, OR REPLACE or ON CONFLICT DO UPDATE. Transactions have savepoints.
Values
Every value has a storage class: NULL, INTEGER, REAL, TEXT or BLOB. A column's declared type gives it an affinity, which converts what is stored in it, so the text '3.0' stored in a NUMERIC column becomes the integer 3. A comparison applies the affinity SQLite picks for the pair. Integers are 64 bits wide and overflow to REAL. NULL follows three-valued logic. REAL is printed with SQLite's own digits: its decimal conversion is written again, down to the double-double arithmetic it uses.
Storage
A table is a B+-tree keyed by rowid, with its rows in the leaves in SQLite's record format. An index is a B-tree keyed by its columns and the rowid. Both live on pages of 4,096 bytes, and a long value continues in a chain of overflow pages. A full page splits and a page that falls below a third full is merged or rebalanced with its neighbor.
A transaction's changed pages are held in memory. COMMIT appends each of them to a write-ahead log as a frame. The last frame is marked as the commit and holds the size of the database. Then the log is made durable. Each frame has a checksum that runs on from the frame before it. After a crash, Strata reads the log up to its last whole commit and drops the rest, so a transaction that did not commit leaves nothing behind. The console's database is kept in IndexedDB as its two files.
The planner
The planner works by cost. It keeps the row count of each table, and ANALYZE adds the distinct counts of each index. For each table it weighs a scan, a seek on the rowid, an index seek on an equality and a range, an IN list and an index that holds every column the query needs. It orders up to six joined tables by working out the cheapest plan for every subset of them. Each join is a nested loop, often with an index seek, or a hash join. A filter runs at the first step where its columns are there. EXPLAIN shows the plan as a tree with the rows each step was expected to give, the rows it gave and its time.
The judge
Strata is held against SQLite 3.51.3, the SQLite built into node. A script runs the corpus in SQLite and records every answer: scripts grouped by family, the shop and TPC-H with their queries, and the statements of a fuzzer that writes random schemas, rows and queries from a seed. The page against SQLite runs the same statements in Strata in the browser and compares each answer. Two values are equal when they have the same storage class and value, and two REALs when SQLite prints them alike.
Previous: Map of Aarhus (P37). Next: JavaScript engine (P39).