Macaw.Data.Operations.Transforms.Ladder (macaw_data v0.13.0)
View SourceThe bucket ladder m4 and lttb reduce on (spec/04 §4.4, §4.5; macaw_data#9 §5): one
absolute ladder of buckets in the space the x scale maps through, so a chunk's partial
depends on its rows, the scale's kind and the level alone, never on the data first read
or on the extent.
- The space is the scale's kind (
scale:in the context)::linear, x as a number, a time in seconds;:time, a time in microseconds since the Unix epoch;:log, the base-2 logarithm of x, which is above 0. A step reads:timefor a time column and:linearotherwise when the context names none. - A bucket at level
kis2^kwide,kany integer, from origin 0: the valueslies in bucketfloor(s / 2^k). - The level is the coarsest whose bucket is at most an ideal width the step derives
from the span and its count,
floor(log2(ideal)). Hysteresis: the previous level, given aslevel:in the context, is kept while its bucket is within a factor of 2 of the ideal width, so a span drifting near a power of two keeps one level. - A partial holds a piece a view, in chunk order: the view's runs of rows, split by
gaps (a row whose x or y is
nil, each run of gap rows kept as its first), each run its buckets ascending by bucket, per bucket the first, the last, the least and the greatest point, each{row, s, y}, packed into one binary a piece (Ladder.Packed), off the process heap, so a cache of partials costs its holder a few words each. Partials merge associatively in chunk order by concatenation (combine/2), so a merge costs the chunks, not the buckets; the chunk edges are joined once, when the merged partial is read (runs/1): a bucket straddling an edge merges its two summaries and a gap on an edge stays one gap. A finer partial folds into a coarser level exactly (coarsen/2), so a zoom out reuses finer partials.
Summary
Types
A bucket's summary as runs/1 reads it, {view, summary}: its points are rows of that
view, or, view nil, they carry their {view, row} (a bucket straddling a chunk edge).
A partial: its level, the views its pieces index, and a piece a view, in order.
One view's segments packed into one binary (Ladder.Packed), under the view's index
among the partial's views: off the process heap, so a cache of partials costs its holder
a few words a piece, whatever the buckets.
A point of a bucket: {row, s, y} in a piece, row the row of its view; {ref, s, y}
as runs/1 reads it.
A row of a merged partial: {view, row}, in input order.
A run's buckets, ascending by bucket, each once.
A view's segments in row order: its runs, and each run of gap rows as its first row.
A bucket's first, last, least and greatest points.
Functions
The step's fields, the scale's kind and the x extent over the whole input, once:
%{x, y, x_name, y_name, kind, extent}, extent {lo, hi} in the space or nil.
A sorted x column is read at its ends, any other scanned. A context's scale that is not
one of linear, time or log is {"op", {:unknown, :scale, scale}}; an x reading the
scale cannot place, or a y reading that is no number, {"fields", {:reads, kind}}
(spec/04 §3.1), answered before any row is read. An x past what the arithmetic over it
holds is {"fields", :overflow} (spec/04 §5, macaw_data#181).
The bucket of s at level k: floor(s / 2^k), exactly.
A partial folded into a level at or above its own: each bucket into the coarser bucket holding it, one pass a run, exactly as computing the partial at that level would give it.
Two partials merged, the first's chunks before the second's, at the coarser of their
levels: the views and the pieces concatenated, the second's view indexes moved past the
first's. No bucket is read, so a combine costs the chunks, never the buckets; a run or
a gap continuing across the chunk edge, and a bucket straddling it, are joined once, by
runs/1. Any grouping of the same partials gives the same partial.
The rows at refs ({view, row}, any order) gathered from their views, in input order,
each view's run named by key and the rows taken: a table of the input's columns.
The level for an ideal bucket width: the previous level while its bucket is within a factor of 2 of it, else the coarsest whose bucket is at most it; the previous level, or 0, with no width (a single point or none).
Two located summaries of one bucket merged (summary/2): within one view they stay
that view's rows; across two, every point is given its {view, row}.
One view's partial at level k: its rows' buckets, run by run between gaps, as the one
piece of view 0. A run's buckets are ascending by bucket, each once. Where the native
kernels are loaded and both columns are in a form the kernel reads, on a linear or time
scale, the kernel computes the piece from the columns' buffers in place, equal term for
term to the Elixir walk's (spec/04 §4.5.2).
A located point with its ref {view, row}, given its summary's view (nil: it has it).
A bucket's width at level k, 2^k.
A located point's ref, {view, row}, given its summary's view (nil: it has it).
A merged partial read once, in input order: its gaps, {:gap, {view, row}}, and its
runs, {:run, buckets}, each run's buckets {b, located} ascending, each once (a
located/0 summary). A run ending one piece and one starting the next are one run, a
bucket they share merged; a gap ending one and one starting the next are one gap, the
first. Buckets out of order across pieces (an x not sorted) are merged through a map.
No point is copied but a bucket's that straddles a chunk edge.
An x reading in the scale's space: seconds (a time) or the number itself for :linear;
microseconds since the Unix epoch for :time, a number read as seconds; log2 of a
number above 0 for :log. Any other reading is refused before (bind/4's
{"fields", {:reads, kind}}), so one here is a broken invariant and raises.
Two summaries of one bucket merged: the first and last by input order, the least and
greatest by y, the earlier on a tie. Commutative and associative, whether the points'
refs are rows of one view or {view, row}.
Types
@type located() :: {non_neg_integer() | nil, summary()}
A bucket's summary as runs/1 reads it, {view, summary}: its points are rows of that
view, or, view nil, they carry their {view, row} (a bucket straddling a chunk edge).
@type partial() :: {integer(), [Macaw.Data.Table.view()], [piece()]}
A partial: its level, the views its pieces index, and a piece a view, in order.
@type piece() :: {non_neg_integer(), binary()}
One view's segments packed into one binary (Ladder.Packed), under the view's index
among the partial's views: off the process heap, so a cache of partials costs its holder
a few words a piece, whatever the buckets.
@type point() :: {non_neg_integer() | ref(), number(), number()}
A point of a bucket: {row, s, y} in a piece, row the row of its view; {ref, s, y}
as runs/1 reads it.
@type ref() :: {non_neg_integer(), non_neg_integer()}
A row of a merged partial: {view, row}, in input order.
A run's buckets, ascending by bucket, each once.
@type segments() :: [run: run(), gap: non_neg_integer()]
A view's segments in row order: its runs, and each run of gap rows as its first row.
A bucket's first, last, least and greatest points.
Functions
@spec bind([Macaw.Data.Table.name()], Macaw.Data.Table.t(), map(), String.t()) :: map() | {:error, {String.t(), term()}}
The step's fields, the scale's kind and the x extent over the whole input, once:
%{x, y, x_name, y_name, kind, extent}, extent {lo, hi} in the space or nil.
A sorted x column is read at its ends, any other scanned. A context's scale that is not
one of linear, time or log is {"op", {:unknown, :scale, scale}}; an x reading the
scale cannot place, or a y reading that is no number, {"fields", {:reads, kind}}
(spec/04 §3.1), answered before any row is read. An x past what the arithmetic over it
holds is {"fields", :overflow} (spec/04 §5, macaw_data#181).
The bucket of s at level k: floor(s / 2^k), exactly.
A partial folded into a level at or above its own: each bucket into the coarser bucket holding it, one pass a run, exactly as computing the partial at that level would give it.
Two partials merged, the first's chunks before the second's, at the coarser of their
levels: the views and the pieces concatenated, the second's view indexes moved past the
first's. No bucket is read, so a combine costs the chunks, never the buckets; a run or
a gap continuing across the chunk edge, and a bucket straddling it, are joined once, by
runs/1. Any grouping of the same partials gives the same partial.
@spec gather( [Macaw.Data.Table.view()], [{non_neg_integer(), non_neg_integer()}], Macaw.Data.Table.t(), term() ) :: Macaw.Data.Table.t()
The rows at refs ({view, row}, any order) gathered from their views, in input order,
each view's run named by key and the rows taken: a table of the input's columns.
The level for an ideal bucket width: the previous level while its bucket is within a factor of 2 of it, else the coarsest whose bucket is at most it; the previous level, or 0, with no width (a single point or none).
Two located summaries of one bucket merged (summary/2): within one view they stay
that view's rows; across two, every point is given its {view, row}.
@spec partial(Macaw.Data.Table.view(), map(), integer(), String.t()) :: partial()
One view's partial at level k: its rows' buckets, run by run between gaps, as the one
piece of view 0. A run's buckets are ascending by bucket, each once. Where the native
kernels are loaded and both columns are in a form the kernel reads, on a linear or time
scale, the kernel computes the piece from the columns' buffers in place, equal term for
term to the Elixir walk's (spec/04 §4.5.2).
@spec point(non_neg_integer() | nil, point()) :: {ref(), number(), number()}
A located point with its ref {view, row}, given its summary's view (nil: it has it).
A bucket's width at level k, 2^k.
@spec ref(non_neg_integer() | nil, point()) :: ref()
A located point's ref, {view, row}, given its summary's view (nil: it has it).
A merged partial read once, in input order: its gaps, {:gap, {view, row}}, and its
runs, {:run, buckets}, each run's buckets {b, located} ascending, each once (a
located/0 summary). A run ending one piece and one starting the next are one run, a
bucket they share merged; a gap ending one and one starting the next are one gap, the
first. Buckets out of order across pieces (an x not sorted) are merged through a map.
No point is copied but a bucket's that straddles a chunk edge.
An x reading in the scale's space: seconds (a time) or the number itself for :linear;
microseconds since the Unix epoch for :time, a number read as seconds; log2 of a
number above 0 for :log. Any other reading is refused before (bind/4's
{"fields", {:reads, kind}}), so one here is a broken invariant and raises.
Two summaries of one bucket merged: the first and last by input order, the least and
greatest by y, the earlier on a tie. Commutative and associative, whether the points'
refs are rows of one view or {view, row}.