# 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<string, i64>; terms: Vec<string>; docs: Vec<Vec<u32>>; tfs: Vec<Vec<u32>>; lengths: Vec<u32>; totalLength: i64; documents: i64; sorted: bool; order: 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>>`
- `lengths`: `Vec<u32>`
- `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<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; }
```

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`

### `Flat`

```gizlang
type Flat = { terms: Vec<string>; starts: Vec<i64>; docs: Vec<u32>; tfs: Vec<u32>; lengths: Vec<u32>; }
```

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<string>`
- `starts`: `Vec<i64>`
- `docs`: `Vec<u32>`
- `tfs`: `Vec<u32>`
- `lengths`: `Vec<u32>`

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

### `Searched`

```gizlang
type Searched = { fields: Vec<TextIndex>; lives: Vec<bytes>; visible: bytes; allowed: bytes; base: i64; rows: i64; texts: (row: i64) => Vec<string>; }
```

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<M93.TextIndex>`
- `lives`: `Vec<bytes>`
- `visible`: `bytes`
- `allowed`: `bytes`
- `base`: `i64`
- `rows`: `i64`
- `texts`: `(row: i64) => Vec<string>`

### `Narrowed`

```gizlang
type Narrowed = { rows: bytes; check: Vec<i64>; listed: bool; held: Vec<i64>; }
```

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<i64>`
- `listed`: `bool`
- `held`: `Vec<i64>`

### `Hit`

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

One scored row.

- `row`: `i64`
- `score`: `f64`

### `TopK`

```gizlang
type TopK = { k: i64; hits: Vec<Hit>; floor: f64; }
```

`floor`: a score below which no hit can matter, known before any is kept.

- `k`: `i64`
- `hits`: `Vec<M93.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.

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

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

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

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

### `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, console, io.

### `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, read, write, console, io.

### `union`

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

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

### `searchFields`

```gizlang
function searchFields(fields: Vec<TextIndex>, weights: Vec<f64>, q: Query, stats: Vec<Stats>, 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<string>, 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<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.

### `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<i64>): Vec<i64>
```

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

### `TextIndex.postingPages`

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

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

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

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.

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<string, i64>; terms: Vec<string>; docs: Vec<Vec<u32>>; tfs: Vec<Vec<u32>>; lengths: Vec<u32>; totalLength: i64; documents: i64; sorted: bool; order: 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>>
lengths: Vec<u32>
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<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; }

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

`Flat`

gizlang

type Flat = { terms: Vec<string>; starts: Vec<i64>; docs: Vec<u32>; tfs: Vec<u32>; lengths: Vec<u32>; }

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<string>
starts: Vec<i64>
docs: Vec<u32>
tfs: Vec<u32>
lengths: Vec<u32>

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

`Searched`

gizlang

type Searched = { fields: Vec<TextIndex>; lives: Vec<bytes>; visible: bytes; allowed: bytes; base: i64; rows: i64; texts: (row: i64) => Vec<string>; }

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<M93.TextIndex>
lives: Vec<bytes>
visible: bytes
allowed: bytes
base: i64
rows: i64
texts: (row: i64) => Vec<string>

`Narrowed`

gizlang

type Narrowed = { rows: bytes; check: Vec<i64>; listed: bool; held: Vec<i64>; }

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<i64>
listed: bool
held: Vec<i64>

`Hit`

gizlang

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

One scored row.

row: i64
score: f64

`TopK`

gizlang

type TopK = { k: i64; hits: Vec<Hit>; floor: f64; }

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

k: i64
hits: Vec<M93.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.

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

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

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

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

`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, console, io.

`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, read, write, console, io.

`union`

gizlang

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

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

`searchFields`

gizlang

function searchFields(fields: Vec<TextIndex>, weights: Vec<f64>, q: Query, stats: Vec<Stats>, 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<string>, 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<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.

`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<i64>): Vec<i64>

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

`TextIndex.postingPages`

gizlang

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

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<i64>

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<Hit>

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.