GizStack
View .mdOpen in ChatGPTOpen in Claude

gizmodel/core/inverted

The inverted index of a text column and BM25 top-k search over it.

One byte layout is the index, in memory and in a segment's file (segment.giz), read in pages of PAGE bytes: a resident index holds every page, a cold one the pages its queries read. Its sections: a head; the first term of each group of GROUP terms (resident, so a lookup reads one group); a table of ENTRY bytes a term (its document count, its text, its postings, and from version 2 its positions); the terms' texts; the postings; the length of each row; from version 2 each term's positions. A term's postings are blocks of 128 rows (the last one fewer): a skip list of each block's last row, then each block's record with the (frequency, length) pairs that bound its BM25 contribution and its row gaps and frequencies packed at the widths the block needs (kernels.giz packBlock). Search skips the blocks whose best possible score cannot enter the current top k: one term alone by its blocks, an OR of words by block-max MaxScore over windows of rows, every word by leapfrog. A block is decoded only when a search reads its rows. A phrase is decided by the positions of its words in a row, read at the rows that hold them all. A typeahead query expands each word over the sorted dictionaries of every part first (prefix, typos, Hangul initials), and a row scores each query word once, at its best term.

gizlang
import * as Inverted from "gizmodel/core/inverted";

Types

PostingsBuilder

gizlang
type PostingsBuilder = { lookup: Map<string, i64>; terms: Vec<string>; docs: Vec<Vec<u32>>; tfs: Vec<Vec<u32>>; poss: Vec<Vec<u32>>; lengths: Vec<u32>; totalLength: i64; documents: i64; sorted: bool; order: Vec<i64>; fresh: Vec<i64>; }

Postings being built (the delta's, or a segment's during its build).

  • lookup: _gizlang_sdk_collections.Map<string, i64>
  • terms: Vec<string>
  • docs: Vec<Vec<u32>>
  • tfs: Vec<Vec<u32>>
  • poss: Vec<Vec<u32>> — Each term's positions in its rows, a posting's after the one before it.
  • lengths: Vec<u32>
  • totalLength: i64
  • documents: i64
  • sorted: bool — Whether the term ids are kept by their bytes: ORDER, and FRESH, the newer ids (at most FRESH_TERMS), merged into it once they are that many. A delta page keeps them, so a search of the page sorts at most FRESH_TERMS terms (PostingsBuilder.ordered). A new term put in place in ORDER moved the ids after it: the delta's index build was 37% of a load of 200,000 documents.
  • order: Vec<i64>
  • fresh: Vec<i64>

TextIndex

gizlang
type TextIndex = { pages: Vec<bytes>; terms: i64; rows: i64; totalLength: i64; documents: i64; table: i64; texts: i64; textsEnd: i64; postings: i64; postingsEnd: i64; norms: i64; width: i64; firsts: Vec<string>; starts: Vec<i64>; size: i64; headBytes: i64; entry: i64; positionsEnd: i64; }

