Join Complexity and Database Indexes

Brute force join

Given relations $R(A, B)$ and $S(B, C)$, the naive approach to compute $R \bowtie S$ scans $R$, and for each tuple in $R$, scans all of $S$. In the worst case this requires on the order of $|R| \times |S|$ steps:

$T_{\text{brute}} \propto |R| \cdot |S|$

This is quadratic in the table sizes and becomes infeasible for large tables.

The common case

In practice, on each iteration over $R$, there may be only a very small number of matching records in $S$. If $R$‘s $B$ is a foreign key referencing $S(B)$, there is exactly one matching tuple. The brute force strategy still scans all of $S$ to find it.

Indexes

An index is a data structure that can greatly reduce the time needed to locate records matching a given key. With an index on $S(B)$, the inner loop becomes a lookup on S-INDEX-ON-B(b):

$T_{\text{indexed}} \propto |R| \cdot \log |S|$

This reduces the inner loop from $\propto |S|$ (linear scan) to $\propto \log |S|$ (index lookup). For large tables, the difference is enormous.

SQL syntax

CREATE INDEX index_name ON S(B);

DROP INDEX index_name;

Index types and considerations

There are many types of database indexes (B-trees, hash indexes, bitmap indexes, GIN, GiST, and so on). The SQL standard does not define index creation; the syntax varies between implementations. Index creation is a physical design concern and may be handled by a specialist DBA team or by automated tools in modern systems.

The fundamental trade-off

Operation	Effect of indexes
Read (SELECT)	Faster (lookup instead of scan)
Write (INSERT, UPDATE, DELETE)	Slower (index must be updated)

This is a fundamental database trade-off: every index speeds up queries that use it, but imposes a cost on every write operation. Choosing which indexes to create requires understanding the workload’s balance of reads and writes.

Underlying data structures

The Ia Algorithms course presents the data structures used to implement indexes:

• Search trees (B-trees and variants): support range queries and ordered access.
• Hash tables: provide $O(1)$ average-case equality lookups but no range queries.

A database may maintain multiple indexes per table, each optimised for different query patterns.

Summary

• Without indexes, $R \bowtie S$ is $\propto |R| \cdot |S|$.
• An index on the join column reduces the inner loop to $\propto \log |S|$.
• Indexes speed reads but slow writes — a fundamental trade-off.
• Underlying data structures: search trees, hash tables.