Indexes: Building a Faster Way to Find Things

15.1.1 PLAIN — in simple words#

1. An index keeps selected information arranged so that certain questions can reach useful records without inspecting everything. It resembles a guide, but it is part of the database’s maintained state.
2. A guide arranged by order number helps with order-number questions. It may do little for a search based on a note buried inside a description.
3. The guide must still lead to the right records. An index key and the rest of a row can live in different structures, so finding an entry is not always the end of the work.
4. Different index designs support different operations. Equality, ordered ranges, text search and geometric proximity are not interchangeable questions.

15.1.2 PLAIN — a picture in your head#

1. A book’s alphabetical index maps a topic to pages. It can save opening every page to find “transactions.” The contents page is another guide, organised by the book’s hierarchy rather than by topic.
2. Neither guide replaces the chapters. A useful entry must identify where the explanation actually appears.
3. Where the comparison breaks: a printed index is fixed after publication. A database index often changes as records are inserted, updated or removed. It also contains machine comparison keys and record locators rather than human topic descriptions.

15.1.3 PLAIN — a worked example#

1. The shop asks, “Which agreed lines refer to P-NOTE?” The original four lines contain two matching line records, representing three units. Keep the distinction between matching rows and units.

CREATE INDEX order_lines_product_idx
ON order_lines(product_id);

SELECT order_id, line_no, quantity, unit_price_minor
FROM order_lines
WHERE product_id = ?
ORDER BY order_id, line_no;

2. This SQLite example uses a bound parameter for P-NOTE. It creates an additional candidate access path in a disposable practice database; the tiny table may still be scanned.
3. The correct result must not change after index creation. Compare complete ordered result rows before discussing the plan or time.
4. An index on product_id does not itself promise the final order by order identifier and line number. That ordering remains an explicit requirement of the query.

15.1.4 PLAIN — what is really happening inside#

1. An index stores keys in a form suited to a supported operation. Entries also contain, or imply, enough identity to reach the corresponding data according to the engine’s layout.
2. A lookup navigates the structure, obtains candidates, applies required checks and retrieves additional fields when needed. The route can be shorter than a broad scan but still involve several steps.
3. Index structure is engine-specific. A SQLite rowid-table secondary index and a PostgreSQL heap index do not use identical record-location and visibility machinery. Chapter 16 separates the common ordered-tree idea from those details.
4. An index can support enforcement as well as access. Unique indexes help enforce uniqueness in specific engines, but the business meaning and NULL rules still come from the chosen schema and product behaviour.

15.1.5 TECHNICAL — the engineer’s version#

1. Treat an index as a maintained access method with an operator contract. PostgreSQL offers B-tree, hash, GiST, SP-GiST, GIN and BRIN methods for different classes of operations; the mere presence of an index says little without its method and supported operators. [S104]
2. A secondary access path can return candidate record locations rather than a complete final result. Rechecks, visibility checks and additional field retrieval may remain. SQLite and PostgreSQL documentation describe their own layouts; do not transplant one engine’s assumptions into another. [S89] [S92]
3. CREATE INDEX is a schema-changing operation. Use disposable databases for the exercises. Building an index on a live table has concurrency, space and operational consequences not established by this four-row demonstration.

15.1.6 WORDS — remember these#

1. Index: an extra route to selected records — a maintained data structure supporting specified search, ordering or constraint operations. Access method: the machinery behind a route — an engine-defined algorithm and operator interface used to organise and search index entries. Secondary index: an additional searchable organisation — an access path distinct from the primary physical or identifying organisation of the table.

15.2.1 PLAIN — in simple words#

1. A useful index can reduce work for reads. Keeping it correct adds work to changes that affect its entries.
2. Every extra structure also occupies space, participates in backup and maintenance, and competes for memory when used. An unused index can therefore cost something even while no query benefits from it.
3. A write does not always update every index in exactly the same way. Which fields change and how the engine stores versions matter. Avoid the opposite oversimplification that one row update always performs one identical operation per index.
4. Evaluate an index against a workload: how often questions run, what they need, how often data changes, and which delays are acceptable.

15.2.2 PLAIN — a picture in your head#

