Module 04 · Lesson 4 of 14Free

Indexes: speeding up queries without full scans

Level

Beginner

Topic

SQL databases: modeling, indexing and transactions

Reading time

15 min

Twenty products, a million checks

A customer opens a seller’s page on Kartly. The database checks a million product rows to show just 20 products. During the festival sale, other customers compete for those same database resources.

How can the database find the right products without checking every row?

Kartly is now split into services with sharded data. This lesson follows one catalog shard containing a million products. Assume seller 7 owns 500 of them. These are illustrative numbers for this lesson, not measurements.

The catalog service asks for that seller’s cheapest products:

SELECT product_id, name, price_minor
FROM products
WHERE seller_id = 7
ORDER BY price_minor, product_id
LIMIT 20;

price_minor stores integer paise. product_id breaks price ties, giving the query a stable order.

An index stores selected values in a structure that supports faster lookup. PostgreSQL can use it instead of scanning every row.^{111.1. IntroductionPostgreSQL Global Development Group, PostgreSQL 18 Documentation}

The problem is finding candidates cheaply. Returning fewer rows does not necessarily mean examining fewer rows.

Store a route to the rows

Without a useful index, the simplest solution is a full scan: examine the table and test each row. No extra lookup structure needs maintenance.

For our query, the executor keeps seller 7’s rows and selects the cheapest results. It need not sort every product, but it still checks every row.

A seller index gives it a different route:

-- Catalog database: supports finding one seller's products.
CREATE INDEX products_seller_idx ON products (seller_id);

Think of entries grouped by seller, each leading back to a product row. Duplicate seller values are expected: one seller owns many products. SQLite’s documentation illustrates this key-to-row lookup mechanism explicitly.^{2Query PlanningSQLite, SQLite Documentation}

The entries are not full product records. Our seller index does not contain the product names or prices the response needs.

Follow one read

1. The catalog service sends the SQL through its data-access layer, covered in Repository pattern.
2. The database executor seeks the beginning of seller 7’s entries.
3. It follows matching entries to fetch the product rows.
4. It reads prices, selects the cheapest products, and returns the requested fields.

If the index has no matching entry, this path returns an empty result. It does not need a second full scan.

The index belongs to the database. Application code does not fetch row locations or maintain entries itself.

A seller index removes unrelated sellers from this path. It does not yet solve the price ordering.

Buy fewer checks with extra writes

An index is not automatically the right answer. First compare the avoided work with the work it introduces.

For this scenario, compare logical row candidates:

The fraction of rows matched is often called selectivity. Here, the seller filter matches a small fraction, making targeted lookup attractive.

Now change the request. Suppose a catalog export needs almost every product and has no ordering requirement. Following index references would add work without skipping much data. A sequential pass becomes a reasonable alternative.

The query planner chooses an execution strategy from available paths. PostgreSQL uses statistics to help decide whether an index is worthwhile.^{111.1. IntroductionPostgreSQL Global Development Group, PostgreSQL 18 Documentation} Query plans explains how to inspect that choice.

The index is an option, not an instruction to use it.

Column order determines the shortcut

The seller index still leaves a problem. It finds the seller’s products, but not in price order.

A composite index uses more than one column as its key. The first column determines the main grouping. Later columns order entries within equal earlier values.^{2Query PlanningSQLite, SQLite Documentation}

For our query, use seller, then price, then product ID:

-- Catalog database schema fragment.
CREATE TABLE products (
  product_id BIGINT PRIMARY KEY,
  seller_id BIGINT NOT NULL,
  name TEXT NOT NULL,
  price_minor BIGINT NOT NULL CHECK (price_minor >= 0)
);

-- Supports one seller's cheapest products, with stable price ties.
CREATE INDEX products_seller_price_id_idx
ON products (seller_id, price_minor, product_id);

The table relationships are covered in Relational data modeling. This fragment shows only fields relevant to our access path.

Consider these index keys:

Seller 8’s cheaper product comes after seller 7’s products because seller is the first key.

This arrangement lets the executor seek seller 7’s range and read in the requested order. An ordered composite index can support filtering and ordering together.^{2Query PlanningSQLite, SQLite Documentation}

In our simplified example, it can stop after collecting 20 matching products. It no longer needs all 500 prices before choosing the cheapest ones. Names still come from the table.

The leading columns also determine which other lookups fit naturally. MySQL documents this as using the leftmost prefixes of a composite index.^{310.3.6 Multiple-Column IndexesOracle, MySQL 8.4 Reference Manual}

Our chosen index can locate one seller without specifying a price. A price-only filter does not identify one continuous seller-first range.

That is a design rule, not a claim that databases can never use later columns. Judge the access path for the actual query.

Every shortcut needs maintenance

Suppose a seller adds a product. The catalog service writes the row; PostgreSQL maintains the index automatically.^{111.1. IntroductionPostgreSQL Global Development Group, PostgreSQL 18 Documentation}

Conceptually, the write path is:

1. Accept the product fields.
2. Store the table row.
3. Add the corresponding seller-price-ID entry.
4. Report success after the database operation succeeds.

The application must not write the table and index separately.

For a price change, the key’s old price position becomes obsolete. The database must maintain the index accordingly. Two concurrent price changes are still a transaction problem, not something a normal lookup index resolves. Isolation levels and locking covers that behavior.

This exposes the cost of “index every column.” Each extra structure occupies space and adds maintenance. PostgreSQL explicitly warns about this write overhead.^{111.1. IntroductionPostgreSQL Global Development Group, PostgreSQL 18 Documentation}

For Kartly, the original seller-only index may now duplicate a useful leading part of the composite index. Treat it as a removal candidate. Check the wider workload before removing it.

Deploy without stopping sellers

Building the index also requires work against existing data. PostgreSQL’s ordinary index creation permits reads but blocks writes during the build.^{111.1. IntroductionPostgreSQL Global Development Group, PostgreSQL 18 Documentation}

On the live catalog, sellers could be unable to save product changes. Use the deployment approach covered in Online index builds on live tables, rather than running this lesson’s basic command without planning.

After deployment, compare seller-page latency, product-update latency and index size. Test a large seller as well as a typical seller.

If seller pages stay slow, inspect the chosen access path before adding another index. If writes become slower, review which indexes actually serve requests. Remove unnecessary ones through a planned change.

An index should earn its ongoing cost, not only make one isolated read look faster.

Common mistakes

• Treating a small response as little work. Our first query returns few rows but must identify the cheapest matches.
• Choosing columns without choosing their order. Seller-first and price-first answer different questions efficiently.
• Calling every full scan a failure. A broad export may benefit little from indexed row lookups.
• Expecting an index to remove output cost. Returning many matching products still requires producing and transferring them.

Where this shows up

• Design: a key-value store built on SQL: key lookup needs an access path that avoids searching unrelated records.
• Design: a fast product catalog page: efficient database reads matter when a requested page is not cached.

We have chosen an ordered access path; next, B-trees explain how that order stays searchable as products change.

Check your understanding

Summary