Macaw.Data.Operations.Transforms.Ladder (macaw_data v0.12.0)

View Source

The 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 :time for a time column and :linear otherwise when the context names none.
  • A bucket at level k is 2^k wide, k any integer, from origin 0: the value s lies in bucket floor(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 as level: 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.

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

located()

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

partial()

@type partial() :: {integer(), [Macaw.Data.Table.view()], [piece()]}

A partial: its level, the views its pieces index, and a piece a view, in order.

piece()

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

point()

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

ref()

@type ref() :: {non_neg_integer(), non_neg_integer()}

A row of a merged partial: {view, row}, in input order.

run()

@type run() :: [{integer(), summary()}]

A run's buckets, ascending by bucket, each once.

segments()

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

summary()

@type summary() :: {point(), point(), point(), point()}

A bucket's first, last, least and greatest points.

Functions

bind(list, table, context, op)

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

bucket(s, k)

@spec bucket(number(), integer()) :: integer()

The bucket of s at level k: floor(s / 2^k), exactly.

coarsen(arg, to)

@spec coarsen(partial(), integer()) :: partial()

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.

combine(arg1, arg2)

@spec combine(partial(), partial()) :: partial()

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.

gather(views, refs, input, key)

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.

level(ideal, previous)

@spec level(number() | nil, integer() | nil) :: integer()

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

located(arg1, arg2)

@spec located(located(), located()) :: located()

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

partial(view, bound, k, op)

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

point(v, point)

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

pow2(k)

@spec pow2(integer()) :: number()

A bucket's width at level k, 2^k.

ref(v, arg)

@spec ref(non_neg_integer() | nil, point()) :: ref()

A located point's ref, {view, row}, given its summary's view (nil: it has it).

runs(arg)

@spec runs(partial()) :: [gap: ref(), run: [{integer(), located()}]]

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.

space(value, map, op)

@spec space(term(), map(), String.t()) :: number()

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.

summary(arg1, arg2)

@spec summary(summary(), summary()) :: summary()

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