1. Dev maintains three paper guides to the same folders: by order number, customer and product. Looking up a folder can be easier, but a new order now requires the appropriate entries in several guides.
2. A guide nobody consults still takes shelf space and must not be allowed to point to nonexistent folders.
3. Where the comparison breaks: database maintenance is coordinated by an engine and can use batching, page splits, logging and versioning. The cost is not simply “three guides equals three times the duration,” and an engine may avoid some index work for eligible updates.

15.2.3 PLAIN — a worked example#

1. Use a hypothetical workload of 50,000 product lookups and 2,000 line inserts per hour. Suppose measurements in a particular test show the candidate index saves 200 microseconds per lookup but adds an average 20 microseconds to each insert under that test’s conditions.
2. The simplified saved read time is 50,000 × 200 µs = 10 seconds of summed operation durations per hour. The extra insert duration is 2,000 × 20 µs = 0.04 seconds.
3. This arithmetic is not a production recommendation. The numbers are invented, summing durations does not directly yield wall-clock capacity, and storage, tail latency, contention and index-build cost are omitted.
4. Now reverse the mix: few lookups and millions of writes. The same local trade-off can become unattractive. Requirements, not the word “index,” decide what deserves measurement.

15.2.4 PLAIN — what is really happening inside#

1. Insertions add index entries. Updates to indexed values may replace or add representations. Deletions and version cleanup remove or retire entries according to the storage engine.
2. Ordered indexes may need page splits when a page has insufficient room. Wider keys and included payload can reduce entries per page, increasing size and affecting cache behaviour.
3. Maintenance includes more than immediate writes. Vacuuming or cleanup, rebuilding when justified, statistics collection and monitoring all have resource costs. The exact operations depend on the engine.
4. Removing an index can also remove an enforcement mechanism or harm a less frequent but important query. Inspect dependencies and workload coverage before treating “rarely observed” as “safe to delete.”

15.2.5 TECHNICAL — the engineer’s version#

1. Read amplification, write amplification and space amplification are separate ratios whose baselines must be specified. An index can improve one while worsening another. Do not report a percentage without stating the counted operations or bytes.
2. PostgreSQL’s B-tree implementation includes page management and version-related maintenance details; covering payload increases index size. These observations motivate testing, not a universal write-cost multiplier. [S105] [S92]
3. A uniqueness-supporting structure is not merely a performance accessory. Changing or removing it requires preserving the intended constraint through an explicitly reviewed alternative, not just comparing SELECT timings.
4. Benchmark both the intended benefit and affected write paths, including representative skew and concurrency. A read-only microbenchmark establishes only its read-only result.

15.2.6 WORDS — remember these#

1. Write amplification: extra work caused by one logical change — a ratio of physical or internal writes to a clearly defined logical write baseline. Index maintenance: keeping the extra route correct — updates, cleanup and related work required as the underlying data changes. Workload mix: the combination of operations a system serves — their frequencies, parameters, sizes, concurrency and correctness requirements.

15.3.1 PLAIN — in simple words#

1. A composite index organises entries using more than one field. Their order matters because the first field groups entries before the second field orders within each group.
2. An index on (branch_id, order_date) is naturally useful for dates within one branch. It is not physically identical to (order_date, branch_id).
3. This does not mean a later column can never help. Engines have additional strategies, and an index may still be useful for other reasons. The safe statement is that leading-key constraints strongly influence the part of an ordinary ordered index that can be narrowed efficiently.
4. Choose an order from concrete questions, not an alphabetic sorting of column names.

15.3.2 PLAIN — a picture in your head#

1. A telephone directory sorted by surname and then given name groups everyone named Singh together. Looking for a specific surname gives you a clear region. Looking for everyone named Dev across all surnames is a different task.
2. A directory sorted by given name first would reverse those conveniences.
3. Where the comparison breaks: database optimisers may combine indexes, scan narrower index entries, use skip-like strategies in particular versions, or choose other access methods. The directory analogy explains lexicographic grouping, not a prohibition on all alternative execution techniques.

15.3.3 PLAIN — a worked example#

