Prototypes StrataP38 · SQL database

Strata against SQLite

SQLite 3.51.3, the one built into node on the Mac that made the corpus, answered every statement below: scripts grouped by family, the shop and TPC-H with their queries, and random schemas, rows and queries from a fuzzer. This page runs the same statements with Strata, in this browser, and compares each answer with SQLite’s: the same columns, the same rows with the same storage classes, the same number of changed rows, or an error of the same kind (the same message, in the families on WITHOUT ROWID tables, on UPDATE with FROM and on RETURNING).

Working. The corpus is being loaded and run.

How Strata is built
  1. Strata is a SQL database written for this prototype in plain JavaScript, with no dependencies. It reads SQL as SQLite does: tables with types, keys and constraints, WITHOUT ROWID tables, indexes (on expressions too), joins of every kind, subqueries, GROUP BY, window functions, set operations, WITH and WITH RECURSIVE, UPDATE … FROM, RETURNING, and transactions with savepoints.
  2. Values are typed as SQLite types them: each value has a storage class (NULL, INTEGER, REAL, TEXT or BLOB), and a column’s declared type gives it an affinity that converts what is stored in it. Comparisons apply the affinity SQLite picks for the pair, integers are 64-bit and overflow to REAL, and NULL follows three-valued logic. REAL is printed with SQLite’s own digits, from its decimal conversion written again.
  3. Tables are B+-trees keyed by rowid, with the rows in the leaves in SQLite’s record format; an index is a B-tree keyed by its columns and the rowid. A WITHOUT ROWID table is an index B-tree keyed by its PRIMARY KEY that holds the whole row, the key’s columns first, and its indexes end in the key’s columns instead of a rowid. All of them live on pages of 4,096 bytes, and a long value goes on in a chain of overflow pages.
  4. A transaction’s pages wait in memory. COMMIT appends each changed page to a write-ahead log as a frame, marks the last frame as the commit and makes the log durable. Each frame has a checksum that runs on from the one before, so after a crash Strata replays the log up to the last whole commit and drops the rest. ROLLBACK and savepoints put back the pages they kept, and a statement that fails runs in a savepoint of its own and changes nothing.
  5. The planner works by cost. It keeps row counts per table, and ANALYZE adds distinct counts per index. For each table it weighs a scan, a seek on the rowid or on an index (equality on a prefix, then a range), an IN list and a covering index. It orders up to six joined tables by dynamic programming over their subsets, with a nested loop or a hash join for each step, and pushes each filter down to the first step where it can run. EXPLAIN shows the tree with the rows each step was expected to give and the rows it gave.
  6. The executor is a tree of iterators, one per step of the plan, which pass rows up as they are asked for them, so a LIMIT stops the work below it.
  7. UPDATE … FROM runs as SQLite runs it: the target joined with the FROM clause is a query of its own, which the planner orders like any join and EXPLAIN shows. Each target row changes once, with the last joined row it met, in the order of its rowid or key.
  8. RETURNING on an INSERT, an UPDATE or a DELETE gives a row for each row the statement changed: the row as it is after the change, and for a DELETE the row that went. Each row is worked out right after its change, so a subquery in the list sees the rows changed so far, and EXPLAIN shows RETURNING as a step over the write.
  9. The console’s database is kept in this browser’s Origin Private File System as two files, strata.db and strata.db-wal. Each time the database makes bytes durable, a worker writes them through a synchronous access handle and flushes, so a reload opens the files again through the same recovery. A database an earlier visit kept in IndexedDB moves into OPFS on the first visit, and a browser without OPFS keeps using IndexedDB. The console shows which of the two holds the database.
  10. Strata is judged against SQLite 3.51.3 itself. A script ran every statement of the corpus in SQLite and recorded its answers, and the page against SQLite runs the same statements in Strata and compares each answer. Two values are equal when they have the same storage class and value; two REALs count as equal when SQLite prints them alike, to 15 significant digits.