Code in-memory mini-SQL engine

The Goal

Let’s build in-memory mini-SQL engine. We need to build a system that supports:

1. Data Manipulation: INSERT rows and SELECT rows based on simple criteria.
2. Performance: Optimize SELECT queries from O(N) to O(1) using indexes.
3. Memory Management: Handle DELETE operations efficiently without causing memory fragmentation or performance degradation.

The Architecture: Vector + Index + Free List

To achieve this, we need three specific components working in harmony:

1. Primary Storage (std::vector<Row>): We use a vector because it provides contiguous memory, which is friendly to the CPU cache.
2. Indexes (unordered_map): To achieve O(1) reads, we map values to Row IDs (indices in the vector).
3. The Free List (vector<size_t>): To handle deletes without shifting the main vector, we track "holes" in our storage. When we delete a row, we add its index to this list. When we insert, we check this list first to recycle memory.

Step 1: The Data Structures

“Schema-less” RowData

Think of RowData as a JSON object or a Python Dictionary. It allows each row to hold arbitrary key-value pairs without pre-defining a strict table schema (like CREATE TABLE in SQL). RowData is defined as:

using RowData = std::unordered_map<std::string, std::string>;

Example RowData:

// RowData instance
{
    {"id", "101"},
    {"name", "Alice"},
    {"role", "Engineer"}
}

Note: We must acknowledge that while this is good for coding speed, it is bad for system performance.

Memory Overhead: This is the biggest flaw.

• In a real database with 1 million rows, storing the string keys "id", "name", and "role" inside every single row is a massive waste of RAM.
• Real World Fix: A real database stores the column names once in a separate metadata structure (Catalog) and rows only store values.

Cache Locality: std::unordered_map allocates nodes on the heap. This means a single "row" is actually scattered across memory, causing cache misses.

• Real World Fix: Use a fixed-size struct or a compact byte array.

Type Safety: Everything is stored as a std::string. If you want to sort by "price," you have to parse the string to a float every time, which is slow.

Row as lifecycle manager

The Row class (or struct) serves as a lifecycle manager for our data. It wraps the raw data payload with metadata essential for the memory management strategy.

struct Row {
    RowData data;           // The actual content (Payload)
    bool isDeleted = false; // The metadata (Tombstone)
};

The “Tombstone” Mechanism (isDeleted)

The boolean flag isDeleted is known in database systems as a Tombstone. It decouples "Logical Deletion" from "Physical Deletion."

• Logical Deletion: The user says “Delete User 123.” We mark isDeleted = true. The data is effectively gone from the user's perspective.
• Physical Deletion: The memory is actually freed or overwritten. In our system, this happens lazily when a new insert overwrites this slot.

Why is this necessary? If we didn’t have this flag, and we simply added the index to the FreeList, we would rely 100% on the perfection of our index cleanup code.

• Scenario: Imagine a bug where an index entry for “Bob” isn’t properly removed, but the slot 5 is added to the free list.
• Risk: If a SELECT query finds the stale index pointing to slot 5, it would return data that is supposed to be dead (or worse, partially overwritten data).
• The Fix: The isDeleted flag acts as a final Guard Clause. Even if the index points to slot 5, the select() function checks if (row.isDeleted) and ignores it. This is "Defensive Coding," a key trait of good software.

IndexMap for O(1) read performance

The IndexMap is the engine that powers the O(1) read performance. It is a nested data structure designed to map specific data values back to their physical location in the main storage vector.

Here is the definition:

using IndexMap = std::unordered_map<std::string, std::unordered_map<std::string, std::vector<size_t>>>;

You can visualize this structure like a filing cabinet system:

• Layer 1: The Column (First Key)
• Layer 2: The Value (Second Key)
• Layer 3: The Row IDs (The Payload)

Concrete Data Example

Get Dilip Kumar’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Here is how the IndexMap looks in memory after inserting these three users:

1. Alice (Admin) -> stored at index 0
2. Bob (User) -> stored at index 1
3. Charlie (User) -> stored at index 2

The IndexMap would look like this:

{
  "role": {              // Layer 1: Column "role"
    "admin": [0],        // Layer 2: Value "admin" -> Layer 3: List [0]
    "user":  [1, 2]      // Layer 2: Value "user"  -> Layer 3: List [1, 2]
  },
  "name": {              // Layer 1: Column "name"
    "Alice":   [0],
    "Bob":     [1],
    "Charlie": [2]
  }
}

freeList for O(1) deletion and O(1) inserstion

The freeList is the component that transforms our solution to an optimized system. It is the key to achieving O(1) Deletions and O(1) Insertions simultaneously while keeping memory usage stable.

In the code, it is defined as:

std::vector<size_t> freeList;

When you Delete: You do not touch the vector’s layout. You simply take the Index ID (e.g., 5) and push it onto the freeList.

When you Insert: Before creating a brand new slot (allocating new memory), you check the freeList. "Do we have any empty space?"

• Yes: Pop index 5freeList. Overwrite the data at storage[5].
• No: Only then do you push_back to the end of the storage vector.

Database as a main container

The Database struct is the main container (the "Engine") that holds everything together. It orchestrates the interaction between our data storage, our search indexes, and our memory recycler.

Here is the definition:

class Database {
    // 1. Contiguous Storage
    std::vector<Row> storage;
    
    // 2. Indexes for fast lookups
    IndexMap indexes;

    // 3. Free List (Recycled Indices)
    std::vector<size_t> freeList;

public:
    // ... methods (insert, select, delete) ...
};

Code for Data Structures

Follownig is code for the proposed data structure.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <memory>

// A flexible row schema. In a real system, this might be a Variant or fixed struct.
using RowData = std::unordered_map<std::string, std::string>;

struct Row {
    RowData data;
    bool isDeleted = false; // "Tombstone" for safety
};

// Index Map: Column Name -> (Value -> List of Row Indices)
// We map to size_t (index in the main vector), NOT pointers, to avoid invalidation if vector resizes.
using IndexMap = std::unordered_map<std::string, std::unordered_map<std::string, std::vector<size_t>>>;

class Database {
    // 1. Contiguous Storage
    std::vector<Row> storage;
    
    // 2. Indexes for fast lookups
    IndexMap indexes;

    // 3. Free List (Recycled Indices)
    std::vector<size_t> freeList;

public:
    // Helper to add to index
    void addToIndex(const std::string& col, const std::string& val, size_t rowId) {
        indexes[col][val].push_back(rowId);
    }

    // Helper to remove from index
    void removeFromIndex(const std::string& col, const std::string& val, size_t rowId) {
        auto& ids = indexes[col][val];
        // Swap-and-pop is O(1), but changes order. 
        // For stability, we use remove, which is O(M) where M is count of duplicates.
        auto it = std::remove(ids.begin(), ids.end(), rowId);
        ids.erase(it, ids.end());
        
        // Clean up empty index keys to save memory
        if(ids.empty()) {
            indexes[col].erase(val);
        }
    }

Step 2: The Optimized Insert (O(1))

This is the critical for database operation. Instead of blindly pushing to the vector, we check the freeList. This keeps our memory footprint compact.

void insert(RowData data) {
    size_t targetIndex;

    if (!freeList.empty()) {
        // REUSE STRATEGY: Pop a "hole" from the free list
        targetIndex = freeList.back();
        freeList.pop_back();
        
        // Overwrite the existing slot (O(1))
        storage[targetIndex] = {data, false}; 
    } else {
        // APPEND STRATEGY: Standard vector growth
        targetIndex = storage.size();
        storage.push_back({data, false});
    }

    // Update all active indexes
    for (const auto& [col, val] : data) {
        // Only update index if we are tracking this column
        if (indexes.find(col) != indexes.end()) {
            addToIndex(col, val, targetIndex);
        }
    }
}

Step 3: The Indexed Select (O(1))

Here we bypass the full table scan entirely. We look up the column and value in our Hash Map, retrieve the Row IDs, and fetch the data directly from the main storage.

std::vector<RowData> select(const std::string& column, const std::string& value) {
        std::vector<RowData> result;

    // 1. Check if we have an index for this column
    if (indexes.find(column) == indexes.end()) {
        std::cout << "Error: No index on " << column << ". Full scan required (not implemented).\n";
        return {};
    }

    // 2. Retrieve Row IDs (O(1) lookup)
    const auto& valMap = indexes[column];
    auto it = valMap.find(value);
    if (it == valMap.end()) return {}; // No match found

    // 3. Fetch Rows (O(M) where M is number of matches)
    const std::vector<size_t>& rowIds = it->second;
    result.reserve(rowIds.size());
    
    for (size_t id : rowIds) {
        // Double check it's not a tombstone (defensive coding)
        if (!storage[id].isDeleted) {
            result.push_back(storage[id].data);
        }
    }
    return result;
}

Step 4: The Efficient Delete (No Memory Moving)

This is the hardest part to get right. We must:

1. Find the rows to delete using the index.
2. Mark them as deleted in the main storage.
3. Remove their references from all indexes (to prevent stale reads).
4. Add their IDs to the Free List.

void deleteRows(const std::string& column, const std::string& value) {
    if (indexes.find(column) == indexes.end()) return;

    // Get copy of IDs to delete (because we will modify indexes deeply)
    auto& targetIds = indexes[column][value];
    if (targetIds.empty()) return;
    
    std::vector<size_t> idsToDelete = targetIds; 

    for (size_t id : idsToDelete) {
        Row& row = storage[id];
        if (row.isDeleted) continue;

        // 1. Mark Tombstone
        row.isDeleted = true;

        // 2. Clean up ALL indexes referencing this row
        // We iterate the row's data to find which indexes need updating
        for (const auto& [col, val] : row.data) {
            if (indexes.count(col)) {
                removeFromIndex(col, val, id);
            }
        }

        // 3. Add to Free List for reuse
        freeList.push_back(id);
    }
}

// Ability to create an index dynamically
void createIndex(const std::string& column) {
    if (indexes.count(column)) return;
    
    // Backfill index for existing data
    for (size_t i = 0; i < storage.size(); ++i) {
        if (!storage[i].isDeleted && storage[i].data.count(column)) {
            indexes[column][storage[i].data[column]].push_back(i);
        }
    }
}
};

Step 5: Database usage as main method

Here is how we drive this code in the main function to demonstrate correctness.

int main() {
    Database db;
    
    // Create indexes upfront (showing foresight)
    db.createIndex("id");
    db.createIndex("role");

    // Insert Data
    db.insert({{"id", "1"}, {"role", "admin"}, {"name", "Alice"}}); // Index 0
    db.insert({{"id", "2"}, {"role", "user"},  {"name", "Bob"}});   // Index 1
    db.insert({{"id", "3"}, {"role", "user"},  {"name", "Charlie"}}); // Index 2

    // Select O(1)
    auto users = db.select("role", "user");
    std::cout << "Active Users: " << users.size() << " (Expected: 2)\n";

    // Delete O(1) logic (plus index cleanup)
    std::cout << "Deleting Bob...\n";
    db.deleteRows("id", "2"); // Deletes Index 1

    // Verify Delete
    users = db.select("role", "user");
    std::cout << "Active Users: " << users.size() << " (Expected: 1)\n";

    // Insert New Data (Should reuse Bob's slot - Index 1)
    std::cout << "Inserting Dave...\n";
    db.insert({{"id", "4"}, {"role", "guest"}, {"name", "Dave"}});

    // Verify Reuse
    // In a real interview, you might inspect the internal state to prove Index 1 was reused.
    // For this demo, simply showing the code runs without error is sufficient.
    auto guests = db.select("role", "guest");
    std::cout << "Guests: " << guests.size() << "\n";

    return 0;
}

This post is based on interaction with https://gemini.google.com.

Happy learning !!!