What is indexing in DBMS? Finding one row in ten lakh

SeatJaldi is safe now: bookings save all or nothing, and Meera Kulkarni has raised a ₹2 crore seed round. This season’s bookings table, a big spreadsheet with one row per booking, has grown to 10 lakh rows.

On a busy sale afternoon, before an investor demo, Meera opens “My bookings”. A spinner turns for 4 seconds. A match page, from the same database, loads at once.

Arjun Nair finds the query, the question the app asks the database. “My bookings” asks SELECT * FROM bookings WHERE user_id = 812: every booking of user 812. The match page asks by id, the number that names each row. Both want a few rows out of ten lakh. Why is one instant and the other 4 seconds?

An index is a sorted helper list that lets the database jump straight to the rows you ask for, instead of reading the whole table. Each detail of a booking, such as user_id, is a column.

The database keeps a table in pages, small blocks of about 8 KB (roughly 8,000 letters of data). With no index on user_id, it must read every page and check every row.

• An index is the back-of-the-book index: fast reads, paid for on every write.
• It is sorted and stores where rows live, so the database narrows and jumps.

You have seen this when a ticket app finds a booking by its id at once, but pauses on a phone number search. Only the id had an index.

Or when a ticket app crawls at “Confirm booking” as a big sale opens. Each booking was also written into many helper lists.

A B-tree is a tree of sorted pages, and each step down narrows the search, so a few page reads find the row. PostgreSQL, a popular database, builds one whenever you ask for an index without naming a type.

Mridul’s book index has thumb tabs: a letter, then a group of words, then the word. A B-tree is the same: a root page on top, branch pages below, and leaf pages holding the row locations.

Skip an index when the column is rarely searched, the table is small, or it is written far more than read. A textbook indexed on every word would have an index as thick as the book.

What just happened? Four of Arjun’s six extra indexes, on seat_code, status, created_at and amount_rupees, served no screen on their own. They only slowed the noon sale, so he dropped them.

An index trades write work and disk space for read speed. Engineers pick indexes from the real queries, then check with EXPLAIN. It shows the plan from the planner, the part of the database that decides how to run a query.

Why so few steps? Assume an index page holds about 500 entries. Ten lakh entries fill 1,000,000 / 500 = 2,000 leaf pages, 4 branch pages and one root: 3 levels. Three levels reach 500 x 500 x 500 = 12.5 crore entries, so even 10 crore rows need about 3 reads.

The table is about 12,000 pages and the look-up reads about 6: 2,000 times fewer. The clock showed 4,000 ms to 15 ms, about 267 times. Pages read in order cost less than scattered jumps, and many were already in memory.

• B-tree, the default: equals, less than, more than and the like, BETWEEN, IN and sorted order. Also LIKE 'A1%', with a special index under some settings.
• Hash: a 32-bit hash of each value, so only “equals”.
• GIN: one entry per part of a value, such as each word, for searching inside values.
• BRIN: the smallest and largest value per run of pages; tiny, for a column like created_at that follows arrival order.

A two-column index is sorted by the first column, then the second. An index on (match_id, status) serves WHERE match_id = 42 AND status = 'sold', and WHERE match_id = 42 alone. It is a textbook index by chapter, then topic: quick if you know the chapter, slow if you know only the topic. An update that changes no indexed column can often skip the indexes; with status in any index, every pending-to-confirmed change touched every index.

What just happened? The first index serves “My bookings”. The second replaces Arjun’s match_id index and counts sold seats per match, match_id first because every such query names the match. The third finds BK-10421 by its code, and UNIQUE refuses a second booking with the same code.

EXPLAIN shows the plan without running the query; on a tiny table a Seq Scan can be right. A plain CREATE INDEX blocks inserts and updates until done. On a live table, CREATE INDEX CONCURRENTLY avoids that, but builds slower and can leave an invalid index behind if it fails.

Try it yourself

1. 1

   Write three queries

   (a) “My bookings” for one user; (b) sold bookings counted for match 42; (c) booking BK-10421 by its code.

2. 2

   Choose the indexes

   Name each query’s WHERE columns; pick the index and its column order.

3. 3

   Count the writes

   Count where one new booking is written: table, primary key index and yours.

4. 4

   Check your answer

   (a) user_id. (b) (match_id, status), match first. (c) booking_code, ideally UNIQUE. Places: 1 + 1 + 3 = 5. You are right if each index matches a query and none is there as a precaution.

Back to Meera’s phone. The match page asks by id, the primary key, and the database indexes that by itself. “My bookings” asked by user_id, which had none, so the database read the whole book for one word.

Six more made each booking write to 9 places, and four of them helped no screen. Arjun keeps three, so each booking now writes to 5 places, and Meera has her fast demo.

Then Meera has news. The team moves to a new office in Baner, and a senior engineer joins there on Monday. Her first question: should payments, match details and venues all live in the same kind of database?