fetan

fetan is a C++23 utility library for Fetan data/indexing code. It contains column-index primitives built on Apache Arrow expressions and CRoaring, an adaptive radix tree for byte keys, row-wise hashing utilities, and small memory/buffer helpers backed by Arrow's memory pool.

Development is dev-container first. New joiners only need Git, Docker, and an editor with Dev Containers support. Do not install the project C++ dependencies on the host machine.

Clone with submodules:

git clone --recurse-submodules <repo-url>
cd fetan

Open the repository in VS Code and run Dev Containers: Reopen in Container. Inside the container:

cmake --preset dev-debug
cmake --build --preset dev-debug
ctest --preset dev-test

The full onboarding and troubleshooting guide is in docs/development.md.

The demos/ targets show how the library primitives can be composed into simple in-memory columnar worker behaviors. They are intentionally single-threaded, RAM-only examples rather than new persistent storage or worker runtime APIs. See demos/README.md for the use-case walkthroughs.

cmake --build --preset dev-debug --target fetan_ingest_upsert_demo
cmake --build --preset dev-debug --target fetan_group_by_demo

.build/dev-debug/demos/fetan_ingest_upsert_demo
.build/dev-debug/demos/fetan_group_by_demo

• fetan::aggregates::ColumnIndex and ColumnPredicateEvaluator for evaluating a subset of Arrow compute expressions against per-column indexes.
• Dictionary and boolean column indexes backed by CRoaring bitmaps.
• Factorized bitmap helpers for numeric, date, and timestamp-style values.
• fetan::util::ArtIndex, an adaptive radix tree that maps arbitrary byte strings to stable integer ids.
• fetan::util::Hasher, an xxHash64-based row-wise hasher for column-major fixed-width data.
• fetan::util::MemoryManager and simple RAII buffers using 64-byte aligned Arrow memory-pool allocations.
• AVX2 helper routines used by the hashing and low-level utilities.

.
├── CMakeLists.txt          # Top-level CMake project
├── CMakePresets.json       # Configure/build/test presets
├── src/                    # Library sources and public headers
├── tests/                  # GoogleTest-based unit tests
├── demos/                  # Small executable examples
├── external/               # CPM helper and vendored Abseil submodule
├── toolchains/             # Dev container image and Arrow build script
└── docs/                   # Developer documentation

The dev container provides the project toolchain and libraries:

• CMake 4.3
• Ninja
• Debian 13/trixie
• Clang 22, libc++, and lld
• GDB, LLDB, Valgrind, and ccache
• Codex CLI through the OpenAI ChatGPT VS Code extension
• Apache Arrow 24 C++ installed under /usr/local
• CRoaring 4.7, Asio 1.38, GoogleTest 1.17, and Google Benchmark 1.9.5 prepared under /opt/fetan-deps
• Abseil from the external/abseil-cpp submodule

Host machines should only need Git, Docker, and the editor/dev-container client.

The library is intentionally a small collection of primitives. It does not own table semantics, query planning, scheduling, persistence, or concurrency. Those concerns are expected to live in the caller.

Column indexes live in fetan::aggregates and are designed around Arrow ArrayData, Arrow compute expressions, and CRoaring row-id sets. ColumnIndexFactory::Make builds an index for an Arrow data type and a ColumnIndexType (DICTIONARY, VALUE, or RANGE).

The implemented index families are:

• DictionaryIndex: dictionary-style indexes for string-like values, integer values, dates, times, and timestamps through the factory. Duration templates are instantiated, but the factory visitor does not currently route duration types.
• BinaryIndex: a compact true/false/null index for boolean columns.
• ValueIndex and RangeIndex: declared/scaffolded, but their main operations currently return NotImplemented.

CRoaring is the external compressed set container used by this library. A single roaring::Roaring represents a set of 32-bit unsigned integers. In this codebase those integers are row ids.

The Roaring format splits each 32-bit integer into:

uint32 value = [high 16-bit key][low 16-bit value]

The high 16 bits select a container. The low 16 bits are stored inside that container. CRoaring chooses among compact container encodings such as array containers for sparse sets, bitset containers for dense sets, and run containers when run optimization is applied. The serialized Roaring format is defined externally by the Roaring project; fetan uses the CRoaring C++ API and does not reimplement this container format.

Important properties for callers:

• Row ids are uint32_t values.
• Iteration is in sorted integer order.
• AND, OR, and other set operations are implemented by CRoaring over its internal containers.
• A roaring::Roaring is one compressed set. The factorized index below is a higher-level layout made out of many such sets.

See the upstream RoaringFormatSpec and CRoaring projects for the portable serialized format and implementation details.

DictionaryIndex<T> is the factorized bitmap encoding implemented by this library. It is not the CRoaring file/container format. It is a column-index layout that uses many roaring::Roaring objects as row-id components.

DictionaryIndex<T> stores a column in three logical layers:

Arrow value -> dictionary id -> factorized digit bitmaps -> row-id result

The factorized diagram above is only the data layout. Build and evaluation behavior is shown separately:

Storage notes:

The caller supplies row ids through the Add(array_data, rids) callback. This is important because the logical row id can differ from the physical Arrow offset. Nulls consume a row id but do not add that id to any value bitmap.

Dictionary ids are factorized by fetan::util::FactorizedBitmap. Its default component_width_bits = 4 splits each dictionary id into 4-bit components, so each component has 1 << 4 = 16 possible digit bins.

The important idea is that the index does not allocate one bitmap per distinct Arrow value. Each distinct value first receives a compact dictionary id:

"CA" -> id 0
"NY" -> id 1
"TX" -> id 2
...

Then each id is split into component positions. Each component/digit pair is a shared bin. With 4-bit components:

id  2 -> component 0 digit 2
id 18 -> component 0 digit 2, component 1 digit 1
id 34 -> component 0 digit 2, component 1 digit 2

All ids whose low 4-bit digit is 2 share the same component-0/digit-2 bitmap. The next component separates 18 from 34, and a range/end marker separates 2 from ids such as 18 that share the low digit but have more components.

FactorizedBitmap stores digit bins and range markers separately. The digit bitmap vector is indexed with a stride of 1 << component_width_bits, so the physical digit vector position is:

digit_bitmap_index = component * (1 << component_width_bits) + digit

Digits use 0..15 with the default 4-bit width. Range markers are stored in range_bitmaps_ by final component index. This distinguishes ids with the same low digit but different component length:

id 2  -> digit c0=2, range component 0
id 18 -> digit c0=2, digit c1=1, range component 1

Build procedure:

When a non-null value is added, DictionaryIndex<T>::Add does the following:

1. Normalize the Arrow value into an owned key.
2. Look up or assign its dictionary id.
3. Decompose that id into fixed-width bit components.
4. Add the row id to one bitmap per digit component.
5. Add the row id to the range marker for the final component count.

For id 18, row r is added to:

bitmap[c0,2]
bitmap[c1,1]
range_bitmap[1]

This is the binning/factorization step: each component-digit pair is a reusable bin that many dictionary ids can share.

Lookup procedure:

Lookup intersects each digit bitmap plus the range marker:

equal(value_with_id_18)
  = bitmap[c0,2] AND bitmap[c1,1] AND range_bitmap[1]

is_in evaluates each value lookup and unions the resulting Roaring sets.

Why this helps high-cardinality data:

A direct dictionary-backed column index would allocate one full bitmap per distinct value. If a string column has 1,000,000 distinct values, that shape can require up to 1,000,000 separate value bitmaps.

The factorized layout creates bitmaps for digit bins instead. With the default 4-bit component width, ids below 1,000,000 need at most five digit components and five possible range markers. Each digit component has 16 slots, so the layout needs on the order of:

5 components * 16 digit slots + 5 range markers = 85 bitmaps

instead of one bitmap per distinct value. Each row is stored in several shared bitmaps rather than in one value-specific bitmap. A point lookup reconstructs the exact row set by intersecting the relevant bins. This is exact, not a Bloom filter-style approximation, because the range marker is part of the intersection.

This is a space/query tradeoff. Storage grows with the number of digit components needed for the assigned dictionary ids, not directly with the number of distinct values. Higher cardinality creates more components as ids become longer; point lookup does more intersections. Inserts also touch multiple bitmaps per row. The payoff is that many high-cardinality values can share a small set of component bitmaps while still supporting exact equality lookup.

BinaryIndex is simpler: it stores one bitmap for true, one bitmap for false, and omits nulls. If all indexed values are the same boolean, lookup can return a scalar true or false result instead of materializing a set.

Index lookups return std::variant<roaring::Roaring, bool>, surfaced as RowIdSelection by the evaluator:

bool true    -> every row in the caller's range matches
bool false   -> no row matches
Roaring set  -> only these row ids match

This lets simple all-match/no-match predicates stay cheap while selective predicates return compressed row-id sets.

ColumnPredicateEvaluator evaluates a focused subset of Arrow compute expressions over the available column indexes:

• and
• or
• equal
• is_in

ColumnPredicateEvaluator::Make(schema, expression) converts the Arrow expression into a reverse-polish syntax vector. During Eval, field references select a column index, literals become lookup datums, and logical operators combine intermediate row-id sets with CRoaring AND and OR.

The main performance shape is:

hash lookup for the literal value
copy/intersect/union compressed row-id sets
materialize rows later, only if the caller needs them

fetan::util::ArtIndex maps arbitrary byte strings to stable monotonically assigned ids. Repeated IndexOf calls with the same key return the same id, and ValueOf retrieves the original key bytes by id.

The layout diagram above shows only the in-memory records. Lookup and insertion behavior is shown separately:

The ART is useful when a caller wants to intern variable-width keys before using compact integer ids in side tables, aggregate state, or row-position maps. Keys may be empty and may contain embedded NUL bytes; they are treated as byte sequences, not C strings.

The public calls take raw pointer plus explicit length:

IndexOf(bytes, len)  -> existing id or newly assigned id
FindIndex(bytes,len) -> existing id or 0
ValueOf(id)          -> original bytes