1. Consider invented keys (A, 1), (A, 3), (A, 8), (B, 2), (B, 7) in an index ordered by branch and day.
2. The condition branch = A AND day >= 3 identifies a contiguous suffix within A’s region: (A, 3) and (A, 8).
3. The condition day = 7 without a branch does not describe one simple leading-key region in this ordering. The matching key lies inside B’s group; more branches would create more groups to consider.
4. For the real four-line fixture, an index on (product_id, order_id, line_no) groups by product and orders matching product entries by the remaining key. Whether it removes a sort for a particular query should be checked in that engine’s actual plan.

CREATE INDEX order_lines_product_order_idx
ON order_lines(product_id, order_id, line_no);

5. This is a candidate for the exercise, not an instruction to keep both this index and every earlier overlapping index permanently.

15.3.4 PLAIN — what is really happening inside#

1. Ordered tuple comparison examines the first differing field. Equal leading fields allow the search to focus on a narrower set of later-field values.
2. A range condition can widen the region compared with an equality. Additional conditions may still reject entries, but they do not necessarily reduce the initial visited interval in the same way.
3. Sorting requirements add another dimension. A mixture of ascending and descending directions, null placement and collation must match the query’s required ordering before an index can be assumed to supply it.
4. Redundant-looking indexes are not automatically redundant in performance: width, uniqueness, predicates and included columns differ. Conversely, several overlapping indexes may create avoidable maintenance. Inspect purpose and measured workload, not names alone.

15.3.5 TECHNICAL — the engineer’s version#

1. For the explicitly cited PostgreSQL 17 B-tree behaviour, equality constraints on leading columns and a range condition on the first subsequent non-equality column are central to limiting the scanned portion. Constraints farther right can still be checked; their usefulness is not equivalent to leading equality. [S91]
2. This is version- and method-specific guidance, not a timeless claim that every database can only use a leftmost prefix. SQLite describes its own composite-index and planning rules. [S89] [S98]
3. An index’s lexicographic order and the final ORDER BY are separate contracts. Confirm the actual plan and retain the explicit final ordering even when a current execution happens to emit the desired sequence. [S106]

15.3.6 WORDS — remember these#

1. Composite index: one index built from several fields — an access structure over tuples of expressions in a specified order. Leading key: the first part of an ordered index key — the prefix that groups entries before later components are compared. Lexicographic order: compare the first difference — tuple ordering determined by the earliest component on which two tuples differ.

15.4.1 PLAIN — in simple words#

1. A covering index contains the values a particular query needs, so the engine may be able to answer using the index without retrieving every full table row. Covering is relative to a query, not a permanent label that covers all possible questions.
2. A partial index contains only records satisfying a stated condition. It can be smaller than an index of the whole table and useful for a frequently queried subset.
3. These are different ideas. One concerns which values an entry carries; the other concerns which records receive entries.
4. Both create obligations. Wider entries cost space and maintenance. A partial index helps only when the engine can establish that its contents are sufficient for the query.

15.4.2 PLAIN — a picture in your head#

1. A quick-reference card contains an order number and the small amount field a clerk needs. The clerk can answer some questions from the card without fetching the entire folder. That is the covering idea.
2. A separate guide listing only unfinished orders is the partial-index idea. It is useful for a question about unfinished work, not for a complete history of all orders.
3. Where the comparison breaks: the database still has transaction-visibility rules. Having the requested values in an index does not always establish that the entry is visible to the current transaction without another check. Nor does an index independently decide what “unfinished” means.

15.4.3 PLAIN — a worked example#

1. In a new disposable table for this exercise, define tasks(task_id, branch_id, status, created_at), with status restricted to open or closed. These are invented work items, not extra canonical sales.

CREATE INDEX open_tasks_by_branch
ON tasks(branch_id, created_at, task_id)
WHERE status = 'open';

2. The partial index omits closed tasks. A query whose conditions include status = 'open' and a branch can be a candidate user of this index. A query for every task in that branch cannot rely on it alone because closed tasks are missing.
3. A query returning only branch, creation time and task identifier may also be covered by these indexed fields in an engine and plan that can use them that way.
4. In PostgreSQL, non-key payload can be expressed with INCLUDE, for example ON tasks(branch_id, created_at) INCLUDE (task_id) WHERE status = 'open'. This is PostgreSQL syntax, not SQLite syntax, and it is documented here rather than executed in the SQLite lab. [S92]

15.4.4 PLAIN — what is really happening inside#

