DOCSEARCHbyAlgolia
Submit Docs

HeavyDB Documentation

repository·master·Indexed 25 days ago

https://github.com/heavyai/heavydb

HeavyDB is an open-source, SQL-based, relational, columnar database engine designed for high-performance querying of multi-billion row datasets using CPU and GPU parallelism. This documentation covers benchmarking tools including the Conbench client, TPC-DS comparison via Rake, and Python-based scripts such as run_benchmark.py and run-benchmark-import.py for performance and import testing.

Tokens
39.2K
Snippets
91
Records
236
Agent score
85%

What's inside HeavyDB

  1. Overview of WARPCORE hashing data structures

    master

    WARPCORE is a framework for creating high-throughput, purpose-built hashing data structures on CUDA-accelerators. It supports key types std::uint32_t and std::uint64_t along with any trivially copyable value type.

    Available data structures include:

    • SingleValueHashTable: stores key-value pairs
    • HashSet: stores a set of keys
    • CountingHashTable: tracks occurrences of inserted keys
    • BloomFilter: pattern-blocked bloom filter for approximate membership queries
    • MultiValueHashTable: stores a multi-set of key-value pairs
    • BucketListHashTable: alternative variant of MultiValueHashTable
    • MultiBucketHashTable: alternative variant of MultiValueHashTable

    The library provides modular components for customization, including hash functions, probing schemes, and data layouts.

  2. Understand HeavyDB Data Flow and Input Loading

    master

    HeavyDB query execution follows a transformation model where the Executor acts as the central component. Data flows from physical storage through a memory hierarchy to the execution device (e.g., a GPU).

    Input Data Loading

    Input requests are initiated by the Executor via the ColumnFetcher class. The loading process depends on the type of input:

    1. Physical Tables: Data is loaded from the storage layer through a buffer manager hierarchy. The request flows through the following layers until the required chunk is found or loaded:
      • GPU Buffer Mgr (terminates if data is already on GPU)
      • CPU Buffer Mgr
      • File Mgr (storage layer)
    2. Intermediate Results: Data is loaded directly from a per-query temporary tables map and transferred to the GPU via the Data Mgr.

    Output Data Management

    Query step outputs are managed by the ResultSet class. To ensure data validity, HeavyDB uses a RowSetMemoryOwner helper structure to manage the lifetime of all outputs related to a specific query. The ResultSet holds a shared pointer to the RowSetMemoryOwner, guaranteeing that the data remains valid until the ResultSet object is destroyed.

  3. Understand HeavyDB Query Execution via DAG

    master

    HeavyDB executes queries by interpreting an optimized relational algebra tree provided by Calcite. This tree is converted into a Directed Acyclic Graph (DAG) where each node (excluding RelTableScan and RelJoin) represents a query step.

    Execution follows these principles:

    • Execution Order: Determined by performing a topological sort over the DAG to ensure dependencies are met.
    • Step Dependencies: Each step is executed in order, making the results of previous steps available to subsequent steps.
    • Special Nodes: Scan and Join nodes are not executed as independent steps; they are automatically rolled into the next node during work unit generation.

  4. Understand the HeavyDB columnar data model

    master

    HeavyDB uses a columnar data organization where data is structured into two primary hierarchical components:

    1. Columns: The fundamental unit of storage, where data is organized by attribute rather than by row.
    2. Fragments: A horizontal partitioning mechanism that stripes across rows.
    3. Chunks: The intersection of a specific column and a specific fragment. Chunks represent the actual storage units for a subset of data within a column.

  5. Understand the HeavyDB DAG Builder and Optimizer

    master
    HeavyDB uses RelAlgDagBuilder and RelAlgOptimizer to transform the optimized relational algebra (RA) tree received from Calcite into a HeavyDB-specific Directed Acyclic Graph (DAG). This DAG is constructed using HeavyDB data structures and then undergoes several optimization passes to improve query execution efficiency.

  6. Understand the ResultSet and ResultSetStorage data model

    master

    HeavyDB uses the ResultSet class to drive all result set processing, including reduction, iteration, lazy fetch, string dictionary lookups, and serialization (Enterprise Edition only).

    Each device output is a ResultSet object, but the actual data is managed by an underlying ResultSetStorage object. ResultSetStorage is responsible for:

    • Managing output buffers (stored as a flat byte stream for efficient CPU/GPU transfer).
    • Storing metadata about initialization values and projected targets.
    • Providing low-level driver methods for reductions.

    To determine specific buffer layouts, the system uses a QueryMemoryDescriptor (generated during code generation) which encodes target information such as the number of targets and their physical and logical sizes.

  7. Understand HeavyDB memory hierarchy and slab allocation

    master

    HeavyDB uses a BufferMgr hierarchy to manage data movement. Data follows a specific path: Disk $\rightarrow$ CPU $\rightarrow$ GPU. Data cannot be loaded directly from disk to the GPU.

    Memory is managed by the DataMgr using slabs:

    • CPU Memory: Allocated in 4GB slabs.
    • GPU Memory: Allocated in 2GB slabs.

    When requesting memory (for input chunks, query parameters, or output buffers), the DataMgr finds the first available space in an existing slab. If no space is available, a new slab is allocated.

    Key characteristics:

    • Alignment: All top-level allocations are aligned to a 512-byte boundary (slabs are divided into 512-byte pages).
    • Eviction: The system uses a last-recently used (LRU) caching mechanism based on access counters. Buffers can be pinned to a slab to prevent them from being evicted.

  8. Understand the HeavyDB Query Engine architecture

    master

    The HeavyDB Query Engine manages query kernel compilation and execution. It consists of two primary layers:

    1. RelAlgExecutor: Manages the overall query state and the execution of relational algebra (RA) query steps.
    2. Executor: Manages code generation and execution for individual query steps. It takes a WorkUnit as input and returns a ResultSet.

    The engine supports complex multi-step queries (such as joins on subquery results) and can execute queries on either the CPU or the GPU.

  9. Understand Hash Join execution in HeavyDB

    master

    HeavyDB uses hash joins to accelerate SQL join queries by replacing the inner loop of a standard loop join with a hash table lookup.

    • Loop Joins: A slow $O(n^2)$ technique where the inner table is rescanned for every row in the outer table.
    • Hash Joins: A faster $O(n)$ technique where the inner table is scanned once to build a hash table, allowing for efficient lookups.

    Note: If there is insufficient memory to build a hash table, HeavyDB may automatically fall back to a loop join.

  10. Understand HeavyDB Code Generation architecture

    master

    HeavyDB uses the LLVM library to generate native code for queries. The process is managed by the Executor object assigned to a query, and the state is stored in a QueryCompilationDescriptor.

    Key Components

    • QueryCompilationDescriptor: Initiates code generation via its .compile() method.
    • Executor: Manages the code generation process for a query.
    • CodeGenerator: Converts analyzer expressions into LLVM IR using the context and module from the code generation state.
    • Kernel Structure: A typical kernel consists of two functions:
      • query_func: Loops over all input rows.
      • row_func: Contains the logic for processing inputs, running expressions, and writing outputs.
    • Code Cache: Generated CPU and GPU code is cached per query using an LRU (Least Recently Used) eviction mechanism. The cache key is the serialized LLVM representation of the query_func.

  11. Understand the Calcite Parser integration in HeavyDB

    master

    HeavyDB uses Apache Calcite to handle SQL query string parsing and cost-based optimization.

    Key aspects of this integration include:

    • Relational Algebra Generation: Calcite converts SQL queries into extended relational algebra, returning a relational algebra tree serialized as a JSON string.
    • Node Types: The generated Directed Acyclic Graph (DAG) typically consists of Scan, Filter, Project, Aggregate, and Join nodes.
    • Cost-Based Optimization: Calcite applies high-level transformations (such as filter pushdown through joins) to the relational algebra based on query patterns and statistics. These complement HeavyDB's low-level optimizations like operator fusion.
    • Extensibility: Calcite allows for the specification of additional runtime functions (e.g., trigonometric functions for geospatial projections) which are treated as first-class citizens with proper type checking.

  12. Understand HeavyDB Query Execution and Parallelism

    master

    HeavyDB executes query steps in parallel using fragments as the smallest unit of parallelism. The execution flow involves:

    1. Fragment Assignment: The QueryFragmentDescriptor partitions fragments among available devices (CPU threads or GPUs).
    2. Kernel Launch: An ExecutionKernel is assigned to fragments/groups and launched asynchronously via a thread pool.
    3. Device Execution: Each device (GPU or CPU thread) has a dedicated CPU thread.
      • CPU: Execution within a single device is serial.
      • GPU: Execution within a device occurs in parallel.
    4. Result Aggregation: Results are stored in ResultSet objects. Once all devices finish, these are reduced into a single ResultSet returned to the caller.

    Input Data Assignment: Input fragments are typically assigned in round-robin order. If input data is sharded, all shards with the same key are assigned to the same device.