Building SaarDB, Part 8: Secondary Indexes

In Part 7, we built two strategies for SELECT: primary key lookup and full table scan. We teased that secondary indexes can dramatically speed up non-PK queries.

Now let us build the capability to add secondary indexes.

Secondary Indexes

As of now, queries like SELECT * FROM users WHERE city = NYC must:

1. Prefix scan all keys starting with users:
2. Deserialize every row
3. Check if city = NYC
4. Return matching rows

With 10 million rows and 500 matching, we read ALL 10 million rows. 99.995% of the work is wasted.

Can we find the 500 matching rows without reading the other 9,999,500?

This is where secondary indexes help. Similar to how a primary key maps to the entire row, we can also create a mapping of secondary index value to the list of rows it maps to.

Example: A key _index:users:city can be added with value as the list of all primary keys. Then for each primary key we can do a lookup directly of the key and run individual GET queries.

The above approach would help with doing 500 targeted GET queries instead of scanning an entire table of 10 million rows which would be much faster.

Problems With The Brute Force Approach

While the above approach of key as index name and value as list of primary keys works, it has multiple issues which will impact the performance of the database at scale. This includes:

1. Slower Writes: Each insert requires first fetching the key (GET), appending to the list and then setting the updated key (PUT). This is an entire read-modify-write cycle.
2. Concurrency: Every insert to the same index "city" writes to the same key: _index:users:city. This is a hot-key problem as every concurrent transaction needs a write lock on this key.
3. Growing Values: If 100k rows have city = "NYC", the value is a massive serialized list. Every insert rewrites the entire list leading to a lot of wasted space. This is O(N) space amplification per insert.

Notice that the issues in this approach are very similar to the issues encountered when we were trying to do a full-table scan by storing all of the list of primary keys for a table.

Prefix Scan For Secondary Indexes

In Part 7, we solved full-table scan by realising that table rows are adjacent in sorted order. users:1001, users:1002, users:1003 sit next to each other because they share the users: prefix. A prefix scan on users: finds all of them in one pass.

The same principle applies here. If we can design index keys such that all NYC entries are adjacent in sorted order, a prefix scan on index:users:city:NYC: finds all 500 matching rows in one pass and we avoid scanning the remaining 9,999,500.

The entire question then becomes: how do we design the key to guarantee that adjacency?

The brute force approach failed because it crammed all primary keys into a single value under one key. Every problem (read-modify-write cycles, hot keys, growing values) traced back to that one decision.

The fix is to give each index entry its own key. One key per (city_value, row) pair. This immediately eliminates the hot key and the read-modify-write cycle. Inserting a new row becomes a single append-only PUT of a new key.

But three requirements must be satisfied:

1. Uniqueness: each row needs its own key, so the primary key value must be part of it.
2. Searchability: a prefix scan on city = NYC must return only NYC rows, so the city value must be in the key.
3. PK extractability: after the prefix scan, we need the primary key to fire a GET for the full row. The PK must be recoverable from the key itself.

Requirements 1 and 3 are solved by including the PK in the key. Requirement 2 depends critically on where the city value sits.

Why city value must come before the PK:

Prefix scan relies on sorted adjacency. SSTables store keys in sorted order, so all keys sharing a prefix are grouped together. For a prefix scan on city = NYC to find all matching rows, every NYC entry must be adjacent to every other NYC entry in that sorted order.

Consider what happens if we put PK before city value:

index:users:city:1001:LA
index:users:city:1002:NYC
index:users:city:1003:LA
index:users:city:1004:NYC

Keys sort by PK. NYC entries are scattered and prefix scan cannot help.

With city value before PK:

index:users:city:LA:1001
index:users:city:LA:1003
index:users:city:NYC:1002
index:users:city:NYC:1004

All NYC entries are now adjacent. A prefix scan on index:users:city:NYC: finds exactly the rows we need.

Think of a dictionary: words are sorted alphabetically (the value you search by), not by page number (the row identifier). If a dictionary sorted by page number, you would have to read every page to find all words starting with "A".

This gives us the key structure:

index:<table_name>:<column_name>:<column_value>:<primary_key_value>

For SELECT * FROM users WHERE city = NYC, we prefix scan on index:users:city:NYC:. This returns ~500 keys. From each key, we extract the PK (the last segment after :). Then we fire a GET per primary key to fetch the full row.

Notice how this closes all three problems from the brute force approach:

1. No read-modify-write: inserting a new row is a single append-only PUT of index:users:city:NYC:1005. No existing key is touched.
2. No hot key: each row gets its own key. A million NYC users means a million separate keys, not one key with a million PKs packed inside.
3. No space amplification: each insert adds a fixed-size key, not an O(N) rewrite of a growing list.

Queries on Multiple Columns

Let's take a query example which has multiple AND conditions over multiple columns:

SELECT * FROM users WHERE city = NYC AND age = 25

We have an index on city. We can find all NYC users. But then we still need to filter by age in memory. If NYC has 100k users and out of those 100k users only 500 are age 25, we still need to pull 100k rows and then carry out filter in-memory. This is 99.5% wasted work.

If we have 2 separate indexes on city and age, only one of them can be chosen at a time. Assume that if we apply any one of the 2 indexes individually (index 1: city = NYC and index 2: age = 25) and both of them return a large result set, let's say 100k rows each. In that case, only after applying the second condition, we get the benefit of significantly reducing the number of rows we need to pull.

This problem can be solved by having an index on multiple columns which is exactly what composite indexes are used for.

Composite Index Design

Continuing the above example, if instead of having city:NYC or age:25 as the prefix to be scanned, if we have a prefix city:NYC:age:25, it will return exactly the 500 rows which we need.

Hence composite index becomes an extension over the secondary index which we discussed. We just need to store multiple column values: all of the ones which are a part of the index.

Key format: _index:<table>:<index_name>:<col1_val>:<col2_val>:<col3_val>:<pk>

The Leftmost Prefix Rule

The structure of composite index helps us solve an additional problem. The interesting part from the above example is that if we have an index on (city, age), we don't need a separate index on city column. This is because we can still do a prefix scan over index:users:city_age_idx:NYC.

Which brings us to a rule that:

All prefix columns of a composite index can also be utilised as individual indexes.

Think of a phone book sorted by (last_name, first_name). We can efficiently find:

• All Smiths (prefix: Smith)
• All John Smiths (prefix: Smith:John)

But we CANNOT efficiently find:

• All Johns regardless of last name (John could be under any last name, hence we would have to scan everything)

The same rule applies to composite indexes. Let's take an example index on (city, age, gender) to solidify our understanding:

Query	Can Use Index?	Why
WHERE city = NYC	Yes	Matches leftmost prefix
WHERE city = NYC AND age = 25	Yes	Matches first two columns
WHERE city = NYC AND age = 25 AND gender = F	Yes	Full match
WHERE age = 25	No	City (leftmost) is missing
WHERE gender = F	No	City and age are missing
WHERE city = NYC AND gender = F	Partial	Uses city prefix, filters gender in memory

The last case is interesting: the index covers city (leftmost prefix) but gender is the third column and age (second) is missing. We cannot skip columns in the prefix. So, we narrow down to only using the first part of index which is city and then the gender filtering happens in memory.

This also shows us the importance of carefully deciding the order of the columns in the composite index that we create.

Index-only Scan

The design of composite index also enables something called as index-only scan. Basis the core logic and intuition that we have developed for secondary indexes, there are two steps required during index scan:

1. Apply prefix scan for the specific index. This would return a list of primary keys which satisfy the secondary index.
2. Iterate through the primary keys list and fire a GET query with primary key as the key to get all of the column values.

Step 2 is required to fetch all of the column values for the required row.

But what if we can get all the details just by step 1?

Let's say we have a query like SELECT age FROM users WHERE city = 'NYC'. If we have a composite index on (city, age), we will utilise the prefix scan on _index:users:city_age_idx:NYC: to get all NYC rows. When we are doing the prefix scan, we will also have all of the age values as part of the key. This removes the need of step 2 itself.

Index-only scan can provide major improvement over regular index scan as we don't need to fire multiple GET queries which are random seeks.

This brings us to the rule that:

If we only require a limited set of columns for a SQL query, we can design the composite index in a way to enable index-only scan removing the need of random seeks.

Implementation

Now that we have covered the core intuition and logic, let's think how we would implement indexes end-to-end including the read and write path.

CREATE TABLE Path

Index creation generally happens during table creation via CREATE TABLE query or via CREATE INDEX query.

During table creation, we need to persist the table level secondary indexes catalog which is the list of secondary indexes for the table. This includes secondary index details like: the index name and the list of columns present. This is very similar to how we persisted the schema during CREATE TABLE. These secondary index details are also considered a part of the schema.