1. Partial-index maintenance evaluates its predicate as relevant records change. A task moving from open to closed leaves the indexed subset; moving back can add it again.
2. To use a partial index safely, the planner needs to know that every qualifying query row belongs to the indexed subset. Superficial similarity between two predicates is not a proof of that implication.
3. A parameterised query may not expose enough information at the relevant planning stage for a particular partial index to be chosen. Behaviour depends on the engine, parameter values and plan strategy. Do not replace safe binding with string concatenation merely to force a desired plan.
4. Covering can reduce full-row retrieval, but carrying a large text payload in an index can enlarge it enough to offset the benefit. Measure the chosen query and affected writes together.

15.4.5 TECHNICAL — the engineer’s version#

1. SQLite’s partial-index documentation frames eligibility as an implication between the query condition and the index predicate, using specific supported proof rules rather than a general theorem prover. Predicate spelling and supported forms can therefore matter operationally. [S93]
2. PostgreSQL index-only scans need both available index values and a visibility route that avoids unnecessary heap checks; visibility-map state affects actual heap visits. An eligible plan is not a guarantee of zero heap access in every execution. [S92]
3. Key columns determine search and ordering properties. Included payload is not automatically an additional search-key component. State this distinction when proposing a covering design.
4. Keep unique constraints separate from a convenient filtered read path. A partial unique index, where supported and appropriate, enforces uniqueness only over its qualifying subset; it does not silently extend that rule to omitted rows.

15.4.6 WORDS — remember these#

1. Covering index: the guide carries the values this question needs — an index containing sufficient query attributes for an eligible index-only or covering access path. Partial index: a guide for a defined subset — an index whose entries include only rows satisfying its predicate. Included column: payload carried alongside search keys — a non-key attribute stored in an index by an engine supporting that feature.

15.5.1 PLAIN — in simple words#

1. An index is often most useful when it leads to a small, useful part of the data. But the shape of that part matters as well as its size.
2. One thousand records close together can be cheaper to retrieve than one thousand scattered records. A narrow index can sometimes be cheaper to scan than a wide table even when it does not eliminate many entries.
3. A field with only two possible values can still support a useful index when one value is rare and important. “Never index a Boolean” is too broad; “every filter needs an index” is equally unreliable.
4. Choose representative parameter values. A plan that excels for a rare product may be poor for the best seller, and one average can hide both behaviours.

15.5.2 PLAIN — a picture in your head#

1. A cupboard guide points to 100 folders. If all 100 sit on the same shelf, collection is easy. If each sits in a different room, the same count creates more movement.
2. A two-colour label can also be useful if only ten folders in a million are marked red and the task concerns those ten.
3. Where the comparison breaks: an engine can batch accesses, cache pages and reorganise work. Physical clustering, logical key order and device latency interact; the cupboard does not supply a universal cost equation.

15.5.3 PLAIN — a worked example#

1. In a synthetic million-row task collection, 999,000 tasks are closed and 1,000 are open. The open subset is 0.1 percent. A partial index on open tasks has a plausible purpose.
2. Six months later in a different hypothetical operating state, 800,000 tasks are open. The same predicate now covers 80 percent. A design justified only by the first distribution needs review.
3. Suppose a report needs every open task’s large description. A tiny key-only index may find the tasks but still require many full-row visits. If the report needs only indexed identifiers, the retrieval cost can be quite different.
4. These are workload scenarios, not predicted query times. Record observed counts and payloads when testing them.

15.5.4 PLAIN — what is really happening inside#

1. Planner statistics summarise distributions rather than storing every possible answer to every possible condition. Frequent values, distinct counts and correlations inform estimates, with sampling limitations.
2. Data can change faster than those summaries. Bulk loads, unusual seasonal activity or a new dominant value can make prior estimates less representative.
3. Parameter values can select radically different populations. A reusable query shape is not necessarily a single stable cost profile.
4. An index experiment should therefore include rare values, frequent values, absent values and boundary ranges. For composite conditions, include correlated cases rather than assuming independent fields.

15.5.5 TECHNICAL — the engineer’s version#

