GizStack
View .mdOpen in ChatGPTOpen in Claude

gizmodel/core/column

Columns: the one in-memory layout of data, shared by segments, the delta's scans and the executor's batches. Text is always a dictionary (codes into distinct strings), so equality, grouping and joins on text compare integers; a segment's dictionary is sorted, so its codes also order. Booleans are int columns of 0 and 1. Decimals are their coefficients as 64-bit two's complement words (values the low word, highs the words above it, highWidth a row: none while every coefficient fits an i64), at one scale (scale, the coefficients then order) or at each row's own (scale -1, scales one byte a row, or two little-endian bytes a row when a scale passes 255: scaleAt). nulls is empty when no value is null, else one byte per row, 1 for null.

gizlang
import * as Column from "gizmodel/core/column";

Types

Column

gizlang
type Column = | { kind: "int"; values: Vec<i64>; nulls: bytes; } | { kind: "float"; values: Vec<f64>; nulls: bytes; } | { kind: "text"; codes: Vec<u32>; dict: Texts; sorted: bool; nulls: bytes; } | { kind: "blob"; offsets: Vec<i64>; values: bytes; nulls: bytes; } | { kind: "vector"; dim: i64; values: Vec<f32>; nulls: bytes; } | { kind: "decimal"; values: Vec<i64>; highs: Vec<i64>; scale: i64; scales: bytes; nulls: bytes; } | { kind: "mixed"; values: Vec<Value>; }

A column of values of one kind, with a null bitmap (empty: no nulls).

  • int
  • float
  • text
  • blob
  • vector
  • decimal
  • mixed

Texts

gizlang
type Texts = { chars: bytes; at: Vec<i64>; }

A text column's dictionary: the bytes of its strings back to back (chars, valid UTF-8) and where each starts (at, one more than the strings: string k is chars[at[k] .. at[k + 1]]; at[0] is past 0 in a block read in place, Texts.owned). One buffer, not a string object a string: a cold URL column's 27M strings took 40 bytes each besides their text, so ClickBench's 100M rows did not stay in the cells at 10 GiB, and each query decoded them again, an allocation, a copy and a free a string (Data Studio's filter count).

  • chars: bytes
  • at: Vec<i64>

Builder

gizlang
type Builder = { ty: Type; ints: Vec<i64>; floats: Vec<f64>; codes: Vec<u32>; dict: Vec<string>; dictBytes: i64; lookup: Map<u64, i64>; clashes: Map<string, i64>; vectors: Vec<f32>; blobOffsets: Vec<i64>; blobValues: bytes; scales: bytes; highs: Vec<i64>; nulls: bytes; hasNull: bool; count: i64; }

Builds a column from values one at a time, interning text.

  • ty: M143.Type
  • ints: Vec<i64>
  • floats: Vec<f64>
  • codes: Vec<u32>
  • dict: Vec<string>
  • dictBytes: i64
  • lookup: _gizlang_sdk_collections.Map<u64, i64>
  • clashes: _gizlang_sdk_collections.Map<string, i64>
  • vectors: Vec<f32>
  • blobOffsets: Vec<i64>
  • blobValues: bytes
  • scales: bytes
  • highs: Vec<i64>
  • nulls: bytes
  • hasNull: bool
  • count: i64

WordMatch

gizlang
type WordMatch = { values: Vec<i64>; nulls: bytes; want: i64; never: bool; }

The rows of a column that equal a number, read as words: each row's integer word (VALUES, NULLS) is WANT. NEVER: no row holds the number (a fraction past the column's scale).

  • values: Vec<i64>
  • nulls: bytes
  • want: i64
  • never: bool

Functions

noTexts

gizlang
function noTexts(): Texts

A dictionary of no string.

Effects: fail, alloc.

textsOf

gizlang
function textsOf(strings: Vec<string>): Texts

The dictionary of STRINGS, in their order.

Effects: fail, alloc.

textsOfRefs

gizlang
function textsOfRefs(from: Vec<Texts>, refs: Vec<i64>): Texts

