[C++][Parquet] Encoding tools for variant type

[mapleFU]

Describe the enhancement requested

The patch[1] does the decoding logics for Variant type. The encoding is the another part of the variant type. Since VariantValue is a wrapper for (std::string_view, std::string_view), we should more carefully on design the variant encoding tools.

The code I need to follow is the code from parquet-java [2], iceberg [3] and arrow-rs [4]. Some apis in C++ like velocypack [5] is also taken into account.

Set API

The first logics we need take care is how the setter api works. We focus on two parts: primitive types and complex types.

Complex types

Builder style api?

We need consider the complex type before the normal type. In a builder, a complex type is coming before the primitive type. The builder might have some modes:

1. set a primitive type directly
2. set key-value pair in object (str key, value)
3. append the values in array

Besides, the nested object add key always added to meta dictionary.

The api might be:

void startObject();
void endObject();
void startArray();
void endArray();
// Append key in object.
// This should be called in a object
void appendKey(...);
// Primitive api
// When in an object, appendInt should be called with key exists
// When in an array, just append
// When not an object or an array, this directly set the int.
void appendInt(..);

We might also suply the builder helper:

void setInt(key, value);

Value style api?

We can also support a VariantBuilder. And subtypes can have VariantObjectBuilder, VariantPrimitiveContainer, VariantArrayBuilder.

VariantBuilder can produce bytes, which could build array bottom-up

struct VariantBuilder {
 std::string build();
 uint32_t addDictionaryKey(std::string_view key);
};

struct VariantObjectBuilder {
 void set(uint32_t field_id, std::string_view);
};

struct VariantArrayBuilder {
 void append(std::string_view);
 void appends(std::span<std::string_view>);
};

Primitive types

For types like timestamp, null, boolean(true, false), api can set directly.

For types like double / float, user might set it themselve

For types like Integer, we might provide setInt8, setInt16, setInt32, setInt64 or:

 void addInt(int64_t v) {
 if (v can be repr in int8) {
 // int8
 } else if (v can be repr in int16) {
 // int16
 } else {
 // ...
 }
 }

Buffer and view handling

Buffer handling is also we should consider. Assume a one level builder for objects like:

{"a": 1}
{"a": 2, "b": 2}
{"a": 3, "b": 3}
...

We might need:

1. allocate temp buffer for inner object to store field_id and offsets
2. A pooled buffer for built strings
3. A ordered set for sorted keys, or a unordered vector for unsorted keys
4. final buffer for output

The buffer handling would be a place to consider here:

1. For output, we can have two mode (1) std::string finish() for output (2) append to output buffer
2. For inner buffer, we can use Arena style management rule

Reference

[1] #46372
[2] https://github.com/apache/parquet-java/blob/1f1e07bbf750fba228851c2d63470c3da5726831/parquet-variant/src/main/java/org/apache/parquet/variant/VariantBuilder.java#L31
[3] https://github.com/apache/iceberg/blob/1911c94ea605a3d3f10a1994b046f00a5e9fdceb/parquet/src/main/java/org/apache/iceberg/parquet/VariantWriterBuilder.java#L46
[4] apache/arrow-rs#7424
[5] https://github.com/arangodb/velocypack

Component(s)

C++, Parquet

[mapleFU]

cc @pitrou @alamb @wgtmac @emkornfield @zeroshade for some interface design ideas

[zeroshade]

I've been building out an API for a Variant Builder for the Go implementation, and so far I have based it on the Spark Variant Builder.

The API looks like this for the primitive types:

func (b *Builder) AppendNull() error {...}
func (b *Builder) AppendBool(v bool) error {...}
// uses the smallest int type it can based on the value
func (b *Builder) AppendInt(v int64) error {...}
func (b *Builder) AppendTimestamp(v arrow.Timestamp, useMicro, useUTC bool) error {...}
// and so on....

There are also methods for adding a key to the metadata:

func (b *Builder) AddKey(k string) (id uint32) {...}
func (b *Builder) AddKeys(k []string) (id []uint32) {...}

Which just adds them so they will get put into the metadata when you finally build it, and returns the IDs.

For managing objects and arrays, I decided against using sub-builders as that would require having to manage the lifetime of multiple objects and sub-builders which could get very complex. Instead the pattern is the following:

1. Get the starting offset via Buffer.Offset()
2. Use the starting offset and helper functions to build a list of fields/offsets while appending the values
3. Call FinishArray / FinishObject with the start offset + list of offsets/fields.

Code-wise it looks like this to build a list:

var b variant.Builder
start := b.Offset()
offsets := make([]int, 0)

offsets = append(offsets, b.NextElement(start))
b.AppendInt(5)

offsets = append(offsets, b.NextElement(start))
b.AppendBool(true)

offsets = append(offsets, b.NextElement(start))
b.AppendInt(9)

b.FinishArray(start, offsets)

v, err := b.Build()

Resulting in a variant that is equivalent to [5, true, 9].

For an object it looks like:

var b variant.Builder
start := b.Offset()
fields := make([]variant.FieldEntry, 0)

fields := append(fields, b.NextField(start, "int_field"))
b.AppendInt(1)

fields = append(fields, b.NextField(start, "string_field"))
b.AppendString("Variant")

fields = append(fields, b.NextField(start, "null_field"))
b.AppendNull()

b.FinishObject(start, fields)

v, err := b.Build()

This would create a variant that is equivalent to { "int_field": 1, "string_field": "Variant", "null_field": null }

What do you think?

[mapleFU]

@zeroshade This builder api sounds ok to me for primitive api, though I found maybe only integer will use smallest ( can float/double cannot distinct it fits the smallest type? Perhaps not? )

I also wonder what the decimal value in builder api would be like, since arrow doesn't have Java's BigDecimal type. I draft a

template<typename ArrowDecimalType>
struct DecimalValue {
 ArrowDecimalType decimal;
 uint8_t scale;
};

What would here better being?

Also, I've list a part for output and internal buffer handling. Arena like data structure would be used here. Previously I've think how to do think of reusing buffer and making build array of Variant vectorization. But now I found it's complex to vectorize building a so complex type. So maybe I should focous on reuse buffer and decrease dynamic buffer allocation

[zeroshade]

So, I used that DecimalValue type for how I return the decimal types:

type DecimalValue[T decimal.DecimalTypes] struct {
	Scale uint8
	Value decimal.Num[T]
}

But the builder currently has:

func (b *Builder) AppendDecimal4(scale uint8, v decimal.Decimal32) error {...}
func (b *Builder) AppendDecimal8(scale uint8, v decimal.Decimal64) error {...}
func (b *Builder) AppendDecimal16(scale uint8, v decimal.Decimal128) error {...}

( can float/double cannot distinct it fits the smallest type? Perhaps not? )

I'll try that, shouldn't be difficult to set it up for that.

Also, I've list a part for output and internal buffer handling. Arena like data structure would be used here. Previously I've think how to do think of reusing buffer and making build array of Variant vectorization. But now I found it's complex to vectorize building a so complex type. So maybe I should focous on reuse buffer and decrease dynamic buffer allocation

Another reason why I avoided the "child builder" construction is to improve buffer reuse and reduce dynamic allocation. There's a single buffer in the builder that everything writes to. FinishObject / FinishArray are called, the buffer is expanded and the size of the header is calculated. The raw data is then shifted by that many bytes and the header is written in the new space. That way we aren't creating a separate buffer for each child builder that we then have to copy back to the main one (which is what https://github.com/apache/parquet-java/blob/1f1e07bbf750fba228851c2d63470c3da5726831/parquet-variant/src/main/java/org/apache/parquet/variant/VariantObjectBuilder.java does)

[mapleFU]

Yeah:

1. for array and object, size is unknown before finishObject
2. For element in array and object, an "arena" like object is likely used

I found the parquet-java uses nested impl [1], and velocypack uses internal arena stack [2]. [1] is more easy to implement, [2] is more efficient for me.

And for final output, I'm also think about what to return, maybe an api below is ok?

struct Builder {
void finish();
std::string_view buffer() const;
std::string_view meta_buffer() const;
void reset();
};

The caller:

::arrow::BinaryViewBuilder array_builder;
::arrow::BinaryViewBuilder metadata_builder;
VariantBuilder variant_builder;
for (size_t idx = 0; idx < row_size(); ++idx) {
 // build from array
 array_builder.Append(variant_builder.buffer());
 metadata_builder.Append(variant_builder.meta_buffer());
 variant_builder.reset();
}

Since array builder is complex

[1] https://github.com/apache/parquet-java/blob/1f1e07bbf750fba228851c2d63470c3da5726831/parquet-variant/src/main/java/org/apache/parquet/variant/VariantBuilder.java#L437
[2] https://github.com/arangodb/velocypack/blob/8f0fc652e7641046a9f12b7d8a9917dcc507a5c2/include/velocypack/Builder.h#L98-L99

[zeroshade]

The only thing I like better about the nested impl approach is that the developer API is slightly easier to use and better (in some ways). Instead of needing the NextElement and NextField calls, a user can just make the Append* calls on the ArrayBuilder or ObjectBuilder. Though it does have the complexity of the extra child builder objects, it does make things slightly easier in some ways even though it's less efficient.

I guess I'll finish this up and put the PR up and see what people think

[mapleFU]

Thanks for the sharing! It's really inspiring! Looks like this kind of api has some best practice. And since variant object is complex, maybe we cannot expect executing it could be fast, maybe the bottleneck will be memory allocation in the main path, and it cannot be vectorized in most of cases ( since so many memory dependency in main path )

[zeroshade]

I think the work we're doing is gonna defining the best practices since so far we're seeing a divergence in approach between Spark, Parquet-java, and others. 😄 I guess we're gonna have to compare and contrast and see what the community likes. In addition, there may be language specific divergences in what makes the most sense.

[zeroshade]

@mapleFU I've put up my changes finally by updating the PR at apache/arrow-go#344 complete with my updated design and docs for the builder and encoding/decoding values. Let me know what you think there! Inspiration there includes your C++ code and the Spark and parquet-java implementations.

@alamb Since you've brought this to the attention of the rust devs, I'd also be curious of your (and their!) thoughts on what I ended up coming up with.

[mapleFU]

It's impressive to use one buf during building the variant object!

// Builder is used to construct Variant values by appending data of various types.
// It manages an internal buffer for the value data and a dictionary for field keys.
type Builder struct {
	buf bytes.Buffer
	dict map[string]uint32
	dictKeys [][]byte
	allowDuplicates bool
}