# gizdb: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); the terms' texts; the postings; the length of each row. 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 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 "gizdb:core/inverted"; ``` ## Types ### `PostingsBuilder` ```gizlang type PostingsBuilder = { lookup: Map; terms: Vec; docs: Vec>; tfs: Vec>; lengths: Vec; totalLength: i64; documents: i64; sorted: bool; order: Vec; } ``` Postings being built (the delta's, or a segment's during its build). - `lookup`: `_gizlang_sdk_collections.Map` - `terms`: `Vec` - `docs`: `Vec>` - `tfs`: `Vec>` - `lengths`: `Vec` - `totalLength`: `i64` - `documents`: `i64` - `sorted`: `bool` — Whether ORDER is kept: the term ids by their bytes, each new term put in place as it arrives. A delta page keeps it, so a search of the page reads its dictionary without a sort (PostingsBuilder.dictionary). - `order`: `Vec` ### `TextIndex` ```gizlang type TextIndex = { pages: Vec; terms: i64; rows: i64; totalLength: i64; documents: i64; table: i64; texts: i64; textsEnd: i64; postings: i64; postingsEnd: i64; norms: i64; width: i64; firsts: Vec; starts: Vec; size: i64; headBytes: i64; } ``` A finished, immutable index of one segment's text column: a view over its layout. - `pages`: `Vec` — 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` — The first term of each group and where its texts start: a lookup's search of the groups reads no page. - `starts`: `Vec` - `size`: `i64` — The layout's bytes, and its head's (the head and the groups' first terms: what a cold open reads). - `headBytes`: `i64` ### `Flat` ```gizlang type Flat = { terms: Vec; starts: Vec; docs: Vec; tfs: Vec; lengths: Vec; } ``` An index as versions 1 and 3 of the segment file hold it: the sorted terms, where each one's postings start in DOCS and TFS (one more than the terms), and each row's length. - `terms`: `Vec` - `starts`: `Vec` - `docs`: `Vec` - `tfs`: `Vec` - `lengths`: `Vec` ### `Stats` ```gizlang type Stats = { documents: i64; totalLength: i64; frequencies: Vec; } ``` 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` ### `Searched` ```gizlang type Searched = { fields: Vec; lives: Vec; visible: bytes; allowed: bytes; base: i64; rows: i64; texts: (row: i64) => Vec; } ``` One part a search reads: the index of each searched column (one row numbering) and the live rows of each (empty: every row; a live row has a value in the column), the rows it sees (empty: every row), the rows the caller's conditions keep (empty: every row it sees), the number of its first row in the search, its rows, and the texts of a row in the columns, read only for the check of a phrase or an excluded sequence. - `fields`: `Vec` - `lives`: `Vec` - `visible`: `bytes` - `allowed`: `bytes` - `base`: `i64` - `rows`: `i64` - `texts`: `(row: i64) => Vec` ### `Narrowed` ```gizlang type Narrowed = { rows: bytes; check: Vec; listed: bool; held: Vec; } ``` The rows that can meet a query's operators by their postings alone, and `check`, the rows, ascending, whose texts must still be read (Operators.admitsAny) because a phrase or an excluded sequence has more than one term. With a phrase `listed` is true and `held` lists the rows, ascending, that may match: no row past them is read. Else `rows` is empty (every row) or 1 for each row that may match. - `rows`: `bytes` - `check`: `Vec` - `listed`: `bool` - `held`: `Vec` ### `Hit` ```gizlang type Hit = { row: i64; score: f64; } ``` One scored row. - `row`: `i64` - `score`: `f64` ### `TopK` ```gizlang type TopK = { k: i64; hits: Vec; floor: f64; } ``` `floor`: a score below which no hit can matter, known before any is kept. - `k`: `i64` - `hits`: `Vec` - `floor`: `f64` ### `Query` ```gizlang type Query = { terms: Vec; weights: Vec; groups: Vec; 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` - `weights`: `Vec` - `groups`: `Vec` - `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. ### `postingsBuilder` ```gizlang function postingsBuilder(): PostingsBuilder ``` An empty builder. Effects: fail. ### `sortedBuilder` ```gizlang function sortedBuilder(): PostingsBuilder ``` An empty builder that keeps its terms in order (PostingsBuilder.order). Effects: fail. ### `emptyIndex` ```gizlang function emptyIndex(): TextIndex ``` An index of no documents. ### `indexOf` ```gizlang function indexOf(flat: Flat, totalLength: i64, documents: i64): TextIndex ``` The index of FLAT, from a file of version 1 or 3 (segment.giz). Effects: fail. ### `merged` ```gizlang function merged(indexes: Vec, maps: Vec>, 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. ### `indexColumn` ```gizlang function indexColumn(codes: Vec, 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. ### `headOf` ```gizlang function headOf(head: bytes): Option ``` 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. ### `layoutIndex` ```gizlang function layoutIndex(data: bytes): Option ``` The resident index of the layout DATA, undefined when DATA is not one (segment.giz reads it from a file). Effects: fail. ### `best` ```gizlang function best(q: Query, ops: Operators, weights: Vec, parts: Vec, 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, console, io. ### `matching` ```gizlang function matching(q: Query, ops: Operators, parts: Vec, 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, read, write, console, io. ### `union` ```gizlang function union(lists: Vec>): Vec ``` The rows of any of LISTS, ascending, each once. 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. ### `resolve` ```gizlang function resolve(words: Vec, indexes: Vec): 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. ### `searchFields` ```gizlang function searchFields(fields: Vec, weights: Vec, q: Query, stats: Vec, allowed: bytes, base: i64, heap: mut TopK): 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 empty (every row) or one byte per row, 1 when the row 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. ## Methods ### `PostingsBuilder.add` ```gizlang function PostingsBuilder.add(self: mut PostingsBuilder, row: i64, words: Vec, present: bool): void ``` Adds row `row` (rows arrive in increasing order) with its tokens; none for a null. Effects: fail. ### `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. ### `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. ### `PostingsBuilder.only` ```gizlang function PostingsBuilder.only(self: PostingsBuilder, rows: i64, terms: Vec): 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. ### `TextIndex.flat` ```gizlang function TextIndex.flat(self: TextIndex): Flat ``` The index as FLAT: what a file of version 1 holds (segment.giz encodeWithin). Effects: fail. ### `TextIndex.missing` ```gizlang function TextIndex.missing(self: TextIndex, at: Vec): Vec ``` The pages of AT that this index has not read. Effects: fail. ### `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. ### `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, terms: Vec): Vec ``` 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. ### `TextIndex.postingPages` ```gizlang function TextIndex.postingPages(self: TextIndex, terms: Vec, lengths: bool): Vec ``` The pages a search of TERMS reads here once their dictionary pages are held: their postings, and with LENGTHS the rows' lengths. A count (matching) scores no row: it reads no length page. Effects: fail. ### `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. ### `TextIndex.statistics` ```gizlang function TextIndex.statistics(self: TextIndex, q: Query, live: bytes): Stats ``` Snapshot statistics count live documents, before application filters. An empty LIVE is every document: the index's own counts, with no row read. Effects: fail. ### `TextIndex.candidates` ```gizlang function TextIndex.candidates(self: TextIndex, q: Query): Vec ``` The rows, ascending, that hold a term of Q: only they need the application's conditions or their values read. Effects: fail. ### `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. ### `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. ### `TopK.sorted` ```gizlang function TopK.sorted(self: TopK): Vec ``` The hits, best first. Effects: fail. ### `TextIndex.search` ```gizlang function TextIndex.search(self: TextIndex, q: Query, stats: Stats, allowed: bytes, base: i64, heap: mut TopK): void ``` TextIndex.searchFields of this one column. Effects: fail, read, write. ### `PostingsBuilder.search` ```gizlang function PostingsBuilder.search(self: PostingsBuilder, q: Query, stats: Stats, allowed: bytes, 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. ## Constants ### `BLOCK` ```gizlang const BLOCK = 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 = 65536 ``` Bytes of a page of the layout. No record crosses one, so a cold index reads whole records from the pages it holds.