Building SaarDB, Part 7: SELECT Query

In Part 6, we saw that CREATE TABLE and INSERT are just PUT operations. Basis that, we can simply build SELECT queries, just by modelling it as GET operations, right? Well, not quite.

SELECT queries can be complex with multiple joins, aggregations and multiple WHERE conditions. Add to that, we can have multiple possible indexes to choose or even full-table scans if appropriate index is not present.

We will not start with tackling all possible problems, but focus on solving the simplest set of problems. The simplest problem is primary-key based lookup queries as those are just GET queries with key as the primary key itself.

After solving for primary-key based lookup, we will move to full-table scan to fetch all rows of a table. This is the next important step, because it is a brute force approach which is usually taken when we don't have the required set of indexes. If we are able to do a full-table scan, we can still return result for any SELECT query in a specific table even if that might not be optimal.

Primary Key Lookup

SELECT * FROM payments WHERE id = 5

During insert, we had already set the following key: _table:payments:5 as id was the primary-key.
After running the GET query, we just need to deserialise the schema based on the binary serialisation deserialisation contract we had agreed to while working on INSERT query.

Full-table Scan

SELECT * FROM payments

This is a fundamentally different problem compared to SELECT by primary key. We need every row in the table, but:

We do not have a list of all the primary keys of a table anywhere. Our KV store only supports GET by exact key. How do we scan an entire table?

Full-table Scan Approach 1: Maintain a Separate Key List

The first idea that comes to mind is to store a separate key primary_keys:payments containing a regular list or a sorted list of all primary keys: [1, 2, 3, 5, 7, ...].

On every INSERT, update this list. On SELECT *, read the list, then GET each key individually.

This sounds simple but has multiple shortcomings. Let us walk through them.

Updating a sorted list is O(N). To insert a new key into a sorted list of N keys, we need to find the insertion point and shift everything after it. With millions of rows, this becomes expensive for every single INSERT.

The list itself becomes a hot key. Every INSERT to the payments table writes to primary_keys:payments. Under concurrent writes, this single key becomes a bottleneck. Every transaction needs a write lock on it.

It does not scale. With 10 million rows, the list of primary keys alone is a massive value. Reading it into memory, deserializing it, then doing 10 million individual GETs is wasteful.

This approach was actually explored during development and explicitly discarded. It is worth showing the wrong path as the right solution is much more elegant.

Full-table Scan Approach 2: Prefix Scan

When we look at how the keys (rows) would be stored, we realise a clear pattern and a much more simpler, elegant and optimal solution:

_table:payments:1   → [row data]
_table:payments:2   → [row data]
_table:payments:5   → [row data]
_table:payments:7   → [row data]

Notice that both memtable and SSTable are sorted. This means that all rows (keys) for payments table would already be adjacent to each other.

We can just search for the first key which has the prefix as _table:payments: and then carry out a sequential scan till we encounter a different key. This approach solves the two areas which made our previous approach inefficient:

1. We don't need to store any additional list of primary keys. The required data already exists sequentially adjacent in both SSTable and memtable.
2. Since the data exists sequentially together, we get the performance benefit of sequential scans during reads instead of random scans. On the other hand, the previous approach required random scan for each GET query as the search for each key had to be done again explicitly even if we know that the keys are adjacent to each other.

We saw in the second blog that a key can reside either in memtable or in multiple SSTable files. And the priority order is memtable, then the SSTable files from newest to the oldest. Hence for carrying out a full-table scan, we require search through both memtable and SSTable.

Let's explore how this would be done in both SSTable and memtable:

Prefix Scan in SSTable

Recalling the SSTable Structure

In blog 2, we built SSTables with three parts: data blocks, an index block, and a footer block.

Data blocks hold the actual key-value pairs in sorted order. The index block holds one entry per data block: the first key of that data block and its byte offset. The footer holds the offset of the index block so we can find it.

Let's say the payments table has 8 rows. The SSTable would look like this:

Data block 0 (offset 0):
  _table:payments:1   → [row bytes]
  _table:payments:3   → [row bytes]
  _table:payments:5   → [row bytes]

