Skip to content
Loess

@loess/database

A circle's SQLite database over the pages of its newest commit. It reads pages only through a PageSource, so it knows nothing about storage, keys, or the network, and it reads only the pages a query touches.

const database = yield * CircleDatabase;
const Message = Schema.Struct({ id: Schema.String, value: Schema.String });
const newest =
  yield *
  database.query(
    sql(Message)`SELECT id, value FROM stored_facts
      WHERE field = ${'message/text'} AND current ORDER BY id DESC LIMIT 20`,
  );

layerCircleDatabase(options) builds a CircleDatabase over the PageSource in context, and reads page 1 when it is built. A source without page 1 is a new circle, and the database makes its schema in memory, so the first commit holds every page. In a Cloudflare Worker, which can't compile WebAssembly from bytes, pass the sqlite3.wasm module the bundle imports as wasm. pageLimit sets the most pages one query touches before it fails with TooManyPages.

Interface

  • query(statement) runs a read-only Statement from sql and decodes each row with its schema. It fails with TooManyPages before it fetches past its page limit, 128 by default, and with PagesMissing when the source leaves out a page it needs, as an offline device's does.
  • facts is the program package's Facts. A program can't wait for a read, so a call that needs a missing page throws PagesMissing, and fetch(pages) reads those pages before the program runs again.
  • write(written) writes a transaction. With an inboxCounter it is settled, and without one it is pending, held in memory on top of the settled state. A rejection stores the transaction's row and no facts. A change whose replaces no longer matches the current value fails with Conflict, which carries that value. A writer, device, and deviceCounter that a commit already settled fail with AlreadySettled.
  • commit(commit, hash) records the commit of the settled transactions written since the last one, and returns the plain pages it changed and the page count. The caller seals the pages.
  • moveTo(source) moves to a new head's pages and writes each pending transaction again on top, in order. It returns the pending transactions the head settled, found by writer, device, and deviceCounter, and the ones that no longer apply.
  • drop(hash) takes a pending transaction out of the pending layer, such as one storage refused, and writes the others again on top.

pageMapLeaves and pageMapRoot build a commit's page map from the hash of each sealed page: the leaves it changes, which the caller seals, and then the root. leafOfPage gives the leaf that holds a page's hash, and each leaf holds pagesPerLeaf hashes. The root also holds the hashes of the first firstPagesInRoot pages, which are page 1 and the B-tree roots, so a cold device reads them without a leaf. leavesReadAtOpen is the most leaves a cold device reads when it opens a circle.

@loess/database/test gives testDatabase, the contract suite.

How it reads pages

A query that needs a page the database doesn't hold stops, and runs again over stand-in pages to find the other missing pages of the same B-tree level. Each stand-in holds the keys that bound its page, taken from the held interior page above it, so the scan stops about where the real one would. The stand-in for a page of a rowid table, such as transactions or an FTS5 content table, holds rows of one NULL column with rowids from those bounds, so looking up 50 scattered rowids among 10,000 messages takes 4 reads, not 16. A filter drops every stand-in row, so a filtered scan stops after a run of neighbouring stand-in leaves as long as the pages of that table it already holds. The dry run stops at a missing page of another B-tree, such as the table a join reads next, because a lookup in a stand-in finds no data and the join would scan on. Then the database reads every missing page it found in one read, and runs the query again.

The schema

A fact row stores its transaction, its writer, and its commit time, and the facts_value, facts_field, and facts_long indexes hold every column, so a view walks one B-tree. facts_value holds numbers, references, and other values of at most 64 bytes, sorted by value, and facts_long holds the longer ones by id, so the messages of a commit don't each change a page of the value index. SQLite uses a partial index only when the query's WHERE repeats the index's condition, or one side of its OR, such as typeof(value) IN ('integer', 'real'). The newest 20 of 30,000 messages take 4 round trips and 12 KiB. transactions holds a row for each settled or pending transaction, with its writer, device, device_counter, inbox_counter, commit, and rejection, and transactions_rejected finds a rejected one by (writer, device, device_counter). devices holds each device's settled counters as ranges, such as [[1,41],[43,90]], so a write fails with AlreadySettled when its counter is in them. commits holds each commit's hash and time. The stored_facts view gives each fact with its writer and committed_at, so facts and an app read the same SQL. A fact that no commit holds yet reads committedAt as Number.MAX_SAFE_INTEGER.

A value is text, a number, bytes, null for a deleted fact, or a reference, stored as the id it refers to, with is_reference set to 1.

Edit on GitHub