Database Indexes Explained with a Library of Books

For anyone who writes SQL queries or asks an AI to write them, including beginners. You do not need to know how a database works inside. Every term comes with an everyday picture, and the script and code are marked optional if you only want the results.

Every number in this article comes from an experiment I really ran on SQLite 3.53.4 (the version bundled with Python 3.14.8, macOS, arm64 chip), and the output is pasted as it came. The experiment is small, on one machine, with randomly generated data, so treat it as a way to learn, not as a performance benchmark. How a database really chooses a plan is complicated, and the pictures below are memory aids, not the whole story.

---

Quick summary#

• With no index, a database often has to read every row of the table to find a result. In the experiment with 100,000 books, finding one author took about 2.2 ms.
• After adding an index on the author column, the same query took about 0.03 ms, roughly 79 times faster (other runs gave 75 to 82 times).
• An index does not always help. For a column with only two values (in stock or not), the query used the index and still took 43.6 ms against 39.9 ms for a full scan.
• With a multi-column index, column order decides which queries can use it. An index on (genre, year) did not help a query that filters only on year, while an index on (year, genre) did.
• An index has a price: inserting 20,000 rows was about 2.2 times slower with one index and about 5 times slower with three, and the file grew by about 2.5 MB for the first index.
• The cheap check is to read the query plan (SCAN means a full scan, SEARCH means only part of the rows). It is also the evidence worth asking for when an AI writes a query for you.

---

Hard words, plain meaning#

---

After this article you can explain#

1. Why queries slow down as a table grows: without an index the time grows with the number of rows, with an index it grows very slowly.
2. A good index needs three things: the right leading column, a condition that rules out many rows, and a query that does not "hide" the column behind a function or a leading %.
3. Every index has a price: it slows writes and takes space, so add one when you can measure the benefit and drop it when nobody uses it.

---

1. A picture first: the library card catalogue#

Imagine a library with 100,000 books. You want every book by the author "Author 1234". One way is to walk past every shelf and open each book to see who wrote it. The other is to open the card catalogue, where the cards are already sorted by author, find "Author 1234" and read the cards there, each saying which shelf the book is on.

The second way is much faster, but it has conditions. The catalogue must have been made, and it must be kept correct every time the library receives new books. If you ask in a way the catalogue is not sorted for (for example "authors whose name ends in 1234"), the librarian still has to walk every shelf.

A database index is that catalogue. The rest of this article measures how much faster it is, when it does not help and what it costs, with real numbers.

Takeaway: an index does not make the table faster, it gives the database a shortcut when the question matches the way the shortcut is sorted.

---

2. The real experiment: 100,000 books#

2.1 Setup#

The books table has 100,000 randomly generated rows with a fixed seed, so you can rebuild exactly the same data: title, author (2,000 different authors, so about 50 books each), year of publication from 1950 to 2024, genre (8 kinds) and an in-stock column (about 90% equal to 1). Each query ran 200 times and I took the median. The database ran in memory (:memory:), so the numbers do not reflect a real disk; see the limits further down.

The full script is in section 7 so you can rerun it. Below is the output of the run I used as the main numbers of this article.

2.2 Finding one author: full scan against an index#

SELECT * FROM books WHERE author = 'Author 1234'    (59 result rows)

No index:
    plan : SCAN books
    median: 2.204 ms

After CREATE INDEX idx_author ON books(author):
    plan : SEARCH books USING INDEX idx_author (author=?)
    median: 0.028 ms

The plan changed from SCAN (walk the whole table) to SEARCH books USING INDEX (use the index), and the time fell from 2.204 ms to 0.028 ms, about 79 times faster. I ran the whole script four times and the ratio stayed between 75 and 82 times. I measured only one table size (100,000 rows), so I cannot show how the time changes with a bigger table. In principle a scan must pass through every row, so it takes longer as the table grows, while the PostgreSQL docs describe an index lookup as walking a few levels of a search tree.

Takeaway: for a condition that rules out almost every row, an index gives a very large improvement.

2.3 A column with two values: the index is used and it is still not faster#

SELECT * FROM books WHERE in_stock = 1              (89,966 result rows)

No index:
    plan : SCAN books
    median: 39.896 ms

After CREATE INDEX idx_stock ON books(in_stock):
    plan : SEARCH books USING INDEX idx_stock (in_stock=?)
    median: 43.571 ms

Here the plan does use the index (SEARCH books USING INDEX) but the time did not fall, it even got a little slower (43.571 against 39.896 ms). The most reasonable explanation: the query still has to fetch almost 90% of the rows, so the main work is reading and passing on 89,966 rows, and an index lookup does not reduce that part. This is my explanation; I did not separate the cost of each step to prove it.

