From SQL to Key-Value: The SaarDB Transformation

Building a database from the ground up involves dissecting familiar query languages and reassembling them into a fundamentally different operational paradigm. In the sixth installment of the SaarDB development blog, the focus shifts to a critical transformation: how structured SQL queries are translated into the simpler, yet powerful, key-value operations that underpin SaarDB's architecture. This process is not merely a syntactic translation; it's a deep dive into the semantic interpretation of database commands and their efficient execution within a non-relational data model.

The previous installment, Part 5, successfully introduced a SQL parser. This parser takes human-readable SQL statements and converts them into an Abstract Syntax Tree (AST) – a structured representation of the query's logic. For example, an `INSERT` statement like:

INSERT INTO payments VALUES (500, 'payment_1', 'pending', 1)

is transformed into a Go struct, effectively capturing the intent and data within the query:

InsertIntoTable{
    TableName:    "payments",
    ColumnValues: []string{"500", "payment_1", "pending", "1"},
}

This AST serves as the intermediary, bridging the gap between the declarative nature of SQL and the operational commands SaarDB needs to perform. The challenge now is to take these structured representations and map them onto SaarDB's underlying key-value store.

Deconstructing SQL Operations for Key-Value Stores

SQL, a declarative language, specifies *what* data to retrieve or modify, not *how* to do it. Key-value stores, on the other hand, operate on simple `GET`, `PUT`, and `DELETE` operations based on unique keys. The translation process must therefore infer the necessary key-value operations from the SQL AST.

Handling `INSERT` Operations

For an `INSERT` statement, the AST provides the table name and the values to be inserted. In a key-value store, each row typically needs a unique identifier to serve as its key. SaarDB must generate or derive this key. If the table schema defines a primary key, that column's value from the `INSERT` statement becomes the key. If not, SaarDB might generate a unique ID. The value associated with this key would be a serialized representation of the entire row's data. This serialization could be JSON, Protocol Buffers, or another format, ensuring that all column values are stored together, ready to be retrieved later.

Consider the `INSERT` example: `INSERT INTO payments VALUES (500, 'payment_1', 'pending', 1)`. If `500` is the primary key for the `payments` table, SaarDB would construct a `PUT` operation. The key would be `payments:500` (using a common convention to include the table name for namespacing), and the value would be a serialized representation of `{'payment_1', 'pending', 1}` (excluding the primary key itself, as it's part of the key). The AST's `InsertIntoTable` struct directly informs this:

Diagram illustrating the mapping of SQL INSERT INTO statement to key-value PUT operation

Translating `SELECT` Queries

`SELECT` queries present a more complex challenge. A simple `SELECT * FROM payments WHERE id = 500` translates relatively straightforwardly. The `WHERE` clause directly informs the key to be fetched. The AST's `SelectFromTable` struct, with its `TableName` and `Filter` (e.g., `id = 500`), would guide SaarDB to perform a `GET` operation. The key would be constructed as `payments:500`.

However, `SELECT` queries involving multiple rows, aggregations (`COUNT`, `SUM`, `AVG`), joins (if supported), or complex filtering become significantly more intricate. Since a pure key-value store doesn't natively support these operations across arbitrary data, SaarDB must simulate them. This often involves fetching multiple values based on a pattern or range of keys, deserializing them, and then performing the aggregation or filtering in memory or through intermediate processing steps. For instance, a `SELECT COUNT(*) FROM payments` would require SaarDB to iterate through all keys starting with `payments:` (or a similar prefix), count the number of corresponding values, and return that count. This is fundamentally different from a relational database's optimized index scans.

Managing `UPDATE` and `DELETE`

`UPDATE` operations also rely on identifying the correct key. An `UPDATE payments SET status = 'completed' WHERE id = 500` would involve fetching the existing record using `payments:500`, deserializing its data, modifying the `status` field, re-serializing the updated data, and then performing a `PUT` operation to overwrite the old value with the new one. This read-modify-write cycle is a common pattern when implementing update semantics on key-value stores.

`DELETE` operations are the most direct translation. A `DELETE FROM payments WHERE id = 500` translates directly to a `DELETE` operation on the key `payments:500`. The AST's `DeleteFromTable` struct, specifying the table and the condition, directly maps to this. If the `DELETE` statement has no `WHERE` clause (which is typically disallowed in standard SQL for safety but might be possible in custom implementations), it could imply deleting all records associated with a table prefix, a potentially very expensive operation.

The Role of the Query Planner

The translation from an AST to specific key-value operations is the domain of the query planner. SaarDB's query planner analyzes the parsed SQL query (the AST) and determines the most efficient sequence of key-value operations. For complex queries, this might involve:

  • Key Generation Strategy: Deciding how to form keys for `PUT` and `GET` operations, incorporating table names and primary keys.
  • Data Fetching: Identifying which keys need to be fetched for `SELECT` and `UPDATE` statements. This could involve prefix scans or fetching individual keys.
  • In-Memory Processing: For queries that cannot be directly mapped to single key-value operations (e.g., aggregations, `ORDER BY`), the planner must devise a strategy to fetch necessary data and process it client-side or on the server.
  • Transaction Management: If SaarDB supports transactions, the planner must also ensure that sequences of operations are correctly ordered and atomic.

This translation layer is crucial. It abstracts the complexities of the underlying key-value store from the user, allowing them to interact with SaarDB using the familiar SQL interface. The efficiency of the query planner and its ability to optimize these translations directly impact SaarDB's performance and scalability.

Challenges and Future Directions

The primary challenge in this translation lies in bridging the semantic gap between relational algebra (which SQL queries are based on) and the simple key-value model. Operations that are native and highly optimized in relational databases (like joins or complex aggregations) require significant emulation in a key-value system. This can lead to performance bottlenecks if not handled carefully. For instance, emulating a join might involve multiple `GET` operations to fetch related data from different