The dictionary of string K of FROM[D] for each reference D << 32 | K of REFS, in that order: the bytes copied once, and no string made (Texts.get makes one and checks it as UTF-8 again, a fifth of ClickBench Q40's groups).

Effects: fail, alloc.

emptyColumn

gizlang
function emptyColumn(ty: Type): Column

An empty column for a type.

Effects: fail, alloc.

builder

gizlang
function builder(ty: Type): Builder

An empty builder for a column of type TY.

Effects: fail, alloc.

sortedText

gizlang
function sortedText(codes: Vec<u32>, dict: Texts, nulls: bytes): Column

The same text column with its dictionary sorted and codes renumbered. A null row keeps code 0, which names no string when every row is null.

Effects: fail, alloc.

textOrder

gizlang
function textOrder(dict: Texts): Vec<i64>

Positions of dict in the order of the strings they name.

Effects: fail, alloc.

orderParallel

gizlang
function orderParallel<F>(n: i64, parts: i64, less: F): Vec<i64>

Positions 0 to N-1 in the order LESS gives, ties in either order unless LESS breaks them: PARTS runs each sorted on a core, then merged in pairs (a run before its neighbour on ties), each pair in PARTS / pairs pieces cut where the merged order puts them (coRank), so every level runs on every core. Merged whole, the last pair took one core for all the rows: 4M sort keys of ld.sh.

lowerBound

gizlang
function lowerBound(dict: Texts, text: string): i64

The first code whose text is not below text in a sorted dictionary.

Effects: fail.

gatherPieces

gizlang
function gatherPieces(pieces: Vec<Column>, pieceStarts: Vec<i64>, rows: Vec<u32>): Column

Rows ROWS (numbers over all the pieces laid end to end, PIECE_STARTS their first rows and one past the last) of text columns PIECES, as one column whose dictionary holds the strings of those rows once each. A hash join's build keeps the text it carries as its batches' columns: laid together they merged and sorted every string of the build (1.5M names, TPC-H Q18), where the few rows a probe takes need only theirs.

Effects: fail, alloc.

compactText

gizlang
function compactText(c: Column): Column

A text column whose dictionary holds only the strings its rows use, in the same order, when it holds more strings than rows. A column gathered from a segment keeps the segment's whole dictionary, so anything computed per string (LIKE, a comparison, join and group keys, a concat's merge) would cost each batch the whole segment: TPC-H's LIKE on o_comment ran on every comment for every morsel. Other columns are returned as they are.

Effects: fail, alloc.

concat

gizlang
function concat(parts: Vec<Column>, ty: Type): Column

Columns of one type joined end to end; text dictionaries merge into one sorted one.

Effects: fail, alloc.

sortedConcat

gizlang
function sortedConcat(parts: Vec<Column>, ty: Type): Column

