pager

package
v0.63.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 27, 2026 License: AGPL-3.0 Imports: 14 Imported by: 0

Documentation

Overview

Package pager — PageBackend integrates the page-based storage engine with the tinySQL StorageBackend interface.

Package pager implements a page-based, transactional storage engine with Write-Ahead Logging (WAL) for tinySQL.

The storage format consists of a main database file (tinysql.db) with fixed-size pages (default 8 KiB) and a sequential WAL file (tinysql.wal). The first page is a superblock; subsequent pages are typed (B+Tree internal, B+Tree leaf, overflow, freelist). Every page carries a header with type, page-ID, LSN, and CRC32 checksum. Crash recovery replays committed WAL transactions from the last checkpoint_lsn.

Index

Constants

View Source 
const (
	// DefaultPageSize is the default page size in bytes (8 KiB).
	DefaultPageSize = 8192

	// MinPageSize is the minimum allowed page size (4 KiB).
	MinPageSize = 4096

	// MaxPageSize is the maximum allowed page size (64 KiB).
	MaxPageSize = 65536

	// PageHeaderSize is the size of the common page header in bytes.
	// Layout:
	//   [0]    PageType   (1 byte)
	//   [1]    Flags      (1 byte)
	//   [2:4]  Reserved   (2 bytes)
	//   [4:8]  PageID     (4 bytes, uint32 LE)
	//   [8:16] LSN        (8 bytes, uint64 LE)
	//   [16:20] CRC32     (4 bytes, uint32 LE)
	//   [20:32] Reserved  (12 bytes)
	PageHeaderSize = 32

	// InvalidPageID represents a null/invalid page pointer.
	InvalidPageID PageID = 0

	// OverflowThreshold is the max inline value size (bytes) before an
	// overflow page chain is used. Set to 1/4 of usable leaf space.
	// Adjusted dynamically based on page size, but this is the default.
	OverflowThreshold = 1024
)
View Source 
const (
	// SuperblockMagic identifies a valid tinySQL database file.
	SuperblockMagic = "TNSQLDB\x00"

	// CurrentFormatVersion is the on-disk format version.
	CurrentFormatVersion uint32 = 1
)
View Source 
const (
	WALMagic       = "TNSQWAL\x00"
	WALVersion     = uint32(1)
	WALFileHdrSize = 32
	WALRecHdrSize  = 33
)
View Source 
const MaxValueBytes = 64 << 20

MaxValueBytes is the defensive decoder bound for one variable-length row field. SQL writes are capped earlier by engine.MaxBlobBytes; this second boundary keeps damaged on-disk lengths from allocating excessive memory.

Variables

This section is empty.

Functions

func ComputePageCRC 

func ComputePageCRC(page []byte) uint32

ComputePageCRC computes the CRC32-C of a full page, treating the CRC field (bytes 16..20) as zero during computation.

func DumpTree 

func DumpTree(dbPath string, rootPageID PageID, pageSize int) (string, error)

DumpTree produces a human-readable dump of a B+Tree starting at root.

func FreeListCapacity 

func FreeListCapacity(pageSize int) int

FreeListCapacity returns how many page IDs fit in one free-list page.

func MarshalHeader 

func MarshalHeader(h *PageHeader, buf []byte)

MarshalHeader writes a PageHeader into the first PageHeaderSize bytes of buf.

func MarshalRow 

func MarshalRow(row []any, buf []byte) []byte

MarshalRow encodes a row into the compact binary format. It reuses the provided buf if large enough.

func MarshalSuperblock 

func MarshalSuperblock(sb *Superblock, pageSize int) []byte

MarshalSuperblock serializes a Superblock into a full page buffer. The buffer must be at least PageSize bytes. The common PageHeader is set (Type=Superblock, ID=0) and the CRC computed.

func NewPage 

func NewPage(pageSize int, pt PageType, id PageID) []byte

NewPage allocates a zeroed page buffer at the given size and writes its header.

func OverflowCapacity 

func OverflowCapacity(pageSize int) int

OverflowCapacity returns the payload capacity of a single overflow page.

func ParseRowKey 

func ParseRowKey(key []byte) int64

ParseRowKey extracts the row ID from a B+Tree key.

func RowKey 

func RowKey(rowID int64) []byte

RowKey creates a B+Tree key from a row index.

func SetPageCRC 

func SetPageCRC(page []byte)

SetPageCRC computes and writes the CRC into the page header.

func UnmarshalRow 

func UnmarshalRow(data []byte) ([]any, error)

UnmarshalRow decodes a row from the compact binary format.

func UnmarshalRowColumn added in v0.28.0 

func UnmarshalRowColumn(data []byte, column int) (any, error)

UnmarshalRowColumn decodes only one requested column. Columns before it are bounds-checked and skipped without constructing interface values. This is useful for typed index readers that need one BLOB or identifier from a wide row and have already validated the complete immutable artifact at open.

func VerifyDB 

func VerifyDB(dbPath string) ([]string, error)

VerifyDB checks the integrity of an entire database file. Returns a list of issues found (empty = healthy).

func VerifyPageCRC 

func VerifyPageCRC(page []byte) error

VerifyPageCRC checks the CRC32 checksum of a page.

Types

type BTree 

type BTree struct {
	// contains filtered or unexported fields
}

BTree represents a B+Tree stored in the pager.

func CreateBTree 

func CreateBTree(p *Pager, txID TxID) (*BTree, error)

CreateBTree allocates a new B+Tree with an empty leaf root page. Must be called within a transaction.

func NewBTree 

func NewBTree(p *Pager, root PageID) *BTree

NewBTree creates a handle to an existing B+Tree with the given root. For a new tree, call CreateBTree first.

func (*BTree) Contains added in v0.28.1 

func (bt *BTree) Contains(key []byte) (bool, error)

Contains reports whether key exists without loading or assembling its value. This matters for large overflow-backed rows when an index validator only needs to prove that a row locator resolves to a physical table entry.

func (*BTree) Count 

func (bt *BTree) Count() (int, error)

Count returns the total number of key-value pairs in the tree.

func (*BTree) Delete 

func (bt *BTree) Delete(txID TxID, key []byte) (bool, error)

Delete removes a key from the B+Tree.

func (*BTree) FreeAllPages 

func (bt *BTree) FreeAllPages()

FreeAllPages recursively frees every page owned by this B+Tree (internal nodes, leaf nodes, and overflow chains). After this call the tree is invalid and must not be used.

func (*BTree) Get 

func (bt *BTree) Get(key []byte) ([]byte, bool, error)

Get looks up a key. Returns (value, true) or (nil, false). Handles overflow pages transparently.

func (*BTree) GetValue added in v0.20.0 

func (bt *BTree) GetValue(key []byte, visit func(value []byte) error) (bool, error)

GetValue resolves key and invokes visit while the containing page remains pinned. Inline values are views into that page and must not be retained by visit. Overflow values are assembled into a temporary slice. This allows index locators and row codecs to decode directly from page memory without allocating a throw-away copy for every B+Tree comparison.

func (*BTree) Insert 

func (bt *BTree) Insert(txID TxID, key, value []byte) error

Insert adds or updates a key-value pair within the given transaction.

func (*BTree) Root 

func (bt *BTree) Root() PageID

Root returns the root page ID.

func (*BTree) ScanRange 

func (bt *BTree) ScanRange(startKey, endKey []byte, fn func(key, value []byte) bool) error

ScanRange calls fn for each key-value pair where startKey <= key <= endKey. If endKey is nil, scans to the end. If fn returns false, the scan stops.

type BTreePage 

type BTreePage struct {
	// contains filtered or unexported fields
}

BTreePage wraps a page buffer as a B+Tree node.

func InitBTreePage 

func InitBTreePage(buf []byte, id PageID, leaf bool) *BTreePage

InitBTreePage initialises a page as a B+Tree node.

func WrapBTreePage 

func WrapBTreePage(buf []byte) *BTreePage

WrapBTreePage wraps an existing buffer.

func (*BTreePage) Bytes 

func (bp *BTreePage) Bytes() []byte

Bytes returns the page's mutable backing buffer.

func (*BTreePage) DeleteLeafEntry 

func (bp *BTreePage) DeleteLeafEntry(pos int) error

DeleteLeafEntry removes the entry at position pos.

func (*BTreePage) FindChild 

func (bp *BTreePage) FindChild(key []byte) PageID

FindChild returns the child PageID covering the given search key.

func (*BTreePage) FindLeafEntry 

func (bp *BTreePage) FindLeafEntry(key []byte) (int, bool)

FindLeafEntry searches for an exact key match. Returns (index, true) or (-1, false).

func (*BTreePage) GetAllInternalEntries 

func (bp *BTreePage) GetAllInternalEntries() []InternalEntry

GetAllInternalEntries returns all separator entries in order.

func (*BTreePage) GetAllLeafEntries 

func (bp *BTreePage) GetAllLeafEntries() []LeafEntry

GetAllLeafEntries returns all leaf entries in order.

func (*BTreePage) GetInternalEntry 

func (bp *BTreePage) GetInternalEntry(i int) InternalEntry

GetInternalEntry returns the i-th separator key and its left child.

func (*BTreePage) GetLeafEntry 

func (bp *BTreePage) GetLeafEntry(i int) LeafEntry

GetLeafEntry returns the i-th key-value pair.

func (*BTreePage) InsertInternalEntry 

func (bp *BTreePage) InsertInternalEntry(entry InternalEntry) error

InsertInternalEntry inserts a separator key at the correct sorted position.

func (*BTreePage) InsertLeafEntry 

func (bp *BTreePage) InsertLeafEntry(entry LeafEntry) (int, error)

InsertLeafEntry inserts a key-value pair at the correct sorted position. Returns the slot index.

func (*BTreePage) IsLeaf 

func (bp *BTreePage) IsLeaf() bool

IsLeaf reports whether bp is a leaf node.

func (*BTreePage) KeyCount 

func (bp *BTreePage) KeyCount() int

KeyCount returns the number of keys stored in bp.

func (*BTreePage) NextLeaf 

func (bp *BTreePage) NextLeaf() PageID

NextLeaf returns the next leaf in the linked leaf chain.

func (*BTreePage) PageID 

func (bp *BTreePage) PageID() PageID

PageID returns bp's persistent page identifier.

func (*BTreePage) PrevLeaf 

func (bp *BTreePage) PrevLeaf() PageID

PrevLeaf returns the previous leaf in the linked leaf chain.

func (*BTreePage) RightChild 

func (bp *BTreePage) RightChild() PageID

RightChild returns the rightmost child page of an internal node.

func (*BTreePage) SearchInternal 

func (bp *BTreePage) SearchInternal(key []byte) PageID

