Documentation
¶
Overview ¶
Package kernel is ursus's compute layer.
The null contract, enforced by types ¶
Getting null propagation right is the hardest correctness problem in a dataframe engine, because getting it wrong is silent: the query returns a number, the number is just subtly incorrect. The design this package replaces had a single signature
func(dst, a, b []T, validity *bitmap.Bitmap)
which takes ONE validity bitmap and no input validities — making `null + 1 == null` literally inexpressible.
The fix here is structural rather than a matter of discipline. Kernels are split into classes by how they relate to nulls, and a kernel is only handed the validity bitmaps it is entitled to see:
Total never sees validity, never produces nulls.
The DISPATCHER computes `valid_out = valid_a AND valid_b`.
Partial may itself produce nulls (integer division by zero, a narrowing
cast, sqrt of a negative). Receives the combined input validity so it
can skip lanes it must not evaluate, and writes its own `ok` mask,
which the dispatcher ANDs with the input validity.
Missing nulls are DATA, not absence. null == null is true and the output is
never null.
Kleene three-valued boolean, where output validity is NOT `va AND vb`.
A Total kernel author cannot get propagation wrong because they are not given the bitmaps. That is the whole point.
Index ¶
- Constants
- func Accelerated() bool
- func ArgSort(n int, cmp Comparator) []int32
- func ArgSortColumns(cols []*data.Column, specs []SortSpec, n int) ([]int32, error)
- func ArgTopK(n, k int, cmp Comparator) []int32
- func Binary(op expr.BinaryOp, name string, out dtype.DataType, l, r *data.Column) (*data.Column, error)
- func Cast(name string, to dtype.DataType, strict bool, c *data.Column) (*data.Column, error)
- func CompilePattern(fn expr.CallFn, args []any) (*regexp.Regexp, error)
- func Concat(schema *dtype.Schema, batches []*data.Batch) (*data.Batch, error)
- func ConcatColumns(name string, parts []*data.Column) (*data.Column, error)
- func DtCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any) (*data.Column, error)
- func EncodeOne(c *data.Column) ([]byte, error)
- func FilterBatch(b *data.Batch, mask *data.Column) (*data.Batch, error)
- func HashKey(b []byte) uint64
- func InSet(name string, c *data.Column, set map[string]struct{}) (*data.Column, error)
- func ListCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any, ...) (*data.Column, error)
- func MathCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any) (*data.Column, error)
- func Mix64(x uint64) uint64
- func NullColumn(name string, dt dtype.DataType, n int) (*data.Column, error)
- func OrderKeyF32(f float32) uint32
- func OrderKeyF64(f float64) uint64
- func Select(name string, mask, a, b *data.Column) (*data.Column, error)
- func SelectionFromMask(mask *data.Column) ([]int32, error)
- func StrCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any, ...) (*data.Column, error)
- func StructCall(fn expr.CallFn, name string, c *data.Column, args []any) (*data.Column, error)
- func Take(c *data.Column, sel []int32) (*data.Column, error)
- func Unary(op expr.UnaryOp, name string, out dtype.DataType, c *data.Column) (*data.Column, error)
- func VectorBits() int
- func WinCall(fn expr.WinFnOp, params expr.WinParams, name string, out dtype.DataType, ...) (*data.Column, error)
- type Accumulator
- type ColumnUDF
- type Comparator
- type CrossComparator
- type GroupKeyEncoder
- type Integer
- type KeyTable
- type KleeneBinary
- type MergeCursor
- type Merger
- type MissingCompare
- type Numeric
- type PartialBinary
- type PartialBinaryScalar
- type RunSet
- type Segments
- type SortSpec
- type TotalBinary
- type TotalBinaryScalar
- type TotalCompare
- type TotalCompareScalar
- type TotalUnary
Constants ¶
const NullIndex = int32(-1)
NullIndex marks a gather slot that should produce a null.
Variables ¶
This section is empty.
Functions ¶
func Accelerated ¶
func Accelerated() bool
Accelerated reports whether hardware SIMD kernels are in use.
func ArgSort ¶
func ArgSort(n int, cmp Comparator) []int32
ArgSort returns the permutation that orders n rows under cmp.
The sort is STABLE, and the stability is load-bearing rather than a nicety:
- It makes a multi-pass sort (`Sort(a)` then `Sort(b)`) mean what people expect — ties on b keep their a order.
- It makes a query's output reproducible when keys contain ties, which is what `dataframe-features.md`'s determinism commitment requires.
- It is what lets ArgTopK be checked against ArgSort at all: without a defined tie order there is no single right answer to compare against.
It uses slices.SortStableFunc rather than sort.SliceStable, which is a typed sort over []int32 rather than a reflective one: sort.SliceStable swaps through reflectlite.Swapper, which the profile put at 5.4% of the engine's hot-path CPU on its own. Prefer ArgSortColumns where the key COLUMNS are available — it avoids comparisons entirely.
func ArgSortColumns ¶
ArgSortColumns is ArgSort given the key COLUMNS rather than a comparator, and is what every sort in the engine should use when it has them.
Having the columns is what lets the sort key be computed ONCE PER ROW instead of once per comparison, which turns an O(n log n) problem with a four-closure inner loop into a handful of linear passes. See radix.go for the argument; the short version is that OrderKeyF64 was already producing exactly the key a radix sort wants, O(n log n) times.
Falls back to the comparator for key types with no order-preserving fixed-width encoding — String, Int128 and so Decimal — and for any mixed set containing one. The result is identical either way, including tie order, which is what TestRadixMatchesComparatorSort exists to hold true.
func ArgTopK ¶
func ArgTopK(n, k int, cmp Comparator) []int32
ArgTopK returns the indices of the k smallest rows under cmp, in order.
The contract ¶
ArgTopK(n, k, cmp) == ArgSort(n, cmp)[:min(k, n)]
EXACTLY — the same indices, in the same order, including for ties. That equivalence is the whole point: it is what makes limit-pushdown (`Sort(...).Head(k)` → top-k) a legal rewrite rather than a silent change of which rows come back.
Why ties need explicit handling ¶
A bounded heap is not naturally stable, and getting this wrong is invisible on data without ties. Two independent bugs had to be fixed here:
- EVICTION. Among equal elements the heap root is whichever element the heap happened to sift there, not the one that should lose. With values [5,5,1,5] and k=2 the naive version evicts index 0 and returns {2,1}, where ArgSort[:2] is {2,0} — a different row entirely.
- THE FINAL SORT. Sorting the surviving indices with a stable sort is meaningless, because they are in heap order rather than original order; "stable" preserves an arbitrary permutation. [7,7,7,3] with k=3 returned {3,1,2} against ArgSort[:3] = {3,0,1}.
Both are fixed by making the comparator TOTAL: ties break by original index, in the heap (so the largest index sits at the root and is evicted first) and in the final sort (so the output order is the original order among equals).
Cost is O(n log k) time and O(k) memory rather than O(n log n) and O(n). For `Sort(...).Head(10)` over ten million rows that is the difference between a sort and a scan.
func Binary ¶
func Binary(op expr.BinaryOp, name string, out dtype.DataType, l, r *data.Column) (*data.Column, error)
Binary applies op to two columns, producing a new column named name with type out (as already determined by expression type resolution).
This function owns null propagation ¶
Kernels compute values; the dispatcher decides which of those values are real. Centralising it here means the rule is written once and every kernel inherits it:
comparison / arithmetic → valid_out = valid_a AND valid_b missing comparison → always valid Kleene boolean → computed by the kernel, because it is NOT va AND vb partial (integer div) → (va AND vb) AND the kernel's own ok mask
Both operands must already be cast to the binding's operand type. Doing the casting in the evaluator rather than here keeps the dispatcher a pure function of physical types.
func Cast ¶
Cast converts a column to another type.
Non-strict casts turn an unrepresentable value into a null, which is why the type checker marks every non-strict cast nullable regardless of its input. Strict casts fail the query and name the offending row.
A Time target is normalised, and that is a fix rather than tidiness ¶
Cast is one of the two producers of a Time value, and it relabels whenever the two sides carry the same tick length — so `Datetime(s) -> Time(s)` reinterpreted SECONDS SINCE THE EPOCH as a time of day. It printed correctly by accident, because ToTime rebuilds the real instant and the "15:04:05" layout throws the date away, while the stored tick stayed a full epoch offset. Sorting such a column therefore ordered by DATE, and equality across two days never matched.
Normalising into [0, 24h) does not merely restore an invariant here; it makes `Cast(Datetime -> Time)` mean what the user asked for. The wrapping is done once, after every arm, rather than in each of the four that can produce a Time.
Only from an instant ¶
Folding is the time of day of an INSTANT. A bare tick count, or a Duration, has no day to take the time of, and folding it made 90000 seconds 01:00 (audit.md S18). From anything but a Datetime, a value outside the day is refused under a strict cast and null under a lossy one, as Polars does.
func CompilePattern ¶
CompilePattern builds the regex for a call, or returns nil for literal matching.
Only the functions that accept a pattern get one, and only when the call asked for regex. Extract is the exception: it is regex-only, because "extract the first literal occurrence" is just Find.
func ConcatColumns ¶ added in v0.3.0
ConcatColumns stacks columns of the same type end to end.
Concat's per-COLUMN half, exported because unpivot needs exactly this and nothing else: it has k columns to lay end to end and no batches to build them from. The name is the caller's, because the parts' names are the ones being melted away.
func DtCall ¶
func DtCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any) (*data.Column, error)
DtCall applies a temporal function to a column.
func EncodeOne ¶
EncodeOne returns the set key for the single row of a length-1 column.
It exists so the probe set and the probed column are encoded by the SAME function. Building the set with any other encoding — even one that looks equivalent — would reintroduce exactly the NaN and -0.0 disagreements the shared encoder exists to prevent.
func FilterBatch ¶
FilterBatch applies a Boolean mask to every column of a batch.
func HashKey ¶
HashKey hashes an encoded group key.
It must be the ENCODED key, never the raw column values ¶
NewGroupKeyEncoder is the single authority on grouping equality: floats go through OrderKey first, so NaN groups with NaN and -0.0 with +0.0. A hash over raw bits would send the two NaNs of one column to different radix partitions, they would be aggregated by separate sinks, and the output would carry TWO rows where one belongs — each with a plausible sub-total and no error anywhere. nuniqueAcc reuses this encoder for exactly the same reason.
Seedless and deterministic, deliberately ¶
hash/maphash is faster and its seed can only come from MakeSeed(), so the group ORDER of a spilled aggregation would differ between processes — a flake that reproduces only under a memory limit and only sometimes. FNV-1a costs a multiply-xor per byte on a path that is already doing file I/O per batch.
The splitmix64 finaliser is not decoration: FNV avalanches poorly in its low bits, and the low bits are exactly what a radix partitioner reads.
func InSet ¶
InSet tests each row for membership in a precomputed set of encoded values.
The set uses GROUPING equality, not IEEE equality ¶
Keys are produced by the same GroupKeyEncoder that n_unique, distinct and the join all use, which canonicalises floats through OrderKey: NaN equals NaN and -0.0 equals +0.0. An is_in built on `==` would disagree with Distinct and GroupBy about the same values, which is the trap nuniqueAcc's doc records for n_unique.
A null is never a member ¶
Output validity is the input's, so `null.IsIn(...)` is NULL rather than false — the rule every non-total unary follows, and the one that keeps null distinct from "absent from the set". The set itself cannot contain a null, because the public signature takes Go values and Go has no null.
func ListCall ¶ added in v0.3.0
func ListCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any, needle []byte) (*data.Column, error)
ListCall applies a list function to a column.
The signature mirrors StrCall, and out comes from expr.ResolveCall so the kernel and the plan cannot disagree about the result type.
func MathCall ¶
func MathCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any) (*data.Column, error)
MathCall evaluates the parameterised maths family.
One member today, Round. The family exists because a parameter belongs in a Call's argument list rather than in a field on expr.Unary — see the note on FnMathRound for the three hand-written Unary rebuilds that would have dropped it.
func Mix64 ¶
Mix64 is splitmix64's finaliser: a bijection that spreads every input bit over the whole output.
func NullColumn ¶
NullColumn builds an all-null column of dt with n rows and a REAL payload buffer.
Why this is not data.NewNull ¶
data.NewNull carries no payload at all — "which makes a typed null literal free". That is right for a value nobody reads, and wrong for anything a kernel then gathers from or concatenates. Take and Concat both route fixed-width columns through data.Values, which refuses a column with no buffer, and the string path builds a zero-length StringAccessor whose Get PANICS on any index.
Both are reachable from ordinary queries. Min over a group whose values are all null produced an unread single-row null that assembleRows then concatenated — so `GroupBy(g).Agg(Col("v").Min())` failed with "column has no fixed-width payload" whenever one group was entirely null. An outer join has the same shape: the unmatched side is gathered from padding on every row.
The rule this establishes: data.NewNull is for a column that is the ANSWER; NullColumn is for a column that is an OPERAND.
func OrderKeyF64 ¶
OrderKeyF64 maps a float64 onto a uint64 whose UNSIGNED ordering is ursus's documented total order:
-Inf < … < -0.0 == +0.0 < … < +Inf < NaN
with all NaNs equal to each other.
Why this deliberately is not IEEE ¶
IEEE says NaN compares false against everything, including itself. That is correct for `Expr.Lt` — asking whether a missing measurement is less than five should not invent an answer — but it is fatal for sorting and grouping:
- A comparison-based sort needs a TOTAL order. With IEEE semantics NaN is unordered, sort becomes non-deterministic, and some algorithms fail to terminate.
- Hash grouping needs an equivalence relation. With IEEE, NaN != NaN, so every NaN would form its own group — you could not count them.
So ursus uses IEEE for comparison expressions and this total order for sort, top-k and group-by. The two must never be confused; that is why this lives in its own file with its own name rather than as a flag on the comparison kernels.
The bit trick: for a positive float, flipping the sign bit gives a uint64 that orders correctly. For a negative float, inverting every bit does. Both are exact and branch-light.
func Select ¶
Select is the masked merge behind When/Then/Otherwise: out[i] is a[i] where the mask is true and b[i] where it is false.
A null mask takes NEITHER branch ¶
This is the same rule SelectionFromMask applies for Filter — "a row survives iff its predicate is VALID AND TRUE" — and it is the one decision here that a reader might expect to go the other way. `When(x.Gt(5)).Then(a).Otherwise(b)` on a row where x is null produces NULL, not b. Treating a null predicate as false would make Otherwise silently absorb missing data, which is exactly the conflation of "absent" with "false" that Filter(p) and Filter(Not(p)) not partitioning exists to prevent.
The mask's payload bit is not trustworthy on its own ¶
Arrow does not guarantee the value bit of a null slot is zero, so every read of the mask is ANDed with its validity before use. dispatch.go's kleene kernel canonicalises for the same reason and says so.
Broadcasting is this kernel's job ¶
Eval returns whatever length a sub-expression produced, and litColumn produces length-1 columns; the operator-boundary broadcast in evalColumn runs afterwards, too late to help. So `When(c).Then(Lit(1)).Otherwise(Lit(0))` arrives here as a length-n mask and two length-1 branches, and this kernel repeats them — the same accommodation kernel.Binary makes via broadcastLen.
a and b must already share a type: the evaluator casts them to the promoted type first, obeying the resolved binding rather than re-deriving it.
func SelectionFromMask ¶
SelectionFromMask turns a Boolean column into the list of row indices to keep.
Filter's null semantics, in one line of code ¶
A row survives iff its predicate is VALID AND TRUE. A null predicate drops the row, matching SQL's WHERE. This is worth being explicit about because the alternative — treating null as true — is a plausible-looking choice that silently changes results, and because it means Filter(p) and Filter(Not(p)) do NOT partition the input: a row where p is null is dropped by both.
func StrCall ¶
func StrCall(fn expr.CallFn, name string, out dtype.DataType, c *data.Column, args []any, re *regexp.Regexp) (*data.Column, error)
StrCall applies a string function to a column.
re is the compiled pattern for the regex forms, or nil for literal matching. It is compiled ONCE per expression node by the evaluator, never per batch and never per row — RE2 compilation is orders of magnitude more expensive than the match.
func StructCall ¶ added in v0.3.0
StructCall applies a struct function to a column.
The output type is not passed in, unlike ListCall's: a field's type comes from the field itself, and expr.ResolveCall has already refused a name the struct does not have. Taking it as an argument would be a second copy of that decision.
func Take ¶
Take gathers rows by index, producing a compacted column.
This kernel is named in none of the design documents and is needed by every operator that changes row count — filter, join, sort, top-k, explode. It is the single most reused primitive in the engine.
A NullIndex entry produces a null, which is what outer joins and out-of-bounds gathers need.
func VectorBits ¶
func VectorBits() int
VectorBits returns the active SIMD vector width in bits, or 0 when scalar.
func WinCall ¶
func WinCall(fn expr.WinFnOp, params expr.WinParams, name string, out dtype.DataType, col *data.Column, fill *data.Column, seg Segments) (*data.Column, error)
WinCall applies an ordered window function.
col is the function's input in ORIGINAL row order — Perm indexes into it. fill is Shift's replacement for vacated rows, or nil for null.
Types ¶
type Accumulator ¶
type Accumulator interface {
// Reserve ensures per-group state exists for n groups.
Reserve(n int)
// AddBatch accumulates col into the groups named by groups, where groups[i] is
// the group ordinal of row i.
AddBatch(groups []int32, col *data.Column) error
// Merge folds another accumulator's state into this one. Both must be for the
// same aggregate.
//
// remap carries the group NUMBERING: remap[i] is this accumulator's group id
// for other's group i, and nil means the two already agree. Two sinks that
// consumed different portions of the input assign ids independently — the
// first key each one sees becomes its group 0 — so without a remap the
// positional fold below adds one group's total to another, silently and with
// no length mismatch to catch it. That is the piece parallel aggregation
// needs; see physical.hashAggSink.Merge for where the mapping is built.
Merge(other Accumulator, remap []int32) error
// Finish emits the result, one row per group.
Finish(name string, nGroups int) (*data.Column, error)
// NBytes reports the per-group state currently held, so a group-by can be
// measured against a memory budget. Implementations must be O(groups): it is
// called once per batch.
NBytes() int64
}
Accumulator computes one aggregate across all groups.
Vectorized, not per-group ¶
There is ONE Accumulator per aggregate expression, holding per-group state in a slice indexed by group ordinal — not one object per group per aggregate. With a million groups the latter would mean a million interface values and a virtual call per row; here the call is per BATCH per aggregate.
Merge is not decoration ¶
Merge combines the state of two accumulators that saw disjoint subsets of the same input. It is what makes PARALLEL aggregation possible in v0.3: N workers accumulate independently, then merge. It is implemented and TESTED now, even though nothing calls it concurrently yet, because a Merge written later against forgotten invariants is a Merge that is wrong.
Spilling aggregation does NOT use it, and that is a design choice rather than an omission. Step 12 partitions by key rather than evicting groups, so one sink sees every row of a group and Merge is never reached — which is what makes First, Last, ArgMin and ArgMax correct on a replayed partition with no position shift. A design that DID merge partial groups would need each accumulator's `other` to have seen a strictly later portion of the input, a precondition eviction cannot supply; argExtremumAcc.Merge carries an explicit index shift for exactly that reason. See hashAggSink for the invariant.
func NewAccumulator ¶
func NewAccumulator(op expr.AggOp, in dtype.DataType, bind expr.AggBinding, params expr.AggParams) (Accumulator, error)
NewAccumulator builds the accumulator for an aggregate over a given input type.
The binding comes from expr.ResolveAggBinding and is OBEYED, not re-derived — the same discipline the evaluator follows for binary operators, and for the same reason: a second copy of the type rules drifts, and the drift shows up as a column whose type does not match the schema the planner promised. params carries the aggregate's configuration — ddof, the quantile — and is the zero value for every aggregate that takes none.
type ColumnUDF ¶ added in v0.3.0
ColumnUDF is a user-supplied kernel with its type parameters erased.
It lives here rather than in internal/expr for one reason: internal/expr sits at the same import level as internal/data and so cannot name *data.Column at all. expr.UDFImpl is the marker that lets the node hold one of these without seeing it; this package (level 30) may import data, so it can declare the concrete type. internal/physical asserts it back out to call it.
The signature takes the output NAME rather than deriving it, because the column a UDF produces is named after the column it consumed — leftmost-column-wins — and expr.UDF.Field has already committed to that name in the schema.
A ColumnUDF must be safe to call from several goroutines at once. That is not a preference: parallelise hands any Select or Filter to runtime.NumCPU() workers by structure, and there is no operator-level flag to decline. The public MapElements and MapBatches say so in their own docs, where a user will see it.
type Comparator ¶
Comparator orders two row indices. Returns <0, 0 or >0.
func NewComparator ¶
func NewComparator(cols []*data.Column, specs []SortSpec) (Comparator, error)
NewComparator builds a lexicographic row comparator over key columns.
Per-column accessors are resolved ONCE here rather than per comparison. A sort performs O(n log n) comparisons, so a type switch inside the comparator would dominate the runtime.
type CrossComparator ¶
CrossComparator orders row ia of run ra against row ib of run rb.
func NewCrossComparator ¶
func NewCrossComparator(runs [][]*data.Column, specs []SortSpec) (CrossComparator, error)
NewCrossComparator builds a comparator over fixed run column sets.
This is the shape a test can drive: comparing two rows through it must agree with NewComparator over the concatenation of the runs, which is what pins the direction and null-placement rules to the ones the in-memory sort already uses.
type GroupKeyEncoder ¶
type GroupKeyEncoder struct {
// contains filtered or unexported fields
}
GroupKeyEncoder turns a row's key columns into a byte string that can be used as a hash-map key.
The encoding, and why the tag byte is not optional ¶
Each key field is written as:
null → 0x00 (tag only, no payload) present → 0x01 || payload
Nulls form their OWN GROUP — the SQL and Polars rule — so a null must encode to something, and that something must not collide with any real value. The tag byte makes collision structurally impossible rather than merely unlikely: a present value's encoding always begins 0x01, so it can never equal a null's 0x00 no matter what its payload contains.
Payloads are fixed-width big-endian for numerics and length-prefixed for strings. Big-endian and length-prefixed are both chosen so that the byte ordering of the encoding matches the value ordering — which this step does not use, but which makes the same encoder reusable for sort-merge joins and for spilling to disk without re-deriving it.
Floats go through OrderKey first, so NaN groups with NaN and -0.0 groups with +0.0. Without that, counting NaNs would be impossible, because IEEE says no NaN equals itself.
func NewGroupKeyEncoder ¶
func NewGroupKeyEncoder(op string, cols []*data.Column) (*GroupKeyEncoder, error)
NewGroupKeyEncoder resolves a per-column writer once, so the per-row cost is a slice of closure calls rather than a type switch per field per row.
op names the user-facing operation in any error — "group_by", "unique", "join". It is a parameter rather than a constant because the encoder has three callers and a join on a List key reporting "cannot group by a List column" would point the user at an operation their query does not contain.
func (*GroupKeyEncoder) Encode ¶
func (e *GroupKeyEncoder) Encode(row int) []byte
Encode returns the key for a row.
The result aliases an internal buffer and is only valid until the next call. Callers that keep the key — the hash table does, on insert — must copy it. This is deliberate: a map lookup `m[string(key)]` does not allocate in Go, so the common path (an existing group) is allocation-free and only a genuinely new group pays for a copy.
type Integer ¶
Integer is the subset of Numeric on which `%` is defined and on which division by zero PANICS rather than producing an infinity. Kernels that divide must be constrained to it, not to Numeric — otherwise instantiating them for float32 fails to compile, which is Go usefully refusing to let the two very different division semantics share one implementation.
type KeyTable ¶ added in v0.3.0
type KeyTable struct {
// contains filtered or unexported fields
}
KeyTable maps encoded group keys to dense int32 ids, in first-seen order.
It replaces the `map[string]int32` that six operators used to identify groups: the hash aggregate and its spilling twin, both join build sinks, and the window sink's partitioning. A profile of a high-cardinality string group-by put 74% of hashAggSink.Consume inside that map — 61% in mapaccess2_faststr and 13% in mapassign_faststr — against 6% encoding the key and 5% doing the actual arithmetic.
Why a map was the wrong shape, specifically ¶
Every call site wanted get-or-insert:
id, seen := ids[string(k)]
if !seen { id = int32(len(ids)); ids[string(k)] = id }
Go has no fused form, so a new key is hashed and probed TWICE. On a high-cardinality group-by, where misses are the common case, that is half the work thrown away. A probe that missed here already knows the slot to fill.
Two more differences, in the order they mattered:
- The hash is stored per id, so a probe rejects on eight bytes before it touches the key. That is aimed at the memeqbody time the map spent comparing keys in full.
- Keys live in one arena rather than an individually allocated string each, so comparison reads contiguous memory and insertion does not allocate.
Ids are dense and first-seen ordered, and that is load-bearing ¶
id N is the Nth DISTINCT key handed to GetOrInsert. Accumulators index their storage by it, hashAggSink.firstSeen records an input ordinal per id, and both Merge implementations build a remap over it. Assigning ids by slot index instead would be silently wrong everywhere at once, which is what the differential test against map[string]int32 exists to catch.
KeyAt reads back by id, so the table's internal order is never observable.
Not safe for concurrent use, except Get ¶
GetOrInsert mutates. Get touches nothing, which is what lets joinTable keep its promise that nothing changes after the build freezes — the property that would let several probe workers share one table with no lock.
func NewKeyTable ¶ added in v0.3.0
func NewKeyTable() *KeyTable
func (*KeyTable) Get ¶ added in v0.3.0
Get looks up a key without inserting it. It mutates nothing, so a frozen table may be read from several goroutines at once.
func (*KeyTable) GetOrInsert ¶ added in v0.3.0
GetOrInsert returns the id for key, inserting it if this is its first sighting. inserted reports which happened.
key is only read, never retained: the bytes are copied into the arena on insert. That matters because every caller passes GroupKeyEncoder.Encode's return value, which aliases a buffer the encoder reuses on the next row.
func (*KeyTable) KeyAt ¶ added in v0.3.0
KeyAt returns the key bytes for an id. The result aliases the arena and is invalidated by the next insert, so a caller that keeps it must copy.
This is what lets both Merge implementations walk their keys in id order. They used to invert the map into a []string first, purely because a Go map cannot be indexed by value; here it is slice arithmetic.
func (*KeyTable) Len ¶ added in v0.3.0
Len is the number of distinct keys, which is also the next id GetOrInsert will hand out.
func (*KeyTable) NBytes ¶ added in v0.3.0
NBytes is what this table holds, EXACTLY.
The map it replaced could not answer this — join.go carried a 48-bytes-per-key estimate covering a string header, a value, a tophash byte and Go's load-factor slack, and said so. A memory limit is enforced against this number, so an estimate spills too early or too late; four slices can simply be measured.
func (*KeyTable) Reserve ¶ added in v0.3.0
grow doubles the slot ring and re-places every id from the stored hashes. No key is read and no key is moved — the arena and offs are untouched, so every id keeps its meaning. Reserve sizes the table for at least n keys, if it is not already that big.
Growth is doubling from 64 slots and each doubling REHASHES every entry, so a table that ends up with millions of keys pays about seventeen full rehashes to get there — random probes, every time. A caller that knows its rough scale up front can skip almost all of it.
It is a hint: the table still grows on demand, and passing a number that turns out too small costs nothing but the doublings it did not save.
type KleeneBinary ¶
KleeneBinary implements three-valued AND/OR/XOR.
Output validity is NOT `va AND vb`:
false AND null == false (valid!) true OR null == true (valid!)
so the kernel must compute both bitmaps itself. Using `va AND vb` here is a silent filter bug: rows that should survive get dropped.
type MergeCursor ¶
MergeCursor is one position in one run.
type Merger ¶
type Merger struct {
// contains filtered or unexported fields
}
Merger emits (run, row) pairs in sorted order across several sorted runs.
It never reads a run itself ¶
The caller pushes a run's current head, and when that head is popped the caller decides what comes next — the next row of the resident batch, the first row of a batch loaded from disk, or nothing because the run is finished. Keeping the disk out of the kernel layer is what lets the merge be tested against ArgSort with no files involved at all.
Stability ¶
ArgSort is stable and the sort's doc calls that load-bearing rather than a nicety. A k-way merge is stable only if a tie between two runs takes from the run holding the EARLIER input rows — so ties break on the run index, ascending, and runs must be created in input order. Within a run, rows are already in stable order and the caller always advances a run's head by one, so intra-run order is preserved for free.
This is the same hazard ArgTopK needed two separate fixes for, and it is invisible on data without ties, which is why the merge is tested against inputs that are mostly ties.
func (*Merger) Pop ¶
func (m *Merger) Pop() (MergeCursor, bool)
Pop removes and returns the smallest cursor, or ok=false when none is left.
type MissingCompare ¶
MissingCompare implements eq_missing / ne_missing, where nulls compare equal to each other. It needs the input validities because nulls are the data, and its output is never null.
type Numeric ¶
type Numeric interface {
~int8 | ~int16 | ~int32 | ~int64 |
~uint8 | ~uint16 | ~uint32 | ~uint64 |
~float32 | ~float64
}
Numeric is the set of physical storage types the kernels operate on.
Logical types reach these through their physical representation: a Datetime column is processed as int64, a Date column as int32. One integer kernel therefore serves every type that stores integers.
type PartialBinary ¶
PartialBinary computes dst = a OP b, writing its own validity into ok.
`in` is the combined input validity, supplied so the kernel can SKIP lanes it must not evaluate. That is not an optimization: integer division panics in Go, so a kernel that blindly computed a[i]/b[i] over a null lane containing a zero would crash the process.
type PartialBinaryScalar ¶
PartialBinaryScalar is PartialBinary with a scalar right operand.
type RunSet ¶
type RunSet struct {
// contains filtered or unexported fields
}
RunSet holds the key columns each run of a merge currently has resident.
A run's columns can be REPLACED, which is the whole reason this is a type and not a closure: a merge holds one batch per run, and when a run's batch is exhausted the caller loads the next one and calls Set again. Accessors are resolved once per Set — once per batch — rather than once per comparison, so comparison stays O(keys).
func NewRunSet ¶
NewRunSet builds a run set for nruns runs ordered by the given key types.
The types are required up front rather than inferred from the first Set because a run can be empty, and a comparator that only exists once some run has delivered a batch would be a lifetime puzzle for no benefit.
type Segments ¶
Segments is a partitioned ordering over a frame.
Perm holds original row indices, arranged partition-major and ordered within each partition. Partition p occupies Perm[Bounds[p]:Bounds[p+1]], so Bounds has one more entry than there are partitions.
type SortSpec ¶
type SortSpec struct {
Descending bool
// NullsLast places nulls at the END OF THE OUTPUT, independent of direction.
// Tying it to direction instead would mean `Desc()` silently moved the nulls,
// which is never what anyone wants.
NullsLast bool
}
SortSpec describes one component of an ordering.
type TotalBinary ¶
type TotalBinary[T Numeric] func(dst, a, b []T)
TotalBinary computes dst = a OP b elementwise.
type TotalBinaryScalar ¶
type TotalBinaryScalar[T Numeric] func(dst, a []T, s T)
TotalBinaryScalar computes dst = a OP s elementwise.
type TotalCompare ¶
TotalCompare writes the boolean PAYLOAD bits of a OP b.
It writes one bitmap, not two. The VALIDITY of the result is the dispatcher's job, because `null > 5` must be null rather than false — an Arrow Boolean column has two bitmaps and conflating them was defect D13(3).
type TotalCompareScalar ¶
TotalCompareScalar writes the boolean payload bits of a OP s.
type TotalUnary ¶
type TotalUnary[T Numeric] func(dst, a []T)
TotalUnary computes dst = OP a elementwise.
Source Files