A finished, immutable index of one segment's text column: a view over its layout.

  • pages: Vec<bytes> — The layout in pages of PAGE bytes. A cold index's pages that no query read yet are empty.
  • terms: i64
  • rows: i64
  • totalLength: i64
  • documents: i64
  • table: i64 — Where the term table, the texts, the postings and the rows' lengths are, and the lengths' bytes each.
  • texts: i64
  • textsEnd: i64
  • postings: i64
  • postingsEnd: i64
  • norms: i64
  • width: i64
  • firsts: Vec<string> — The first term of each group and where its texts start: a lookup's search of the groups reads no page.
  • starts: Vec<i64>
  • size: i64 — The layout's bytes, and its head's (the head and the groups' first terms: what a cold open reads).
  • headBytes: i64
  • entry: i64 — A term's entry's bytes, and where its positions end (0: the index has none).
  • positionsEnd: i64

Stats

gizlang
type Stats = { documents: i64; totalLength: i64; frequencies: Vec<i64>; }

Corpus statistics summed over every part searched, so scores do not depend on how the data is split into segments.

  • documents: i64
  • totalLength: i64
  • frequencies: Vec<i64>

Kept

gizlang
type Kept = { list: Vec<u32>; except: bool; }

The rows of a part a search keeps, in rising order: the rows of LIST, or with EXCEPT every row but those. An empty LIST with EXCEPT is every row. A search reads it in row order (Keeper), so it costs the rows it lists: a mask of one byte a row cost an allocation and a pass over every row of the part for each query.

  • list: Vec<u32>
  • except: bool

Keeper

gizlang
type Keeper = { list: Vec<u32>; except: bool; at: i64; }

A reader of a Kept that is asked its rows in rising order. A scorer tests Kept.every once, outside its row loop: a call a row was 1.3% of disjoined's time.

  • list: Vec<u32>
  • except: bool
  • at: i64

Searched

gizlang
type Searched = { fields: Vec<TextIndex>; nulls: Vec<bytes>; visible: Kept; kept: Kept; base: i64; rows: i64; }

One part a search reads: the index of each searched column (one row numbering) and the null rows of each (a byte a row, read only when the part does not see every row; empty: none), the rows it sees, the rows the caller's conditions keep of them, the number of its first row in the search, and its rows.

  • fields: Vec<M146.TextIndex>
  • nulls: Vec<bytes>
  • visible: M146.Kept
  • kept: M146.Kept
  • base: i64
  • rows: i64

Hit

gizlang
type Hit = { row: i64; score: f64; }

One scored row.

  • row: i64
  • score: f64

TopK

gizlang
type TopK = { kept: Collections.TopK<Hit>; floor: f64; }

The k best rows. floor: a score below which no hit can matter, known before any is kept.

  • kept: _gizlang_sdk_collections.TopK<M146.Hit>
  • floor: f64

Query

gizlang
type Query = { terms: Vec<string>; weights: Vec<f64>; groups: Vec<i64>; size: i64; every: bool; }

The query's terms as they index the corpus. Term i comes from query word groups[i] and scores with weights[i] (the word's repeats times how near it is); a row counts each of the size words once, at its best term. With every (a typeahead query) a row holds each word, so each word a person types narrows the rows; else any word finds a row, and the rows that hold more rank first.

  • terms: Vec<string>
  • weights: Vec<f64>
  • groups: Vec<i64>
  • size: i64
  • every: bool

Functions

textWeight

gizlang
function textWeight(options: string): f64

The weight of a text index: the weight storage parameter (WITH (weight = 3)), 1 by default. A search over several columns adds each column's score times its weight.

Effects: fail, alloc.

postingsBuilder

gizlang
function postingsBuilder(): PostingsBuilder

An empty builder.

Effects: fail, alloc.

sortedBuilder

gizlang
function sortedBuilder(): PostingsBuilder

An empty builder that keeps its terms in order (PostingsBuilder.order).

Effects: fail, alloc.

emptyIndex

gizlang
function emptyIndex(): TextIndex

An index of no documents.

merged

gizlang
function merged(indexes: Vec<TextIndex>, maps: Vec<Vec<i64>>, rows: i64, documents: i64): TextIndex

The index of rows ROWS made of the rows of INDEXES: row MAPS[i][r] of it (-1: none) is row r of INDEXES[i], and DOCUMENTS of its rows hold a value. The dictionaries are merged in order and the postings copied: no text is read again (compaction, table.giz).

Effects: fail, alloc.

indexColumn

gizlang
function indexColumn(codes: Vec<u32>, dict: Texts, nulls: bytes): TextIndex

Builds a segment's index from a text column's dictionary and codes, tokenizing each distinct text once.

Effects: fail, alloc.

headOf

gizlang
function headOf(head: bytes): Option<TextIndex>

The index whose layout starts with HEAD, at least its head (TextIndex.headBytes), its pages unread: a cold segment's (segment.giz); undefined when HEAD is not one.

Effects: fail, alloc.

layoutIndex

gizlang
function layoutIndex(data: bytes): Option<TextIndex>

The resident index of the layout DATA, undefined when DATA is not one (segment.giz reads it from a file).

Effects: fail, alloc.

everyRow

gizlang
function everyRow(): Kept

Every row.

onlyRows

gizlang
function onlyRows(list: Vec<u32>): Kept

The rows of LIST, rising.

exceptRows

gizlang
function exceptRows(list: Vec<u32>): Kept

Every row but those of LIST, rising.

keeper

gizlang
function keeper(kept: Kept): Keeper

A Keeper of KEPT at its first row.

best

gizlang
function best(q: Query, ops: Operators, weights: Vec<f64>, parts: Vec<Searched>, keep: i64): TopK