Data block 1 (offset 512):
  _table:payments:10  → [row bytes]
  _table:payments:12  → [row bytes]
  _table:payments:15  → [row bytes]

Data block 2 (offset 1024):
  _table:payments:20  → [row bytes]
  _table:payments:25  → [row bytes]

Index block:
  _table:payments:1   → offset 0      (first key of block 0)
  _table:payments:10  → offset 512    (first key of block 1)
  _table:payments:20  → offset 1024   (first key of block 2)

The index block is what makes search efficient. Instead of reading the entire file, we binary search the index to narrow down which data block to start from.

How GET Uses the Index Block

getLowerBound(target, indexBlock) returns the index of the largest key less than or equal to the target. If all keys in the index are greater than the target, it returns -1.

Let's dry run GET _table:payments:12:

getLowerBound("_table:payments:12", index):

  _table:payments:1  ≤ _table:payments:12  → candidate
  _table:payments:10 ≤ _table:payments:12  → candidate (larger, preferred)
  _table:payments:20 > _table:payments:12  → too far

Returns index 1 → data block 1 (offset 512)

We jump to data block 1 and scan within it for the exact key. The logic is straightforward: since the index stores the first key of each block, a key X must live in the block whose first key is ≤ X. The next block starts at something larger, so X cannot be there.

Prefix Scan: Same Function, One Edge Case

For SELECT * FROM payments, the prefix we are looking for is _table:payments:.

We apply the same getLowerBound on the prefix key to find the starting block:

getLowerBound("_table:payments:", index):

  _table:payments:1  ≤ _table:payments:  ?
  _table:payments:10 ≤ _table:payments:  ?
  _table:payments:20 ≤ _table:payments:  ?

To answer this, we need to think about how string comparison works. Strings are compared character by character. _table:payments:1 and _table:payments: are identical up to the last character. But _table:payments:1 has one more character after the colon. In string comparison, a longer string that extends a shorter one is always greater. So:

_table:payments:1  > _table:payments:
_table:payments:10 > _table:payments:
_table:payments:20 > _table:payments:

Every index entry is greater than the prefix string. getLowerBound returns -1.

This will always be the case. _table:payments: will always be lexicographically smaller than any actual row key like _table:payments:1 or _table:payments:42, because the moment you append an ID after the colon, the key becomes strictly greater than the bare prefix string.

So -1 does not mean "no matching rows." We need to look at the first key of the index to understand what -1 means in this context. There can be two possible situations:

Situation 1: The file contains rows from the payments table.

index[0].key = _table:payments:1
HasPrefix(_table:payments:1, "_table:payments:") → YES
→ Start scanning from data block 0

Situation 2: The file contains rows from a different table that sorts after payments.

index[0].key = _table:users:1
HasPrefix(_table:users:1, "_table:payments:") → NO
→ Skip this file entirely

Hence, when getLowerBound returns -1, we need to check the prefix of the first key of the SSTable with the table prefix. If the prefix matches, all of the start rows in the SSTable are part of the same table. We should check sequentially till we encounter a different prefix. In case of a different prefix, we stop the search immediately.
On the other, if the prefix of the first key of SSTable doesn't match the table prefix, we can skip the entire file as the table would come after the table that we are searching for.

When getLowerBound returns a valid index (not -1), it means there are keys in the index that are ≤ the prefix. We start from that data block.

This also handles the case where a data block contains rows from multiple tables. For example, if block 0 starts at _table:cart:1 but also contains _table:payments:1 through _table:payments:9, getLowerBound returns block 0, ensuring we do not miss those rows. Starting from the last block whose first key is ≤ the prefix guarantees we never miss rows that happen to sit across a block boundary.

Sequential Scan: Reading Beyond One Data Block

Once we have the starting data block, we read forward sequentially, collecting all keys that match the prefix. Unlike GET which stops at a single data block, prefix scan continues across multiple data blocks as long as the prefix keeps matching.

