Zero-Copy Vector View

[Yuhta]

Background

One of the missing features in Velox is the functionality of a zero-copy vector view. Given an existing vector of any type, if the user only wants a continuous subrange of the vector, in the current implementation, the user has to allocate a new vector and copy the underlying data, which is very expensive.

Interface

The following method will be added to BaseVector:

// Construct a zero-copy slice of the vector with the indicated offset and length.
std::shared_ptr<BaseVector> slice(vector_size_t offset, vector_size_t length) const;

Some invariants:

• The returned slice should have the same type as the original vector
• The returned slice should have the same encoding as the original vector

Performance characteristics:

• When the offset is a multiple of 8, copying of nulls buffer can be avoided and improve the performance

Implementation

FlatVector

For FlatVector::rawValues() and FlatVector::values(),

1. If the underlying type is boolean, and the overall offset is not a multiple of 8 (8 bits = 1 byte), we create a new buffer with values left shifted offset bits, save it as the new value_ buffer, and return the start of that buffer as the result.
2. Otherwise we keep a BufferView in the values_ field, taking offset and size into consideration, and return the start of that buffer, which is already offsetted.

For nulls buffer we treat it same as a boolean type value buffer.

The semantics of non-bit types are exactly the same as Array::raw_values() in Arrow, which returns an offset-applied address from the underlying buffer. The different treatment of a buffer representing bits is the place where we diverge from Arrow: in Arrow, Array::null_bitmap() is always unoffsetted and it is up to the user to left shift the result by Array::offset() bits. This is error-prone and inconsistent, since in case of Array::raw_values(), Arrow returns an offsetted address, but in Array::null_bitmap() it returns an unoffsetted address.

Do we want to support slicing OPAQUE vectors? Currently Buffer::as<std::shared_ptr<void>>() is throwing an exception.

Encodings

Nulls buffer will be sliced the same way as FlatVector.

For different encodings:

• Slice of a ConstantVector will be the same as the original vector, except maybe we change the size.
• Slice of a DictionaryVector will take a slice on the indices and leave the base vector unchanged.
• For RowVector we will take slices on all children.
• For ArrayVector and MapVector we take slices on the offsets and sizes.
• Slice of Bias and Sequence encoding will be left as unimplemented for now.

Peeling an offset dictionary produces the selected indices into base data. When rewrapping the result of the dictionary, the resulting DictionaryVector has the same offset as the original if the indices are reused. If the indices are new, then the resulting vector has no offset.

For LazyVector, since it is not possible to pass rows and hook to the slice, we decide to disable taking the slice on an unloaded vector. Another alternative is to force a full load when slice is called. But forcing full load is tricky because we need to make sure that any potentially wrappings (dict) over the vector are updated during the loading. See DictionaryVector::loadedVector.

Test & Benchmark

Some dedicated aspects should be tested in unit tests:

• Mutation on the original vector or the slice (e.g. set null, set value)

In addition to the normal unit tests, fuzzer will be enhanced to generate some slices. The percentage of that does not need to be large as this change should not affect evaluation heavily.

Benchmark will be taken for:

• Slice vs copy
• Compare the case where nulls are not copied (offset is multiple of 8) vs copied.

Q & A

Will allocating & copying the bits buffer affect performance negatively?

The allocation and copy of a bit buffer is not a concern here since

1. It is only happening when the offset is not a multiple of 8. If the use case is performance critical, there is a chance to choose a batch size multiple of 8 to avoid the copying.
2. The size of a bit buffer is one to two magnitudes smaller than any other types. Thus the time for allocation & copy is also tiny compared to other operations.

How is mutability handled for the slice?

We have 2 cases:

1. If a user tries to write to a slice, we do not allow this case for now. Currently Buffer::mutableRawValues() will check if the buffer is uniquely owned, but for BufferView the reference count is 1, so it might return rawValues_ directly. We need to add an extra check here to block this path. Also a similar check needs to be added to Buffer::mutableNulls() and BaseVector::ensureWritable.
2. If the underlying data is being written, the writer should check if the buffer is uniquely owned; in this case it is not uniquely owned, so the writer should make a copy and write to the copy. So in this case the writer creates a new version of buffer and has the slice untouched as well.

How will the offset change the expression evaluation?

It should not change any behavior in expression evaluation except maybe dictionary rewrapping. With this new design, we no longer leak the concept of offset to the user, including expression eval. So all the vectors, whether or not offsetted, should appear exactly the same. This also saves us a lot of work in terms of testing the feature.

---

[Yuhta]

An implementation is under work.

[Yuhta]

Implemented in #2306