1. Distinguish logical selectivity, physical locality and requested projection. Each affects the relative cost of index access versus a scan. A low distinct-value count alone does not determine whether an index is useful. [S89] [S94]
2. Statistics are estimates with a collection policy. PostgreSQL ANALYZE gathers statistics used by the planner; it does not prove that every future parameter combination is modelled exactly. Extended statistics can address selected relationships, not arbitrary unknown business correlations. [S107] [S94]
3. Avoid overfitting an index portfolio to a single benchmark sample. Record the supported workload envelope, including growth and skew assumptions, and define when to reassess it.

15.5.6 WORDS — remember these#

1. Locality: useful records are close in the accessed representation — spatial or temporal concentration that can reduce repeated movement or improve cache reuse. Frequent value: one value appears in many records — a high-frequency member of a distribution relevant to selectivity estimation. Workload envelope: the conditions a design was evaluated for — declared ranges of size, skew, query mix, concurrency and service requirements.

15.6.1 PLAIN — in simple words#

1. An index is an available option, not an instruction that every matching-looking query must use it. The engine can choose a scan when the estimated alternative is cheaper or when the index cannot satisfy the required operation.
2. A tiny table is a common case where navigating an extra structure may not help. Our four-row shop is deliberately a correctness fixture, not a test that every index must be selected.
3. A mismatched expression, comparison rule, partial predicate or leading-key condition can also limit usefulness. The right investigation is specific: what query, what values, what index, what plan, what observations?
4. Forcing a plan before understanding the reason can replace one bad assumption with another. First check that the result and workload definition are right.

15.6.2 PLAIN — a picture in your head#

1. Dev can see all four order folders on a desk. Looking up their positions in a separate guide would be unnecessary overhead. He reads the desk directly.
2. With a million folders, the guide may become valuable. But not if the requested clue is a field the guide does not organise.
3. Where the comparison breaks: the optimiser uses estimates and rules, not a person’s judgement. It can be wrong because its information or model is wrong. A chosen scan is neither automatic wisdom nor automatic failure.

15.6.3 PLAIN — a worked example#

1. Run the same canonical product query before and after creating the candidate index. Save ordered result rows in both cases. They must agree exactly.
2. In SQLite, run EXPLAIN QUERY PLAN with the same bound value and inspect whether the plan describes a table scan or index search. Save the actual output alongside the SQLite version instead of copying a predicted string from this book.
3. Then repeat on a separately generated larger dataset whose product-frequency distribution is recorded. Compare rare and common products. A changed plan is an observation about those inputs, not proof that the index is universally beneficial.
4. Do not assert a speedup from a plan label alone. Time repeated equivalent tasks, include result retrieval, and report the selected boundary and limitations as Chapter 20 specifies.

15.6.4 PLAIN — what is really happening inside#

1. The planner considers legal access paths and estimates their costs. Some paths are ineligible because they do not implement the required semantics. Others are legal but not selected.
2. Diagnose those two categories separately. An eligibility problem may involve an expression or predicate mismatch; a cost-estimation problem may involve stale statistics or unexpected distribution.
3. Rewriting a query can expose a useful path, but only a semantics-preserving rewrite is valid. Replacing a substring search with an equality is not an optimisation of the same question.
4. Retain a rollback plan for schema experiments. New indexes consume space and can affect writes; removing them requires confirming that they are not supporting constraints or other workloads.

15.6.5 TECHNICAL — the engineer’s version#

1. SQLite EXPLAIN QUERY PLAN is an interactive diagnostic interface whose text can change between releases. Tests should not treat one exact human-readable plan string as a universal compatibility contract. [S90]
2. Compare estimates with observed rows and resource evidence where the engine exposes them. PostgreSQL EXPLAIN ANALYZE executes the query; use its output within an authorised experiment, not as a supposedly read-only plan parser for arbitrary statements. [S65]
3. An index recommendation should state target queries, key order, predicates, payload, expected distribution, write impact and measured evidence. “Add an index on every WHERE column” omits almost all of that reasoning.

15.6.6 WORDS — remember these#

1. Eligible access path: a route that can implement the required semantics — an index or scan option permitted by the query, operators and engine rules. Plan selection: choosing among legal routes — the optimiser’s decision based on estimated costs and available information. Plan regression: a changed execution choice worsens a defined workload — an observed performance deterioration, not merely a different plan diagram.