Indexing

Indexes are essential for query performance. Without indexes, WitDatabase must scan every row to find matching data. With proper indexes, queries can jump directly to the relevant rows, often improving performance by orders of magnitude.

1. Overview

What is an Index?

An index is a separate data structure that maps column values to row locations. Think of it like a book's index — instead of reading every page to find a topic, you look up the topic in the index and go directly to the right page.

[[Svg Src="./witdatabase-index-comparison.svg" Alt="witdatabase-index-comparison"]]

Types of Indexes

WitDatabase supports several index types:

How Indexes Work

WitDatabase indexes use the same B+Tree structure as the primary storage, optimized for fast lookups:

[[Svg Src="./witdatabase-btree-index-structure.svg" Alt="witdatabase-btree-index-structure"]]

When to Create Indexes

Create indexes on columns that are frequently used in:

Index Trade-offs

Indexes have costs as well as benefits:

Rule of thumb: Create indexes for columns used in queries. Don't create indexes "just in case" — only for actual query patterns.

2. Creating and Managing Indexes

CREATE INDEX

The basic syntax for creating an index:

CREATE [UNIQUE] INDEX [IF NOT EXISTS] index_name
ON table_name (column1 [ASC|DESC], column2 [ASC|DESC], ...)
[INCLUDE (column3, column4, ...)]
[WHERE condition];

Examples:

-- Simple index on one column
CREATE INDEX IX_Users_Email ON Users(Email);

-- Unique index (enforces uniqueness)
CREATE UNIQUE INDEX IX_Users_Email ON Users(Email);

-- Index with IF NOT EXISTS
CREATE INDEX IF NOT EXISTS IX_Orders_Status ON Orders(Status);

-- Descending index (for ORDER BY DESC)
CREATE INDEX IX_Orders_Date ON Orders(OrderDate DESC);

-- Composite index (multiple columns)
CREATE INDEX IX_Users_Name ON Users(LastName, FirstName);

-- Covering index (includes extra columns)
CREATE INDEX IX_Orders_Customer ON Orders(CustomerId) INCLUDE (Total, Status);

-- Partial index (only indexes matching rows)
CREATE INDEX IX_Orders_Pending ON Orders(CustomerId) WHERE Status = 'pending';

-- Expression index (on computed value)
CREATE INDEX IX_Users_EmailLower ON Users(LOWER(Email));

DROP INDEX

Remove an index:

DROP INDEX index_name;
DROP INDEX IF EXISTS index_name;

Example:

-- Drop an index
DROP INDEX IX_Users_Email;

-- Drop if exists (no error if missing)
DROP INDEX IF EXISTS IX_Old_Index;

Creating Indexes via ADO.NET

using var connection = new WitDbConnection("Data Source=app.witdb");
connection.Open();

using var cmd = connection.CreateCommand();

// Create a simple index
cmd.CommandText = "CREATE INDEX IX_Products_Category ON Products(CategoryId)";
cmd.ExecuteNonQuery();

// Create a unique index
cmd.CommandText = "CREATE UNIQUE INDEX IX_Users_Email ON Users(Email)";
cmd.ExecuteNonQuery();

// Create a composite index
cmd.CommandText = "CREATE INDEX IX_Orders_CustomerDate ON Orders(CustomerId, OrderDate DESC)";
cmd.ExecuteNonQuery();

Creating Indexes via EF Core

EF Core creates indexes automatically for keys and can be configured for other columns:

public class AppDbContext : DbContext
{
    protected override void OnModelCreating(ModelBuilder modelBuilder)
    {
        // Simple index
        modelBuilder.Entity<User>()
            .HasIndex(u => u.Email);
        
        // Unique index
        modelBuilder.Entity<User>()
            .HasIndex(u => u.Email)
            .IsUnique();
        
        // Composite index
        modelBuilder.Entity<User>()
            .HasIndex(u => new { u.LastName, u.FirstName });
        
        // Named index
        modelBuilder.Entity<Order>()
            .HasIndex(o => o.Status)
            .HasDatabaseName("IX_Orders_Status");
        
        // Partial index (filter)
        modelBuilder.Entity<Order>()
            .HasIndex(o => o.CustomerId)
            .HasFilter("Status = 'pending'");
    }
}

// Or using data annotations
public class User
{
    public long Id { get; set; }
    
    [Index(IsUnique = true)]
    public string Email { get; set; }
    
    [Index("IX_User_Name", 1)]  // Composite index, order 1
    public string LastName { get; set; }
    
    [Index("IX_User_Name", 2)]  // Composite index, order 2
    public string FirstName { get; set; }
}

Viewing Existing Indexes

Query the schema to see existing indexes:

-- List all indexes
SELECT * FROM INFORMATION_SCHEMA.INDEXES;

-- Indexes for a specific table
SELECT * FROM INFORMATION_SCHEMA.INDEXES WHERE TABLE_NAME = 'Users';

// Via ADO.NET
cmd.CommandText = "SELECT * FROM INFORMATION_SCHEMA.INDEXES WHERE TABLE_NAME = 'Users'";
using var reader = cmd.ExecuteReader();

while (reader.Read())
{
    Console.WriteLine(

        
        

            
            Loading...
        
quot;Index: {reader["INDEX_NAME"]}, Columns: {reader["COLUMN_NAME"]}");
}

Index Naming Conventions

Use consistent naming for indexes:

Consistent naming makes it easier to understand index purpose and manage them over time.

3. Index Types in Detail

Primary Key Index

Every table has a primary key index created automatically. It's always unique and provides the fastest access to rows.

-- Primary key is automatically indexed
CREATE TABLE Users (
    Id BIGINT PRIMARY KEY,  -- Auto-creates unique index
    Email VARCHAR(255),
    Name VARCHAR(100)
);

-- Composite primary key
CREATE TABLE OrderItems (
    OrderId BIGINT,
    ProductId BIGINT,
    Quantity INT,
    PRIMARY KEY (OrderId, ProductId)  -- Composite index
);

The primary key index is used automatically for queries like:

SELECT * FROM Users WHERE Id = 123;  -- Uses primary key index

Unique Indexes

Unique indexes enforce that no two rows have the same value(s) in the indexed columns.

-- Single-column unique index
CREATE UNIQUE INDEX IX_Users_Email ON Users(Email);

-- Composite unique index (combination must be unique)
CREATE UNIQUE INDEX IX_ProductVariants ON Products(ProductId, Color, Size);

Behavior:

• INSERT fails if duplicate value exists
• UPDATE fails if it would create duplicate
• NULL values are allowed (NULLs are considered distinct)

try
{
    cmd.CommandText = "INSERT INTO Users (Email) VALUES ('existing@email.com')";
    cmd.ExecuteNonQuery();
}
catch (WitDbConstraintException ex)
{
    Console.WriteLine(

        
        

            
            Loading...
        
quot;Duplicate email: {ex.Message}");
}

Non-Unique Indexes

Non-unique indexes speed up queries without enforcing uniqueness. Multiple rows can have the same indexed value.

-- Index on frequently queried column
CREATE INDEX IX_Orders_Status ON Orders(Status);

-- Index for foreign key (speeds up joins)
CREATE INDEX IX_Orders_CustomerId ON Orders(CustomerId);

Use cases:

• Columns with many duplicates (Status, Category)
• Foreign key columns
• Columns in WHERE clauses

Composite Indexes

Composite indexes include multiple columns. Column order matters significantly.

-- Composite index on (LastName, FirstName)
CREATE INDEX IX_Users_Name ON Users(LastName, FirstName);

The leftmost prefix rule: A composite index can be used for queries on:

• The first column alone
• The first two columns
• All columns

-- These queries CAN use IX_Users_Name (LastName, FirstName):
SELECT * FROM Users WHERE LastName = 'Smith';                    -- ✅ Uses index
SELECT * FROM Users WHERE LastName = 'Smith' AND FirstName = 'John';  -- ✅ Uses index

-- These queries CANNOT use IX_Users_Name:
SELECT * FROM Users WHERE FirstName = 'John';                    -- ❌ Can't use (wrong column)

Column order strategy: Put the most selective (highest cardinality) column first, or the column most often queried alone.

Covering Indexes

A covering index includes all columns needed by a query. This allows the query to be answered entirely from the index without accessing the table.

-- Covering index: includes Total and Status
CREATE INDEX IX_Orders_Customer ON Orders(CustomerId) INCLUDE (Total, Status);

-- This query is "covered" - no table access needed
SELECT CustomerId, Total, Status FROM Orders WHERE CustomerId = 123;

-- Index structure:
-- CustomerId → (RowId, Total, Status)
-- Query reads only from index, never touches table

Benefits:

• Faster queries (fewer I/O operations)
• Reduced table page accesses

Trade-offs:

• Larger index size
• Included columns increase update overhead

Partial Indexes

Partial indexes only include rows that match a condition. They're smaller and more efficient for specific query patterns.

-- Only index active users
CREATE INDEX IX_Users_Email_Active ON Users(Email) WHERE IsActive = 1;

-- Only index pending orders
CREATE INDEX IX_Orders_Pending ON Orders(CustomerId, OrderDate) 
WHERE Status = 'pending';

Benefits:

• Smaller index size (fewer entries)
• Faster updates (only affected rows)
• More efficient for specific queries

-- Uses partial index (condition matches)
SELECT * FROM Users WHERE Email = 'test@example.com' AND IsActive = 1;

-- Cannot use partial index (condition doesn't match)
SELECT * FROM Users WHERE Email = 'test@example.com' AND IsActive = 0;

Expression Indexes

Expression indexes (functional indexes) index the result of an expression, not the raw column value.

-- Index on lowercase email (for case-insensitive lookup)
CREATE INDEX IX_Users_EmailLower ON Users(LOWER(Email));

-- Index on year extracted from date
CREATE INDEX IX_Orders_Year ON Orders(YEAR(OrderDate));

-- Index on computed value
CREATE INDEX IX_Products_PricePerUnit ON Products(Price / Quantity);

Usage:

-- Uses expression index (expression matches exactly)
SELECT * FROM Users WHERE LOWER(Email) = 'john@example.com';

-- Does NOT use expression index (different expression)
SELECT * FROM Users WHERE Email = 'john@example.com';  -- Won't use LOWER index

Important: The query must use exactly the same expression as the index definition.

Descending Indexes

By default, indexes are ascending. For queries that ORDER BY descending, a descending index can avoid a sort operation.

-- Descending index for recent orders
CREATE INDEX IX_Orders_Date_Desc ON Orders(OrderDate DESC);

-- Composite with mixed order
CREATE INDEX IX_Orders_Customer_Date ON Orders(CustomerId ASC, OrderDate DESC);

Usage:

-- Uses descending index efficiently
SELECT * FROM Orders ORDER BY OrderDate DESC LIMIT 10;

-- Without descending index, this requires sorting the results

4. Query Optimizer and Index Selection

WitDatabase includes a cost-based query optimizer that automatically selects the best index for each query.

How the Optimizer Works

The optimizer analyzes each query and estimates the cost of different execution strategies:

[[Svg Src="./witdatabase-query-optimizer.svg" Alt="witdatabase-query-optimizer"]]

Cost Estimation

The optimizer uses these cost factors:

Selectivity estimation:

• Equality predicates (=): ~1% of rows
• Range predicates (<, >, BETWEEN): ~20% of rows
• Default: ~10% of rows

EXPLAIN Query Plan

Use EXPLAIN to see what index the optimizer chooses:

EXPLAIN SELECT * FROM Orders WHERE CustomerId = 123;

Output:

Query Plan:
├─ Index Seek on IX_Orders_CustomerId
│  Table: Orders
│  Index: IX_Orders_CustomerId
│  Seek Key: CustomerId = 123
│  Estimated Rows: 100

More examples:

-- Table scan (no suitable index)
EXPLAIN SELECT * FROM Orders WHERE Notes LIKE '%urgent%';
-- Output: Table Scan on Orders

-- Index range scan
EXPLAIN SELECT * FROM Orders WHERE OrderDate > '2024-01-01';
-- Output: Index Range Scan on IX_Orders_Date

-- Composite index usage
EXPLAIN SELECT * FROM Orders WHERE CustomerId = 123 AND Status = 'pending';
-- Output: Index Seek on IX_Orders_CustomerStatus

When Indexes Are NOT Used

The optimizer may skip an index in certain situations:

1. Low selectivity (too many matching rows):

-- If Status = 'active' matches 90% of rows, table scan might be faster
SELECT * FROM Users WHERE Status = 'active';
-- Optimizer may choose: Table Scan (fewer I/O than index + lookup)

2. Small tables:

-- For tables with < 10-50 rows, scanning is often faster
SELECT * FROM Settings WHERE Key = 'theme';
-- Table scan for small tables is fine

3. Expression doesn't match index:

-- Index on Email won't help with LOWER(Email)
CREATE INDEX IX_Users_Email ON Users(Email);
SELECT * FROM Users WHERE LOWER(Email) = 'john@example.com';
-- Need expression index: CREATE INDEX IX_Email_Lower ON Users(LOWER(Email))

4. OR conditions spanning multiple indexes:

-- Hard to use indexes effectively
SELECT * FROM Orders WHERE CustomerId = 123 OR Status = 'urgent';
-- May result in table scan or index union

5. Leading wildcard in LIKE:

-- Index can't help with leading wildcard
SELECT * FROM Users WHERE Name LIKE '%smith%';
-- Index on Name is useless here

Forcing Index Usage

In rare cases, you may want to override the optimizer. Use index hints:

-- Force specific index
SELECT * FROM Orders WITH (INDEX = IX_Orders_Status) WHERE Status = 'pending';

-- Force table scan (ignore indexes)
SELECT * FROM Orders WITH (INDEX = NONE) WHERE CustomerId = 123;

Warning: The optimizer is usually right. Only use hints after careful benchmarking.

Query Plan Caching

WitDatabase caches query plans to avoid re-optimization:

// First execution: plan is compiled and cached
var results1 = engine.Query("SELECT * FROM Users WHERE Email = @email",
    new Dictionary<string, object?> { ["email"] = "a@example.com" });

// Second execution: cached plan is reused
var results2 = engine.Query("SELECT * FROM Users WHERE Email = @email",
    new Dictionary<string, object?> { ["email"] = "b@example.com" });

The plan cache is automatically invalidated when:

• Schema changes (CREATE/DROP TABLE, CREATE/DROP INDEX)
• Statistics change significantly
• Cache reaches size limit (LRU eviction)

5. Index Maintenance

Automatic Index Updates

WitDatabase automatically maintains indexes when data changes:

INSERT: Index entries are added for the new row.

INSERT INTO Users (Id, Email) VALUES (1, 'john@example.com');
-- Index IX_Users_Email is updated: 'john@example.com' → Row 1

UPDATE: If indexed columns change, old entries are removed and new ones added.

UPDATE Users SET Email = 'john.smith@example.com' WHERE Id = 1;
-- Index IX_Users_Email: Remove 'john@example.com', Add 'john.smith@example.com'

DELETE: Index entries are removed.

DELETE FROM Users WHERE Id = 1;
-- Index IX_Users_Email: Remove 'john.smith@example.com'

Index Build Performance

Creating an index on an existing table with data can take time:

-- This scans the entire table and builds the index
CREATE INDEX IX_Orders_Date ON Orders(OrderDate);

For large tables:

• Index creation time is proportional to table size
• Consider creating indexes during low-traffic periods
• Monitor disk I/O during index creation

Index Statistics

The query optimizer uses statistics to estimate selectivity. WitDatabase maintains basic statistics automatically:

-- Update statistics for optimizer (if available)
ANALYZE TABLE Users;
ANALYZE;  -- All tables

Index Fragmentation

Over time, indexes can become fragmented due to insertions and deletions. WitDatabase's B+Tree structure handles this well, but you can rebuild if needed:

-- Rebuild an index (drop and recreate)
DROP INDEX IX_Users_Email;
CREATE INDEX IX_Users_Email ON Users(Email);

Note: B+Tree engines like WitDatabase handle fragmentation better than some other structures, so frequent rebuilding is rarely needed.

Monitoring Index Usage

Track which indexes are being used:

// Check if an index exists
var indexExists = engine.Query(
    "SELECT 1 FROM INFORMATION_SCHEMA.INDEXES WHERE INDEX_NAME = 'IX_Users_Email'"
).Count > 0;

// Use EXPLAIN to verify index usage
var plan = engine.Query("EXPLAIN SELECT * FROM Users WHERE Email = @email",
    new Dictionary<string, object?> { ["email"] = "test@example.com" });
Console.WriteLine(plan[0]["Plan"]);

6. Best Practices

Do Create Indexes For

Columns in WHERE clauses:

-- Frequent query pattern
SELECT * FROM Orders WHERE Status = 'pending';
-- Create index
CREATE INDEX IX_Orders_Status ON Orders(Status);

Columns in JOIN conditions:

-- Join query
SELECT * FROM Orders o JOIN Customers c ON o.CustomerId = c.Id;
-- Create index on foreign key
CREATE INDEX IX_Orders_CustomerId ON Orders(CustomerId);

Columns in ORDER BY (if frequently used):

-- Frequent sort pattern
SELECT * FROM Orders ORDER BY OrderDate DESC LIMIT 10;
-- Create descending index
CREATE INDEX IX_Orders_Date_Desc ON Orders(OrderDate DESC);

Foreign key columns:

-- FK constraint
ALTER TABLE Orders ADD CONSTRAINT FK_Orders_Customer 
    FOREIGN KEY (CustomerId) REFERENCES Customers(Id);
-- Index speeds up FK checks and joins
CREATE INDEX IX_Orders_CustomerId ON Orders(CustomerId);

Don't Create Indexes For

Columns rarely used in queries:

-- Only used in SELECT, never in WHERE/JOIN/ORDER BY
CREATE INDEX IX_Users_Bio ON Users(Biography);  -- Probably useless

Very small tables:

-- Table with 10 rows
CREATE INDEX IX_Settings_Key ON Settings(Key);  -- Table scan is fine

Columns with very low cardinality:

-- Boolean column with only 2 values
CREATE INDEX IX_Users_IsActive ON Users(IsActive);  -- Usually not helpful
-- Exception: partial index when one value is rare
CREATE INDEX IX_Users_Active ON Users(Email) WHERE IsActive = 1;  -- Good!

Frequently updated columns:

-- Column updated on every request
CREATE INDEX IX_Users_LastLogin ON Users(LastLoginTime);  
-- Update cost may outweigh query benefit

Composite Index Design

Order columns by selectivity (most selective first):

-- Good: CustomerId is more selective than Status
CREATE INDEX IX_Orders_CustomerStatus ON Orders(CustomerId, Status);

-- Less optimal: Status has fewer distinct values
CREATE INDEX IX_Orders_StatusCustomer ON Orders(Status, CustomerId);

Consider query patterns:

-- If you query by CustomerId alone AND by (CustomerId, Status):
CREATE INDEX IX_Orders_CustomerStatus ON Orders(CustomerId, Status);
-- This single index serves both patterns!

-- But if you also query by Status alone:
CREATE INDEX IX_Orders_Status ON Orders(Status);  -- Need separate index

Index Maintenance Strategy

Development:

• Create indexes based on known query patterns
• Use EXPLAIN during development

Staging:

• Test with production-like data volumes
• Verify index usage with realistic queries

Production:

• Monitor slow queries
• Add indexes for new query patterns
• Remove unused indexes

Common Mistakes to Avoid

1. Over-indexing:

-- Too many indexes slow down writes
CREATE INDEX IX_Users_Col1 ON Users(Col1);
CREATE INDEX IX_Users_Col2 ON Users(Col2);
CREATE INDEX IX_Users_Col3 ON Users(Col3);
CREATE INDEX IX_Users_Col1Col2 ON Users(Col1, Col2);
CREATE INDEX IX_Users_Col2Col3 ON Users(Col2, Col3);
-- Consider: Do you really query all these combinations?

2. Duplicate indexes:

-- These are redundant
CREATE INDEX IX_Users_Email ON Users(Email);
CREATE INDEX IX_Users_EmailName ON Users(Email, Name);
-- The second index can serve queries on Email alone
-- Remove the first one

3. Wrong column order in composite indexes:

-- Query pattern
SELECT * FROM Orders WHERE Status = 'pending' AND CustomerId = 123;

-- Wrong order (Status has low cardinality)
CREATE INDEX IX_Orders_StatusCustomer ON Orders(Status, CustomerId);

-- Better order (CustomerId is more selective)
CREATE INDEX IX_Orders_CustomerStatus ON Orders(CustomerId, Status);

4. Ignoring expression indexes:

-- Query with function
SELECT * FROM Users WHERE LOWER(Email) = 'john@example.com';

-- Regular index won't help
CREATE INDEX IX_Users_Email ON Users(Email);  -- Not used!

-- Need expression index
CREATE INDEX IX_Users_EmailLower ON Users(LOWER(Email));  -- Used!

7. Quick Reference

SQL Syntax

Create Index:

-- Basic
CREATE INDEX index_name ON table(column);

-- Unique
CREATE UNIQUE INDEX index_name ON table(column);

-- If not exists
CREATE INDEX IF NOT EXISTS index_name ON table(column);

-- Descending
CREATE INDEX index_name ON table(column DESC);

-- Composite
CREATE INDEX index_name ON table(col1, col2, col3);

-- Covering
CREATE INDEX index_name ON table(col1) INCLUDE (col2, col3);

-- Partial
CREATE INDEX index_name ON table(col1) WHERE condition;

-- Expression
CREATE INDEX index_name ON table(LOWER(col1));

Drop Index:

DROP INDEX index_name;
DROP INDEX IF EXISTS index_name;

View Indexes:

SELECT * FROM INFORMATION_SCHEMA.INDEXES;
SELECT * FROM INFORMATION_SCHEMA.INDEXES WHERE TABLE_NAME = 'TableName';

Query Plan:

EXPLAIN SELECT * FROM table WHERE column = value;

Index Types Summary

Optimizer Behavior

Composite Index Prefix Rule

[[Svg Src="./witdatabase-composite-index-rules.svg" Alt="witdatabase-composite-index-rules"]]

Performance Guidelines

Common Patterns

Foreign Key Index:

ALTER TABLE Orders ADD CONSTRAINT FK_Orders_Customer 
    FOREIGN KEY (CustomerId) REFERENCES Customers(Id);
CREATE INDEX IX_Orders_CustomerId ON Orders(CustomerId);

Case-Insensitive Search:

CREATE INDEX IX_Users_EmailLower ON Users(LOWER(Email));
SELECT * FROM Users WHERE LOWER(Email) = LOWER(@input);

Recent Records:

CREATE INDEX IX_Orders_Date_Desc ON Orders(CreatedAt DESC);
SELECT * FROM Orders ORDER BY CreatedAt DESC LIMIT 10;

Multi-Tenant Application:

CREATE INDEX IX_Data_Tenant ON Data(TenantId, CreatedAt DESC);
SELECT * FROM Data WHERE TenantId = @tenant ORDER BY CreatedAt DESC;

Status-Based Queries:

-- Partial index for common status
CREATE INDEX IX_Orders_Pending ON Orders(CustomerId) WHERE Status = 'pending';
SELECT * FROM Orders WHERE CustomerId = @cid AND Status = 'pending';