SearchInternal finds the child page for a given key in an internal node. Internal page layout: entries[0].child, entries[0].key, entries[1].child, ... Keys divide the key space: key < entry[0].key → entry[0].child, entry[i-1].key <= key < entry[i].key → entry[i].child, key >= entry[last].key → RightChild.

func (*BTreePage) SetNextLeaf 

func (bp *BTreePage) SetNextLeaf(pid PageID)

SetNextLeaf updates the next-leaf link.

func (*BTreePage) SetPrevLeaf 

func (bp *BTreePage) SetPrevLeaf(pid PageID)

SetPrevLeaf updates the previous-leaf link.

func (*BTreePage) SetRightChild 

func (bp *BTreePage) SetRightChild(pid PageID)

SetRightChild updates the rightmost child page of an internal node.

func (*BTreePage) UpdateLeafEntry 

func (bp *BTreePage) UpdateLeafEntry(pos int, entry LeafEntry) error

UpdateLeafEntry replaces the value at the given sorted position.

type BufferPoolConfig 

type BufferPoolConfig struct {
	MaxPages int // maximum number of cached pages (default 1024)
}

BufferPoolConfig configures the page buffer pool.

type Catalog 

type Catalog struct {
	// contains filtered or unexported fields
}

Catalog manages the system catalog B+Tree.

func OpenCatalog 

func OpenCatalog(p *Pager, txID TxID) (*Catalog, error)

OpenCatalog opens or creates the system catalog.

func (*Catalog) DeleteEntry 

func (c *Catalog) DeleteEntry(txID TxID, tenant, table string) error

DeleteEntry removes a catalog entry within the given transaction.

func (*Catalog) GetEntry 

func (c *Catalog) GetEntry(tenant, table string) (*CatalogEntry, error)

GetEntry retrieves a catalog entry. Returns nil if not found.

func (*Catalog) ListTables 

func (c *Catalog) ListTables(tenant string) ([]string, error)

ListTables returns all table names for a tenant.

func (*Catalog) PutEntry 

func (c *Catalog) PutEntry(txID TxID, entry CatalogEntry) error

PutEntry upserts a catalog entry within the given transaction.

func (*Catalog) Root 

func (c *Catalog) Root() PageID

Root returns the catalog tree's root page ID.

type CatalogColumn 

type CatalogColumn struct {
	NotNull    bool   `json:"not_null,omitempty"`
	StrictJSON bool   `json:"strict_json,omitempty"`
	Name       string `json:"name"`
	Type       int    `json:"type"`       // ColType as int
	Constraint int    `json:"constraint"` // ConstraintType as int
	FKTable    string `json:"fk_table,omitempty"`
	FKColumn   string `json:"fk_col,omitempty"`
	PtrTable   string `json:"ptr_table,omitempty"`
}

CatalogColumn describes a column in the system catalog.

type CatalogEntry 

type CatalogEntry struct {
	Tenant        string          `json:"tenant"`
	Table         string          `json:"table"`
	RootPageID    PageID          `json:"root_page_id"`
	Columns       []CatalogColumn `json:"columns"`
	Indexes       []IndexInfo     `json:"indexes,omitempty"`
	RowCount      int64           `json:"row_count"`
	Version       int             `json:"version"`
	StructVersion int             `json:"struct_version,omitempty"`
	FTSIndexes    []byte          `json:"fts_indexes,omitempty"`
	VectorIndexes []byte          `json:"vector_indexes,omitempty"`
}

CatalogEntry is the value stored in the system catalog B+Tree.

type ColumnInfo 

type ColumnInfo struct {
	Name         string
	Type         int // ColType as int
	Constraint   int // ConstraintType as int
	FKTable      string
	FKColumn     string
	PointerTable string
	NotNull      bool
	StrictJSON   bool
}

ColumnInfo is a simplified, pager-internal column descriptor that does not import the storage package (to avoid circular dependencies).

type FeatureFlag 

type FeatureFlag uint64

FeatureFlag is a bitmask of optional format features. 

const (
	FeatureCompression FeatureFlag = 1 << iota // reserved: page-level compression
	FeatureEncryption                          // reserved: page-level encryption
	FeatureMVCC                                // reserved: multi-version concurrency
	FeaturePartitions                          // reserved: range partitioning
)

FeatureFlag bits (bitmask). Version 1 has no flags set. 

const SupportedFeatures FeatureFlag = 0 // v1: none

SupportedFeatures is the set of features understood by this build. Any flag outside of this set causes the file to be rejected.

type FreeListPage 

type FreeListPage struct {
	// contains filtered or unexported fields
}

FreeListPage wraps a page buffer as a free-list page.

func InitFreeListPage 

func InitFreeListPage(buf []byte, id PageID) *FreeListPage

InitFreeListPage creates a new empty free-list page.

func WrapFreeListPage 

func WrapFreeListPage(buf []byte) *FreeListPage

WrapFreeListPage wraps an existing free-list buffer.

func (*FreeListPage) AddEntry 

func (fl *FreeListPage) AddEntry(pid PageID) bool

AddEntry appends a free page ID. Returns false if the page is full.

func (*FreeListPage) AllEntries 

func (fl *FreeListPage) AllEntries() []PageID

AllEntries returns all stored free page IDs.

func (*FreeListPage) Bytes 

func (fl *FreeListPage) Bytes() []byte

Bytes returns the underlying page buffer.

func (*FreeListPage) EntryCount 

func (fl *FreeListPage) EntryCount() int

EntryCount returns the number of free page IDs stored.

func (*FreeListPage) GetEntry 

func (fl *FreeListPage) GetEntry(i int) PageID

GetEntry returns the i-th free page ID.

func (*FreeListPage) NextFreeList 

func (fl *FreeListPage) NextFreeList() PageID

NextFreeList returns the next free-list page in the chain.

func (*FreeListPage) PopEntry 

func (fl *FreeListPage) PopEntry() PageID

PopEntry removes and returns the last entry. Returns InvalidPageID if empty.

func (*FreeListPage) SetNextFreeList 

func (fl *FreeListPage) SetNextFreeList(pid PageID)

SetNextFreeList sets the next page pointer.

type FreeManager 

type FreeManager struct {
	// contains filtered or unexported fields
}

FreeManager tracks free pages using an in-memory set backed by free-list pages on disk. The pager calls its methods during allocation and deallocation.

func NewFreeManager 

func NewFreeManager() *FreeManager

NewFreeManager creates a FreeManager. Call LoadFromDisk to populate.

func (*FreeManager) AllFree 

func (fm *FreeManager) AllFree() []PageID

AllFree returns all free page IDs (unsorted).

func (*FreeManager) Alloc 

func (fm *FreeManager) Alloc() PageID

Alloc returns a free page ID (popped from the set) or InvalidPageID if empty.

func (*FreeManager) Count 

func (fm *FreeManager) Count() int

Count returns the number of free pages.

func (*FreeManager) FlushToDisk 

func (fm *FreeManager) FlushToDisk(pageSize int, allocPage func() (PageID, []byte)) (PageID, [][]byte)

FlushToDisk writes the in-memory free set into free-list pages. It returns the head PageID of the new chain and the list of page buffers to write. allocPage is a callback that returns a new, zeroed page buffer with a fresh ID.

func (*FreeManager) Free 

func (fm *FreeManager) Free(pid PageID)

Free marks a page ID as available for reuse.

func (*FreeManager) LoadFromDisk 

func (fm *FreeManager) LoadFromDisk(head PageID, readPage func(PageID) ([]byte, error)) error

LoadFromDisk walks the free-list chain starting at head and populates the in-memory set. readPage is a callback that reads a page by ID.

type GCResult 

type GCResult struct {
	TotalPages     int      // total allocated pages in the file
	ReachablePages int      // pages reachable from roots
	FreeBefore     int      // free pages before GC
	FreeAfter      int      // free pages after GC
	Reclaimed      int      // newly freed orphan pages
	Errors         []string // non-fatal issues found during the scan
}

GCResult holds statistics about a garbage collection run.

type IndexEntry added in v0.20.0 

type IndexEntry struct {
	Key    []byte
	RowIDs []int
}

IndexEntry maps one canonical key to row IDs in table order.

type IndexInfo added in v0.20.0 

type IndexInfo struct {
	Name       string       `json:"name"`
	Columns    []string     `json:"columns"`
	Unique     bool         `json:"unique"`
	RootPageID PageID       `json:"root_page_id"`
	Entries    []IndexEntry `json:"-"`
}

IndexInfo identifies one persistent secondary-index B+Tree. Entries are supplied only while building a table; root and schema are persisted in the catalog and are sufficient for immutable seeks after reopening the file.

type InternalEntry 

type InternalEntry struct {
	ChildID PageID
	Key     []byte
}

InternalEntry represents a key + left-child pointer for internal pages.

type LSN 

type LSN uint64

LSN is a monotonically increasing Log Sequence Number.

type LeafEntry 

type LeafEntry struct {
	Key            []byte
	Value          []byte // inline value (empty when overflow)
	Overflow       bool
	OverflowPageID PageID
	TotalSize      uint32
}

LeafEntry represents a key-value pair stored in a leaf page.

type OverflowPage 

type OverflowPage struct {
	// contains filtered or unexported fields
}

OverflowPage wraps a page buffer as an overflow page.

func InitOverflowPage 

func InitOverflowPage(buf []byte, id PageID) *OverflowPage

InitOverflowPage creates a new overflow page.

func WrapOverflowPage 

func WrapOverflowPage(buf []byte) *OverflowPage

WrapOverflowPage wraps an existing overflow page buffer.

func (*OverflowPage) Bytes 

func (op *OverflowPage) Bytes() []byte

Bytes returns the underlying page buffer.

func (*OverflowPage) Data 

func (op *OverflowPage) Data() []byte

Data returns the payload bytes.

func (*OverflowPage) DataLen 

func (op *OverflowPage) DataLen() int

DataLen returns the number of payload bytes stored.

func (*OverflowPage) NextOverflow 

func (op *OverflowPage) NextOverflow() PageID

NextOverflow returns the next overflow page in the chain.

func (*OverflowPage) SetData 

func (op *OverflowPage) SetData(data []byte) error

SetData writes payload into the overflow page. Returns an error if the data exceeds the capacity.

func (*OverflowPage) SetNextOverflow 

func (op *OverflowPage) SetNextOverflow(pid PageID)

SetNextOverflow sets the next-page pointer.

type PageBackend 

type PageBackend struct {
	// contains filtered or unexported fields
}

PageBackend implements a disk-based key-value store backed by B+Trees, a WAL for crash safety, and a buffer pool for caching.

func NewPageBackend 

func NewPageBackend(cfg PageBackendConfig) (*PageBackend, error)

NewPageBackend opens or creates a page-based database.

func (*PageBackend) AppendRows added in v0.26.2 