I also tried the other side: in_stock = 0 returns only 10,034 rows (about 10%). On a fresh database, the scan took 5.551 ms and the index 5.029 ms, only about 9% faster. Even when the query rules out 90% of the rows, the benefit is small compared with the 79 times for one author, because an author matches only 59 rows out of 100,000.

Takeaway: selectivity decides the value of an index. The question to ask is "how many rows does this condition rule out?", not "is this column often filtered on?". Seeing USING INDEX in a plan does not mean the query is fast.

2.4 A multi-column index: column order decides#

I tried two indexes on genre (genre) and year (year), with two queries.

Query A: WHERE genre = 'tech' AND year >= 2020    (827 rows)
Query B: WHERE year = 2015                        (1,321 rows)

No multi-column index:
    A: SCAN books                                         3.124 ms

Index (genre, year):
    A: SEARCH books USING INDEX idx_genre_year (genre=? AND year>?)   0.437 ms
    B: SCAN books                                         2.067 ms

Index (year, genre):
    A: SEARCH books USING INDEX idx_year_genre (year>?)     0.561 ms
    B: SEARCH books USING INDEX idx_year_genre (year=?)     0.694 ms

Reading it:

• Query A can use both indexes, but the (genre, year) index uses both conditions (genre=? AND year>?) while the (year, genre) index can use only the first condition, year>?. The times are 0.437 against 0.561 ms: different, but not by much.
• The big difference is in query B. The (genre, year) index cannot be used for a query that filters only on year (the plan is still SCAN, 2.067 ms), while the (year, genre) index can (0.694 ms).

Picture a catalogue sorted in two levels: first by genre, then by year inside each genre. Asking for "genre tech, year 2020 or later" goes straight to the tech drawer and reads on. Asking for "every book from 2015" finds 2015 scattered across every genre drawer, so the catalogue cannot help. The SQLite docs state this rule: the columns of an index are used from left to right, without gaps. Use The Index, Luke (Markus Winand) compares it with a phone book sorted by surname, where you cannot look someone up by first name alone.

One caution so you do not over-read this: for a query that uses equality on both columns (for example year = 2015 AND genre = 'tech'), I tried both orders and both used both columns, about 0.07 ms each against 1.6 ms for a scan. Column order matters most when there are queries filtering on a single column, or range conditions (>=, BETWEEN) on the leading column. The PostgreSQL docs also advise using multi-column indexes sparingly and say an index with more than three columns is rarely helpful unless table usage is very regular. PostgreSQL 18 can even "skip" the leading column in some cases, so the column order rule here is a general rule, not a law for every system and every version.

Takeaway: write down your real queries first, then choose the column order so that the leading column appears in as many of them as possible.

2.5 When an index exists and the query still scans#

I kept idx_author and tried four ways of asking for the same author:

WHERE lower(author) = 'author 1234'     plan: SCAN books                  5.539 ms
WHERE author LIKE '%1234'               plan: SCAN books                  3.798 ms
WHERE author LIKE 'Author 1234%'        plan: SCAN books                  2.852 ms
WHERE author GLOB 'Author 1234*'        plan: SEARCH books USING INDEX idx_author (author>? AND author<?)   0.029 ms

• Wrapping the column in a function (lower(author)): the index is sorted by author, not by lower(author), so it is ignored. Like a catalogue sorted by the original name while you ask using the lowercase version of the name.
• A % at the start (LIKE '%1234'): the catalogue is sorted by the first letters, so asking by the end of the name cannot use it.
• LIKE with a fixed beginning (LIKE 'Author 1234%'): in theory it can use an index, but here it is still SCAN. According to the SQLite docs, LIKE is case-insensitive by default, so it can use an index only when the column uses the NOCASE collation. My default index compares byte by byte (BINARY), so it cannot be used. When I also created an index on author COLLATE NOCASE, the plan changed to SEARCH.
• GLOB is case-sensitive, so it matches the default index and took 0.029 ms.

This detail is specific to SQLite. PostgreSQL has its own rules about LIKE and indexes (they depend on the collation and the index type), and I did not check them in this round. The general lesson still holds: do not guess, read the plan.

2.6 The price: slower writes and more space#

Insert 20,000 rows into a 100,000 row table (median of 7 runs, in memory):

0 indexes                                  6.4 ms   (x1.00)   file 4.98 MB
1 index (author)                          13.9 ms   (x2.18)   file 7.48 MB
3 indexes (author, genre+year, title)     31.8 ms   (x5.00)   file 12.23 MB

Each time a row is inserted, the database must update the table and every index. Three indexes made inserting about 5 times slower, and the file nearly 2.5 times bigger (from 4.98 MB to 12.23 MB). The PostgreSQL docs also say an index adds overhead to data modification and advise dropping indexes that are rarely or never used.

Note: the example ran in memory, with bulk inserts in one transaction, no concurrent access and no disk. A real system can differ quite a lot, in either direction. Use this number to see the direction (writes cost more with more indexes), not to forecast.

Takeaway: add indexes for the queries you really run often, and measure again. An index "just in case" on every column is a way of paying a lot for something that goes unused.

---

3. How to read a query plan#

Picture the librarian telling you in advance how they will search. In SQLite you type EXPLAIN QUERY PLAN before the query:

EXPLAIN QUERY PLAN SELECT * FROM books WHERE author = 'Author 1234';

According to the SQLite docs, there are two words to know:

Three easy mistakes:

1. SEARCH does not guarantee speed (the example in 2.3 used the index and still took about as long as a scan).
2. The brackets show which condition the index uses. In 2.4, (year>?) shows that only half of the conditions were used.
3. The SQLite docs state that this output is meant for human readers and may change between versions, so do not write code that depends on it.

Other systems have similar tools with different formats. PostgreSQL uses EXPLAIN (and EXPLAIN ANALYZE to run and measure), so do not carry the SQLite way of reading plans over to it unchanged.

---

4. Where indexes often go wrong#

Picture a library with a single librarian: the more catalogues, the busier they are whenever books arrive.

4.1 What about AI-written queries#

An AI assistant writing a query usually does not know whether your table will have 100 or 100 million rows unless you say so. The query it writes is usually correct in its results and fast on test data, so a reviewer easily lets it pass. I have not found independent measurements of how often AI-generated queries lack an index, so this is a warning from the mechanism, not from data. The cheapest remedy is to ask for evidence, as in way 2 of Make AI Output Prove Itself: ask the AI to paste the real query plan and the assumed number of rows.

---

5. Illustration: a query that was fine at first and slow months later#

This is an illustration. It names no real person or product, and the scaled-up numbers are multiplications I made up, not measurements.

• 10:00. A dev asks an agent: "Add a screen to search books by author."
• 10:20. The agent writes the query WHERE author = ?, tries it on 1,000 books and it runs in under 1 ms. The dev approves because the result is right and the tests are green.
• Three months later, 09:30. The catalogue has 5 million books. If scan time grew in proportion to the row count (an assumption for illustration), 2.2 ms at 100,000 rows becomes about 110 ms at 5 million rows (2.2 times 50). Each author search now occupies the machine for a noticeable time, and when many people search at once the screen feels slow.
• The fix: run the query plan, see SCAN books, add an index on author and measure again. With the assumption that an index lookup grows very slowly with row count, the time would stay very small.

What to do from 10:20: when reviewing a new query, ask for the query plan and the expected number of rows. The illustration proves nothing. The evidence is the experiment in section 2 and the PostgreSQL docs: an index costs something on writes, so choose it on purpose and measure, instead of adding them everywhere. As for the need to learn this, ITviec (through search results, the figure being from the job platform's own data) reports job postings requiring SQL up about 38.7% year on year in Q3 2025, so this is not a skill made obsolete by AI.

---

6. Exercises with an answer key#

Run the script in section 7 once to have the data, then do three exercises. Try to guess the result before you run it.

Exercise 1. Add an index for the query WHERE year = 2015 AND genre = 'tech'. Try both (year, genre) and (genre, year). Which index uses both conditions, and how do the times differ?

Exercise 2. Create an index on in_stock, then run WHERE in_stock = 0 and WHERE in_stock = 1. Why is the benefit so different from searching by author?

Exercise 3. Run WHERE author LIKE 'Author 1234%' when only the default index on author exists. Why is it still a SCAN? There are two ways to fix it; can you find them?

Answers (from my run)#

Exercise 1. Both orders use both conditions, because both are equalities:

no index:      SCAN books                                    1.602 ms (149 rows)
(year, genre): SEARCH books USING INDEX a (year=? AND genre=?) 0.071 ms
(genre, year): SEARCH books USING INDEX b (genre=? AND year=?) 0.074 ms

The difference is almost nothing. The point to remember: for a query using only equality on every column, the order matters little. It matters when a query filters on a single column (as in 2.4) or has a range.

Exercise 2. On a fresh database for each measurement:

in_stock = 0  (10,034 rows): scan 5.551 ms, index 5.029 ms
in_stock = 1  (89,966 rows): scan 39.209 ms, index 41.749 ms

The benefit is tiny for = 0 (about 9%) and absent for = 1. Fetching and passing on many rows takes most of the time. The lesson: selectivity, and the number of rows returned, decide the value of an index. Some other queries on this column may still benefit (for example counting the books in stock could use a covering index); I did not measure that case separately in this article.

Exercise 3. According to the SQLite docs, LIKE is case-insensitive by default, so the LIKE optimization uses only an index with the NOCASE collation. The default index is BINARY, so it is not used. Two fixes: write GLOB 'Author 1234*' (GLOB is case-sensitive and can use a BINARY index, 0.029 ms), or create the index CREATE INDEX nc ON books(author COLLATE NOCASE), after which LIKE 'Author 1234%' switches to SEARCH (I tried it: 0.029 ms).

---

7. The script to rerun (optional)#

All you need is Python 3 (the sqlite3 library is included). Save it as index_demo.py and run python3 index_demo.py. It takes about half a minute. The numbers will differ by machine, but the shape of the results (SCAN against SEARCH, which times are larger or smaller) should be similar.

import itertools
import random
import sqlite3
import statistics
import time

N = 100_000
REPS = 200
GENRES = ["novel", "science", "history", "children", "cooking", "tech", "poetry", "comic"]


def make_rows(n, seed):
    rnd = random.Random(seed)
    rows = []
    for i in range(n):
        rows.append((
            f"Book {rnd.randrange(10**6):06d}",
            f"Author {rnd.randrange(2000):04d}",
            rnd.randrange(1950, 2025),
            rnd.choice(GENRES),
            1 if rnd.random() < 0.9 else 0,
        ))
    return rows


def new_db(rows):
    db = sqlite3.connect(":memory:")
    db.execute("CREATE TABLE books (id INTEGER PRIMARY KEY, title TEXT, author TEXT, "
               "year INTEGER, genre TEXT, in_stock INTEGER)")
    db.executemany("INSERT INTO books (title, author, year, genre, in_stock) VALUES (?,?,?,?,?)", rows)
    db.commit()
    return db


_n = itertools.count()


def plan(db, sql):
    # the counter comment makes each EXPLAIN text unique, so Python never reuses a stale cached plan
    return [r[3] for r in db.execute(f"EXPLAIN QUERY PLAN /*{next(_n)}*/ " + sql)]


def timed(db, sql):
    samples = []
    count = 0
    for _ in range(REPS):
        t = time.perf_counter()
        count = len(db.execute(sql).fetchall())
        samples.append((time.perf_counter() - t) * 1000)
    return statistics.median(samples), count


def show(db, label, sql):
    p = plan(db, sql)
    ms, count = timed(db, sql)
    print(f"[{label}] {sql}")
    print(f"    plan : {' | '.join(p)}")
    print(f"    rows : {count}   median: {ms:.3f} ms over {REPS} runs")


rows = make_rows(N, seed=42)
db = new_db(rows)
print("SQLite", sqlite3.sqlite_version, "rows", N)
print()

print("=== 1. One author: scan then index ===")
q1 = "SELECT * FROM books WHERE author = 'Author 1234'"
show(db, "no index", q1)
db.execute("CREATE INDEX idx_author ON books(author)")
show(db, "index on author", q1)
print()

print("=== 2. A column with two values (in_stock: 90% are 1) ===")
q2 = "SELECT * FROM books WHERE in_stock = 1"
show(db, "no index", q2)
db.execute("CREATE INDEX idx_stock ON books(in_stock)")
show(db, "index on in_stock", q2)
db.execute("DROP INDEX idx_stock")
print()

print("=== 3. Two columns: order matters ===")
q3 = "SELECT * FROM books WHERE genre = 'tech' AND year >= 2020"
q4 = "SELECT * FROM books WHERE year = 2015"
show(db, "no composite index, q3", q3)
db.execute("CREATE INDEX idx_genre_year ON books(genre, year)")
show(db, "index (genre, year), q3", q3)
show(db, "index (genre, year), q4 uses year only", q4)
db.execute("DROP INDEX idx_genre_year")
db.execute("CREATE INDEX idx_year_genre ON books(year, genre)")
show(db, "index (year, genre), q3", q3)
show(db, "index (year, genre), q4 uses year only", q4)
db.execute("DROP INDEX idx_year_genre")
print()

print("=== 4. Queries an index on author cannot help ===")
q5 = "SELECT * FROM books WHERE lower(author) = 'author 1234'"
q6 = "SELECT * FROM books WHERE author LIKE '%1234'"
q7 = "SELECT * FROM books WHERE author LIKE 'Author 1234%'"
show(db, "index on author, lower()", q5)
show(db, "index on author, LIKE '%1234'", q6)
show(db, "index on author, LIKE 'Author 1234%'", q7)
q8 = "SELECT * FROM books WHERE author GLOB 'Author 1234*'"
show(db, "index on author, GLOB 'Author 1234*'", q8)
print()

print("=== 5. The price: size and inserts (20,000 new rows, 7 runs each) ===")
extra = make_rows(20_000, seed=7)


def insert_time(index_sqls):
    samples = []
    pages = 0
    for _ in range(7):
        d = new_db(rows)
        for s in index_sqls:
            d.execute(s)
        t = time.perf_counter()
        d.executemany("INSERT INTO books (title, author, year, genre, in_stock) VALUES (?,?,?,?,?)", extra)
        d.commit()
        samples.append((time.perf_counter() - t) * 1000)
        pages = d.execute("PRAGMA page_count").fetchone()[0] * d.execute("PRAGMA page_size").fetchone()[0]
        d.close()
    return statistics.median(samples), pages / (1024 * 1024)


setups = [
    ("0 indexes", []),
    ("1 index (author)", ["CREATE INDEX i1 ON books(author)"]),
    ("3 indexes (author, genre+year, title)", [
        "CREATE INDEX i1 ON books(author)",
        "CREATE INDEX i2 ON books(genre, year)",
        "CREATE INDEX i3 ON books(title)",
    ]),
]
base = None
for name, sqls in setups:
    ms, mb = insert_time(sqls)
    base = base or ms
    print(f"{name:40s} insert 20,000 rows: {ms:8.1f} ms  (x{ms / base:.2f})   size after: {mb:6.2f} MB")

---

8. A checklist before adding or reviewing a query#

1. How many rows will this table have after a year, and did I try it at that size?
2. Did I read the query plan? Is the first line SCAN or SEARCH?
3. About what percentage of rows does the filter rule out?
4. Does the query wrap the column in a function, or put % at the start of a LIKE?
5. For a multi-column index, does the leading column appear in the real queries?
6. Which conditions do the brackets in the plan show the index using?
7. Is the write cost of the new index acceptable for a table that changes often?
8. Is there an old index that no longer appears in the plan of any real query and can be dropped?
9. If an AI wrote the query, did it paste the plan and the assumed number of rows for me?

---

9. A balanced view#

Fairly solid (measured or in the docs): an index can make a selective query tens of times faster at around 100,000 rows; selectivity, column order and the way the condition is written decide whether an index helps; indexes make writes slower and take space.

Handle with care:

• The experiment ran on one machine, in memory, with randomly generated data distributed evenly. Real data is often skewed (a few authors have very many books), and disks, caches and concurrent access change the results.
• SQLite is not PostgreSQL or MySQL. Each has its own planner, LIKE rules, index types and optimizations (for example PostgreSQL 18 can skip the leading column in some cases). I did not test PostgreSQL directly in this round, and what is said about it comes from its docs.
• The article does not cover planner statistics (ANALYZE), partial indexes, deeper covering indexes, caching or how a table is stored on disk. Those are good topics to learn next.
• The 79 times figure belongs to this experiment. Do not use it as a promise for your system.

Do not overstate: an index is not a cure for every slow query. Sometimes a query is slow because it fetches too many rows or columns, lacks a LIMIT, or because of the table design. Do not dismiss it either: on a large table, not reading the query plan is often the cheapest cause to fix.

---

10. Conclusion#

An index is the database's card catalogue: very fast when the question matches the way it is sorted, useless when it does not, and always costly to maintain. To use it well you need three habits: read the query plan, ask how many rows the condition rules out, and measure again after adding one. For a query written by AI, ask for that same plan as evidence. These habits will outlast any tool.

To go further: Reviewing AI-Written Code has a checklist for changes, and Testing AI-Written Code helps you have tests protecting you when you change a query.

---

References#

The measurements in this article are mine, run on SQLite 3.53.4 (Python 3.14.8, macOS arm64), and may differ on your machine. I opened the documents below to check the points attributed to them. The ITviec figure was seen only through search results and I did not open the original report.

• SQLite, The SQLite Query Optimizer Overview (multi-column indexes used left to right, the conditions for the LIKE and GLOB optimizations)
• SQLite, EXPLAIN QUERY PLAN (meaning of SCAN, SEARCH and USING INDEX, the note that the format may change)
• PostgreSQL, Multicolumn Indexes and Introduction to indexes (version 18 docs)
• Markus Winand, Use The Index, Luke: Concatenated Indexes
• ITviec, Vietnam IT recruitment market overview Q3 2025 (seen only through search results, measures only job postings on its own platform)