The best KEEP rows of PARTS for Q under the operators OPS, the columns weighted by WEIGHTS: BM25F with the statistics of each column summed over every part, so a score does not depend on how the rows are split into parts. A phrase holds in one column and an excluded word in none. The one search path: SQL MATCH and in-memory indexes.

Effects: fail, read, write, alloc.

matching

gizlang
function matching(q: Query, ops: Operators, parts: Vec<Searched>, keep: i64): i64

How many rows of PARTS best would find for Q and OPS, at most KEEP, from the postings alone: a row that holds a term of each group when the query needs every group, else of any group. A count scores no row, and its cursors walk the postings once in row order and stop at KEEP: a mask and a count of every row of each part cost more than the search.

Effects: fail, alloc.

union

gizlang
function union(lists: Vec<Vec<i64>>): Vec<i64>

The rows of any of LISTS, ascending, each once.

Effects: fail, alloc.

bm25Idf

gizlang
function bm25Idf(documents: i64, df: i64): f64

BM25's inverse document frequency of a term DF of DOCUMENTS hold (Lucene's, never negative).

Effects: fail.

topK

gizlang
function topK(k: i64): TopK

An empty TopK that keeps the K best hits.

query

gizlang
function query(text: string): Query

The exact query of TEXT.

Effects: fail, read, write, alloc.

resolve

gizlang
function resolve(words: Vec<Word>, indexes: Vec<TextIndex>): Query

The query of WORDS over the dictionaries of INDEXES (every part searched, so each part scores the same terms with the same statistics): an exact word is its term, a typeahead word also each term it accepts in any of them.

Effects: fail, read, write, alloc.

searchFields

gizlang
function searchFields(fields: Vec<TextIndex>, weights: Vec<f64>, q: Query, stats: Vec<Stats>, allowed: Kept, base: i64, heap: mut TopK, admit: mut Admission): void

The best rows of the indexes FIELDS of one segment's columns, one row numbering, with the column weights WEIGHTS and the statistics STATS of each: offers each allowed row scoring above the heap's threshold, as row base + row. A row's score is the sum over the columns of the weight times the column's BM25 score, each word at its best term in the column (BM25F as the indexes weigh it). allowed is the rows that may match. Rows are offered in increasing order and callers search segments in row order, so a row that only ties the threshold loses to the earlier one exactly as the heap's rule says: skipping it (strict >) gives the same result as exhaustive scoring.

Effects: fail, read, write, alloc.

saturate

gizlang
function saturate(tf: f64, length: f64, avg: f64): f64

BM25's term frequency part: TF in a text of LENGTH terms, AVG terms the average.

Methods

PostingsBuilder.add

gizlang
function PostingsBuilder.add(self: mut PostingsBuilder, row: i64, words: Vec<string>, present: bool): void

Adds row row (rows arrive in increasing order) with its tokens; none for a null.

Effects: fail, alloc.

PostingsBuilder.finish

gizlang
function PostingsBuilder.finish(self: PostingsBuilder, rows: i64): TextIndex

The index of a built set of postings over rows rows, terms sorted.

Effects: fail, alloc.

PostingsBuilder.dictionary

gizlang
function PostingsBuilder.dictionary(self: PostingsBuilder): TextIndex

The dictionary of a sorted builder: its terms in order with their document counts, and no postings. A query is resolved over it (resolve), then reads PostingsBuilder.only.

Effects: fail, alloc.

PostingsBuilder.only

gizlang
function PostingsBuilder.only(self: PostingsBuilder, rows: i64, terms: Vec<string>): TextIndex

The index over ROWS rows of a builder's TERMS alone: a search of a delta page copies only the postings it reads.

Effects: fail, alloc.

TextIndex.missing

gizlang
function TextIndex.missing(self: TextIndex, at: Vec<i64>): Vec<i64>

The pages of AT that this index has not read.

Effects: fail, alloc.

TextIndex.df

gizlang
function TextIndex.df(self: TextIndex, t: i64): i64

How many rows hold term T.

Effects: fail.

TextIndex.term

gizlang
function TextIndex.term(self: TextIndex, t: i64): string

Term T's text.

Effects: fail, alloc.

TextIndex.lengthOf

gizlang
function TextIndex.lengthOf(self: TextIndex, row: i64): i64

The length of row ROW, in tokens.

Effects: fail.

TextIndex.find