func (pb *PageBackend) AppendRows(tenant, name string, newRows [][]any, newIndexKeys map[string][][]byte) (int64, error)

AppendRows inserts newRows into an existing table's B+Tree in place, without reading or rewriting any row already on disk, and inserts newIndexKeys into the existing unique secondary-index B+Trees the same way.

This is what SaveTable cannot do: SaveTable always frees the whole existing tree and rebuilds it from a complete row set, so its cost -- and the memory needed to hold that complete row set -- grows with the table's total size. Building a tileset far larger than memory means every batch after the first must cost only its own size, not the size of everything imported so far; AppendRows is the primitive that makes that possible. See ImportMBTiles in internal/importer, which uses it when the destination is paged-index storage.

newIndexKeys maps index name to one canonical key per row in newRows, in the same order; a nil/empty key skips that row for that index. Only unique indexes are meaningful here: a duplicate key is rejected by neither this method nor the underlying B+Tree (which stores the last write), so the caller is responsible for uniqueness -- true for a well-formed MBTiles source, whose own UNIQUE index already guarantees it.

Returns the row ID assigned to newRows[0]; subsequent rows are numbered sequentially from there.

func (*PageBackend) Close 

func (pb *PageBackend) Close() error

Close performs a final checkpoint and closes all files.

func (*PageBackend) DBPath 

func (pb *PageBackend) DBPath() string

DBPath returns the database file path.

func (*PageBackend) DeleteTable 

func (pb *PageBackend) DeleteTable(tenant, name string) error

DeleteTable removes a table from the catalog and frees its pages.

func (*PageBackend) GC 

func (pb *PageBackend) GC() (*GCResult, error)

GC performs a full reachability-based garbage collection on the database. It must be called when no other writers are active (exclusive access). The GC does NOT shrink the file — it only adds orphans to the free-list so they can be reused by future writes.

func (*PageBackend) ListTableNames 

func (pb *PageBackend) ListTableNames(tenant string) ([]string, error)

ListTableNames returns all table names for a tenant.

func (*PageBackend) LoadTable 

func (pb *PageBackend) LoadTable(tenant, name string) (*TableData, error)

LoadTable retrieves all rows of a table from its B+Tree.

func (*PageBackend) LookupIndexRows added in v0.20.0 

func (pb *PageBackend) LookupIndexRows(tenant, table, indexName string, key []byte) ([][]any, bool, error)

LookupIndexRows follows an immutable secondary-index B+Tree and loads only referenced row records from the table B+Tree. It intentionally bypasses LoadTable, which materializes all rows for compatibility callers.

func (*PageBackend) LookupIndexRowsByRoot added in v0.20.0 

func (pb *PageBackend) LookupIndexRowsByRoot(tableRoot, indexRoot PageID, indexName string, key []byte) ([][]any, bool, error)

LookupIndexRowsByRoot is the locator form of LookupIndexRows. A caller that has already validated an immutable catalog entry can bypass the catalog B+Tree and JSON decode on every point lookup. Roots are only accepted from the same open PageBackend; they are not a portable public file-format API.

func (*PageBackend) LookupUniqueIndexRowBytesColumnByRoot added in v0.33.0 

func (pb *PageBackend) LookupUniqueIndexRowBytesColumnByRoot(tableRoot, indexRoot PageID, indexName string, key []byte, column int, visit func([]byte) error) (bool, error)

LookupUniqueIndexRowBytesColumnByRoot is the concrete-BLOB variant of LookupUniqueIndexRowColumnByRoot. It is for typed serving paths that always read a BLOB column (notably immutable tile artifacts), avoiding interface boxing and a type assertion per request.

func (*PageBackend) LookupUniqueIndexRowColumnByRoot added in v0.28.0 

func (pb *PageBackend) LookupUniqueIndexRowColumnByRoot(tableRoot, indexRoot PageID, indexName string, key []byte, column int, visit func(any) error) (bool, error)

LookupUniqueIndexRowColumnByRoot resolves one unique index entry and decodes only the requested table column. It avoids allocating a row-ID slice, an outer rows slice and values for columns the typed caller does not consume.

func (*PageBackend) LookupUniqueIndexRowExistsByRoot added in v0.28.1 

func (pb *PageBackend) LookupUniqueIndexRowExistsByRoot(tableRoot, indexRoot PageID, indexName string, key []byte) (bool, error)

LookupUniqueIndexRowExistsByRoot follows a unique index locator and proves that its table row exists without reading the row value. It validates the same durable 12-byte locator used by typed lookups while avoiding overflow BLOB I/O for integrity checks that need reachability only.

func (*PageBackend) MaxCachePages added in v0.20.0 

func (pb *PageBackend) MaxCachePages() int

MaxCachePages reports the strict page-cache capacity used by this backend.

func (*PageBackend) Pager 

func (pb *PageBackend) Pager() *Pager

Pager returns the underlying pager (for inspection tools).

func (*PageBackend) SaveTable 

func (pb *PageBackend) SaveTable(tenant string, td *TableData) error

SaveTable persists all rows of a table into a B+Tree. This replaces the entire table contents (drop + recreate of the tree).

func (*PageBackend) ScanIndexRowsRange added in v0.27.1 

func (pb *PageBackend) ScanIndexRowsRange(tenant, table, indexName string, startKey, endKey []byte, fn func([]any) bool) error

ScanIndexRowsRange streams rows selected by an ordered composite index. It is the range counterpart to LookupIndexRows and deliberately invokes the callback per row so spatial windows do not materialize a whole tile band.

