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.
import * as Inverted from "gizmodel/core/inverted";Types
PostingsBuilder
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:i64documents:i64sorted: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
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:i64rows:i64totalLength:i64documents:i64table:i64— Where the term table, the texts, the postings and the rows' lengths are, and the lengths' bytes each.texts:i64textsEnd:i64postings:i64postingsEnd:i64norms:i64width:i64firsts: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:i64entry:i64— A term's entry's bytes, and where its positions end (0: the index has none).positionsEnd:i64
Stats
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:i64totalLength:i64frequencies:Vec<i64>
Kept
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
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:boolat:i64
Searched
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.Keptkept:M146.Keptbase:i64rows:i64
Hit
type Hit = { row: i64; score: f64; }One scored row.
row:i64score:f64
TopK
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
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:i64every:bool
Functions
textWeight
function textWeight(options: string): f64The 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
function postingsBuilder(): PostingsBuilderAn empty builder.
Effects: fail, alloc.
sortedBuilder
function sortedBuilder(): PostingsBuilderAn empty builder that keeps its terms in order (PostingsBuilder.order).
Effects: fail, alloc.
emptyIndex
function emptyIndex(): TextIndexAn index of no documents.
merged
function merged(indexes: Vec<TextIndex>, maps: Vec<Vec<i64>>, rows: i64, documents: i64): TextIndexThe 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
function indexColumn(codes: Vec<u32>, dict: Texts, nulls: bytes): TextIndexBuilds a segment's index from a text column's dictionary and codes, tokenizing each distinct text once.
Effects: fail, alloc.
headOf
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
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
function everyRow(): KeptEvery row.
onlyRows
function onlyRows(list: Vec<u32>): KeptThe rows of LIST, rising.
exceptRows
function exceptRows(list: Vec<u32>): KeptEvery row but those of LIST, rising.
keeper
function keeper(kept: Kept): KeeperA Keeper of KEPT at its first row.
best
function best(q: Query, ops: Operators, weights: Vec<f64>, parts: Vec<Searched>, keep: i64): TopKThe 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
function matching(q: Query, ops: Operators, parts: Vec<Searched>, keep: i64): i64How 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
function union(lists: Vec<Vec<i64>>): Vec<i64>The rows of any of LISTS, ascending, each once.
Effects: fail, alloc.
bm25Idf
function bm25Idf(documents: i64, df: i64): f64BM25's inverse document frequency of a term DF of DOCUMENTS hold (Lucene's, never negative).
Effects: fail.
topK
function topK(k: i64): TopKAn empty TopK that keeps the K best hits.
query
function query(text: string): QueryThe exact query of TEXT.
Effects: fail, read, write, alloc.
resolve
function resolve(words: Vec<Word>, indexes: Vec<TextIndex>): QueryThe 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
function searchFields(fields: Vec<TextIndex>, weights: Vec<f64>, q: Query, stats: Vec<Stats>, allowed: Kept, base: i64, heap: mut TopK, admit: mut Admission): voidThe 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
function saturate(tf: f64, length: f64, avg: f64): f64BM25's term frequency part: TF in a text of LENGTH terms, AVG terms the average.
Methods
PostingsBuilder.add
function PostingsBuilder.add(self: mut PostingsBuilder, row: i64, words: Vec<string>, present: bool): voidAdds row row (rows arrive in increasing order) with its tokens; none for a null.
Effects: fail, alloc.
PostingsBuilder.finish
function PostingsBuilder.finish(self: PostingsBuilder, rows: i64): TextIndexThe index of a built set of postings over rows rows, terms sorted.
Effects: fail, alloc.
PostingsBuilder.dictionary
function PostingsBuilder.dictionary(self: PostingsBuilder): TextIndexThe 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
function PostingsBuilder.only(self: PostingsBuilder, rows: i64, terms: Vec<string>): TextIndexThe 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
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
function TextIndex.df(self: TextIndex, t: i64): i64How many rows hold term T.
Effects: fail.
TextIndex.term
function TextIndex.term(self: TextIndex, t: i64): stringTerm T's text.
Effects: fail, alloc.
TextIndex.lengthOf
function TextIndex.lengthOf(self: TextIndex, row: i64): i64The length of row ROW, in tokens.
Effects: fail.
TextIndex.find
function TextIndex.find(self: TextIndex, word: string): i64Term WORD's number, or -1 when the index does not hold it.
Effects: fail.
TextIndex.dictionaryPages
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
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
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
function TextIndex.frequency(self: TextIndex, term: string): i64How many documents hold TERM (its document frequency); 0 for a term it does not have.
Effects: fail.
Kept.every
function Kept.every(self: Kept): boolWhether it keeps every row.
Keeper.has
function Keeper.has(self: mut Keeper, row: i64): boolWhether 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
function TextIndex.statistics(self: TextIndex, q: Query, seen: Kept, nulls: bytes): StatsSnapshot 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
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
function PostingsBuilder.frequency(self: PostingsBuilder, term: string): i64How many documents built so far hold TERM; 0 for a term it does not have.
Effects: fail.
Hit.less
function Hit.less(self: Hit, other: Hit): boolA 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
function TopK.threshold(self: TopK): f64The 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
function TopK.offer(self: mut TopK, hit: Hit): voidKeeps HIT when it is among the K best so far; the worst kept hit then leaves.
Effects: fail, alloc.
TopK.sorted
function TopK.sorted(self: TopK): Vec<Hit>The hits, best first.
Effects: fail, alloc.
TextIndex.search
function TextIndex.search(self: TextIndex, q: Query, stats: Stats, allowed: Kept, base: i64, heap: mut TopK): voidTextIndex.searchFields of this one column.
Effects: fail, read, write, alloc.
PostingsBuilder.search
function PostingsBuilder.search(self: PostingsBuilder, q: Query, stats: Stats, allowed: Kept, base: i64, heap: mut TopK): voidExhaustive BM25 over built postings: the oracle of TextIndex.search (each word group at its best term).
Effects: fail, alloc.
Constants
BLOCK
const BLOCK: i64 = 128Postings per block. A block keeps its largest term frequency: a search skips a block that cannot reach top k.
PAGE
const PAGE: i64 = 65536Bytes of a page of the layout. No record crosses one, so a cold index reads whole records from the pages it holds.