Chapter 1: Buffers and Flat Vectors

Velox stores and processes data one column at a time. A column of 64-bit integers is stored in memory using 2 contiguous buffers: a buffer of values and a buffer of null flags. To store 100 rows, we need to allocate values buffer that fits 100 64-bit integers: 100 * 8 = 800 bytes, and nulls buffer that fits 100 bits: 100 / 8 = 13 bytes. Velox allocates memory using MemoryPool.

Let’s start by getting access to a MemoryPool:

#include "velox/common/memory/Memory.h"

auto pool = memory::memoryManager()->addLeafPool();

pool is a std::shared_ptr<velox::memory::MemoryPool>. We can use it to allocate buffers.

#include "velox/buffer/Buffer.h"

auto values = AlignedBuffer::allocate<int64_t>(100, pool.get());
auto nulls = AlignedBuffer::allocate<bool>(100, pool.get());

AlignedBuffer::allocate is a template with a single template parameter T, which indicates the type of values we want to store in the buffer. sizeof(T) is used to determine how many bytes each value needs. AlignedBuffer::allocate takes number of values (numElements) and a memory pool and allocates at least numElement * sizeof(T) bytes, but usually more. We can find out how much memory was allocated using capacity() method on the returned BufferPtr.

template <typename T>
static BufferPtr allocate(
   size_t numElements,
   velox::memory::MemoryPool* pool,
   const std::optional<T>& initValue = std::nullopt) {

The values and nulls variables above are instances of BufferPtr, which is a boost::intrusive_ptr<Buffer>. Similar to std::vector, a Buffer has a size and capacity. Let’s check these for the values and nulls buffers.

LOG(INFO) << values->size() << ", " << values->capacity();

> 800, 928

LOG(INFO) << nulls->size() << ", " << nulls->capacity();

> 13, 32

As expected, the size of the values buffer is 800 bytes and size of the nulls buffer is 13 bytes. The capacity of the buffers is slightly more. We can change the size of the buffer to any value that doesn’t exceed the buffer’s capacity using Buffer::setSize() method.

values->setSize(900);

> 900, 928

nulls->setSize(20);

> 20, 32

Notice that setSize method takes number of bytes, not number of values of type T. Also, Buffer itself is not a template and therefore is not aware of the type of values that are being stored in it.

Setting the size to a value that exceeds the Buffer’s capacity results in an error.

values->setSize(1'000);

VeloxRuntimeError
Error Source: RUNTIME
Error Code: INVALID_STATE
Reason: (1000 vs. 928)
Retriable: False
Expression: size <= capacity_
Function: setSize
File: /Users/mbasmanova/cpp/velox-1/./velox/buffer/Buffer.h
Line: 119

To read values from a buffer, call Buffer::as<T> template method that returns a const T*. It is effectively a reinterpret_cast of the underlying memory buffer.

auto* rawValues = values->as<int64_t>();

LOG(INFO) << rawValues[5];

> -6799976246779207263

We allocated memory for the values buffer, but didn’t write any values yet, hence, we are getting some “garbage” values when reading from the buffer. That’s expected.

We could pass an initial value to AlignedBuffer::allocate though. Let’s allocate the values buffer and initialize all values to “25”.

auto values = AlignedBuffer::allocate<int64_t>(100, pool.get(), 25);

auto* rawValues = values->as<int64_t>();

LOG(INFO) << rawValues[5];

> 25

To write values into the allocated buffer, call Buffer::asMutable<T> template method that returns a T*. Just like the Buffer::a<T> template, it is effectively a reinterpret_cast of the underlying memory buffer.

Let’s populate the buffer with 100 sequential numbers starting from 0: 0, 1, 2,…99.

auto* rawValues = values->asMutable<int64_t>();

for (auto i = 0; i < 100; ++i) {
 rawValues[i] = i;
}

LOG(INFO) << rawValues[5];

> 5

We could also use std::iota to populate the buffer with sequential values:

std::iota(rawValues, rawValues + 100, 0);

for (auto i = 0; i < 10; ++i) {
 LOG(INFO) << i << ": " << rawValues[i];
}

> 0: 0
> 1: 1
> 2: 2

BufferPtr is a smart pointer, so we don’t need to worry about freeing up memory. Once the last reference goes out of scope, the Buffer object will get destroyed calling MemoryPool to release the memory.

We do need to make sure that MemoryPool stays alive until after all buffers allocated from it are destroyed.

Let’s now look at the nulls buffer.

We use the nulls buffer to store null flags, one bit per value. AlignedBuffer<bool>::allocate template is overwritten to allocate only one bit per entry, not 1 byte (=sizeof(bool)). To read and write null bits we use Buffer::as<uint64_t>() and Buffer::asMutable<uint64_t>() method. Notice that we use uint64_t as template parameter, not bool.

#include "velox/common/base/Nulls.h"

auto* rawNulls = nulls->as<uint64_t>();

LOG(INFO) << std::boolalpha << bits::isBitNull(rawNulls, 5);

> false

We use bits::isBitNull function to read the N-th bit of the nulls buffer and turn it into a boolean.

We haven’t written any values into the nulls buffer and we haven’t provided an initial value when allocating the buffer, hence, we are getting some “garbage” values as expected.

We can pass an initial value to AllignedBuffer::allocate<bool>(): bits::kNull or bits::kNotNull.

auto nulls = AlignedBuffer::allocate<bool>(100, pool.get(), bits::kNull);

auto* rawNulls = nulls->as<uint64_t>();

LOG(INFO) << std::boolalpha << bits::isBitNull(rawNulls, 5);

> true

We can also use helper function allocateNulls:

// Allocate nulls buffer to fit 100 null flags and initialize these to bits::kNotNull.
auto nulls = allocateNulls(100, pool.get());

// Allocate nulls buffer to fit 100 null flags and initialize these to bits::kNull.
auto nulls = allocateNulls(100, pool.get(), bits::kNull);

Finally, we can fill in the nulls buffer “manually”. Let’s set every other row to null.

auto* rawNulls = nulls->asMutable<uint64_t>();

for (auto i = 0; i < 10; ++i) {
 bits::setNull(rawNulls, i, i % 2 == 0);
}

for (auto i = 0; i < 10; ++i) {
 LOG(INFO) << i << ": " << std::boolalpha << bits::isBitNull(rawNulls, i);
}

> 0: true
> 1: false
> 2: true
> 3: false

We can also use printNulls helper function to print the null flags:

LOG(INFO) << printNulls(nulls, 10);

> 99 out of 104 rows are null: n.n.n.n.n.

LOG(INFO) << printNulls(nulls);

> 99 out of 104 rows are null: n.n.n.n.n.nnnnnnnnnnnnnnnnnnnn

printNulls function takes a nulls buffer and an optional maxBitsToPrint number which has a default value of 30.

std::string printNulls(
   const BufferPtr& nulls,
   vector_size_t maxBitsToPrint = 30);

This function returns a string where each character represents a single null flag: ‘n’ for null and ‘.’ for non-null. The result string also includes a summary prefix telling us how many entries are null. Notice that the summary says that there are a total of 104 entries, not 100. This is because BufferPtr doesn’t know that it is used to store null flags. It just knows its size in bytes, which is 13. The last byte has some bits unused.

We have learned how to allocate memory and fill it in with values and null flags. We are now ready to assemble a flat vector to hold data for a single column. Let’s make a vector to store 100 sequential BIGINT values with every other value being null: [0, null, 2, null, 4, null, 6,..].

#include "velox/vector/FlatVector.h"

auto vector = std::make_shared<FlatVector<int64_t>>(
   pool.get(), BIGINT(), nulls, 100, values, std::vector<BufferPtr>{});

LOG(INFO) << vector->toString();

> [FLAT BIGINT: 100 elements, 50 nulls]

To make a vector, we use FlatVector<T> class template with T being int64_t (64-bit integer). We pass a pointer to MemoryPool, a Type object that describes the type of values to store, nulls buffer, number of values, values buffer and an empty list of string buffers. Let’s ignore the string buffers for now. We’ll discuss these later.

FlatValue<T> class can be used to store values of primitive types. The following types are supported in Velox:

Type	C++ Type	Description
BOOLEAN	bool	A boolean flag: true or false.
TINYINT	int8_t	8-bit integer.
SMALLINT	int16_t	16-bit integer.
INTEGER	int32_t	32-bit integer.
BIGINT	int64_t	64-bit integer.
HUGEINT	int128_t	128-bit integer.
REAL	float	32-bit floating point number.
DOUBLE	double	64-bit floating point number.
VARCHAR	struct StringView	Variable width string.

Nulls buffer can be null, which indicates that all values are not null.

auto nonNullVector = std::make_shared<FlatVector<int64_t>>(
   pool.get(), BIGINT(), nullptr, 100, values, std::vector<BufferPtr>{});

LOG(INFO) << nonNullVector->toString();

> [FLAT BIGINT: 100 elements, no nulls]

Values buffer can also be null in case all values are null.

auto nulls = allocateNulls(100, pool.get(), bits::kNull);
auto allNullVector = std::make_shared<FlatVector<int64_t>>(
   pool.get(), BIGINT(), nulls, 100, nullptr, std::vector<BufferPtr>{});

LOG(INFO) << allNullVector->toString();

> [FLAT BIGINT: 100 elements, 100 nulls]

However, it is invalid to create a vector with both nulls and values buffers being null.

std::make_shared<FlatVector<int64_t>>(
   pool.get(), BIGINT(), nullptr, 100, nullptr, std::vector<BufferPtr>{});

VeloxRuntimeError
Error Source: RUNTIME
Error Code: INVALID_STATE
Reason: FlatVector needs to either have values or nulls
Retriable: False
Expression: values_ || BaseVector::nulls_
Function: FlatVector
File: /Users/mbasmanova/cpp/velox-1/./velox/vector/FlatVector.h
Line: 89

FlatVector::size() and FlatVector::type() getters return the number and type of values stored in the vector.

LOG(INFO) << vector->size();
LOG(INFO) << vector->type()->toString();

> 100
> BIGINT

FlatVector::isNullAt(index) and FlatVector::isValueAt(index) return the null flag and the value at specified index (row).

LOG(INFO) << std::boolalpha << vector->isNullAt(5);

> false

LOG(INFO) << vector->valueAt(5);

> 5

LOG(INFO) << std::boolalpha << vector->isNullAt(6);

> true

LOG(INFO) << vector->valueAt(5);

> 6

Notice that the values buffer has a value for all positions even the ones that are null. However, the value for null positions cannot be trusted. It can be any value.

In this chapter we have learned how to allocate memory and create vectors of integers. In the next chapter we’ll look into how to create vectors of strings.