func (*PageBackend) ScanIndexRowsRangeBatch added in v0.46.0 

func (pb *PageBackend) ScanIndexRowsRangeBatch(tenant, table, indexName string, startKey, endKey, resumeKey []byte, skipAtResumeKey, limit int) (rows [][]any, nextKey []byte, nextSkip int, done bool, err error)

ScanIndexRowsRangeBatch decodes at most limit table rows from an ordered secondary-index interval. It resumes at (resumeKey, skipAtResumeKey), where the skip count is necessary because one index key can point to many rows. Like ScanTableRowsBatch, it never invokes user code while pb.mu is held.

A full batch may conservatively leave done false even at EOF. Calling it once more with the returned cursor establishes EOF without dropping rows.

func (*PageBackend) ScanTableRows added in v0.26.2 

func (pb *PageBackend) ScanTableRows(tenant, name string, fn func(row []any) bool) error

ScanTableRows streams a table's rows to fn in key order, one B+Tree leaf page at a time, instead of collecting them all into one slice the way LoadTable does. fn returning false stops the scan early, same as BTree.ScanRange. Memory use is bounded by one leaf's worth of rows (plus whatever overflow pages a single oversized row needs), not by the table's total size -- the reader side of the same "larger than memory" property AppendRows gives the writer side. ExportMBTiles (internal/importer) is the motivating caller: writing out a tileset larger than memory should not need loading it into memory first.

func (*PageBackend) ScanTableRowsBatch added in v0.46.0 

func (pb *PageBackend) ScanTableRowsBatch(tenant, name string, afterKey []byte, limit int) (rows [][]any, nextKey []byte, done bool, err error)

ScanTableRowsBatch decodes at most limit rows after afterKey and releases the backend read lock before returning them to the caller. It is the cursor building block for slow network result streams: unlike ScanTableRows, a blocked consumer can never retain pb.mu's read side while it waits.

nextKey is the final returned table key. When done is false, pass it as afterKey to continue. A full final batch can conservatively report done false; one cheap empty follow-up call then establishes EOF without risking a missed last row.

func (*PageBackend) Stats 

func (pb *PageBackend) Stats() PageBackendStats

Stats returns operational statistics.

func (*PageBackend) Sync 

func (pb *PageBackend) Sync() error

Sync performs a checkpoint.

func (*PageBackend) TableEntry added in v0.20.0 

func (pb *PageBackend) TableEntry(tenant, table string) (*CatalogEntry, error)

TableEntry returns table and index metadata without scanning row pages.

func (*PageBackend) TableExists 

func (pb *PageBackend) TableExists(tenant, name string) bool

TableExists reports whether a table exists in the catalog.

type PageBackendConfig 

type PageBackendConfig struct {
	Path          string // database file path (.db)
	PageSize      int    // 0 = DefaultPageSize (8 KiB)
	MaxCachePages int    // buffer pool size (0 = default 1024)
	ReadOnly      bool
}

PageBackendConfig configures the page-based StorageBackend.

type PageBackendStats 

type PageBackendStats struct {
	PageSize        int
	PageCount       uint64
	FreePages       int
	CheckpointLSN   LSN
	NextTxID        TxID
	SyncCount       int64
	LoadCount       int64
	PageReads       int64
	CacheHits       int64
	CacheMisses     int64
	CachedPages     int
	PinnedPages     int
	TransientPages  int
	TransientFrames int
	MaxCachePages   int
	DBPath          string
	WALPath         string
}

PageBackendStats holds operational metrics.

type PageBufferPool 

type PageBufferPool struct {
	// contains filtered or unexported fields
}

PageBufferPool is an LRU page cache with dirty-page tracking.

type PageFrame 

type PageFrame struct {
	// contains filtered or unexported fields
}

PageFrame is an in-memory cached page. 

type PageHeader struct {
	Type     PageType // 1 byte
	Flags    uint8    // 1 byte
	Reserved uint16   // 2 bytes
	ID       PageID   // 4 bytes
	LSN      LSN      // 8 bytes
	CRC      uint32   // 4 bytes — CRC32 of the entire page (with CRC field zeroed)
	Pad      [12]byte // reserved for future use
}

PageHeader is the 32-byte header present at the start of every page.

func UnmarshalHeader 

func UnmarshalHeader(buf []byte) PageHeader

UnmarshalHeader reads a PageHeader from the first PageHeaderSize bytes of buf.

type PageID 

type PageID uint32

PageID is a 32-bit page identifier. Page 0 is always the superblock.

type PageInfo 

type PageInfo struct {
	ID       PageID
	Type     PageType
	TypeStr  string
	LSN      LSN
	CRC      uint32
	CRCValid bool
	Flags    uint8
	// B+Tree specifics
	IsLeaf     bool
	KeyCount   int
	RightChild PageID
	NextLeaf   PageID
	PrevLeaf   PageID
	// Slotted page stats
	SlotCount int
	FreeSpace int
	// Overflow
	NextOverflow PageID
	DataLen      int
	// FreeList
	NextFreeList PageID
	EntryCount   int
}

PageInfo holds inspection information about a single page.

func InspectPage 

func InspectPage(dbPath string, pageID PageID, pageSize int) (*PageInfo, error)

InspectPage reads a single page and returns detailed information.

type PageType 

type PageType uint8

PageType identifies the kind of data stored in a page. 