Ids start at 1; 0 is reserved as the not-found/null value.

Every child slot is an ArtNodePtr, a single std::uintptr_t with a 3-bit tag in the low bits:

bits = pointer | tag       for nodes
bits = (id << 3) | kValue  for leaves

The tag table is:

0 Null
1 Node4
2 Node16
3 Node48
4 Node256
5 Value

Pointer storage checks that the raw node pointer has its low 3 bits clear. The library memory path uses 64-byte aligned allocation, which satisfies that contract and also keeps node starts cache-line friendly.

The implementation uses the standard ART node growth pattern:

• Node4
• Node16
• Node48
• Node256

All node variants share this header:

int32 partial_len
int32 num_children
ArtNodePtr terminal
uint8 partial[8]

partial stores up to eight bytes of compressed path prefix. partial_len may be larger than eight; the inline prefix is used to accelerate the common match, and the leaf table is used when a full comparison is needed.

The terminal slot is what makes prefix keys safe. For example, inserting "a" and "ab" does not require a sentinel child. The "a" value lives in the terminal slot of the node reached at depth 1, and "ab" continues through the child byte 0x62.

Leaf storage is split between an inline representation for small keys and heap buffers for larger keys. Heap buffers are allocated through the library memory helpers and support oversized keys with dedicated contiguous allocations. The result is a compact structure for many short keys while preserving byte-for-byte round trips for larger values.

Leaf records are 16-byte entries in LeafTable:

inline leaf:
  int32 size
  uint8 data[12]

spilled leaf:
  int32 size
  uint8 prefix[4]
  int32 buffer_index
  int32 offset

The table allocates inline pages of 64 * sizeof(Leaf) bytes. Small keys stay inside the leaf record. Larger keys keep a short prefix in the leaf and store their full bytes in HeapBuffer. This gives lookup a cheap prefix check while still allowing exact byte-for-byte validation through Match, LCP, and ValueOf.

ArtIndex is an in-memory, single-process structure. It does not provide thread safety, persistence, MVCC, or deletion semantics.

fetan::util::Hasher computes one xxHash64 value per row over column-major fixed-width input buffers. It is a helper for callers that need row grouping, deduplication buckets, or hash-table probes over Arrow-style fixed-width columns.

The hasher layout diagram shows stored metadata and buffers. Hash execution is shown separately:

The input contract and logical row mapping are summarized here:

The constructor receives the number of 64-bit, 32-bit, 16-bit, and 8-bit input columns:

Hasher(num_64bit_columns, num_32bit_columns, num_16bit_columns,
       num_8bit_columns)

Hash(num_rows, offset, data, hash, memory_mgr) receives raw column pointers and a caller-provided output buffer, then writes one uint64_t hash per row.

Layout notes:

The memory shape is column-major:

col0: v0 v1 v2 v3 ...
col1: v0 v1 v2 v3 ...
out : h0 h1 h2 h3 ...

This matches Arrow fixed-width buffers. The hasher conceptually builds this row byte stream:

row i = [all 8-byte values][all 4-byte values][all 2-byte values][all 1-byte values]

but it does not allocate that row object. The limits vector and generated function vectors store the mapping from logical row offsets back to physical column pointers.

Execution notes:

Construction computes the read plan. Each generated read function knows which source column and byte offset to load for an 8-byte, 4-byte, or 1-byte xxHash step.

For wide rows (Length() >= 32), the implementation allocates four temporary state arrays through MemoryManager and follows the four-lane xxHash64 shape. For narrower rows, it uses the shorter xxHash path. AVX2 builds use vector operations for the lane updates; scalar builds keep the same logical layout.

Hash values are bucket keys, not proof of equality. Callers must still compare the original key columns inside a bucket when correctness depends on exact equality.

fetan::util::MemoryManager wraps an Arrow MemoryPool and allocates 64-byte-aligned memory. SimpleBuffer, SimpleBitBuffer, and HeapBuffer provide RAII wrappers used by the index and hashing code.

The 64-byte alignment is intentional:

• it fits common cache-line and SIMD access patterns;
• it supports aligned AVX state buffers in hashing code;
• it allows internal low-bit pointer tagging in structures that validate pointer alignment before storing tagged pointers.

SimpleBuffer<T> owns a typed contiguous allocation. SimpleBitBuffer owns a zeroed byte buffer for bit-style scratch data. HeapBuffer provides chunked heap storage for variable-width data and dedicated contiguous buffers for oversized requests.

These helpers are still ordinary in-RAM buffers. They do not provide spilling, admission control, shared memory, or durable storage.

This project is an internal/common library rather than a standalone application. Some pieces are production-shaped, while others are still experimental:

• DictionaryIndex, BinaryIndex, ArtIndex, Hasher, and memory helpers have concrete implementations and tests or supporting utilities.
• ValueIndex and RangeIndex are declared and explicitly instantiated, but their operations are not implemented yet.
• tests/test_avx.cc contains AVX experiments and is not part of the current fetan_test target.