NURLNURL registrynurl-lang.org →

← nurldb

nurldb 0.1.1 API

bufpool.nu

packages/nurldb/src/bufpool.nu — the buffer pool.

A fixed number of page frames shared by every thread. A page is reached only through a guard:

( pool_read p pid ) → PageRead shared: any number of readers ( pool_write p pid ) → PageWrite exclusive ( pool_new_page p type ) → PageWrite a page appended to the file ( page_bytes r ) / ( page_bytes_mut w ) → ( Slice u )

A guard pins its frame (the frame is not evicted while it is held) and latches it (a read or a write latch on the frame's RwLocked). The bytes are a view held to the guard: the borrow checker ends the view where the guard goes, so hand-over-hand traversal — take the child's guard, then let the parent's go — is safe by construction, and a read guard's view is frozen (RGuard is % Frozen, and a struct holding one lends frozen views too): nothing can write through it. A guard is released by its drop, on every way out, a panic included (the drop journal).

Concurrency. The page table (pid → frame) is an RwLocked: a lookup that finds its page takes it shared, so hits on different pages never wait for each other; only a miss takes it exclusively. A miss evicts by the clock algorithm: a frame nobody pins whose reference bit is clear. A clean victim's write latch is taken (it is uncontended: nothing pins the frame) before the page table is let go, so the page it is about to hold cannot be read before it is loaded. A dirty victim is written back first — pinned, outside the table lock, after the log is durable up to the page's LSN (the write-ahead rule) — and the miss starts over.

Writing a page out happens under a READ latch (readers carry on): the page's checksum goes into a copy, which is what reaches the disk.

API

: Frame

: Frame {
    ( Vec u ) data
    // The page it holds, -1 none.
    i pid
}

: PidMap

: PidMap {
    ( Vec i ) keys
    ( Vec i ) vals
    i mask
    // The clock hand, kept with the table it is moved under.
    i hand
}

pid → frame, open addressing with linear probing: keys -1 empty. A deletion shifts the entries after it back (no tombstones), so a table that churns forever — every eviction deletes one page and inserts another — never fills up with dead slots a lookup must walk past.

: PoolImpl

: PoolImpl {
    PFile file
    Wal wal
    ( Vec ( RwLocked Frame ) ) frames
    ( Vec Atomic ) pins
    ( Vec Atomic ) dirty
    ( Vec Atomic ) refb
    ( RwLocked PidMap ) map
    // Pages in the file: the next page appended gets this number.
    Atomic npages
    i nframes
    Atomic hits
    Atomic misses
    Atomic writes
    // The log position of the last checkpoint: a page last changed before
    // it gets a full-page image at its next change (heap.nu log_page).
    Atomic redo
    // Recovery: a page that fails its check is a torn write, rebuilt by
    // redo from its full-page image — read as empty, not refused.
    Atomic recovering
}

: BufPool { ( Arc PoolImpl ) a }

@ BufPool_share BufPool p → BufPool

@ BufPool_drop sink BufPool p → v

: PageRead

: PageRead {
    ( RGuard Frame ) g
    Atomic pin
    i pid
}

: PageWrite

: PageWrite {
    ( WGuard Frame ) g
    Atomic pin
    Atomic dirty
    i pid
}

% Drop PageRead { @ drop PageRead r → v { ( atomic_sub . r pin 1 ) } }

Unpinned when the guard goes; its latch goes with its field right after.

% Drop PageWrite

% Drop PageWrite {
    @ drop PageWrite w → v {
        ( atomic_store . w dirty 1 )
        ( atomic_sub . w pin 1 )
    }
}

@ page_bytes PageRead r → ( Slice u )

The page's bytes: a frozen view, held to the guard.

@ page_bytes_mut PageWrite w → ( Slice u )

@ page_read_pid PageRead r → i

@ page_write_pid PageWrite w → i

@ pool_new PFile file Wal wal i nframes → BufPool

A pool of nframes frames over the data file file, writing back under the log wal.

@ pool_redo BufPool p → i

@ pool_set_redo BufPool p i lsn → v

@ pool_set_recovering BufPool p b on → v

@ pool_ensure_npages BufPool p i n → v

The file holds at least n pages (recovery: a page the log names that a crash kept from reaching the file).

@ pool_npages BufPool p → i

@ pool_hits BufPool p → i

@ pool_misses BufPool p → i

@ pool_writes BufPool p → i

: Claim

: Claim {
    i frame
    // > 0: a dirty victim was pinned for write-back; the miss starts over.
    b flush
    // -1: the page was already there (another thread installed it).
    ? ( WGuard Frame ) g
}

What a miss decided under the exclusive table lock: the frame it pinned, and either the frame's write latch (a clean victim, now the page's) or the old page to write back first.

@ pool_read BufPool p i pid → PageRead

@ pool_write BufPool p i pid → PageWrite

@ pool_new_page BufPool p i type → PageWrite

A page appended to the file: a zeroed frame with the header of type, write-latched. Its number is the next one; the file grows when it is written back.

@ pool_flush_all BufPool p → v

Write every dirty page out (a checkpoint's first half). Pages changed while it runs are written by the next one.

@ pool_dirty_count BufPool p → i

Dirty frames right now (racy: a statistic).

keys.nu

packages/nurldb/src/keys.nu — index keys as bytes that sort the way the values do.

An index compares keys with one memcmp (btree.nu), so a key is encoded once, when it is made, into bytes whose order is the values' order:

NULL 0x00 (sorts first) INT 0x01, the value with its sign bit flipped, big-endian REAL 0x01, the IEEE bits — all flipped when negative, the sign bit flipped when not — big-endian BOOL 0x01, 0 or 1 TEXT 0x01, the bytes with each 0x00 written 0x00 0xFF, then 0x00 0x00 (so a prefix sorts before what it prefixes)

A column's values are all of the column's type (the planner converts a constant compared with it first), so the encodings of different types never meet. An entry's key is its columns' encodings and then the TID of the row version it points at, big-endian: entries are unique, and the versions of one value lie together in TID order.

API

: i MIN_I64 -9223372036854775808

@ key_put ( Vec u ) out Value v i ty → v

Append the encoding of v, a value of column type ty.

@ key_of_row ( Vec Value ) row ( Vec i ) cols ( Vec i ) types i tid → ( Vec u )

The key of row's columns cols (of types types), and then tid.

@ key_tid ( Slice u ) key → i

The TID a full entry key ends with.

@ key_lo ( Slice u ) prefix → ( Vec u )

The bounds of every entry whose columns encode as prefix: from the prefix with the lowest TID to the prefix with the highest (inclusive).

@ key_hi ( Slice u ) prefix → ( Vec u )

@ key_has_prefix ( Slice u ) key ( Slice u ) prefix → b

Does key start with prefix?

btree.nu

packages/nurldb/src/btree.nu — B+tree indexes, shared by every thread.

A node is a page (PT_LEAF or PT_INNER). After the common header:

32 u16 n entries 34 u16 hi the start of the entry area (0: the page's end) 36 u16 level 0 for a leaf 38 u16 flags BTF_ROOT on the root 40 slots: u16 offset per entry, in key order

An entry is u16 length, the key (keys.nu: the columns' bytes and the row version's TID, so every key is unique), and in an inner node the u32 number of its child. An inner node's keys separate its children: keys from entry k's up to entry k+1's live under child k, and keys below entry 0's under the leftmost child (PG_AUX). A leaf links to its right neighbour (PG_NEXT); a scan walks the leaves along it.

Concurrency is latch crabbing over the buffer pool's page latches:

child before it lets the parent go — so no split can move what it is looking for between the two.

writing (optimistic: most inserts fit). When the leaf is full it starts again pessimistically: write latches from the root down, and every time a node with room for one more entry is latched, the latches above it are let go — a split below cannot reach past a node that has room. The nodes still latched are exactly the ones a split may change, and they split bottom-up.

threads never wait on each other in a circle.

The root may split: a new root is made above it, its number goes into the index's anchor page (PG_AUX: what survives a restart) and into the shared atomic every descent starts from. A descent that latches a page that is no longer the root (it split meanwhile) lets go and starts again.

Entries are never deleted while a transaction may see them; the vacuum removes those of row versions nobody can see (bt_delete), leaving a node with less in it: nodes are not merged.

Every change is logged first: an insert as R_BT_INSERT, a delete as R_BT_DELETE (redone by bt_redo), a split or a compaction as the images of the pages it rewrote (R_PAGE_IMAGE).

API

: i BT_N 32

: i BT_HI 34

: i BT_LEVEL 36

: i BT_FLAGS 38

: i BT_SLOTS 40

: i BTF_ROOT 1

: i BT_MAX_KEY 1032

The longest key an index takes (columns and TID): a node holds at least seven, so a split always leaves room in both halves.

: i BT_MAX_ENTRY 1040

The room one entry needs at most (slot, length, key, child).

: IndexImpl

: IndexImpl {
    i id
    i table
    i anchor  // the page that names the root (PG_AUX)
    Atomic root
    ( Vec i ) cols  // the table's columns it is on, in key order
    ( Vec i ) types
    b unique
}

: Index { ( Arc IndexImpl ) a }

@ Index_share Index t → Index

@ Index_drop sink Index t → v

@ index_new i id i table i anchor i root ( Vec i ) cols ( Vec i ) types b unique → Index

@ index_id Index t → i

@ index_root Index t → i

@ index_anchor Index t → i

@ index_unique Index t → b

@ index_key Index t ( Vec Value ) row i tid → ( Vec u )

The key of row (stored at tid) in this index.

@ bt_init ( Slice u ) p i level b root → v

@ bt_n ( Slice u ) p → i

@ bt_level ( Slice u ) p → i

@ bt_is_root ( Slice u ) p → b

@ bt_set_root ( Slice u ) p b r → v

@ bt_key ( Slice u ) p i k → ( Slice u )

@ bt_child ( Slice u ) p i k → i

@ bt_free ( Slice u ) p → i

Bytes free between the slots and the entries.

@ bt_need i klen b inner → i

The room an entry with a key of klen bytes takes, its slot included.

@ bt_lower ( Slice u ) p ( Slice u ) key → i

The first entry whose key is not below key.

@ bt_upper ( Slice u ) p ( Slice u ) key → i

The first entry whose key is above key.

@ bt_descend ( Slice u ) p ( Slice u ) key → i

The child of inner node p that key belongs under.

@ bt_put_at ( Slice u ) p i pos ( Slice u ) key i child b inner → v

Put an entry at position pos (the caller checked it fits).

@ bt_remove_at ( Slice u ) p i pos → v

Take entry pos out (its bytes stay until a compaction).

@ bt_create Store st → i

An empty index: its anchor page and a root leaf. The anchor's number.

@ bt_anchor_root Store st i anchor → i

The root an anchor page names.

@ bt_insert Store st Index ix ( Slice u ) key → v

Insert key (a full entry key: keys.nu) into the index.

: Peek { i level i child b safe }

What the bottom of a pessimistic descent knows about the node it latched.

: Pending

: Pending {
    ( Vec u ) key
    i child  // the node the entry points at, in an inner node
    i level
}

The entry an insert still has to put in, at the level it belongs to (a split passes its separator up: inout, changed in place).

@ bt_scan Store st Index ix ( Slice u ) lo ( Slice u ) hi ( @ b ( Slice u ) ) f → v

Call f with each entry key from lo to hi (both inclusive), in order; F from f stops. A leaf is copied out and let go before f sees its keys: f may read the table, or change it. Entries a split moves right while the scan is between leaves are met on the leaf they moved to; ones inserted meanwhile belong to row versions the scan's snapshot does not see either way.

: BtCursor

: BtCursor {
    ( Vec u ) page
    i k
    i next
    b started
    b done
}

A scan one entry at a time (a query's index scan): the leaf it is on, copied out, and where in it.

@ bt_cursor → BtCursor

@ bt_cursor_next Store st Index ix inout BtCursor c ( Slice u ) lo ( Slice u ) hi inout ( Vec u ) out → b

The next entry key from lo up to hi (inclusive) into out: F at the end of the range.

@ bt_delete Store st Index ix ( Slice u ) key → b

Take the entry key out of the index (the vacuum: no snapshot can see the row version it points at). F when it was not there.

@ bt_redo ( Slice u ) p ( Slice u ) r → v

Apply an R_BT_INSERT / R_BT_DELETE record r to the node p it names.

heap.nu

packages/nurldb/src/heap.nu — tables as chains of slotted pages.

A heap page (PT_HEAP), after the common header:

32 u16 nslots 34 u16 lo the end of the slot array 36 u16 hi the start of the tuple area (tuples grow down from the end of the page) 40 slots: u16 offset, u16 length each — offset 0 is a free slot

A tuple is one version of a row (MVCC, txn.nu):

0 u64 xmin the transaction that made it 8 u64 xmax the one that deleted or superseded it (0: none yet) 16 u32 cmin the command within xmin that made it, and within xmax 20 u32 cmax the one that deleted it — a statement does not see its own changes (the Halloween problem) 24 u64 next reserved (0) 32 u16 ncols 34 u16 flags 36 the row (value.nu)

A TID is pid * 65536 + slot.

Every change goes through the log first (logrec.nu): under the page's write latch the record is appended, the change applied, and the page's LSN set to the record's. The same functions apply the record during recovery (heap_redo), so redo makes exactly the page the change made.

API

: i HP_NSLOTS 32

: i HP_LO 34

: i HP_HI 36

: i HP_SLOTS 40

: i TH_XMIN 0

: i TH_XMAX 8

: i TH_CMIN 16

: i TH_CMAX 20

: i TH_NEXT 24

: i TH_NCOLS 32

: i TH_FLAGS 34

: i TH_SIZE 36

: Store { BufPool pool Wal wal }

The pool and the log: what every logged change needs. A handle: every copy shares the one pool and the one log.

@ Store_share Store s → Store

@ Store_drop sink Store s → v

@ tid_of i pid i slot → i

@ tid_pid i tid → i

@ tid_slot i tid → i

@ hp_init ( Slice u ) p → v

@ hp_nslots ( Slice u ) p → i

@ hp_fits ( Slice u ) p i n → b

Bytes free for one more tuple of n bytes (a new slot included).

@ hp_place ( Slice u ) p i slot ( Slice u ) t → v

Place t in slot slot (a new slot when it is nslots): what an insert and its redo both do, so redo builds the same page.

@ hp_pick_slot ( Slice u ) p → i

The slot an insert of n bytes takes: the first free one, or a new one.

@ hp_tuple ( Slice u ) p i slot → ( Slice u )

The tuple in slot: its bytes, or an empty window for a free slot.

@ th_xmin ( Slice u ) t → i

@ th_xmax ( Slice u ) t → i

@ th_cmin ( Slice u ) t → i

@ th_cmax ( Slice u ) t → i

@ th_next ( Slice u ) t → i

@ hp_set_x ( Slice u ) p i slot i xmax i cmax i next → v

@ tuple_build i xmin i cmin ( Vec Value ) row → ( Vec u )

A tuple's bytes for row, made by xmin in its command cmin.

@ tuple_row ( Slice u ) t ( Vec i ) types → ( Vec Value )

The row a tuple holds.

@ log_page Store st PageWrite pw ( Vec u ) rec → i

Append rec — the change just made to the page under pw — and stamp the page with its LSN. The first change to a page since the last checkpoint logs the whole page instead (a full-page image, which holds the change): a write of the page torn by a power cut is then rebuilt by redo, never read back half old (db.nu).

@ log_page_image Store st PageWrite pw → i

Log the page under pw whole (R_PAGE_IMAGE): a split, a compaction, a page's first change after a checkpoint.

@ heap_new_page Store st → PageWrite

A fresh heap page, logged: what a table's chain grows by.

@ heap_link Store st PageWrite pw i next → v

Link pid's page to next (logged).

@ heap_put Store st PageWrite pw ( Slice u ) t → i

Insert tuple t into the page under pw if it fits: its slot, or -1.

@ heap_set_x Store st PageWrite pw i slot i xmax i cmax i next → v

Set a version's xmax / cmax / next (logged).

@ heap_redo ( Slice u ) p ( Slice u ) r → v

Apply a page record r to the page p it names (recovery.nu has checked the page's LSN is below the record's).

nurldb.nu

packages/nurldb/src/nurldb.nu — the library: a relational database in pure NURL.

$ deps/nurldb/src/nurldb.nu

: Db d ?? ( db_open /var/lib/app/db ( db_default_opts ) ) { T x → x F e → … } : ~ Session s ( session_new d ) ?? ( session_exec s ( string_from SELECT name FROM emp WHERE id = 3 ) ) { T r → ( nurl_print ( string_data ( result_text r ) ) ) F e → ( nurl_println ( string_data e ) ) } ( session_close s ) ( db_close d )

A Db is shared by every thread that uses it (each with a Session of its own); serve puts it on a TCP port. See README.md for the SQL it speaks and how it is built.

page.nu

packages/nurldb/src/page.nu — the on-disk page.

The data file is an array of PAGE_SIZE-byte pages; page pid lives at byte pid * PAGE_SIZE. Every page starts with the same 32-byte header:

0 u64 lsn the log sequence number of the last change applied to this page (the end of its log record): redo skips a record whose change the page already holds, and the buffer pool writes the page out only once the log is durable up to here (the write-ahead rule) 8 u32 pid the page's own number, checked on every read 12 u16 type PT_* 14 u16 flags 16 u32 crc CRC-32 of the page with this field read as zero, written when the page goes to disk, checked when it comes back: a torn or corrupted page is an error, never data 20 u32 next a heap page: the next page of its table; a B+tree leaf: its right sibling 24 u32 prev 28 u32 aux type-specific

A page is reached only through the buffer pool's guards (bufpool.nu): a read guard lends a frozen view of the bytes, a write guard a changeable one. These accessors take either view.

API

: i PAGE_SIZE 8192

: i PG_LSN 0

: i PG_ID 8

: i PG_TYPE 12

: i PG_FLAGS 14

: i PG_CRC 16

: i PG_NEXT 20

: i PG_PREV 24

: i PG_AUX 28

: i PG_HDR 32

: i PT_FREE 0

Page types.

: i PT_META 1

: i PT_HEAP 2

: i PT_LEAF 3

: i PT_INNER 4

: i PT_CLOG 5

: i NO_PAGE 0

"No page": a link that leads nowhere (page 0 is the meta page, which nothing links to).

@ pg_lsn ( Slice u ) p → i

@ pg_set_lsn ( Slice u ) p i lsn → v

@ pg_id ( Slice u ) p → i

@ pg_type ( Slice u ) p → i

@ pg_next ( Slice u ) p → i

@ pg_set_next ( Slice u ) p i n → v

@ pg_prev ( Slice u ) p → i

@ pg_set_prev ( Slice u ) p i n → v

@ pg_aux ( Slice u ) p → i

@ pg_set_aux ( Slice u ) p i n → v

@ pg_init ( Slice u ) p i pid i type → v

A fresh page of type: zeroes, then the header.

@ pg_checksum ( Slice u ) p → i

The page's checksum: CRC-32 of its bytes with the crc field read as zero (it is the bytes before the field, four zero bytes, the bytes after it).

@ pg_crc ( Slice u ) p → i

@ pg_set_crc ( Slice u ) p i c → v

@ pg_verify ( Slice u ) p i pid → b

Whether a page read from disk is intact: an all-zero page (a hole the file was extended over) is a page never written, and passes; anything else must carry its own number and a matching checksum.

server.nu

packages/nurldb/src/server.nu — the database over TCP.

One thread per connection, each with a session of its own (exec.nu); a checkpointer thread writes the dirty pages out every 30 seconds.

The protocol is lines. The client sends one statement per line; the server answers

OK <n> then n lines: the result as text (result_text) ERR <reason>

A connection ends when the client closes it; a transaction it left open is rolled back.

API

: LineReader

: LineReader {
    TcpConn c
    ( Vec u ) buf
    b eof
}

Lines out of a byte stream: what has arrived but not been read yet.

@ line_reader TcpConn c → LineReader

@ read_line_from inout LineReader r → ?String

The next line (without its newline); none at the end of the stream.

@ serve Db d s host i port → !v String

Serve d on port until the process is stopped.

: Client

: Client {
    TcpConn c
    LineReader r
}

@ client_connect s host i port → !Client String

@ client_exec inout Client cl String sql → !String String

Send one statement; the server's answer as text, or its error.

@ client_close inout Client cl → v

logrec.nu

packages/nurldb/src/logrec.nu — what the log records say.

Every record starts with its kind (one byte). Integers are little-endian.

R_PAGE_INIT u32 pid u16 type a page formatted R_HEAP_INSERT u32 pid u16 slot u32 n n bytes a tuple placed R_HEAP_SETX u32 pid u16 slot u64 xmax u32 cmax u64 next a version deleted / superseded (or undone) R_LINK u32 pid u32 next a page chain extended R_PAGE_IMAGE u32 pid PAGE_SIZE bytes a page replaced whole (a B+tree split, a prune) R_COMMIT u64 xid R_ABORT u64 xid R_CHECKPOINT u64 next_xid u64 npages every page before it is on disk R_META u32 key u64 value a database-wide counter R_BT_INSERT u32 pid u16 pos u32 child u16 n n bytes an index entry put in R_BT_DELETE u32 pid u16 pos an index entry taken out

Redo (recovery.nu) applies a page record only to a page whose LSN is below the record's: a change the page already holds is skipped, so replaying the log twice changes nothing the first replay did not.

API

: i R_PAGE_INIT 1

: i R_HEAP_INSERT 2

: i R_HEAP_SETX 3

: i R_LINK 4

: i R_PAGE_IMAGE 5

: i R_COMMIT 6

: i R_ABORT 7

: i R_CHECKPOINT 8

: i R_META 9

: i R_BT_INSERT 10

: i R_BT_DELETE 11

@ rec_new i kind i cap → ( Vec u )

@ rec_u16 ( Vec u ) r i x → v

@ rec_u32 ( Vec u ) r i x → v

@ rec_u64 ( Vec u ) r i x → v

@ rec_bytes ( Vec u ) r ( Slice u ) b → v

@ rec_kind ( Slice u ) r → i

@ rec_pid ( Slice u ) r → i

exec.nu

packages/nurldb/src/exec.nu — statements, run.

A SELECT becomes a tree of operators, each a % Op with one method, next inout self → ?( Vec Value ): pull a row from below, hand one up (the Volcano model). The tree is built from the bottom:

scan SeqScan, page by page under the transaction's snapshot, or IndexScan over a range of an index whose leading columns the WHERE pins down (col = const, then a range) join HashJoin on an equality between the two tables, or a nested loop over the right side otherwise Filter WHERE aggregation HashAgg (GROUP BY and the aggregates) — or, over a plain scan of one table, ParAgg: the table's pages dealt out to worker threads, each aggregating its own, merged after Filter HAVING Sort ORDER BY (an alias of the select list may be named) Project the select list Distinct, Limit

Expressions are evaluated over the row at hand by index into the statement's arena (sql.nu); a column is bound to its position before the tree is built. NULL follows SQL: arithmetic and comparisons with a NULL are NULL, AND / OR are three-valued, WHERE keeps a row only when its condition is TRUE.

Writes (INSERT / UPDATE / DELETE) find their rows the way a SELECT would, all of them first — the statement does not see its own changes — then change them one by one through db.nu.

A session runs SQL text: one statement at a time, in an explicit transaction (BEGIN … COMMIT / ROLLBACK) or in one of its own. A statement that fails panics — a serialization failure, a deadlock, a duplicate key, a type error — and its transaction is rolled back by abort: every version it made becomes invisible, and the page latches, locks and memory the statement held go with the unwind.

API

: Exprs { ( Arc ( Vec Ex ) ) a }

@ Exprs_share Exprs x → Exprs

@ Exprs_drop sink Exprs x → v

@ ex_at Exprs x i e → Ex

@ val_true Value v → b

@ eval Exprs x i e ( Vec Value ) row → Value

The value of expression e over row.

@ eval_true Exprs x i e ( Vec Value ) row → b

: Scope

: Scope {
    ( Vec String ) quals
    ( Vec String ) names
}

The columns a row has, in order: each one's table (or alias) and name.

@ scope_new → Scope

@ scope_add inout Scope sc TableMeta m String qual → v

@ bind_expr inout ( Vec Ex ) ex i e Scope sc → v

Bind every column under e to its position in sc (aggregates' too).

@ collect_aggs ( Vec Ex ) ex i e inout ( Vec i ) out → v

The aggregates under e, in the order met (not inside one another).

@ bind_post inout ( Vec Ex ) ex i e Scope sc ( Vec i ) gcols ( Vec i ) aggs → v

After aggregation a row is the GROUP BY values and then the aggregates'. Bind e to that row: a column must be one grouped by (gcols: the base position of each GROUP BY column, -1 for an expression), an aggregate is at its slot.

% Op [T]

% Op [T] {
    @ next inout T self → ?( Vec Value )
}

: SeqScan

: SeqScan {
    Store st
    TxnMgr tm
    Snapshot snap
    Table t
    i next
    ( Vec ( Vec Value ) ) buf
}

% Op SeqScan

% Op SeqScan {
    @ next inout SeqScan s → ?( Vec Value ) {
        ~ T {
            ?? ( vec_pop [( Vec Value )] . s buf ) { T r → { ^ @ ?( Vec Value ) { T r } } F → {} }
            ? == . s next NO_PAGE { ^ @ ?( Vec Value ) { F } } {}
            : ~ ( Vec ( Vec Value ) ) rows ( vec_new [( Vec Value )] )
            : ~ ( Vec i ) tids ( vec_new [i] )
            = . s next ( tbl_page_rows . s st . s tm . s snap . s t . s next rows tids )
            ( __push_reversed . s buf rows )
        }
    }
}

: IndexScan

: IndexScan {
    Store st
    TxnMgr tm
    Snapshot snap
    Table t
    Index ix
    ( Vec u ) lo
    ( Vec u ) hi
    BtCursor cur
    ( Vec u ) key
}

% Op IndexScan

% Op IndexScan {
    @ next inout IndexScan s → ?( Vec Value ) {
        ~ ( bt_cursor_next . s st . s ix . s cur ( slice_from_vec [u] . s lo ) ( slice_from_vec [u] . s hi ) . s key ) {
            ?? ( tbl_fetch . s st . s tm . s snap . s t ( key_tid ( slice_from_vec [u] . s key ) ) ) {
                T r → { ^ @ ?( Vec Value ) { T r } }
                F → {}
            }
        }
        ^ @ ?( Vec Value ) { F }
    }
}

: OneRow { b done }

One empty row (a SELECT with no FROM).

% Op OneRow

% Op OneRow {
    @ next inout OneRow s → ?( Vec Value ) {
        ? . s done { ^ @ ?( Vec Value ) { F } } {}
        = . s done T
        ^ @ ?( Vec Value ) { T ( vec_new [Value] ) }
    }
}

: Filter

: Filter {
    % Op src
    Exprs x
    i pred
}

% Op Filter

% Op Filter {
    @ next inout Filter s → ?( Vec Value ) {
        ~ T {
            : ?( Vec Value ) r ( next . s src )
            ?? r {
                T row → { ? ( eval_true . s x . s pred row ) { ^ @ ?( Vec Value ) { T row } } {} }
                F → { ^ @ ?( Vec Value ) { F } }
            }
        }
    }
}

: Project

: Project {
    % Op src
    Exprs x
    ( Vec i ) items  // expression per output column; -1 - k: input column k
}

% Op Project

% Op Project {
    @ next inout Project s → ?( Vec Value ) {
        ?? ( next . s src ) {
            T row → {
                : ( Vec Value ) out ( vec_with_cap [Value] ( vec_len [i] . s items ) )
                ~ it . s items {
                    ? < it 0 { ( vec_push [Value] out ( val_clone ( vec_at [Value] row - -1 it ) ) ) } {
                        ( vec_push [Value] out ( eval . s x it row ) )
                    }
                }
                ^ @ ?( Vec Value ) { T out }
            }
            F → { ^ @ ?( Vec Value ) { F } }
        }
    }
}

: Limit

: Limit {
    % Op src
    i limit  // -1: none
    i offset
    i seen
}

% Op Limit

% Op Limit {
    @ next inout Limit s → ?( Vec Value ) {
        ~ < . s seen . s offset {
            ?? ( next . s src ) { T _ → { = . s seen + . s seen 1 } F → { ^ @ ?( Vec Value ) { F } } }
        }
        ? & >= . s limit 0 >= - . s seen . s offset . s limit { ^ @ ?( Vec Value ) { F } } {}
        ?? ( next . s src ) {
            T row → { = . s seen + . s seen 1 ^ @ ?( Vec Value ) { T row } }
            F → { ^ @ ?( Vec Value ) { F } }
        }
    }
}

@ drain inout %Op src → ( Vec ( Vec Value ) )

Every row of src.

: Sort

: Sort {
    % Op src
    Exprs x
    ( Vec OrderItem ) keys
    ( Vec ( Vec Value ) ) out
    b loaded
}

% Op Sort

% Op Sort {
    @ next inout Sort s → ?( Vec Value ) {
        ? ! . s loaded {
            = . s loaded T
            : ( Vec ( Vec Value ) ) rows ( drain . s src )
            : i nk ( vec_len [OrderItem] . s keys )
            : ( Vec b ) desc ( vec_new [b] )
            ~ o . s keys { ( vec_push [b] desc . o desc ) }
            // Each row behind its keys, sorted by them, the keys taken off.
            : ( Vec ( Vec Value ) ) keyed ( vec_with_cap [( Vec Value )] ( vec_len [( Vec Value )] rows ) )
            ~ r rows {
                : ( Vec Value ) kr ( vec_with_cap [Value] + nk ( vec_len [Value] r ) )
                ~ o . s keys { ( vec_push [Value] kr ( eval . s x . o e r ) ) }
                ~ cell r { ( vec_push [Value] kr ( val_clone cell ) ) }
                ( vec_push [( Vec Value )] keyed kr )
            }
            ( sort_by [( Vec Value )] keyed \ ( Vec Value ) a ( Vec Value ) b → i { ^ ( __row_order a b desc ) } )
            // Handed out from the end: reversed.
            : ~ i k - ( vec_len [( Vec Value )] keyed ) 1
            ~ >= k 0 {
                : ( Vec Value ) kr ( vec_at [( Vec Value )] keyed k )
                : ( Vec Value ) row ( vec_with_cap [Value] - ( vec_len [Value] kr ) nk )
                : ~ i j nk
                ~ < j ( vec_len [Value] kr ) { ( vec_push [Value] row ( val_clone ( vec_at [Value] kr j ) ) ) = j + j 1 }
                ( vec_push [( Vec Value )] . s out row )
                = k - k 1
            }
        } {}
        ?? ( vec_pop [( Vec Value )] . s out ) { T r → { ^ @ ?( Vec Value ) { T r } } F → { ^ @ ?( Vec Value ) { F } } }
    }
}

: GroupMap

: GroupMap {
    ( Vec ( Vec Value ) ) rows
    ( Vec i ) heads
    ( Vec i ) chain
    i nkeys
}

Rows by a key — the first nkeys values of each — in a hash table (chained through next).

@ gmap_new i nkeys → GroupMap

@ gmap_slot inout GroupMap m ( Vec Value ) key ( @ ( Vec Value ) ) fresh → i

The row of key's group: found, or made from fresh (key and initial state).

: AggSpec

: AggSpec {
    Exprs x
    ( Vec i ) group
    ( Vec i ) aggs
}

What an aggregation computes: the GROUP BY expressions, then per aggregate four state values — count, sum, min, max — turned into the aggregate's value at the end.

: HashAgg

: HashAgg {
    % Op src
    AggSpec sp
    ( Vec ( Vec Value ) ) out
    b loaded
}

% Op HashAgg

% Op HashAgg {
    @ next inout HashAgg s → ?( Vec Value ) {
        ? ! . s loaded {
            = . s loaded T
            : ~ GroupMap m ( gmap_new ( vec_len [i] . . s sp group ) )
            ~ T {
                ?? ( next . s src ) { T row → { ( __agg_add . s sp m row ) } F → { break } }
            }
            = . s out ( __agg_output . s sp m )
        } {}
        ?? ( vec_pop [( Vec Value )] . s out ) { T r → { ^ @ ?( Vec Value ) { T r } } F → { ^ @ ?( Vec Value ) { F } } }
    }
}

: ParAgg

: ParAgg {
    Store st
    TxnMgr tm
    Snapshot snap
    Table t
    i pred
    AggSpec sp
    i workers
    ( Vec ( Vec Value ) ) out
    b loaded
}

The same aggregation over a table's pages dealt out to workers threads: each scans every workers-th page under the statement's snapshot, keeps the rows WHERE (pred, -1 none) keeps, and aggregates them into a map of its own; the maps are merged when all are done.

% Op ParAgg

% Op ParAgg {
    @ next inout ParAgg s → ?( Vec Value ) {
        ? ! . s loaded {
            = . s loaded T
            : ( Vec i ) pages ( tbl_pages . s st . s t )
            : ( Locked ( Vec GroupMap ) ) parts ( locked_new [( Vec GroupMap )] ( vec_new [GroupMap] ) )
            : ( Vec Thread ) ts ( vec_new [Thread] )
            : ~ i w 0
            ~ < w . s workers {
                : i me w
                : Store st . s st
                : TxnMgr tm . s tm
                : Snapshot snap @ Snapshot { . . s snap xid . . s snap cid . . s snap xmin . . s snap xmax ( vec_clone [i] . . s snap active ) }
                : Table t . s t
                : AggSpec sp @ AggSpec { ( Exprs_share . . s sp x ) ( vec_clone [i] . . s sp group ) ( vec_clone [i] . . s sp aggs ) }
                : i pred . s pred
                : i n . s workers
                : ( Vec i ) pg ( vec_clone [i] pages )
                : !Thread ThreadErr r ( thread_spawn \ → v {
                    : GroupMap m ( __par_worker st tm snap t pred sp pg me n )
                    ( locked_update [( Vec GroupMap )] parts \ inout ( Vec GroupMap ) ps → v { ( vec_push [GroupMap] ps m ) } )
                } )
                ?? r { T h → { ( vec_push [Thread] ts h ) } F _ → { ( __fails `cannot start a scan thread` ) } }
                = w + w 1
            }
            ~ h ts { ( thread_join h ) }
            : ( Vec GroupMap ) got ( locked_take [( Vec GroupMap )] parts )
            ? != ( vec_len [GroupMap] got ) . s workers { ( __fails `a scan thread failed` ) } {}
            : AggSpec spec @ AggSpec { ( Exprs_share . . s sp x ) ( vec_clone [i] . . s sp group ) ( vec_clone [i] . . s sp aggs ) }
            : i ng ( vec_len [i] . spec group )
            : ~ GroupMap m ( gmap_new ng )
            ~ part got {
                ~ prow . part rows {
                    : i g ( gmap_slot m prow \ → ( Vec Value ) { ^ ( __agg_fresh spec ( __key_prefix_of prow ng ) ) } )
                    ( __agg_merge spec m g prow )
                }
            }
            = . s out ( __agg_output spec m )
        } {}
        ?? ( vec_pop [( Vec Value )] . s out ) { T r → { ^ @ ?( Vec Value ) { T r } } F → { ^ @ ?( Vec Value ) { F } } }
    }
}

: Distinct

: Distinct {
    % Op src
    GroupMap seen
}

% Op Distinct

% Op Distinct {
    @ next inout Distinct s → ?( Vec Value ) {
        ~ T {
            ?? ( next . s src ) {
                T row → {
                    : i before ( vec_len [( Vec Value )] . . s seen rows )
                    : i g ( gmap_slot . s seen row \ → ( Vec Value ) { ^ ( vec_clone_with [Value] row \ Value v → Value { ^ ( val_clone v ) } ) } )
                    ? == g before { ^ @ ?( Vec Value ) { T row } } {}
                }
                F → { ^ @ ?( Vec Value ) { F } }
            }
        }
    }
}

: NestLoop

: NestLoop {
    % Op left
    ( Vec ( Vec Value ) ) right
    Exprs x
    i on
    ( Vec ( Vec Value ) ) out
}

Left rows joined to the right rows on holds for — the right side read once, into memory.

% Op NestLoop

% Op NestLoop {
    @ next inout NestLoop s → ?( Vec Value ) {
        ~ T {
            ?? ( vec_pop [( Vec Value )] . s out ) { T r → { ^ @ ?( Vec Value ) { T r } } F → {} }
            ?? ( next . s left ) {
                T l → {
                    : ~ ( Vec ( Vec Value ) ) hits ( vec_new [( Vec Value )] )
                    ~ r . s right {
                        : ( Vec Value ) j ( __concat l r )
                        ? ( eval_true . s x . s on j ) { ( vec_push [( Vec Value )] hits j ) } {}
                    }
                    ( __push_reversed . s out hits )
                }
                F → { ^ @ ?( Vec Value ) { F } }
            }
        }
    }
}

: HashJoin

: HashJoin {
    % Op left
    GroupMap right  // key: the right join value; then the right row
    ( Vec ( Vec Value ) ) rrows
    ( Vec i ) heads
    i lcol
    Exprs x
    i on
    ( Vec ( Vec Value ) ) out
}

An equality join: the right rows in a hash table by their join column, each left row probing it with its own.

% Op HashJoin

% Op HashJoin {
    @ next inout HashJoin s → ?( Vec Value ) {
        ~ T {
            ?? ( vec_pop [( Vec Value )] . s out ) { T r → { ^ @ ?( Vec Value ) { T r } } F → {} }
            ?? ( next . s left ) {
                T l → {
                    : Value key ( val_clone ( vec_at [Value] l . s lcol ) )
                    ? ( val_is_null key ) { continue } {}
                    : ~ ( Vec ( Vec Value ) ) hits ( vec_new [( Vec Value )] )
                    : ( Vec Value ) probe ( vec_new [Value] )
                    ( vec_push [Value] probe key )
                    : i h ( __key_hash_of probe 1 )
                    : ~ i k ( vec_at [i] . . s right heads & h - ( vec_len [i] . . s right heads ) 1 )
                    ~ >= k 0 {
                        : ( Vec Value ) kr ( vec_at [( Vec Value )] . . s right rows k )
                        ? == ( val_order ( vec_at [Value] kr 0 ) ( vec_at [Value] probe 0 ) ) 0 {
                            : ( Vec Value ) j ( __concat l ( vec_at [( Vec Value )] . s rrows ( __as_i ( vec_at [Value] kr 1 ) ) ) )
                            ? ( eval_true . s x . s on j ) { ( vec_push [( Vec Value )] hits j ) } {}
                        } {}
                        = k ( vec_at [i] . . s right chain k )
                    }
                    ( __push_reversed . s out hits )
                }
                F → { ^ @ ?( Vec Value ) { F } }
            }
        }
    }
}

: Pinned { i lit i op }

col op const (or const op col) on column col of the row: the constant's node, and the operator as if the column were on the left; -1 when the conjunct is not of that shape.

: Access

: Access {
    i index
    ( Vec u ) lo
    ( Vec u ) hi
    i eqcols
}

The index scan a WHERE allows on table m (its rows at positions [0, n) of the scope): which index, and the key range. -1: none.

: ~ i g_par_workers 4

How many threads an aggregation over a seq scan uses.

: Result

: Result {
    ( Vec String ) cols
    ( Vec ( Vec Value ) ) rows
    i affected
    String tag  // what the statement did: SELECT 3, INSERT 2, BEGIN …
}

@ exec_select Db d Txn x inout Stmt st → Result

: Targets

: Targets {
    ( Vec i ) tids
    ( Vec ( Vec Value ) ) rows
}

The rows a write changes: their TIDs and current values, found under the statement's snapshot before anything changes.

@ exec_insert Db d inout Txn x inout Stmt st → Result

@ exec_update Db d inout Txn x inout Stmt st → Result

@ exec_delete Db d inout Txn x inout Stmt st → Result

: Session

: Session {
    Db d
    b in_txn
    Txn txn
}

@ session_new Db d → Session

@ session_exec inout Session s String sql → !Result String

Run one statement of SQL text: its result, or why it failed (the transaction it ran in is rolled back then).

@ session_close inout Session s → v

End the session: an open transaction is rolled back.

@ result_text Result r → String

A result as a text table (what the shell prints).

value.nu

packages/nurldb/src/value.nu — SQL values, and a row's bytes.

A value is NULL or one of four types. A row is a ( Vec Value ); on a page it is encoded after the tuple header (heap.nu) as a null bitmap and the non-null columns in order:

INT 8 bytes, little-endian two's complement REAL 8 bytes, the IEEE 754 bits BOOL 1 byte TEXT u32 length, then the bytes

Values compare the way SQL orders them within one type (NULL sorts first, and = with NULL is decided by the caller: SQL's three-valued logic lives in the expression evaluator, expr.nu).

API

: i TY_INT 1

: i TY_REAL 2

: i TY_TEXT 3

: i TY_BOOL 4

: | Value

: | Value {
    VNull
    VInt i
    VReal f
    VText String
    VBool b
}

@ ty_name i t → s

@ val_is_null Value v → b

@ val_type Value v → i

@ val_cmp Value a Value b → i

Three-way order of two non-null values of one type (or an INT and a REAL, compared numerically). -2: the types cannot be compared.

@ val_order Value a Value b → i

The order a sort and an index use: NULL first, then by value; values of types that do not compare order by their type tag.

@ val_eq Value a Value b → b

@ val_clone Value v → Value

@ val_hash Value v → i

A 64-bit hash, equal for values val_eq calls equal (an INT and the equal REAL included).

@ val_text Value v → String

The value as text (what the shell prints).

@ row_size ( Vec Value ) row → i

The encoded size of row's columns (bitmap included).

@ row_encode ( Vec Value ) row ( Slice u ) dst i off → v

Encode row at off of dst (which holds row_size bytes from there).

@ row_decode ( Slice u ) src i off ( Vec i ) types → ( Vec Value )

Decode ncols columns of the types types from src at off.

main.nu

packages/nurldb/src/main.nu — the nurldb command.

nurldb DIR a shell: statements end with ; nurldb DIR -c "SQL; SQL …" run the statements, print the results nurldb serve DIR [PORT] serve DIR over TCP (port 5433) nurldb client [HOST] [PORT] a shell talking to a server nurldb bench DIR [THREADS] [SECONDS] transfers from THREADS sessions for SECONDS, then a parallel aggregate

In the shell, \dt lists the tables and \q quits.

API

: s VERSION 0.1.1``

@ usage → i

@ split_sql String text → ( Vec String )

The statements of text, split at each ; outside a quoted string.

@ run_one inout Session s String sql → b

@ shell ( @ v String ) exec ( @ v ) tables → v

A shell over stdin: exec runs one statement.

@ local_main s dir ( Vec String ) args → i

@ client_main s host i port → i

@ q inout Session s s sql → b

@ bench_main s dir i threads i seconds → i

@ main → i

sql.nu

packages/nurldb/src/sql.nu — SQL text to statements.

The dialect (keywords in any case; identifiers fold to lower case):

CREATE TABLE t ( col type [NOT NULL] [PRIMARY KEY], … [, PRIMARY KEY ( col, … )] ) type: INT | INTEGER | BIGINT | REAL | FLOAT | DOUBLE | TEXT | VARCHAR [( n )] | BOOL | BOOLEAN CREATE [UNIQUE] INDEX name ON t ( col, … ) INSERT INTO t [( col, … )] VALUES ( expr, … ) [, ( … ) …] SELECT [DISTINCT] expr [[AS] name], … | * [FROM t [[AS] a] [[INNER] JOIN u [[AS] b] ON expr]] [WHERE expr] [GROUP BY expr, …] [HAVING expr] [ORDER BY expr [ASC | DESC], …] [LIMIT n [OFFSET n]] UPDATE t SET col = expr, … [WHERE expr] DELETE FROM t [WHERE expr] BEGIN | COMMIT | ROLLBACK | CHECKPOINT | EXPLAIN select

Expressions: literals (integers, reals, 'text' with '' for a quote, TRUE, FALSE, NULL), columns (col or t.col), + - / % || unary -, = <> != < <= > >=, AND OR NOT, IS [NOT] NULL, [NOT] LIKE, [NOT] BETWEEN … AND …, [NOT] IN ( … ), COUNT() COUNT SUM AVG MIN MAX, and parentheses.

A statement keeps its expressions in one arena (ex) and refers to them by index: a tree without boxes, walked by index by the evaluator.

API

: i TK_EOF 0

: i TK_ID 1

: i TK_INT 2

: i TK_REAL 3

: i TK_STR 4

: i TK_OP 5

: Tok

: Tok {
    i kind
    String text  // an identifier folded to lower case; an operator's spelling
    i ival
    f fval
}

@ sql_lex String src → !( Vec Tok ) String

The tokens of src; a stray character is an error.

: i EX_LIT 1

: i EX_COL 2

: i EX_UN 3

: i EX_BIN 4

: i EX_AGG 5

: i EX_ISNULL 6

: i EX_LIKE 7

: i EX_BETWEEN 8

: i EX_IN 9

: i OP_ADD 1

: i OP_SUB 2

: i OP_MUL 3

: i OP_DIV 4

: i OP_MOD 5

: i OP_EQ 6

: i OP_NE 7

: i OP_LT 8

: i OP_LE 9

: i OP_GT 10

: i OP_GE 11

: i OP_AND 12

: i OP_OR 13

: i OP_NOT 14

: i OP_NEG 15

: i OP_CONCAT 16

: i AG_COUNT 1

: i AG_SUM 2

: i AG_AVG 3

: i AG_MIN 4

: i AG_MAX 5

: Ex

: Ex {
    i kind
    i op
    i a
    i b
    i c
    b neg
    Value lit
    String name
    String qual
    ( Vec i ) list
    i col
}

One node. a / b / c: operands (indices into the arena, -1 none); neg: NOT for IS NULL / LIKE / BETWEEN / IN; list: IN's values; col: a column's position once bound (exec.nu), an aggregate's slot.

: SelItem

: SelItem {
    i e  // -1: `*`
    String alias
}

: OrderItem

: OrderItem {
    i e
    b desc
}

: i ST_SELECT 1

: i ST_INSERT 2

: i ST_UPDATE 3

: i ST_DELETE 4

: i ST_CREATE_TABLE 5

: i ST_CREATE_INDEX 6

: i ST_BEGIN 7

: i ST_COMMIT 8

: i ST_ROLLBACK 9

: i ST_CHECKPOINT 10

: Stmt

: Stmt {
    i kind
    b explain
    ( Vec Ex ) ex
    String table
    String alias
    String jtable
    String jalias
    i on
    ( Vec SelItem ) items
    b distinct
    i where_e
    ( Vec i ) group
    i having
    ( Vec OrderItem ) order
    i limit
    i offset
    ( Vec String ) cols
    ( Vec ( Vec i ) ) rows
    ( Vec i ) sets
    ( Vec ColDef0 ) defs
    String name
    b unique
}

: ColDef0

: ColDef0 {
    String name
    i ty
    b notnull
    b pk
}

A column of CREATE TABLE as parsed (db.nu makes its ColDef).

@ stmt_new i kind → Stmt

: P

: P {
    ( Vec Tok ) toks
    i pos
    ( Vec Ex ) ex
}

@ parse_expr inout P p → i

@ sql_parse String src → Stmt

Parse one statement (a trailing ; is fine).

txn.nu

packages/nurldb/src/txn.nu — transactions: ids, the commit log, snapshots, visibility, and the lock manager.

Multi-version concurrency control. A row's versions are tuples (heap.nu) stamped with the transaction that made each one (xmin) and the one that deleted or superseded it (xmax). A transaction reads through a SNAPSHOT: the set of transactions whose work it sees is fixed when the snapshot is taken — those that had committed by then — so readers never wait for writers and a query sees one consistent state of the database (snapshot isolation).

( txn_begin m ) → Txn ( txn_snapshot m x cid ) → Snapshot ( tuple_visible m s tuple ) → b ( txn_commit m wal x ) → v durable before it returns ( txn_finish_readonly m x ) → v one that wrote nothing ( txn_abort m wal x ) → v

The commit log (clog) holds each transaction's fate: 0 in progress, 1 committed, 2 aborted. A version made by an aborted transaction is invisible to everyone — rollback needs no undo.

Ordering, which is the whole correctness argument:

the one a snapshot is taken under, so no snapshot sees an id that is neither active nor finished;

THEN removed from the active set: a snapshot taken before the removal lists it as active (invisible to that snapshot for good), one taken after finds it committed — no snapshot sees a transaction's work come and go.

Write-write conflicts: a transaction that updates or deletes a version another one has claimed (xmax set by a transaction still running) waits for that one to finish — by asking the lock manager for the other transaction's id, which its owner holds exclusively until it ends. Every wait first checks the waits-for graph: a wait that would close a cycle is refused and its transaction aborted (deadlock).

API

: i XS_RUNNING 0

: i XS_COMMITTED 1

: i XS_ABORTED 2

: i XID_BOOT 1

The id of the bootstrap transaction: committed before anything began (what the catalog's first rows are stamped with).

: i LK_S 1

: i LK_X 2

: Snapshot

: Snapshot {
    i xid  // the reader's own transaction
    i cid  // its current command: its own changes from this one on are unseen
    i xmin  // every id below it had finished when the snapshot was taken
    i xmax  // every id from it on had not begun
    ( Vec i ) active  // ids in [xmin, xmax) still running then
}

: TxnState

: TxnState {
    i next
    ( Vec i ) active
}

: LockEntry

: LockEntry {
    i res
    i txn
    i mode
    b granted
}

: LockTable { ( Vec LockEntry ) entries }

: TxnMgrImpl

: TxnMgrImpl {
    ( Locked TxnState ) state
    ( RwLocked ( Vec u ) ) clog
    ( Locked LockTable ) locks
    // Commits / aborts / deadlocks so far (statistics).
    Atomic commits
    Atomic aborts
    Atomic deadlocks
}

: TxnMgr { ( Arc TxnMgrImpl ) a }

@ TxnMgr_share TxnMgr m → TxnMgr

@ TxnMgr_drop sink TxnMgr m → v

@ txnmgr_new i next ( Vec u ) clog → TxnMgr

A manager whose next id is next and whose clog is clog (both from recovery; a fresh database starts at 2 with an empty clog).

@ txn_commits TxnMgr m → i

@ txn_aborts TxnMgr m → i

@ txn_deadlocks TxnMgr m → i

@ txn_next_xid TxnMgr m → i

@ clog_get TxnMgr m i xid → i

@ clog_set TxnMgr m i xid i st → v

@ clog_copy TxnMgr m → ( Vec u )

A copy of the clog (for a checkpoint to write out).

@ txn_begin TxnMgr m → i

A new transaction: its id, entered in the active set, holding its own id exclusively in the lock manager (what a transaction waiting for it waits on).

@ txn_snapshot TxnMgr m i xid i cid → Snapshot

The snapshot xid reads through for its command cid.

@ txn_commit TxnMgr m Wal w i xid → v

Commit: the commit record durable, then the clog, then the active set (the order the header gives), then the transaction's locks released.

@ txn_finish_readonly TxnMgr m i xid → v

End a transaction that wrote nothing: there is nothing to make durable, and no version of its own for anyone to see, so no log record is needed (recovery calls it aborted, which says the same).

@ txn_abort TxnMgr m Wal w i xid → v

Abort: its versions become invisible the moment the clog says so; the abort record lets recovery say the same (and need not be durable: a transaction the log does not see commit is aborted by recovery anyway).

@ snap_committed TxnMgr m Snapshot s i x → b

Did x commit before the snapshot was taken?

@ tuple_visible TxnMgr m Snapshot s ( Slice u ) t → b

Is the version t (a tuple's bytes) part of what snapshot s sees?

@ lock_acquire TxnMgr m i txn i res i mode → b

Take res in mode for txn, waiting while another transaction holds it in a mode that conflicts. F: the wait would deadlock — the request is withdrawn, and the caller aborts its transaction.

@ lock_release_all TxnMgr m i txn → v

Release every lock txn holds or waits for (at its end).

@ txn_wait_for TxnMgr m i me i other → b

Wait until transaction other has finished (committed or aborted): ask for its id in shared mode — it holds it exclusively until it ends — and let go at once. F: the wait would deadlock.

wal.nu

packages/nurldb/src/wal.nu — the write-ahead log, with group commit.

Every change to a page is described by a log record before the page changes, and a page goes to disk only once the log is durable up to the record that changed it last (the buffer pool asks wal_flush_to first). A crash then loses no committed work: recovery replays the log over the data file from the last checkpoint (recovery.nu).

The file:

0 "NDBLOG01" 8 u64 base the LSN of byte 16 16 records: [u32 len][u32 crc32(payload)][payload]…

A record's LSN is the log position just past its end, so "record r is durable" is lsn(r) <= flushed. LSNs grow for the life of the database: a log that is reset after a checkpoint starts again at the LSN it had reached (base), so a page's LSN never compares against a smaller log position than the one that changed it.

Threads. Any number of threads append at once: the pending bytes live in an RwLocked buffer, taken exclusively for the copy of one record. One flusher thread owns the file's tail: it is woken through a channel, takes the whole buffer at once, writes it, makes it durable (fdatasync) and publishes how far the log is durable (an Atomic), then wakes every committer waiting on a condition variable. Twenty committers arriving while one write is in flight share the next one: that is group commit, and it is why a commit costs one device round trip however many threads commit at once.

API

: i WAL_HDR 16

: i WAL_REC_HDR 8

: LogBuf

: LogBuf {
    ( Vec u ) buf
    i start
}

What is appended but not yet written: buf holds the log from start.

: WalImpl

: WalImpl {
    PFile file
    ( RwLocked LogBuf ) pend
    // The log position past the last appended record.
    Atomic next
    // How far the log is durable.
    Atomic flushed
    // The LSN of byte 16 of the file.
    i base
    Mutex mu
    Cond cv
    ( Channel i ) wake
    Thread flusher
    b sync
    // Writes the flusher made (each one a device round trip when `sync`).
    Atomic writes
}

: Wal { ( Arc WalImpl ) a }

@ Wal_share Wal w → Wal

@ Wal_drop sink Wal w → v

: WalTail

: WalTail {
    PFile file
    ( RwLocked LogBuf ) pend
    Atomic flushed
    Mutex mu
    Cond cv
    i base
    b sync
    Atomic writes
}

What the flusher thread works with: the parts of the log it shares with the appenders (handles — every copy is the same object).

: LogPend { ( Vec u ) data i start }

What the flusher takes out of the buffer: the bytes and where they go.

@ wal_open s path b sync → !Wal String

Open the log at path (created when absent). sync false skips the fdatasync of each flush: faster, and a crash may lose the last commits (never corrupt anything: the log is still written before the pages).

@ wal_append Wal w ( Slice u ) payload → i

Append one record; its LSN (the log position past it) comes back. The record is in the log buffer, not yet durable: wal_flush_to makes it so.

@ wal_flush_to Wal w i lsn → v

Block until the log is durable up to lsn (a commit record's, a page's last change). Many callers at once are served by one write.

@ wal_flush_all Wal w → v

Everything appended so far, durable.

@ wal_next Wal w → i

@ wal_flushed Wal w → i

@ wal_writes Wal w → i

How many writes the flusher has made: with many committers, far fewer than commits.

@ wal_close Wal w → v

Stop the flusher thread after it has written what is pending. The log handle stays usable for reading; nothing more may be appended.

@ wal_replay s path i from ( @ v i ( Slice u ) ) f → !i String

Every intact record from from (an LSN at a record boundary) on, in order: f gets each record's LSN and its payload (a view, valid for the call). Replay stops at the first record that is short, too long or fails its checksum — a crash in the middle of an append — and the log end it reached comes back: the caller truncates the torn tail there (wal_truncate_to), or every later append would hide behind it.

@ wal_truncate_to s path i lsn → !v String

Cut the log back to lsn (the end replay reached): a torn record past it is dropped, and the next append lands right after the last intact one.

@ wal_reset s path i lsn → !v String

Start the log afresh at lsn (after a checkpoint made every record before it unnecessary): the file holds a header whose base is lsn and nothing else. The log must not be open for appending.

db.nu

packages/nurldb/src/db.nu — a database: its files, its catalog, its transactions, and what a crash leaves behind.

A database is a directory:

data the pages (page.nu); page 0 is the meta page log the write-ahead log (wal.nu) clog every transaction's fate as of the last checkpoint

The meta page, after the common header:

32 u64 magic "NURLDB01" 40 u32 version 44 u32 nurldb_tables root the catalog's own tables (heap 48 u32 nurldb_columns root tables like any other, made by the 52 u32 nurldb_indexes root bootstrap transaction) 56 u64 next xid as of the last checkpoint 64 u64 redo LSN where recovery starts: every page change before it is in the data file 72 u64 next object id

Open. An empty directory is bootstrapped. Otherwise the log's torn tail (a crash in the middle of an append) is cut off, every record from the redo LSN on is applied to a page whose LSN is below it (redo is idempotent), the commit and abort records update the clog, and every transaction the log does not see end is aborted — its versions become invisible, which is all a rollback has to do under MVCC. Then a checkpoint, and the log starts afresh.

Checkpoint. Statements hold the checkpoint latch shared; a checkpoint takes it exclusively, so it sees no statement in flight: every dirty page is written (each after the log up to its LSN), the clog file is replaced, and the meta page records the new redo LSN. The first change to a page after a checkpoint logs the whole page (a full-page image), so a page torn by a power cut in the middle of its write is rebuilt by redo from that image rather than read back broken.

Transaction ids are logged in blocks (R_META), and a checkpoint records the end of the last block as the next id: recovery hands out ids above every one a crashed run could have given away, even to a transaction that left nothing but its tuples.

Locks, in the order they are taken: a table's lock (shared by every statement that changes rows, exclusive for CREATE INDEX), a unique key's lock, a row version's writer (txn_wait_for), then page latches — a statement never waits for a lock while it holds a latch.

API

: i META_MAGIC 3544395820347757646

: i META_VERSION 1

: i M_MAGIC 32

: i M_VERSION 40

: i M_TABLES 44

: i M_COLUMNS 48

: i M_INDEXES 52

: i M_NEXT_XID 56

: i M_REDO 64

: i M_NEXT_OID 72

: i XID_BLOCK 1024

Ids are logged this many at a time.

: i RM_XID_BOUND 1

: i RES_TABLE 1099511627776

Lock resources: a table's, a unique key's (transaction ids are the negative ones, txn.nu).

: i RES_KEY 2199023255552

: i RES_KEY_MASK 1099511627775

: ColDef

: ColDef {
    String name
    i ty
    b notnull
}

: IndexDef

: IndexDef {
    String name
    Index ix
    b primary
}

: TableMeta

: TableMeta {
    i id
    String name
    ( Vec ColDef ) cols
    ( Vec i ) types
    Table t
    ( Vec IndexDef ) indexes
}

What a statement needs of a table: shared, never changed (CREATE INDEX makes a new one).

: TableInfo { ( Arc TableMeta ) a }

@ TableInfo_share TableInfo t → TableInfo

@ TableInfo_drop sink TableInfo t → v

@ ti_meta TableInfo t → TableMeta

: CatState { ( Vec TableInfo ) tables }

: DbImpl

: DbImpl {
    String dir
    Store st
    TxnMgr tm
    PFile data
    ( RwLocked CatState ) cat
    // Statements shared, a checkpoint exclusive.
    ( RwLocked i ) ckpt
    // DDL, one at a time.
    Mutex ddl
    Atomic next_oid
    Atomic xid_bound
    Table sys_tables
    Table sys_columns
    Table sys_indexes
}

: Db { ( Arc DbImpl ) a }

@ Db_share Db d → Db

@ Db_drop sink Db d → v

@ db_impl Db d → DbImpl

@ db_store Db d → Store

@ db_txnmgr Db d → TxnMgr

@ sys_tables_types → ( Vec i )

@ sys_columns_types → ( Vec i )

@ sys_indexes_types → ( Vec i )

: Txn

: Txn {
    i xid
    Snapshot snap
    i cid
    b wrote
}

@ db_begin Db d → Txn

@ db_statement inout Txn x → v

A statement of x begins: it sees what the earlier ones did.

@ db_commit Db d Txn x → v

Commit under the checkpoint latch, shared: a checkpoint sees the commit whole — its record before the redo point and its clog entry in the file the checkpoint writes — or not at all (its record after the redo point, replayed). Interleaved, the record could fall before the redo point while the clog written still said running, and recovery aborted a commit that had been acknowledged.

@ db_abort Db d Txn x → v

@ db_coerce_row TableMeta m ( Vec Value ) row → ( Vec Value )

Make row fit the table: one value per column, of the column's type (an INT given for a REAL column becomes one), NOT NULL kept.

@ db_insert Db d inout Txn x TableInfo ti ( Vec Value ) row → i

Insert row (already coerced) into the table: its TID.

@ db_update Db d inout Txn x TableInfo ti i tid ( Vec Value ) row → i

Replace the version at tid with row: the new version's TID, or -1 when this statement already replaced it.

@ db_delete Db d inout Txn x TableInfo ti i tid → b

@ db_table Db d String name → ?TableInfo

@ db_table_names Db d → ( Vec String )

@ db_find_col TableMeta m String name → i

@ db_create_table Db d String name ( Vec ColDef ) cols ( Vec String ) pk → !i String

CREATE TABLE: its id. pk: the columns of its primary key (a unique index named <table>_pkey), none when empty.

@ db_create_index Db d String name String table ( Vec String ) cols b unique → !i String

CREATE [UNIQUE] INDEX: its id. Every version in the table goes in (a transaction still running may commit it); a unique index refuses a table with two live versions of a key.

: DbOpts

: DbOpts {
    i frames  // the buffer pool's size, in pages
    b sync  // fdatasync the log at each commit
}

@ db_default_opts → DbOpts

: Replay

: Replay {
    i applied
    i xid_max
    i end
}

What recovery learned from the log.

@ db_open s dir DbOpts o → !Db String

Open (or create) the database in directory dir: recovery first when it was not closed cleanly (always, in fact: after a clean close the log holds nothing to redo), then the log starts afresh.

: Meta

: Meta {
    i troot
    i croot
    i iroot
    i next_xid
    i redo
    i next_oid
}

The meta page's fields, read once.

@ db_checkpoint Db d → v

Write every dirty page and the clog, and move the redo point to the log's end: recovery starts there.

@ db_close Db d → v

Let go of the database: a checkpoint, and the log flusher stopped.

@ db_stmt_latch Db d → ( RGuard i )

Statements run under the checkpoint latch, shared.

table.nu

packages/nurldb/src/table.nu — rows of a table, through transactions.

( tbl_insert st t x row ) → i the new version's TID ( tbl_scan st tm snap t f ) → v f gets (tid, row) for each version the snapshot sees; F from f stops the scan ( tbl_fetch st tm snap t tid ) → ?( Vec Value ) ( tbl_update st tm x snap t tid row ) → i the new version's TID, or -1: not there to update ( tbl_delete st tm x snap t tid ) → b F: not there to delete

An update or a delete first CLAIMS the version it replaces: under the page's write latch it sets the version's xmax to its own transaction. A version already claimed by a transaction that is still running is waited for (the latch let go first: nobody waits holding a latch), and then looked at again. One claimed by a transaction that committed after this one's snapshot was taken is a conflict this transaction cannot resolve under snapshot isolation: it panics with a serialization failure, which the statement's recover turns into an abort (db.nu). A wait that would close a cycle of waiting transactions is a deadlock, and ends the same way.

A scan never calls out while it holds a latch: it decodes a page's visible rows, lets the page go, and then hands them to f — which may itself read and change the table (an UPDATE scans what it changes).

API

: TableImpl

: TableImpl {
    i id
    i root  // the first heap page
    Atomic last  // the page inserts go to
    ( Locked i ) grow  // the same, held while the chain grows by a page
    ( Vec i ) types  // column types, for decoding
}

A table as the storage layer knows it: its pages and its row shape. Shared by every thread working on the table.

: Table { ( Arc TableImpl ) a }

@ Table_share Table t → Table

@ Table_drop sink Table t → v

@ table_new i id i root i last ( Vec i ) types → Table

@ table_id Table t → i

@ table_root Table t → i

@ table_last Table t → i

: TxnCtx

: TxnCtx {
    i xid
    i cid
}

A transaction's statement: who writes, and in which command.

: i CLAIM_OK 0

A version claim's verdict.

: i CLAIM_MINE 1

: i CLAIM_GONE 2

@ tbl_insert Store st Table tb TxnCtx x ( Vec Value ) row → i

@ tbl_page_rows Store st TxnMgr tm Snapshot snap Table tb i pid inout ( Vec ( Vec Value ) ) rows inout ( Vec i ) tids → i

The versions of page pid of t that snap sees, appended to rows (their TIDs to tids): the page's latch is let go before this returns. The next page of the chain comes back (NO_PAGE at its end).

@ tbl_pages Store st Table tb → ( Vec i )

Every page of the chain, in order (a parallel scan deals them out).

@ table_types Table tb → ( Vec i )

@ tbl_scan Store st TxnMgr tm Snapshot snap Table tb ( @ b i ( Vec Value ) ) f → v

Call f with each version of t that snap sees, page by page.

@ tbl_scan_all Store st TxnMgr tm Table tb ( @ b i ( Vec Value ) ) f → v

Call f with every version in t whose maker did not abort, seen or not by any snapshot: what an index built now must hold (a transaction still running may commit its versions).

@ tbl_fetch Store st TxnMgr tm Snapshot snap Table tb i tid → ?( Vec Value )

The row at tid if snap sees that version.

@ abort_serialization → v

@ abort_deadlock → v

@ tbl_claim Store st TxnMgr tm TxnCtx x Snapshot snap i tid → i

Claim the version at tid for x (set its xmax): CLAIM_OK, CLAIM_MINE when this statement's own transaction already did, or CLAIM_GONE when the version is not there. Waits out a running claimant; panics on a conflict that snapshot isolation cannot resolve.

@ tbl_delete Store st TxnMgr tm TxnCtx x Snapshot snap Table t i tid → b

@ tbl_update Store st TxnMgr tm TxnCtx x Snapshot snap Table t i tid ( Vec Value ) row → i

Replace the row at tid with row: the old version claimed, a new one inserted. CLAIM_MINE (this statement already replaced it — reached again through an index, say) and CLAIM_GONE leave it be: -1.