One-sentence Summary

Imperial College London proposes BOSS, an architecture for database kernel composition built on partial query evaluation and a unified exchange format for query plans and data that connects components such as Apache Arrow, ArrayFire, and Velox into a hybrid DMS achieving significant performance gains over CPU-only Velox and outperforming GPU-only HeavyDB on some queries.

Key Contributions

• A composable database architecture connects separately designed storage, processing, and planning components through partial query evaluation and a unified exchange format for query plans and data.

• The architecture is instantiated in BOSS, a relational data management system that integrates Apache Arrow storage, the GPU-accelerated ArrayFire kernel, and the CPU-oriented Velox kernel while supporting runtime-opportunistic operator offloading in a full system.

• Evaluation shows the architecture is virtually overhead-free, BOSS improves performance over CPU-only Velox, and BOSS outperforms the highly optimized GPU-only HeavyDB on some queries.

Introduction

Modern data management systems now cover the full data lifecycle, supporting transactional and analytical workloads, data cleaning, model training, graph, JSON, and key value data, and specialized hardware such as CPUs, GPUs, Smart Storage Devices, FPGAs, TPUs, and other ASICs. This matters because applications increasingly need one extensible platform that can exploit heterogeneous resources without hand building specialized systems for every workload or device.

Prior approaches face a tradeoff: extending a DMS kernel can deliver performance but requires heavy engineering and usually supports only narrow parts of heterogeneity, while wrapping libraries in UDFs is easier but often slows execution. Composable designs reduce development effort, yet combining kernels is still difficult because they use different execution models, APIs, state management, metadata handling, and data exchange formats.

The authors leverage partial query evaluation to compose database kernels as a pipeline. They pass the query, including data and code, through stages in a unified in memory representation, allowing each kernel to evaluate as many operators as it benefits from and leaving the rest for later kernels. They also introduce a unified physical format and a compile time programming framework with a type system, domain specific language, and memory management model to integrate kernels with minimal boilerplate and little runtime overhead. They demonstrate this by composing Apache Arrow, Velox, and ArrayFire into a full analytics system with performance comparable to monolithic designs.

Dataset

• The authors provide the source code, data, and related artifacts through the project repository at https://github.com/lsds/MultiKernelBOSS.
• The provided text does not specify the dataset composition, subset sizes, data sources, filtering rules, schema, statistics, cropping strategy, metadata construction, or training split and processing details.

Method

Composable Engine Architecture and Partial Query Evaluation

The authors leverage a composable data management architecture that avoids a single monolithic query kernel. Instead, query processing is fragmented into engines that can be independently designed, integrated, or adopted from existing systems. Each engine accepts a query expression and returns another query expression that is semantically equivalent to the input but closer to the final result. Formally, each engine $E_i$Ei​ maps $Q_i$Qi​ to $Q_{i+1}$Qi+1​ while preserving query semantics, and the pipeline continues until the final expression contains no residual operators to evaluate.

SQL is intentionally not used as the intermediate representation because text-based manipulation introduces parsing, transformation, and serialization overhead. Instead, the framework uses a unified in-memory representation for data and code. This allows engines to exchange relational data, predicates, table symbols, and partial plans with minimal conversion cost. The staged query-evaluation flow is shown in the figure below:

The framework is guided by four design principles. First, it remains unopinionated, meaning it does not force a fixed execution model, memory model, concurrency model, or physical data layout on kernels. Volcano-style processors, vectorized kernels, just-in-time compiled engines, and bulk-processing kernels can therefore be integrated under the same interface. Second, it minimizes boilerplate, which is critical because kernel wrappers often require large amounts of code for data conversion, transfer scheduling, ownership control, and result handling. Third, it targets zero copies and minimal transformations by exploiting the fact that many high-performance kernels already represent bulk data as C-style arrays. Fourth, it follows a language-over-library principle: orchestration is expressed directly in the host programming language rather than through heavyweight runtime libraries, enabling compiler optimizations such as inlining, loop unrolling, and vectorization across kernel boundaries.

At the lowest level, the framework uses an extensible closed-world dynamic type system. This system extends a standard tagged union representation with a compile-time configurable set of atom types. A minimal core can include types such as booleans, integers, floating-point values, and strings, while a kernel-specific extension can add tensor objects, GPU memory buffers, or other specialized data carriers. Because the full type set is fixed for a given executable, the compiler can generate static dispatch code while still supporting kernels that need custom internal types. This avoids the global rigidity of a fixed type system while preventing unbounded runtime type flexibility.

For bulk data exchange, the framework uses memory-managed spans. A span is a thin wrapper around a C-style array and does not impose a particular ownership scheme. Its deallocation behavior is defined by a function pointer and an opaque payload. When a span is destroyed, that function can release an underlying array, unmap a file, decrease a reference count, or perform no action if the span merely borrows memory. Spans are designed as move-only types, so ownership transfer is explicit and compiler-enforced. A span used after a move can trigger a compilation warning or error, which keeps the ownership model simple and reliable without introducing pervasive reference counting.

Data, code, plans, and dynamic behaviors are unified through semi-statically typed expressions. These expressions generalize symbolic expressions with three argument categories: statically typed arguments, dynamically typed arguments using the closed-world atom system, and span arguments that represent collections of identically typed elements. An expression has a symbolic head and can represent values, columns, relations, operators, or unevaluated plan fragments. The API provides both a slow unified path that exposes all arguments as dynamic atoms and a fast path that gives direct access to static arguments and spans. This supports both correctness-critical plan manipulation and performance-critical processing loops.

Structural changes to expressions avoid expensive copies through destructive decomposition. Because expressions may contain move-only spans, they are also non-copyable and move-only. However, an expression that is no longer needed can be decomposed into its head, static arguments, dynamic arguments, and spans. The resulting tuple can then be reassembled into a new expression with modified structure. This pattern allows operations such as projections, column removals, and plan rewrites to update expression structure without copying the underlying column arrays.

To reduce wrapper complexity, the framework synthesizes kernel interaction code through semi-static dispatching. Kernels often need generic operators that work over many static types, but C++ does not provide full dynamic dispatch for static template expansion. The framework instead restricts the type universe at compile time and expands type-specific code paths ahead of time. At runtime, dynamic expression arguments are checked against the known static type parameters. If the types match, the framework moves the data into a statically typed operator invocation with zero unnecessary copies. If the types do not match, the expression is returned unchanged and passed to a later engine. This enables opportunistic kernel execution without requiring explicit operator assignment by the caller.

The framework also includes an embedded expression domain-specific language. In the host language, overloaded syntax constructs symbols and expressions concisely, reducing the verbosity of building columns, tables, predicates, and partial plans. This makes operator implementations more compact while preserving direct control over the underlying representation. The same abstractions support GPU, CPU, storage, and relational kernels without requiring each kernel to reinvent plan representation, transfer logic, or type dispatch code.

In the implemented system, BOSS combines three engines: an Apache Arrow based storage engine, an ArrayFire GPU engine, and a Velox CPU engine. The initial query is first processed by the storage engine, which substitutes table and column symbols with expressions containing the actual stored data. The GPU engine then opportunistically evaluates subexpressions that benefit from GPU acceleration. Finally, the CPU engine evaluates the remaining operators and returns the final result. No explicit assignment of operators to engines is required; the orchestration logic is simply the order of the engines in the pipeline. The staged execution trace is shown below:

The storage engine has two primary responsibilities. It loads relational data into memory using Apache Arrow columnar arrays, which are wrappers around C arrays. These arrays can be converted into BOSS spans by passing the raw pointer into the span constructor. To preserve lifetime safety, the Arrow array’s shared pointer is passed as the span’s destructor payload, ensuring that the underlying memory is released only when the span is destroyed. The storage engine also performs symbol substitution, replacing table identifiers with stored relational expressions. Because the storage engine owns the persistent data and outlives query execution, it can hand out non-owning spans without copying the column contents.

The storage layout differs from Arrow’s native relation-level partitioning. Apache Arrow groups data by partitions, where each partition contains a set of columns. BOSS instead adopts column-level partitioning, where each column is composed of multiple contiguous partitions. This layout simplifies column-wise manipulation and reduces structural redundancy, since column metadata does not need to be repeated for every partition. Conversion between the two layouts is performed through shallow transformation: the structural wrappers are reorganized, but the underlying data remains in place. The relation-level and column-level layouts and their zero-copy conversion are shown below:

The storage engine also handles compressed string dictionaries. Low-cardinality string columns are stored as integer keys that index a dictionary of unique strings. When the query contains string equality predicates, the storage engine rewrites those predicates so that downstream engines operate directly on integer keys. This avoids exposing string dictionary logic to the GPU and CPU relational engines. When results must be returned as strings, the storage engine wraps the output plan with a string lookup operator, converting keys back to dictionary values only where needed.

The CPU engine is built around Velox. Velox processes data in vectorized batches using decomposed column representations. The framework provides shallow conversions between BOSS spans and Velox flat vectors. Flat vectors can adopt ownership of memory, process it, and return ownership without copying. For row-oriented execution interfaces, multiple flat vectors are grouped into row vectors. The CPU engine translates BOSS expressions into Velox plan nodes using a recursive transformation. For example, a filter expression can be decomposed into its predicate and input relation, mapped to Velox filter nodes, and combined with value nodes constructed from converted row vectors. The CPU engine evaluates all residual operators that remain after earlier stages have partially executed the query.

The GPU engine uses ArrayFire as its tensor processing kernel. Relational operations are implemented only when they map efficiently onto ArrayFire operations. Simple projections may become no-ops that rename columns through destructive decomposition, while arithmetic projections use ArrayFire arithmetic functions. Selection predicates are evaluated as bit arrays on the GPU and converted into position lists. The GPU engine does not necessarily materialize the filtered relation immediately. Instead, it can leave a Gather operator that combines the original relation with the GPU-produced position list, allowing the CPU engine to complete the filtering later. This approach reduces cross-device transfer costs when not all predicates can or should be executed on the GPU.

GPU execution faces a hybrid evaluation problem. ArrayFire tensor objects are often lazy computational proxies, but initializing them with CPU data can eagerly transfer data to the GPU memory space. This creates an execution graph in which some operations are lazy and some data transfers are eager. To avoid unnecessary transfers, BOSS encapsulates eager GPU transfers inside closures. A closure atom can hold a deferred operation that will produce an ArrayFire array only when it is actually needed. During plan traversal, GPU-evaluable subexpressions are wrapped in these closures and passed downstream as atoms. If a later stage requires the GPU result, the closure is evaluated; otherwise, the transfer is never performed. This design is particularly important when GPU memory is limited or when some GPU transfers become unnecessary due to failures or pruning. The resulting hybrid lazy and eager evaluation graph is shown below:

Experiment

The evaluation uses the TPC-H benchmark across multiple scale factors to compare the proposed GPU-accelerated co-processing system with CPU-based and GPU-only database systems, while separately analyzing query plans, GPU memory constraints, and framework overhead. The experiments show that partial query evaluation across storage, GPU, and CPU engines improves performance for many typical analytical patterns and remains beneficial when data exceeds GPU memory, where fully GPU-based alternatives can fail or lose efficiency. Ablations and overhead measurements further indicate that zero-copy data exchange and fast-path expression handling are important for practical gains, whereas the orchestration framework itself adds little cost.