const (
	PageTypeSuperblock    PageType = 0x01
	PageTypeBTreeInternal PageType = 0x02
	PageTypeBTreeLeaf     PageType = 0x03
	PageTypeOverflow      PageType = 0x04
	PageTypeFreeList      PageType = 0x05
)

func (PageType) String 

func (pt PageType) String() string

String returns a human-readable label for the page type.

type Pager 

type Pager struct {
	// contains filtered or unexported fields
}

Pager manages page-level I/O, WAL, buffer pool, and free-list.

func OpenPager 

func OpenPager(cfg PagerConfig) (*Pager, error)

OpenPager opens or creates a page-based database.

func (*Pager) AbortTx 

func (p *Pager) AbortTx(txID TxID) error

AbortTx writes an ABORT record. Dirty pages for this TX will be discarded on the next recovery or checkpoint.

func (*Pager) AllocPage 

func (p *Pager) AllocPage() (PageID, []byte)

AllocPage allocates a new page (from the free-list or by extending the file). Returns the page ID and a zeroed buffer. The page is pinned in the cache.

func (*Pager) BeginTx 

func (p *Pager) BeginTx() (TxID, error)

BeginTx starts a new transaction and writes a BEGIN record to the WAL.

func (*Pager) CacheStats added in v0.20.0 

func (p *Pager) CacheStats() PagerCacheStats

CacheStats returns a snapshot of the pager's in-memory page cache.

func (*Pager) Checkpoint 

func (p *Pager) Checkpoint() error

Checkpoint flushes all dirty pages to the database file, writes an updated superblock, fsyncs the file, then truncates the WAL.

func (*Pager) Close 

func (p *Pager) Close() error

Close performs a final checkpoint and closes all files.

func (*Pager) CommitTx 

func (p *Pager) CommitTx(txID TxID) error

CommitTx writes a COMMIT record and fsyncs the WAL.

func (*Pager) FreePage 

func (p *Pager) FreePage(pid PageID)

FreePage marks a page as free for reuse.

func (*Pager) PageSize 

func (p *Pager) PageSize() int

PageSize returns the configured page size.

func (*Pager) Path 

func (p *Pager) Path() string

Path returns the database file path.

func (*Pager) ReadPage 

func (p *Pager) ReadPage(id PageID) ([]byte, error)

ReadPage returns a page by ID, using the buffer pool cache. The page is pinned in the cache; call UnpinPage when done.

func (*Pager) Recover 

func (p *Pager) Recover() error

Recover replays the WAL and applies committed transactions.

func (*Pager) Superblock 

func (p *Pager) Superblock() Superblock

Superblock returns a copy of the current superblock.

func (*Pager) UnpinPage 

func (p *Pager) UnpinPage(id PageID)

UnpinPage decrements the pin count.

func (*Pager) UpdateSuperblock 

func (p *Pager) UpdateSuperblock(fn func(sb *Superblock))

UpdateSuperblock updates the in-memory superblock fields. It does NOT write to disk. Use Checkpoint for that.

func (*Pager) WALPath 

func (p *Pager) WALPath() string

WALPath returns the WAL file path.

func (*Pager) WritePage 

func (p *Pager) WritePage(txID TxID, id PageID, buf []byte) error

WritePage writes (updates) a page through the WAL. The page image is logged to the WAL and cached as dirty. The caller should have called BeginTx beforehand.

type PagerCacheStats added in v0.20.0 

type PagerCacheStats struct {
	PageReads       int64
	CacheHits       int64
	CacheMisses     int64
	CachedPages     int
	PinnedPages     int
	TransientPages  int
	TransientFrames int
	MaxPages        int
}

PagerCacheStats reports the physical-read and bounded-cache state. The counters are deliberately process-local: they describe this open snapshot, not a persisted database property.

type PagerConfig 

type PagerConfig struct {
	DBPath        string
	WALPath       string
	PageSize      int
	MaxCachePages int // buffer pool capacity (0 = default 1024)
	ReadOnly      bool
}

PagerConfig configures a Pager.

type SlotEntry 

type SlotEntry struct {
	Offset uint16
	Length uint16
}

SlotEntry describes one slot in the directory.

type SlottedPage 

type SlottedPage struct {
	// contains filtered or unexported fields
}

SlottedPage wraps a raw page buffer and provides record-level operations.

func InitSlottedPage 

func InitSlottedPage(buf []byte, pt PageType, id PageID) *SlottedPage

InitSlottedPage initialises a page buffer as an empty slotted page.

func WrapSlottedPage 

func WrapSlottedPage(buf []byte) *SlottedPage

WrapSlottedPage wraps an existing page buffer.

func (*SlottedPage) Bytes 

func (sp *SlottedPage) Bytes() []byte

Bytes returns the underlying page buffer.

func (*SlottedPage) Compact 

func (sp *SlottedPage) Compact()

Compact reorganises records to remove gaps left by deletions. Preserves slot order. This is needed before splitting pages.

func (*SlottedPage) DeleteRecord 

func (sp *SlottedPage) DeleteRecord(i int) error

DeleteRecord marks slot i as deleted (tombstone).

func (*SlottedPage) FreeSpace 

func (sp *SlottedPage) FreeSpace() int

FreeSpace returns the number of bytes available for new records+slots.

func (*SlottedPage) FreeSpaceEnd 

func (sp *SlottedPage) FreeSpaceEnd() int

FreeSpaceEnd is the byte offset where the next record will be written.

func (*SlottedPage) GetRecord 

func (sp *SlottedPage) GetRecord(i int) []byte