gizlang
function TextIndex.find(self: TextIndex, word: string): i64

Term WORD's number, or -1 when the index does not hold it.

Effects: fail.

TextIndex.dictionaryPages

gizlang
function TextIndex.dictionaryPages(self: TextIndex, words: Vec<Word>, terms: Vec<string>): Vec<i64>

The pages a query of WORDS reads in this dictionary (resolve), and a lookup of each of TERMS (its phrases' and excluded words): the groups their spans reach. A cold index reads them before the query is resolved.

Effects: fail, alloc.

TextIndex.postingPages

gizlang
function TextIndex.postingPages(self: TextIndex, terms: Vec<string>, lengths: bool, placed: Vec<string>): Vec<i64>

The pages a search of TERMS reads here once their dictionary pages are held: their postings, the positions of the words PLACED (a phrase's or an excluded sequence's), and with LENGTHS the rows' lengths when the terms likely need every page of them (lengthPages). A count (matching) scores no row: it reads no length page.

Effects: fail, alloc.

TextIndex.lengthPages

gizlang
function TextIndex.lengthPages(self: TextIndex, terms: Vec<string>): Vec<i64>

The pages of the lengths of the rows that hold TERMS, once their postings' pages are held (postingPages): a rare term reads the pages of its own rows, where every page was read for each cold search; terms that likely touch every page (lengthsWhole) read them all with no posting decoded.

Effects: fail, alloc.

TextIndex.frequency

gizlang
function TextIndex.frequency(self: TextIndex, term: string): i64

How many documents hold TERM (its document frequency); 0 for a term it does not have.

Effects: fail.

Kept.every

gizlang
function Kept.every(self: Kept): bool

Whether it keeps every row.

Keeper.has

gizlang
function Keeper.has(self: mut Keeper, row: i64): bool

Whether it keeps ROW, at or past every row asked before. A scorer asks for few rows of a long list, so the cursor moves by doubling steps, then halves the last step.

Effects: fail.

TextIndex.statistics

gizlang
function TextIndex.statistics(self: TextIndex, q: Query, seen: Kept, nulls: bytes): Stats

Snapshot statistics count the documents of the rows SEEN keeps, before application filters; NULLS is a byte a row, 1 for a row with no value (empty: none). Every row is the index's own counts, with no row read; otherwise only the rows SEEN lists and each term's postings are read.

Effects: fail, alloc.

TextIndex.candidates

gizlang
function TextIndex.candidates(self: TextIndex, q: Query): Vec<i64>

The rows, ascending, that hold a term of Q: only they need the application's conditions or their values read.

Effects: fail, alloc.

PostingsBuilder.frequency

gizlang
function PostingsBuilder.frequency(self: PostingsBuilder, term: string): i64

How many documents built so far hold TERM; 0 for a term it does not have.

Effects: fail.

Hit.less

gizlang
function Hit.less(self: Hit, other: Hit): bool

A hit is less than another when it scores lower, or the same with a higher row: of equal scores the lower row wins.

TopK.threshold

gizlang
function TopK.threshold(self: TopK): f64

The score a hit must beat to enter: the worst kept score once K hits are kept, and at least the floor.

Effects: fail.

TopK.offer

gizlang
function TopK.offer(self: mut TopK, hit: Hit): void

Keeps HIT when it is among the K best so far; the worst kept hit then leaves.

Effects: fail, alloc.

TopK.sorted

gizlang
function TopK.sorted(self: TopK): Vec<Hit>

The hits, best first.

Effects: fail, alloc.

gizlang
function TextIndex.search(self: TextIndex, q: Query, stats: Stats, allowed: Kept, base: i64, heap: mut TopK): void

TextIndex.searchFields of this one column.

Effects: fail, read, write, alloc.

gizlang
function PostingsBuilder.search(self: PostingsBuilder, q: Query, stats: Stats, allowed: Kept, base: i64, heap: mut TopK): void

Exhaustive BM25 over built postings: the oracle of TextIndex.search (each word group at its best term).

Effects: fail, alloc.

Constants

BLOCK

gizlang
const BLOCK: i64 = 128

Postings per block. A block keeps its largest term frequency: a search skips a block that cannot reach top k.

PAGE

gizlang
const PAGE: i64 = 65536

Bytes of a page of the layout. No record crosses one, so a cold index reads whole records from the pages it holds.