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.
import * as Column from "gizmodel/core/column";Types
Column
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).
intfloattextblobvectordecimalmixed
Texts
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:bytesat:Vec<i64>
Builder
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.Typeints:Vec<i64>floats:Vec<f64>codes:Vec<u32>dict:Vec<string>dictBytes:i64lookup:_gizlang_sdk_collections.Map<u64, i64>clashes:_gizlang_sdk_collections.Map<string, i64>vectors:Vec<f32>blobOffsets:Vec<i64>blobValues:bytesscales:byteshighs:Vec<i64>nulls:byteshasNull:boolcount:i64
WordMatch
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:byteswant:i64never:bool
Functions
noTexts
function noTexts(): TextsA dictionary of no string.
Effects: fail, alloc.
textsOf
function textsOf(strings: Vec<string>): TextsThe dictionary of STRINGS, in their order.
Effects: fail, alloc.
textsOfRefs
function textsOfRefs(from: Vec<Texts>, refs: Vec<i64>): TextsThe 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
function emptyColumn(ty: Type): ColumnAn empty column for a type.
Effects: fail, alloc.
builder
function builder(ty: Type): BuilderAn empty builder for a column of type TY.
Effects: fail, alloc.
sortedText
function sortedText(codes: Vec<u32>, dict: Texts, nulls: bytes): ColumnThe 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
function textOrder(dict: Texts): Vec<i64>Positions of dict in the order of the strings they name.
Effects: fail, alloc.
orderParallel
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
function lowerBound(dict: Texts, text: string): i64The first code whose text is not below text in a sorted dictionary.
Effects: fail.
gatherPieces
function gatherPieces(pieces: Vec<Column>, pieceStarts: Vec<i64>, rows: Vec<u32>): ColumnRows 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
function compactText(c: Column): ColumnA 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
function concat(parts: Vec<Column>, ty: Type): ColumnColumns of one type joined end to end; text dictionaries merge into one sorted one.
Effects: fail, alloc.
sortedConcat
function sortedConcat(parts: Vec<Column>, ty: Type): ColumnPARTS 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
function highWidth(values: Vec<i64>, highs: Vec<i64>): i64The high words a row of a decimal column has: 0 while every coefficient fits an i64.
Effects: fail.
scaleAt
function scaleAt(scales: bytes, rows: i64, row: i64): i64A row's scale in a decimal column at scale -1.
Effects: fail.
sameScales
function sameScales(rows: i64, s: i64): bytesThe scales of rows rows all at scale s, for a decimal column at scale -1.
Effects: fail, alloc.
decimalAt
function decimalAt(values: Vec<i64>, highs: Vec<i64>, row: i64, s: i64): ValueThe 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
function Texts.size(self: Texts): i64The strings of the dictionary.
Effects: fail.
Texts.bytes
function Texts.bytes(self: Texts): i64The bytes of this dictionary: its characters and a word a string.
Effects: fail.
Texts.owned
function Texts.owned(self: Texts): TextsThe 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
function Texts.get(self: Texts, k: i64): stringString K.
Effects: fail, alloc.
Texts.strings
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
function Texts.width(self: Texts, k: i64): i64The bytes of string K.
Effects: fail.
Texts.equals
function Texts.equals(self: Texts, k: i64, text: string): boolWhether string K is TEXT, without a copy.
Effects: fail.
Texts.compare
function Texts.compare(self: Texts, k: i64, other: Texts, j: i64): i64String K against string J of OTHER in byte (code point) order: below 0, 0 or above 0, without a copy.
Effects: fail.
Texts.compareText
function Texts.compareText(self: Texts, k: i64, text: string): i64String K against TEXT in byte order.
Effects: fail.
Texts.compareUtf8
function Texts.compareUtf8(self: Texts, k: i64, t: bytes): i64String K against the UTF-8 bytes T in byte order: a search converts its key once, not at each step.
Effects: fail.
Texts.pick
function Texts.pick(self: Texts, keep: Vec<i64>): TextsThe dictionary of the strings KEEP names, in that order.
Effects: fail, alloc.
Column.count
function Column.count(self: Column): i64The number of values in the column.
Effects: fail.
Column.validLayout
function Column.validLayout(self: Column, rows: i64): boolShared physical-shape validation before storage decoding or page publication.
Effects: fail, alloc.
Column.nullsOf
function Column.nullsOf(self: Column): bytesThe null bitmap of the column (empty: no nulls).
Effects: fail, alloc.
Column.hasNull
function Column.hasNull(self: Column): boolWhether a row of the column is NULL.
Effects: fail, alloc.
Column.addWireSizes
function Column.addWireSizes(self: Column, ty: Type, sizes: mut Vec<i64>): voidAdds 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
function Column.isNull(self: Column, row: i64): boolWhether the value at ROW is null.
Effects: fail, alloc.
Column.value
function Column.value(self: Column, row: i64, ty: Type): ValueThe value at row, typed by the column's schema type (booleans are int columns).
Effects: fail, alloc.
Builder.retainedBytes
function Builder.retainedBytes(self: Builder): i64Retained 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
function Builder.add(self: mut Builder, value: Value): voidAppends a value already of the column's type (coerce first): a mismatch is a fault,
never a silent conversion.
Effects: fail, alloc.
Builder.addInt
function Builder.addInt(self: mut Builder, v: i64): voidBuilder.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
function Builder.addInts(self: mut Builder, values: Vec<i64>): voidBuilder.addInt of each of VALUES: a column of them at once (Conn.bulkChunks).
Effects: fail, alloc.
Builder.addFloat
function Builder.addFloat(self: mut Builder, v: f64): voidBuilder.add of a double not NULL of a double column.
Effects: fail, alloc.
Builder.addCode
function Builder.addCode(self: mut Builder, code: i64): voidBuilder.add of the text not NULL of a text column whose code is CODE (Builder.textCodeAt).
Effects: fail, alloc.
Builder.textCode
function Builder.textCode(self: mut Builder, text: string): i64The dictionary code of TEXT, a new one when the dictionary has not got it.
Effects: fail, alloc.
Builder.textCodeAt
function Builder.textCodeAt(self: mut Builder, d: bytes, from: i64, to: i64): i64Builder.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
function Builder.finish(self: Builder, sortDictionary: bool): ColumnThe built column; text gets a sorted dictionary when sortDictionary.
Effects: fail, alloc.
Column.gather
function Column.gather(self: Column, rows: Vec<u32>): ColumnThe rows rows of a column, in that order.
Effects: fail, alloc.
Column.range
function Column.range(self: Column, start: i64, end: i64): ColumnRows start..end of a column.
Effects: fail, alloc.
Column.footprint
function Column.footprint(self: Column): i64The 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
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
function WordMatch.holds(self: WordMatch, row: i64): boolWhether row ROW holds the number of M.
Effects: fail.