Documentation
¶
Overview ¶
Package strview implements the Arrow variable size binary view layout, which is how kuma stores String and Binary columns.
The classic Arrow layout for a string column is a buffer of offsets and a buffer of bytes, where element i runs from offsets[i] to offsets[i+1]. That is compact and it is a pointer chase for every single comparison, which is most of what an engine does to a string column.
The view layout replaces the offsets with a fixed sixteen byte record per element:
a value of 12 bytes or fewer, kept inline bytes 0 to 3 length bytes 4 to 15 the value, zero padded a value that is longer, kept in a data block bytes 0 to 3 length bytes 4 to 7 the first four bytes of the value bytes 8 to 11 which data block the value is in bytes 12 to 15 where in that block it starts
Three things fall out of that. A value of twelve bytes or fewer is entirely inside its own view, and most real string data is short, so most values are read with no second memory access at all. Every view carries the first four bytes of its value in the same place whether it is short or long, so two values that differ in the first four bytes are ordered without touching the data at all. And a scan over a column becomes a dense walk over fixed width records, which vectorizes, where a walk over offsets does not.
The cost is memory. Sixteen bytes per element against four or eight for an offset, and long values are never deduplicated the way a shared offsets buffer can leave them. Dictionary encoding is the answer for the columns where that matters, and it is a bigger win than either layout.
Arrow calls the data blocks the data buffers and calls the block number the buffer index. They are blocks here because this repository already has a buffer package, and a buffer index into a list of buffers held in a buffer is one word too many.
Everything is little endian, on every machine, because that is what Arrow writes on the wire and converting at the boundary is cheaper than converting on every access. On the machines anyone runs this on, that is a plain load.
Stability: tier 1, stable.
Index ¶
Examples ¶
Constants ¶
const ( // Size is the width of one view in bytes. Size = 16 // MaxInline is the longest value that fits inside a view. A value of this // length or shorter needs no data block. MaxInline = 12 // PrefixLen is how many leading bytes of a value every view carries, // whether the value is inline or not. PrefixLen = 4 // MaxValue is the longest value the layout can describe, and the highest // block number and offset it can name. The length, the block number and the // offset are all signed 32 bit fields, which is Arrow's choice rather than // this package's. MaxValue = math.MaxInt32 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder accumulates values into a Data.
Short values go straight into their views. Long values are copied into a data block, so the builder owns its bytes and the caller may reuse the slice it passed in, which is what makes it safe to build a column out of a scanner's reused read buffer.
The zero Builder is empty and ready to use.
Example ¶
package main
import (
"fmt"
"github.com/tamnd/kuma/strview"
)
func main() {
var b strview.Builder
b.AppendString("kuma")
b.AppendString("a value that is too long to live inside its view")
d := b.Finish()
for i := range d.Len() {
fmt.Printf("%d bytes, inline %v: %s\n", d.View(i).Len(), d.View(i).IsInline(), d.At(i))
}
}
Output: 4 bytes, inline true: kuma 48 bytes, inline false: a value that is too long to live inside its view
func (*Builder) Append ¶
Append adds p, copying it if it is too long to live in its view.
It panics if p is longer than MaxValue, or if the column has grown past what the block and offset fields can name. MakeRef is where that is enforced, rather than here as well, because a limit checked in two places is a limit that gets changed in one.
func (*Builder) AppendString ¶
AppendString adds s. It is Append without the conversion, since a string to byte slice conversion of a long value would be a copy this package is about to make anyway.
func (*Builder) Finish ¶
Finish returns the values appended so far and resets the builder.
The Data takes the builder's memory rather than a copy of it, which is the only reason building a column is one allocation per block instead of two. Finish is what makes that safe: the builder comes back empty, so there is no way to write through it into a column that has already been handed out.
type Data ¶
type Data struct {
// contains filtered or unexported fields
}
Data is the value part of a String or Binary column: the views, and the blocks the long ones point into.
It carries no validity bitmap and no dtype. Those belong to the array that holds this, because a null is not a value and this type is only about values.
func NewData ¶
NewData returns a column over views and blocks after checking that every view describes something that is actually there. It does not copy either argument, and the caller must not modify them afterwards.
The check is the point. Views that came from this process were built by Builder and are correct by construction, but views that arrived in an Arrow IPC message were written by something else, and a view that points past the end of a block is a read of somebody else's memory rather than a wrong answer. Validating once at the boundary is what lets every read after it be a slice with no bounds thinking in it.
Example ¶
ExampleNewData opens a column that was built somewhere else, which is what receiving one over Arrow IPC amounts to. The views are checked against the blocks before anything is read, so a view that points past the end of its block is an error here rather than a wrong answer later.
package main
import (
"fmt"
"github.com/tamnd/kuma/strview"
)
func main() {
var b strview.Builder
b.AppendString("a value that does not fit inline")
d := b.Finish()
views, blocks := d.Views(), d.Blocks()
views[0][12] = 0xff // move the value's offset out past the end of its block
if _, err := strview.NewData(views, blocks); err != nil {
fmt.Println(err)
}
}
Output: strview: view 0: wants bytes 255 to 287 of a block that is 32 long
func (*Data) At ¶
At returns value i.
The result aliases the column, either the view itself for a short value or a data block for a long one, and the caller must not modify it. Copying here would be a copy per element on the hottest path there is.
func (*Data) Compare ¶
Compare returns a negative number, zero or a positive number as value i sorts before, with or after value j, ordering by bytes the way bytes.Compare does.
Prefixes settle it whenever they differ, which for real string data is nearly always, and they are four bytes sitting in a record the caller already had to load. Comparing zero padded prefixes gives the same answer as comparing the values: if the two prefixes first differ at a position past the end of the shorter value, then the shorter value is a prefix of the longer one and sorts first, which is what its pad byte of zero says.
Example ¶
package main
import (
"fmt"
"slices"
"github.com/tamnd/kuma/strview"
)
func main() {
var b strview.Builder
for _, s := range []string{"pear", "apple", "a rather longer name than the others", "banana"} {
b.AppendString(s)
}
d := b.Finish()
order := make([]int, d.Len())
for i := range order {
order[i] = i
}
slices.SortFunc(order, d.Compare)
for _, i := range order {
fmt.Println(string(d.At(i)))
}
}
Output: a rather longer name than the others apple banana pear
func (*Data) Equal ¶
Equal reports whether values i and j are the same bytes.
Most calls are answered by the first two lines. Two views that are equal as sixteen raw bytes hold the same value, whether that is because both carry it inline or because both point at the same place. Two views with different lengths or different prefixes hold different values. Only values that are the same length and start the same way reach a byte comparison.
func (*Data) EqualValue ¶
EqualValue reports whether value i is p. It is the probe side of a hash join or a group by lookup, where one side is a value already in hand.
Example ¶
package main
import (
"fmt"
"github.com/tamnd/kuma/strview"
)
func main() {
var b strview.Builder
b.AppendString("tokyo")
b.AppendString("kumamoto")
d := b.Finish()
for i := range d.Len() {
fmt.Println(string(d.At(i)), d.EqualValue(i, []byte("kumamoto")))
}
}
Output: tokyo false kumamoto true
type View ¶
View describes one value in a String or Binary column.
It is a byte array rather than a struct of fields, so that a slice of views is exactly the bytes Arrow puts on the wire and can be handed across the C data interface without being rewritten. The accessors read little endian integers out of it.
The zero View is a valid empty value, which means a column of views that has been sized but not filled reads as empty strings rather than as anything surprising.
Example ¶
ExampleView shows the layout of a short value. The first four bytes are the length and the rest is the value, zero padded, so nothing else has to be read to get it back.
package main
import (
"fmt"
"github.com/tamnd/kuma/strview"
)
func main() {
v := strview.MakeInline([]byte("kuma"))
fmt.Printf("%v\n", v[:])
fmt.Println(v)
}
Output: [4 0 0 0 107 117 109 97 0 0 0 0 0 0 0 0] inline("kuma")
Example (Prefix) ¶
ExampleView_prefix shows the other half of the layout. A long value keeps its first four bytes in the view, in the same place a short value keeps the start of its own, so a comparison that is settled in the first four bytes never reaches a data block.
package main
import (
"fmt"
"github.com/tamnd/kuma/strview"
)
func main() {
var b strview.Builder
b.AppendString("kuma")
b.AppendString("kumamoto prefecture, in the south")
d := b.Finish()
for i := range d.Len() {
p := d.View(i).Prefix()
fmt.Printf("%q\n", p[:])
}
}
Output: "kuma" "kuma"
func MakeInline ¶
MakeInline returns a view holding value inside itself. It panics if the value is longer than MaxInline.
The bytes past the value are left zero, and they have to be: it is what makes two views of the same short value identical as raw bytes, so equality can be a sixteen byte comparison rather than a length check and a loop.
func MakeRef ¶
MakeRef returns a view for a value that lives at offset in block. It panics if the value is short enough to inline, since a column with two ways to spell the same value is a column where equality has to know about both. It also panics if the value, the block number or the offset is out of range, rather than truncating to 32 bits and describing a value that is not there.
func (View) Block ¶
Block returns which data block holds the value. It is meaningless for an inline view.
func (*View) Inline ¶
Inline returns the bytes of an inline value, aliasing the view itself. The caller must not modify the result. It panics if the view is not inline.
The receiver is a pointer so that the result aliases the caller's view rather than a copy of it, which is what keeps this from allocating.
func (View) IsInline ¶
IsInline reports whether the value is inside the view rather than in a data block.
func (View) Len ¶
Len returns the length of the value in bytes.
The length is a signed 32 bit field in the Arrow layout, so a view that came from somewhere else can claim a negative length. This returns what it claims. Validate is what refuses it.
func (View) Offset ¶
Offset returns where in its block the value starts. It is meaningless for an inline view.
func (View) Prefix ¶
Prefix returns the first PrefixLen bytes of the value, zero padded if the value is shorter than that.
This is the reason the layout exists. Two values whose prefixes differ are ordered by their prefixes alone, with no access to any data block, and for real string data that settles the overwhelming majority of comparisons.
Source Files