We stop when we encounter a key whose first N characters (where N is the length of the prefix) are greater than the prefix. That means we have left the table's key space.

Dry running the full scan with our example:

getLowerBound returns index 0 → start at data block 0

Data block 0:
  _table:payments:1  → has prefix → collect
  _table:payments:3  → has prefix → collect
  _table:payments:5  → has prefix → collect

Data block 1:
  _table:payments:10 → has prefix → collect
  _table:payments:12 → has prefix → collect
  _table:payments:15 → has prefix → collect

Data block 2:
  _table:payments:20 → has prefix → collect
  _table:payments:25 → has prefix → collect

End of file → done

If the next key were _table:products:1, the first 16 characters _table:products: > _table:payments:, so we stop immediately.

One more difference from GET is that prefix scan must go through every SSTable file from newest to oldest. This is because different rows of the same table can exist across multiple files from separate flushes. Unlike GET, which stops at the first file containing the key, we cannot skip any file.

The Code

Based on our learnings, the core logic becomes:

1. Go through every SSTable file from newest to oldest.
2. For each SSTable file, apply binary search on the index block array to find the lowerBound for the prefix key. Prefix key is nothing but the common prefix which each table has. Example: _table:payments:. Lower bound is the largest key in index block which is less than or equal to prefixKey. .
3. If the lowerBound is returned as -1, it could mean two things:
   • If the prefix of the first index block key in the SSTable file is greater than the prefix key of the table, it means that all prefixes in this file are greater and the file can be skipped.
   • On the other hand, if prefix is exactly the same, we sequentially scan the file from the first data block itself.
4. Sequentially go through from the start of the data block ( as per the found lowerBound data block) to the end of the data block (which is the start of the index block).
   • Maintain an in-memory hashmap of result where key is the prefix key and the value is the serialised row. This hashmap is required to ensure that a key is only added if it is seen for the first time. The newest occurence in the newest file is the source of truth for a key as it has the most up-to-date value.
   • If we encounter a prefix which is greater than the table prefix key, we can exit and move to the next file.

With this intuition, the code reads naturally:

func (st *SsTable) PrefixScan(prefixKey string) (map[string]string, error) {
    st.mutex.RLock()
    defer st.mutex.RUnlock()
    tableMap := map[string]string{}
    // go through every SSTable file. rows of the same table can exist across multiple files
    for i := len(st.firstLevelFiles) - 1; i >= 0; i-- {
        file := st.firstLevelFiles[i]
        ssTableIndex := st.indexBlocks[i]
        lowerBoundSliceIndex := getLowerBound(prefixKey, ssTableIndex)
        if lowerBoundSliceIndex == -1 {
            // all index keys are greater than the prefix string.
            // check the first key to understand why.
            if len(ssTableIndex) == 0 || !strings.HasPrefix(ssTableIndex[0].key, prefixKey) {
                // first key does not have our prefix. the file has no matching rows.
                continue
            }
            // first key has our prefix. start from data block 0 and let
            // the sequential scan stop when it moves past the prefix zone.
            lowerBoundSliceIndex = 0
        }
        endOffset := st.indexOffsets[i]
        var err error
        tableMap, err = st.sequentiallyScanTableAndUpdateMap(file, prefixKey,
            ssTableIndex[lowerBoundSliceIndex].offset, endOffset, tableMap)
        if err != nil {
            return nil, err
        }
    }
    return tableMap, nil
}

