Indexing in DBMS Interview Questions

An index is a separate sorted structure, usually a B+ tree, that maps column values to rows, so a lookup takes about log(n) steps instead of a full scan.

CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT, city TEXT);
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email = 'a@b.com';
CREATE INDEX idx_users_email ON users(email);
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email = 'a@b.com';

The last plan is SEARCH users USING INDEX idx_users_email (email=?); before the index the query was SCAN users. Indexes help WHERE, JOIN, ORDER BY and GROUP BY. See indexes.

Each index takes space and slows writes, since inserts, deletes and most updates must change it too. Low-selectivity columns like is_active rarely help, because the optimizer prefers a scan. Index columns in frequent WHERE, JOIN and ORDER BY clauses, plus foreign keys, which most engines other than InnoDB leave unindexed.

A B tree keeps keys and data in every node; a B+ tree keeps data only in the leaves, which are linked, and uses internal nodes for routing. Databases prefer B+ trees: internal nodes hold only keys, so hundreds fit per page and three or four levels index hundreds of millions of rows, and a range scan finds its start and walks the leaf chain. A B tree's one edge: a lookup can stop above the leaves. Unlike a binary search tree, both are many-way.

A clustered index stores the rows themselves in key order, so a table has one; a non-clustered index is separate, its leaves point to rows, and each match costs an extra lookup unless the index covers the query. In InnoDB the primary key is always clustered and secondary indexes store it, so a lookup is two searches. SQL Server lets you choose. PostgreSQL tables are heaps, so every index is non-clustered. SQLite clusters on rowid, or on the primary key in a WITHOUT ROWID table.

Yes. An index on (a, b) is sorted by a, then by b, so it serves conditions on a or on a and b, but not on b alone: the leftmost prefix rule.

CREATE TABLE people (id INTEGER PRIMARY KEY, city TEXT, age INTEGER, name TEXT);
CREATE INDEX idx_city_age ON people(city, age);

EXPLAIN QUERY PLAN SELECT * FROM people WHERE city = 'Pune';
EXPLAIN QUERY PLAN SELECT * FROM people WHERE city = 'Pune' AND age > 30;
EXPLAIN QUERY PLAN SELECT * FROM people WHERE age > 30;

The last plan is SCAN people; the first two search idx_city_age. Put equality columns first and the range or ORDER BY column last. See composite indexes.

The condition is not a plain comparison on the stored column, or a scan looks cheaper. Typical causes: a function on the column (lower(email) = ?), a leading wildcard (LIKE '%gmail.com'), a type mismatch, low selectivity, OR across columns, or stale statistics (run ANALYZE). Rewrite the condition, such as dates as ranges, or index the expression:

CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT);
CREATE INDEX idx_email ON users(email);
EXPLAIN QUERY PLAN SELECT id FROM users WHERE lower(email) = 'asha@mail.com';
CREATE INDEX idx_email_lower ON users(lower(email));
EXPLAIN QUERY PLAN SELECT id FROM users WHERE lower(email) = 'asha@mail.com';

The last plan searches idx_email_lower; before it existed, the query scanned.

A covering index holds every column a query needs, so the database answers from the index and skips the table lookup for each row.

CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT, total INTEGER, notes TEXT);
CREATE INDEX idx_cust_status_total ON orders(customer_id, status, total);
EXPLAIN QUERY PLAN SELECT status, total FROM orders WHERE customer_id = 42;

The plan says USING COVERING INDEX; add notes to the SELECT and each row needs a table lookup. PostgreSQL 11+ and SQL Server can add non-key columns with INCLUDE.

A hash index answers = in about O(1) but cannot do ranges, ordering or prefixes; a B+ tree keeps keys sorted and handles all of those in O(log n). Hash indexes appear in PostgreSQL USING HASH (crash-safe since version 10), MySQL's MEMORY engine and InnoDB's adaptive hash index (off by default since MySQL 8.4). B+ trees are the default since they cover every case. See hash tables.

A dense index has an entry per key value; a sparse index has one per data block, so it is smaller but needs the file sorted on that key. A primary index is on the sorted key and can be sparse (a clustering index if that field is not unique). A secondary index is on any other field, so it must be dense. A multilevel index indexes the index, the idea behind B+ trees.

A partial index (a filtered index in SQL Server) covers only the rows that match a WHERE condition, so it stays small when queries target a small slice, like open orders among millions of shipped ones.

CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, status TEXT);
CREATE INDEX idx_open_orders ON orders(customer_id) WHERE status = 'open';
EXPLAIN QUERY PLAN SELECT id FROM orders WHERE customer_id = 7 AND status = 'open';

The plan is SEARCH orders USING COVERING INDEX idx_open_orders (customer_id=?); ask for status = 'shipped' and it scans, because the index holds none of those rows. A unique partial index enforces a rule on a subset, such as one active subscription per user. PostgreSQL and SQLite support them; MySQL does not. See partial indexes.