This is how the secondary index struct would look like:

    type CreateTable struct {
        TableName                string
        ColumnDetails            []Column
        PrimaryKeyColumnPosition int
        SecondaryIndexes []SecondaryIndex
    }

    type SecondaryIndex struct {
        Columns   []string
        IndexName string
    }

Similar to the CREATE TABLE example in blog 6, we need to persist the secondary index schema as well as key-value pairs. There are two ways to do this:

1. We can utilise the existing key _schema:<table_name> which we used while storing the schema during CREATE TABLE and add secondary indexes related data in a serialised manner apart from the rest of the schema.
2. We persist the secondary indexes schema in a separate key _indexes:<table_name>.

We saw a clear pattern in blog 6 that schema like details should not be fetched via GET operation every time and instead should be read in bulk during application bootup. This is necessary to avoid redundant GET calls for schema which would be required both during INSERT and SELECT queries. The same pattern also applies for the secondary indexes catalog.

Given that, we would not be running direct GET queries for schema every time, both approaches of _schema:<table_name> and _indexes:<table_name> are equally good. We went with the second approach. Note that since _indexes:<table_name> would require a separate PUT, it should be wrapped within a transaction to enable atomicity.

Based on the serialisation examples seen in blog 6, we need a serialisation strategy here to serialise the SecondaryIndexes struct.

The serialised value for _indexes:<table_name> would look like:

    [number_of_indexes][idx_1_name_len][idx_1_name][number_of_columns_in_idx_1][column1_position_for_index_1][column2_position_for_index_1]
    [idx_2_name_len][idx_2_name][number_of_columns_in_idx_2][column1_position_for_index_2][column2_position_for_index_2]

Few things to note here:

1. Since there can be multiple indexes, the serialised value starts with a 4 byte integer number_of_indexes (it can also be converted to 1 byte to reduce space). And subsequently that many iterations would be required to capture details for each index. In the above example, we have assumed 2 indexes and hence idx_1_name_len and idx_2_name_len precede the index specific details.
2. Instead of storing the exact column names in serialised schema, we are only storing column positions. Refer column1_position_for_index_1 as an example. This helps reduce unnecessary space as column names are already available to us and we have already seen in blog 6 that fixed integer datatypes consume less space over variable space datatypes like strings.

Since we have already covered serialisation examples, the code implementation for serialising secondary indexes is kept out of the blog and can be tried out by interested readers.

INSERT Into Path

During row insertion, apart from the PUT operation performed on _table:<table_name>:<primary_key_value>, we also need to perform one or more PUT operations for each of the secondary indexes part of the table. In order to ensure atomicity of the INSERT query, it should be wrapped in a transaction.

Let's look at how the core logic of INSERT query would be like:

1. We first need to find the list of all indexes for the specific table. We had discussed in "CREATE TABLE Path" section that the catalog should be stored in-memory as part of any writes during CREATE TABLE and also fetched and stored in-memory during application bootup.
2. Once we have the secondary indexes catalog, we just need to iterate through it and build the secondary index key for each of them. The key would be set in the following format which we already talked about: _index:<table>:<index_name>:<col1_val>:<col2_val>:<col3_val>:<pk>

Notice the write cost this introduces: every INSERT now requires N+1 PUT operations. 1 for the row itself plus 1 for each secondary index defined on the table. A table with 3 indexes means 4 writes per insert.

This is the fundamental read-write tradeoff of indexing. Faster reads come at the cost of slower writes. The more indexes we add, the heavier each INSERT becomes. This is why blindly adding indexes to every column is a bad idea. Index addition should be based on expected common query patterns.

SELECT Query Path

1. Additional case apart from PK and Full-Table Scan

Till now, the SELECT query was covering two cases:

1. If the query has a primary key column, utilise that and do a direct GET operation with the key containing the primary key value.
2. For any other query, carry out a full-table scan utilising prefix scan on table name. After fetching all of the rows, carry out the necessary filters basis the query in-memory.

In order to also solve for secondary index based queries, we first need to identify if a secondary index can be utilised for the provided query. If multiple indexes are candidates to be used as secondary index, we need to find the most suitable one.

2. Find the appropriate index

For the first version, we will take more of a brute force approach to find the most suitable secondary index. We will work on optimising this approach in the next blog. We have taken the following approach in the current version:

1. Check each index (including regular indexes and composite indexes) whether it is a candidate for being used in the input query. An index is a candidate if one or more columns which are a part of the input query are also a part of the index prefix. "Part of the index prefix" is key here. In case of a composite index, we check from the first column and if a column is not part of the index query, we immediately break.
2. If all the columns part of the input query are covered by the secondary index or composite index, then it should be the most appropriate index. This case where an index covers all of the input query conditions is also called as covering index.
3. If a covering index is not available, we can choose any of the candidate index.

3. Running Prefix Scan

Once we have found the appropriate index, we need to run a prefix scan. The prefix scan details are covered in the previous blog. The only change in this case is how we construct the prefix scan key. The prefix scan would include all of the column values except the primary key: _index:<table>:<index_name>:<col1_val>:<col2_val>:<col3_val>:.

One interesting thing to note in above example is the : at the end after col3_val. Let's say that we need to search for users aged 5 and run a prefix scan query like _index:users:age:5. This would give us all users aged 5, 50, 51, 52, ..., and 59. This is because all of them would satisfy the prefix scan condition of _index:users:age:5 and hence adding an extra colon at the end is critical: _index:users:age:5:. I had exactly encountered this bug during implementation and fixed it when the functional tests started failing.

4. GET Calls For Prefix Scan Results

If we can't use an index-only scan, we need to perform GET operation for each row returned by the prefix scan in order to fetch all of the column values.

5. In-memory filter for columns not covered

After utilising all of the columns from the index, there might still be uncovered columns. These are columns part of the input query but not part of the index.

For these columns, we need to apply in-memory filter from the results we got in the last step.

Code Walkthrough

Now that we have covered both the intuition and a walkthrough of steps involved in a SELECT query, we can also do a code walkthrough.

Above steps are numbered as comments for an easier read.

func (db *DB) selectFromTable(selectFromTableInput sqlparser.SelectFromTable) ([][]string, error) {
    ...
    if isPointedPrimaryKeyQuery(selectFromTableInput, pkColumnName) {
        rowValues, err := db.getRowForPrimaryKey(tableName, selectFromTableInput.QueryConditions[0].Value)
        if err != nil {
            return nil, err
        }
        return [][]string{rowValues}, nil
    }
    if isFullTableScanQuery(selectFromTableInput) {
        return db.fullTableScan(tableName)
    }

    // 1. Additional case apart from PK and Full-Table Scan
    return db.getQueryResultFromSecondaryIndexIfApplicable(tableName, selectFromTableInput, schema)
}


// 2. Finding the appropriate index
func getSecondaryIndexForQueryIfApplicable(input sqlparser.SelectFromTable,
    secondaryIndexes []sqlparser.SecondaryIndex) (*sqlparser.SecondaryIndex, []string) {
    var candidateSecondaryIndex *sqlparser.SecondaryIndex
    colsCoveredInCandidateSecondaryIndex := []string{}

    inputQueryColumn := map[string]bool{}
    for _, qc := range input.QueryConditions {
        inputQueryColumn[qc.ColumnName] = true
    }

    for _, secondaryIndex := range secondaryIndexes {
        secIdxColsCoveredFromInputQuery := []string{}
        for _, secIdxCol := range secondaryIndex.Columns {
            if inputQueryColumn[secIdxCol] {
                secIdxColsCoveredFromInputQuery = append(secIdxColsCoveredFromInputQuery, secIdxCol)
            } else {
                break  // Must match prefix sequentially. If we see that the column is not
                // part of the input query, we should immediately stop.
            }
            if len(secIdxColsCoveredFromInputQuery) == len(secondaryIndex.Columns) {
                return &secondaryIndex, secIdxColsCoveredFromInputQuery
            }
        }
        if len(secIdxColsCoveredFromInputQuery) > len(colsCoveredInCandidateSecondaryIndex) {
            candidateSecondaryIndex = &secondaryIndex
            colsCoveredInCandidateSecondaryIndex = secIdxColsCoveredFromInputQuery
        }
    }
    return candidateSecondaryIndex, colsCoveredInCandidateSecondaryIndex
}

// 3. Running Prefix Scan
// returns an array of primary key IDs which satisfy the index.
func (db *DB) secondaryIndexPrefixScan(prefixKey string) ([]string, error) {
    memTableMap := db.memTable.PrefixScan(prefixKey)
    ssTableMap, err := db.ssTable.PrefixScan(prefixKey)
    if err != nil {
        return nil, err
    }

    // map necessary to de-duplicate primary key as the same primary key can be present
    // in both SSTable and memtable.
    pkSet := make(map[string]bool)

    primaryKeyIds := []string{}
    for key, _ := range ssTableMap {
        keyElements := strings.Split(key, ":")
        pk := keyElements[len(keyElements)-1]
        pkSet[pk] = true
    } 
    for key, _ := range memTableMap {
        keyElements := strings.Split(key, ":")
        pk := keyElements[len(keyElements)-1]
        pkSet[pk] = true
    }
    for pk := range pkSet {
        primaryKeyIds = append(primaryKeyIds, pk)
    }
    return primaryKeyIds, nil
}

func (db *DB) getQueryResultFromSecondaryIndexIfApplicable(tableName string, selectFromTableInput sqlparser.SelectFromTable, schema sqlparser.CreateTable) ([][]string, error) {
    // 2. Finding the appropriate index
    secondaryIndex, colsCoveredInSecIndex := getSecondaryIndexForQueryIfApplicable(selectFromTableInput, schema.SecondaryIndexes)
    if secondaryIndex == nil {
        return db.runFullTableScanAndFilterConditions(tableName, selectFromTableInput)
    }
    indexCoveredColValues := []string{}
    for _, colName := range colsCoveredInSecIndex {
        for _, condition := range selectFromTableInput.QueryConditions {
            if condition.ColumnName == colName {
                indexCoveredColValues = append(indexCoveredColValues, condition.Value)
            }
        }
    }
    prefixKey := getSecondaryIndexKeyOrPrefix(tableName, secondaryIndex.IndexName, indexCoveredColValues, "")
    // 3. Running Prefix Scan
    primaryKeyIds, err := db.secondaryIndexPrefixScan(prefixKey)
    if err != nil {
        return nil, err
    }
    // 4. Run GET query for each primary key id separately and combine the result of each.
    queryResult := [][]string{}
    for _, pkId := range primaryKeyIds {
        rowValues, err := db.getRowForPrimaryKey(tableName, pkId)
        if err != nil {
            return nil, err
        }
        queryResult = append(queryResult, rowValues)
    }
    if allColumnsCoveredBySecondaryIndex(secondaryIndex, colsCoveredInSecIndex) {
        return queryResult, nil
    }

    // 5. In-memory filter for columns not covered
    return db.filterQueryConditions(tableName, selectFromTableInput.QueryConditions,
        colsCoveredInSecIndex, queryResult)
}

Benchmark Results

We benchmarked SELECT queries with and without secondary indexes on an Apple M1 Pro (benchmark code):

Scenario	Without Index (ns/op)	With Index (ns/op)	Speedup
Low cardinality, 100 rows	153,532	53,451	~2.9x
High cardinality, 100 rows	820,046	80,750	~10.2x
Low cardinality, 10k rows	22,126,575	8,549,737	~2.6x
High cardinality, 10k rows	10,927,318,625 (~10.9s)	12,100,610 (~12ms)	~903x

The standout result is that high cardinality with 10,000 rows shows a 903x speedup. From 10.9 seconds to 12 milliseconds.

Why does high cardinality benefit more? With high cardinality (many unique values), each indexed value maps to very few rows. The index scan returns a small result set, so we do very few random GETs. With low cardinality (few unique values, like a boolean column), the index still returns a large fraction of the table, reducing the advantage.

When Is a Full Table Scan BETTER Than an Index Scan?

Index scans are not always faster. Let's take an example to see when index scan performs worse than a full-table scan:

SELECT * FROM users WHERE active = true

If 80% of users are active, the index scan returns 8k out of 10k rows. That means 8k individual random GETs. Each one involves a binary search through SSTable index blocks and a disk read.

A full table scan reads through the data sequentially. One pass through all SSTables. As we have already discussed and discovered: sequential reads are much cheaper than random reads.

Concrete comparison for 10,000 rows, 8,000 matching:

Strategy	Disk Pattern	Total Work
Full table scan	1 sequential scan of 10k rows	Fast sequential I/O
Index scan	1 sequential scan of 8k rows + 8k random GETs	Fast sequential I/O + 8k binary searches + disk reads

The full table scan wins when the query returns a large fraction of the table.

What's Next

Now that we have covered the basics of storage layer, transaction layer and query layer, we would be deep-diving into all three of them further.

As a continuation of the current blog we will deep-dive into finding the most applicable secondary index in the next blog or even finding out the case where an index should not be picked. This is also referred to as query planning. What makes this problem interesting is that it is more of an estimation problem, we can't actually run different queries to find out which is the most appropriate index.

We also have not handled the case where a row is updated or deleted. When a row's indexed column changes, say a user moves from NYC to LA, the old index entry _index:users:city_idx:NYC:<pk> becomes stale. Cleaning up stale index entries is a non-trivial problem we will address in a future blog.

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