func (st *SsTable) sequentiallyScanTableAndUpdateMap(ssTableFile *os.File, tableKey string,
    dataBlockStartOffset, fileEndOffset int, tableMap map[string]string) (map[string]string, error) {
    ssTableDataBlockBuf := make([]byte, fileEndOffset-dataBlockStartOffset)
    _, err := ssTableFile.ReadAt(ssTableDataBlockBuf, int64(dataBlockStartOffset))
    if err != nil && err != io.EOF {
        return nil, err
    }
    for i := 0; i < len(ssTableDataBlockBuf); {
        key, err := extractValueFromSsTable(ssTableDataBlockBuf, i)
        if err != nil {
            return nil, err
        }
        i += (4 + len(key))
        value, err := extractValueFromSsTable(ssTableDataBlockBuf, i)
        if err != nil {
            return nil, err
        }
        i += (4 + len(value))

        if strings.HasPrefix(key, tableKey) {
            // only set if not already found. newest file was processed first,
            // so the first value we see for a key is always the most recent.
            if _, ok := tableMap[key]; !ok {
                tableMap[key] = value
            }
        } else {
            // stop as soon as we have moved past the prefix zone
            keyPrefix := key[0:min(len(tableKey), len(key))]
            if keyPrefix > tableKey {
                return tableMap, nil
            }
        }
    }
    return tableMap, nil
}

Prefix Scan In Memtable

Since memtable contains most up-to date data, we would need to run a prefix scan on the memtable as well.
The prefix scan is much simpler for memtable compared to SSTable. This is because in case of SSTable, we had to deal with "data block first-keys" within index block (means that index block stores the first keys of the data block and their offset) and due to that, we need to find the last key in index block which is just less than the prefix key (lowerBound).

Lets take an example to make this more clear. Let's assume that the index block is:
_table:cart:4, _table:cart:20, _table:orders:10, _table:payments:25

If we are searching for payments table, we should be looking for keys from _table:orders:10 which is just less than or equal to _table:payments, even though the only index block containing payments keyword is _table:payments:25. This is because _table:orders:10 might contain some keys from payments:1 to payments:24 and we would miss out on those keys if we only search from _table:payments:25.

On the other hand, in case of memtable we deal with all the list of keys present in the in-memory sorted hashmap. Hence, we just need to find the first key which is just greater than or equal to the prefix key (we can call this upperBound). For example, in case of memtable, it will just return some key starting with _table:payments like _table:payments:4 for payments table and we don't need to look at keys which are less than _table:payments.

We have done exactly that in our memtable implementation. We have used github.com/google/btree go package which implements B-tree and provides AscendGreaterOrEqual function to return the first key greater than or equal to target and also allows iterating over those keys.

Using Both

Based on our learnings from blog 2, we now that memtable contains the most recent writes. Hence, in cases where the same key is present in both SSTable and Memtable, memtable is the source of truth.

We have done exactly that in the implementation:

func (db *DB) fullTableScan(tableName string) ([][]string, error) {
    key := fmt.Sprintf("%s:", tableName)
    memTableMap := db.memTable.PrefixScan(key)
    ssTableMap, err := db.ssTable.PrefixScan(key)
    if err != nil {
        return nil, err
    }

    scanOutput := [][]string{}
    // Process memtable results first
    for _, value := range memTableMap {
        values, err := db.deserializeRowValues(tableName, value)
        if err != nil {
            return nil, err
        }
        scanOutput = append(scanOutput, values)
    }

    // Process SSTable results, skip keys already in memtable
    for key, value := range ssTableMap {
        if _, ok := memTableMap[key]; ok {
            // memtable has the most up-to-date value. if key already ready in memtable, skip
            // reading SSTable.
            continue
        }
        values, err := db.deserializeRowValues(tableName, value)
        if err != nil {
            return nil, err
        }
        scanOutput = append(scanOutput, values)
    }
    return scanOutput, nil
}

Filtering by Non-Primary-Key Columns

Let's look at filtering queries like:

SELECT * FROM payments WHERE status = pending

status is not the primary key. We cannot do a targeted GET. There is no key payments:pending in our KV store. The key is payments:<id>, not payments:<status>.

Without any additional structures, the only option is:

1. Full table scan (prefix scan on payments:)
2. For each row, deserialize and check if status = pending
3. Return matching rows

This works. But it is O(N). We read every row in the table to find the ones that match. With 10 million rows and only 500 matching, 99.995% of the work is wasted.

What's Next

We were able to build solution for running full-table scan which can also be extended to filter based on the required conditions.

In Part 8, we will deep-dive into secondary and composite indexes and add support for them in our database. These would help optimise non-primary-key column queries to only go through the required number of rows.

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb