# 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.

### `TextIndex.search`

```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.

### `PostingsBuilder.search`

```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.