GetRecord returns the raw bytes of the record at slot i. Returns nil if the slot is a tombstone.

func (*SlottedPage) GetSlot 

func (sp *SlottedPage) GetSlot(i int) SlotEntry

GetSlot returns the slot entry at index i.

func (*SlottedPage) InsertRecord 

func (sp *SlottedPage) InsertRecord(data []byte) (int, error)

InsertRecord adds a new record to the page. Returns the slot index, or an error if there is insufficient space.

func (*SlottedPage) IsDeleted 

func (sp *SlottedPage) IsDeleted(i int) bool

IsDeleted returns true if slot i is a tombstone.

func (*SlottedPage) LiveRecords 

func (sp *SlottedPage) LiveRecords() int

LiveRecords returns the count of non-deleted records.

func (*SlottedPage) SlotCount 

func (sp *SlottedPage) SlotCount() int

SlotCount returns the number of slots (including tombstones).

func (*SlottedPage) UpdateRecord 

func (sp *SlottedPage) UpdateRecord(i int, data []byte) error

UpdateRecord replaces the record at slot i. If the new data fits in the old slot's space, it is written in-place; otherwise the old slot is tombstoned and a new record is appended.

type Superblock 

type Superblock struct {
	FormatVersion uint32
	PageSize      uint32
	PageCount     uint64
	FeatureFlags  FeatureFlag
	CatalogRoot   PageID
	FreeListRoot  PageID
	CheckpointLSN LSN
	NextTxID      TxID
	NextPageID    PageID
}

Superblock holds the parsed contents of page 0.

func NewSuperblock 

func NewSuperblock(pageSize uint32) *Superblock

NewSuperblock creates a default Superblock for a new database.

func UnmarshalSuperblock 

func UnmarshalSuperblock(buf []byte) (*Superblock, error)

UnmarshalSuperblock decodes page 0 from buf. It validates magic bytes, format version, feature flags, and CRC. Returns an error on any mismatch.

type SuperblockInfo 

type SuperblockInfo struct {
	FormatVersion uint32
	PageSize      uint32
	PageCount     uint64
	FeatureFlags  uint64
	CatalogRoot   PageID
	FreeListRoot  PageID
	CheckpointLSN LSN
	NextTxID      TxID
	NextPageID    PageID
	CRCValid      bool
}

SuperblockInfo holds display-friendly superblock data.

func InspectSuperblock 

func InspectSuperblock(dbPath string) (*SuperblockInfo, error)

InspectSuperblock reads and returns the superblock metadata.

type TableData 

type TableData struct {
	Name          string
	Columns       []ColumnInfo
	Rows          [][]any
	Indexes       []IndexInfo
	IsTemp        bool
	Version       int
	StructVersion int
	FTSIndexes    []byte
	VectorIndexes []byte
}

TableData is the pager-level representation of a table. Higher layers convert between TableData and storage.Table.

type TxID 

type TxID uint64

TxID is a transaction identifier.

type WALFile 

type WALFile struct {
	// contains filtered or unexported fields
}

WALFile manages the append-only WAL file.

func OpenWALFile 

func OpenWALFile(path string, pageSize int) (*WALFile, error)

OpenWALFile opens or creates a WAL file. If the file exists, it validates the header. If it does not exist, it writes a new header.

func (*WALFile) AppendRecord 

func (wf *WALFile) AppendRecord(rec *WALRecord) (LSN, error)

AppendRecord writes a WAL record and assigns it a monotonic LSN. Returns the assigned LSN.

func (*WALFile) Close 

func (wf *WALFile) Close() error

Close closes the WAL file.

func (*WALFile) NextLSN 

func (wf *WALFile) NextLSN() LSN

NextLSN returns the next LSN that will be assigned.

func (*WALFile) SetNextLSN 

func (wf *WALFile) SetNextLSN(lsn LSN)

SetNextLSN allows recovery to set the LSN counter.

func (*WALFile) Sync 

func (wf *WALFile) Sync() error

Sync fsyncs the WAL file to guarantee durability.

func (*WALFile) Truncate 

func (wf *WALFile) Truncate() error

Truncate resets the WAL file to just the header (after a checkpoint).

type WALInfo 

type WALInfo struct {
	PageSize   int
	Records    int
	MinLSN     LSN
	MaxLSN     LSN
	TxCount    int
	Committed  int
	Aborted    int
	PageImages int
}

WALInfo holds information about a WAL file.

func InspectWAL 

func InspectWAL(walPath string) (*WALInfo, error)

InspectWAL reads and summarises a WAL file.

type WALRecord 

type WALRecord struct {
	Type   WALRecordType
	LSN    LSN
	TxID   TxID
	PageID PageID
	Data   []byte // full page image for PAGE_IMAGE, nil otherwise
}

WALRecord is an in-memory representation of a WAL record.

func ReadAllRecords 

func ReadAllRecords(path string) ([]*WALRecord, error)

ReadAllRecords reads all WAL records from the file (after the header). Partial/corrupt records at the tail are silently ignored (crash truncation).

type WALRecordType 

type WALRecordType uint8

WALRecordType identifies the kind of WAL record. 

const (
	WALRecordBegin      WALRecordType = 0x01
	WALRecordPageImage  WALRecordType = 0x02
	WALRecordCommit     WALRecordType = 0x03
	WALRecordAbort      WALRecordType = 0x04
	WALRecordCheckpoint WALRecordType = 0x05
)

func (WALRecordType) String 

func (rt WALRecordType) String() string

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.