We want something like sqlite, but for Graph Databases!
Most of the existing triple stores and graph databases are very heavyweight services that would be impractical for packaging in a portable daemon in the same way that sqlite works. Maybe we can learn from how sqlite works and do something similar for graph databases?
How come these things can be faster than idk like a .json file
How are they different architecturally than a traditional SQL server
Rollback Journal - stores additional information to restore in case of a crash. Store a copy of the original DB, write changes directly into DB file. COMMIT occurs when rollback is deleted
Write-ahead Log - if in WAL mode, append updates to WAL file. COMMIT occurs when writing to WAL file (not to main DB). Multiple transactions can be batched.
Pages are the basic unit of an sqlite file.
Each page can be a power of 2 between 512 and 65536
All pages are the same size
2^32 - 2pages in a single DB.
Each page has a single type:
The lock-byte page
A freelist page
A freelist trunk page
A freelist leaf page
A b-tree page
A table b-tree interior page
A table b-tree leaf page
An index b-tree interior page
An index b-tree leaf page
A payload overflow page
A pointer map page
(artifact of windows 95 compatibility)
Linked list of “trunks and leaves” to keep track of unused pages:
Series of 4-byte integers that take up full page
First integer is the page number of the next trunk (zero if it’s the last page)
Second integer is number of leaf pointers that follow
Two types of b-trees: table and index
One table b-tree in the db file for each
rowidtable in the database schema
64-bit signed integer key that refers to the
Store all data in leaves (interior pages just point to leaves)
One index b-tree for each index in the schema
Store no data.
Two types of b-tree pages:
Define the “payload” of a cell to be the arbitrary length section of the cell.
For an index b-tree, the key is always arbitrary in length and hence the payload is the key.
There are no arbitrary length elements in the cells of interior table b-tree pages and so those cells have no payload.
Table b-tree leaf pages contain arbitrary length content and so for cells on those pages the payload is the content.
When a payload is bigger than some threshold, store it on a linked list of payload overload pages. The first four bytes of each overflow page are a 4-byte big-endian integer indicating the page number of the next page in the chain, or zero for the final page.
Backlinks from child to parent nodes in index trees to assist with vacuuming :)
Each pointermap page provides backlinks for the pages immediately following it.
Each 5-byte ptrmap entry consists of:
1 byte of page type information:
0: A b-tree root page
0: Freelist page
first page: payload overflow page
parent page: non-root b-tree page
4 byte big-endian page number
(Add header info here as the rest of the spec makes it relevant)
Magic header string makes it easy to identify sqlite files
File change counter & schema cookie - 4-byte integer that increments whenever the db file is unlocked. useful for cache invalidation
version-valid-for-number- stores the version of the software that most recently modified it, and the change counter at that modification. Useful for detecting if certain behaviors like updating the in-header db size are behaving correctly by knowing what version made a given change.
How does writing and querying an sqlite file actually work???
All reads from and writes to the main database file happen at a page boundary.
All writes are an integer number of pages in size.
Most reads are also an integer number of pages in size, except opening the database which reads the header (first 100 bytes).
SQLite Quirks - useful for understanding some design decisions