PARTS joined end to end as concat joins them, a text column with a sorted dictionary. Parts of mostly distinct strings (as many as half their rows) are sorted at once, each string kept once: a map of every string (concat's merge), then a sort of the merged dictionary, put the map in a fifth of a load of unique texts and the sort in 3%. Parts of few strings, which repeat from part to part, are merged by the map, then sorted.

Effects: fail, alloc.

highWidth

gizlang
function highWidth(values: Vec<i64>, highs: Vec<i64>): i64

The high words a row of a decimal column has: 0 while every coefficient fits an i64.

Effects: fail.

scaleAt

gizlang
function scaleAt(scales: bytes, rows: i64, row: i64): i64

A row's scale in a decimal column at scale -1.

Effects: fail.

sameScales

gizlang
function sameScales(rows: i64, s: i64): bytes

The scales of rows rows all at scale s, for a decimal column at scale -1.

Effects: fail, alloc.

decimalAt

gizlang
function decimalAt(values: Vec<i64>, highs: Vec<i64>, row: i64, s: i64): Value

The value at row of a decimal column's coefficients at scale s: NaN and the infinities come back as floats, as coerce makes them.

Effects: fail, alloc.

Methods

Texts.size

gizlang
function Texts.size(self: Texts): i64

The strings of the dictionary.

Effects: fail.

Texts.bytes

gizlang
function Texts.bytes(self: Texts): i64

The bytes of this dictionary: its characters and a word a string.

Effects: fail.

Texts.owned

gizlang
function Texts.owned(self: Texts): Texts

The dictionary in a buffer of only its strings: one read in place (segment.giz blockColumn) holds its whole block, which a column the cells keep must not (ColdHome.keep).

Effects: fail, alloc.

Texts.get

gizlang
function Texts.get(self: Texts, k: i64): string

String K.

Effects: fail, alloc.

Texts.strings

gizlang
function Texts.strings(self: Texts): Vec<string>

Each string, a copy each: for a path that is not a scan's (a file format, a test).

Effects: fail, alloc.

Texts.width

gizlang
function Texts.width(self: Texts, k: i64): i64

The bytes of string K.

Effects: fail.

Texts.equals

gizlang
function Texts.equals(self: Texts, k: i64, text: string): bool

Whether string K is TEXT, without a copy.

Effects: fail.

Texts.compare

gizlang
function Texts.compare(self: Texts, k: i64, other: Texts, j: i64): i64

String K against string J of OTHER in byte (code point) order: below 0, 0 or above 0, without a copy.

Effects: fail.

Texts.compareText

gizlang
function Texts.compareText(self: Texts, k: i64, text: string): i64

String K against TEXT in byte order.

Effects: fail.

Texts.compareUtf8

gizlang
function Texts.compareUtf8(self: Texts, k: i64, t: bytes): i64

String K against the UTF-8 bytes T in byte order: a search converts its key once, not at each step.

Effects: fail.

Texts.pick

gizlang
function Texts.pick(self: Texts, keep: Vec<i64>): Texts

The dictionary of the strings KEEP names, in that order.

Effects: fail, alloc.

Column.count

gizlang
function Column.count(self: Column): i64

The number of values in the column.

Effects: fail.

Column.validLayout

gizlang
function Column.validLayout(self: Column, rows: i64): bool

Shared physical-shape validation before storage decoding or page publication.

Effects: fail, alloc.

Column.nullsOf

gizlang
function Column.nullsOf(self: Column): bytes

The null bitmap of the column (empty: no nulls).

Effects: fail, alloc.

Column.hasNull

gizlang
function Column.hasNull(self: Column): bool

Whether a row of the column is NULL.

Effects: fail, alloc.

Column.addWireSizes

gizlang
function Column.addWireSizes(self: Column, ty: Type, sizes: mut Vec<i64>): void

Adds the wire size of each row's value (valueWireSize) to SIZES, a row each, read from the column's storage for the usual kinds: a load sized its chunks by a Value made for every cell (Conn.bulkChunks).

Effects: fail, alloc.

Column.isNull

gizlang
function Column.isNull(self: Column, row: i64): bool

Whether the value at ROW is null.

Effects: fail, alloc.

Column.value

gizlang
function Column.value(self: Column, row: i64, ty: Type): Value

The value at row, typed by the column's schema type (booleans are int columns).

Effects: fail, alloc.

Builder.retainedBytes

gizlang
function Builder.retainedBytes(self: Builder): i64

Retained column content, not wire size or allocator capacity. Text dictionary and clashing keys share their string payload; count that payload once.

Effects: fail.

Builder.add

gizlang
function Builder.add(self: mut Builder, value: Value): void

Appends a value already of the column's type (coerce first): a mismatch is a fault, never a silent conversion.

Effects: fail, alloc.

Builder.addInt

gizlang
function Builder.addInt(self: mut Builder, v: i64): void

Builder.add of a value not NULL of an integer column, with no Value to match (a COPY's fields, Conn.bulkChunks).

Effects: fail, alloc.

Builder.addInts

gizlang
function Builder.addInts(self: mut Builder, values: Vec<i64>): void

Builder.addInt of each of VALUES: a column of them at once (Conn.bulkChunks).

Effects: fail, alloc.

Builder.addFloat

gizlang
function Builder.addFloat(self: mut Builder, v: f64): void

Builder.add of a double not NULL of a double column.

Effects: fail, alloc.

Builder.addCode

gizlang
function Builder.addCode(self: mut Builder, code: i64): void

Builder.add of the text not NULL of a text column whose code is CODE (Builder.textCodeAt).

Effects: fail, alloc.

Builder.textCode

gizlang
function Builder.textCode(self: mut Builder, text: string): i64

The dictionary code of TEXT, a new one when the dictionary has not got it.

Effects: fail, alloc.

Builder.textCodeAt

gizlang
function Builder.textCodeAt(self: mut Builder, d: bytes, from: i64, to: i64): i64

Builder.textCode of the text D[FROM, TO) spells: a string is made only for a text the dictionary has not got. A string a field and a lookup by it were a sixth of a COPY's CPU (ClickBench's hits).

Effects: fail, alloc.

Builder.finish

gizlang
function Builder.finish(self: Builder, sortDictionary: bool): Column

The built column; text gets a sorted dictionary when sortDictionary.

Effects: fail, alloc.

Column.gather

gizlang
function Column.gather(self: Column, rows: Vec<u32>): Column

The rows rows of a column, in that order.

Effects: fail, alloc.

Column.range

gizlang
function Column.range(self: Column, start: i64, end: i64): Column

Rows start..end of a column.

Effects: fail, alloc.

Column.footprint

gizlang
function Column.footprint(self: Column): i64

The bytes the column's values take in memory (an estimate: 8 per number, a dictionary's text once, 16 per mixed value), for the size of a table that has no files.

Effects: fail.

Column.wordMatch

gizlang
function Column.wordMatch(self: Column, v: Value): Option<WordMatch>

WordMatch of V, an integer or a decimal, for an int column or a decimal one at one scale whose coefficients each fit a word; none for other columns. A walk that checks a condition on each row read a Value of it (Column.value).

Effects: fail, alloc.

WordMatch.holds

gizlang
function WordMatch.holds(self: WordMatch, row: i64): bool

Whether row ROW holds the number of M.

Effects: fail.