Insights from paper: DuckDB: an Embeddable Analytical Database
1. Abstract
Recently, SQLite has become very popular. So, what is SQLite?
SQLite is an in-process OLTP database.
The DuckDB team observed no solution for in-process OLAP space.
The team created DuckDB, a novel embedded data management system to execute analytical SQL queries.
The paper also discusses a demonstration.
The demo compares DuckDB and other data management solutions and showcases their performance in the embedded analytics scenario.
2. Introduction
Most Data management systems are large monolithic database servers running as stand-alone processes.
Some data management systems have a completely separate use case. It involves running a database system as a linked library in the host process.
The most well-known representative of this use case is SQLite. It is the most widely deployed SQL database engine, with more than a trillion databases in active use.
SQLite strongly focuses on transactional (OLTP)workloads. Its row-based execution engine operates on a B-tree storage format. So, its performance on analytical (OLAP) workloads is inferior.
There is a clear need for embeddable analytical data management. There are two reasons for this.
Interactive data analysis is performed using tools such as R or Python. These environments' extensions (dplyr and panda) lack full-query optimization and transactional storage.
Embedded analytical data management is also desirable for edge computing scenarios.
This team initially developed MonetDBLite, an embedded analytical system derived from the MonetDB system.
The team identified the following requirements for embedded analytical databases:
High efficiency for OLAP workloads without completely sacrificing OLTP performance
The high degree of stability
Efficient transfer of tables to and from the database
Practical portability
DuckDB is a new purpose-built embeddable relational database management system. It is available as Open-Source software under the MIT license.
3. Design and Implementation
DuckDB has logically separated components, such as the parser, logical planner, optimizer, physical planner, and execution engine. From the system’s point of view, it has transaction and storage managers.
DuckDB does not have a client protocol interface or a server process. It is accessed using a C/C++ API.
DuckDB also provides an SQLite compatibility layer. This layer helps allow applications that previously used SQLite to use DuckDB through re-linking or library overloading.
The SQL parser is derived from Postgres’ SQL parser but stripped down. It inputs an SQL query string and returns a parse tree of C structures. This parse tree is then immediately transformed into C++ classes.
The logical planner consists of the binder and the plan generator.
The binder resolves all expressions referring to schema objects, such as tables or views, with their column names and types.
The logical plan generator transforms the parse tree into a tree of basic logical query operators such as scan, filter, project, etc.
The DuckDB’s optimizer optimizes join order using dynamic programming with a greedy fallback for complex join graphs. A set of rewrite rules simplifies the expression tree. Cardinality estimation is done using a combination of samples and HyperLogLog.
The physical planner transforms the optimized logical plan into the physical plan.
DuckDB uses a vectorized interpreted execution engine. DuckDB uses vectors of a fixed maximum amount of values.
Fixed-length types, such as integers, are stored as native arrays. Variable-length values, such as strings, are represented as a native array of pointers in a separate string heap.
DuckDB contains an extensive library of vector operations that support the relational operators.
The execution engine executes the query in a Vector Volcano model.
DuckDB provides ACID compliance through Multi-Version Concurrency Control (MVCC). The team implemented HyPer’s serializable MVCC variant tailored specifically for hybrid OLAP/OLTP systems.
DuckDB uses the read-optimized DataBlocks storage layout for persistent storage.
Logical tables are horizontally partitioned into chunks of columns. The columns are compressed into physical blocks using lightweight compression methods. Blocks carry min/max indexes for easy filtering.
4. Demonstration Scenario
The team described a demonstration to highlight the two benefits of DuckDB:
The ability to process large data sets on restricted hardware resources
The benefit of embedded operations
The demonstration is set up on a table with a screen, a large dial, and four identical benchmark computers.
Each computer runs a different DBMS: SQLite, MonetDBLite, HyPer, and DuckDB.
Each database is pre-loaded with the TPC-H benchmark tables.
The screen shows real-time metrics from all four benchmark computers.
The team showcased two demonstration scenarios, a teaser and a drill-down.
For the teaser scenario, a suitable query is pre-configured, and the user can increase or decrease the amount of data read from the fact tables.
For the drill-down scenario, the users propose that their query be configured. They can increase or decrease the amount of data read by the query.
5. Current Steps and Next Steps
DuckDB runs all TPC-H queries for performance.
As for paper writing, two TPC-DS queries are unavailable for performance comparison.
The DuckDB team is working on completing the DataBlocks storage scheme and subquery folding.
The implementation of a buffer manager is a work in progress.
The team plans to implement a work-stealing scheduler to balance resources between short and long-running queries.
References
MonetDB/X100: Hyper-Pipelining Query Execution
Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems
Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation