Prototypes StrataP38 · SQL database

Inside the database

Strata keeps every table and index as a B-tree on pages of 4,096 bytes, writes each transaction to a log before it touches the database file, and plans each query by cost. This page opens the database the console keeps in this browser and shows its pages, its log, a crash and its recovery, and the planner at work.

The B-tree of a table or an index

A table’s tree is keyed by rowid and holds its rows in the leaves; an index’s tree is keyed by its columns and the rowid. A WITHOUT ROWID table is an index tree keyed by its PRIMARY KEY, whose entries are whole rows, and its indexes end in the key’s columns. Open an interior page to see the pages under it, and press a page to see its cells.

A page

Press a page.

The write-ahead log

A commit appends every page it changed as a frame, marks the last frame as the commit with the size of the database, and makes the log durable. Each frame carries a checksum that runs on from the frame before it. A checkpoint copies the newest frames into the database file and starts the log again.

A crash in the middle of a transaction

A database of its own, so the console’s is not touched: three transactions commit, a fourth inserts rows until its pages spill into the log, and then the power goes. A random part of what the disk had not yet made durable survives, so the last frame can be cut in the middle. Opening the files again replays the log up to its last whole commit.

    The planner choosing a join order

    For a join of four tables the planner works out the cheapest way to join every subset of them, from one table up, and keeps the best for each. Below are the ways it weighed for the whole join, cheapest first, with the cost it estimated, and then the plan it chose, run with the rows each step expected and gave.

    

    

    The plan it chose
    

    

    

    

    

    


    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. 

    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. 

    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. 

    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. 

    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. 

    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. 

    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. 

    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. 

    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. 

    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.
      11.