Chapter

Scanning, Sorting and the Cost of a Question

Part C · Finding Answers|4,803 words|about 21 min read|Volume C

14.0 What this chapter gives you#

A query can return one number after examining millions of records. Another can return hundreds of records after examining only a small region of an index. Output size and work performed are not the same thing.
You will follow scans, estimate data volume, understand why a sort may need temporary storage, and separate an optimiser’s cost estimate from elapsed time on a clock.
The large datasets and machine rates in this chapter are invented arithmetic exercises unless explicitly described as measured. They do not describe KedByte’s infrastructure or a benchmark of any database product.

14.1 What a scan does#

14.1.1 PLAIN — in simple words#

A scan visits records through an access path and checks which ones contribute to the question. Without a more selective route, finding one matching order may require looking through a large collection.
Scanning is not inherently bad. To total almost every sale, visiting most of the relevant data may be exactly the right work. An index is useful only if its alternative route saves enough work for this question.
A limit on the answer does not necessarily limit the search. “Give me one order above an amount that no order reaches” may still require checking every eligible order.
Read a slow query as a sequence of responsibilities: find candidates, test conditions, combine records, calculate results, order them if required, and deliver them. The expensive stage may be nowhere near the final output.

14.1.2 PLAIN — a picture in your head#

Mira asks Dev to find a paper order from a cupboard. If folders are arranged by order number but the only clue is a handwritten note inside, Dev may need to open many folders.
If Mira asks for the total number of sheets in the cupboard, opening every folder is not a failed search strategy; the question asks about all of them.
Where the comparison breaks: a database can read pages containing many records, keep pages in memory, process batches and use several workers. A scan is not necessarily one physical disk operation per row or one person walking slowly between folders.

14.1.3 PLAIN — a worked example#

Imagine 100,000 synthetic orders, with one labelled TARGET. A simple linear search could encounter it first, last or somewhere between. A missing target requires examining the entire eligible collection in this elementary algorithm.
If the records are already ordered by a searchable key and the structure supports choosing regions, a lookup can skip much of that collection. Chapter 16 explains how a tree makes the skipped regions trustworthy.
Now ask for a sum over all 100,000 order amounts. A selective lookup for one key is no longer the answer. Unless an appropriate maintained summary is available and acceptable, the system must account for all contributing amounts.
Returning one SUM cell therefore does not establish that one row was read. The output has one aggregate row; its input may contain 100,000 contributions.

14.1.4 PLAIN — what is really happening inside#

The engine chooses a physical plan that implements the query’s logical result. A table scan and an index scan are different paths; each can still examine many entries.
A predicate may discard most candidates after they have been read. A narrow result can therefore hide a wide scan. Conversely, an index may narrow candidates before fetching full records.
Some engines can avoid reading entire partitions, pages or column blocks using metadata. This is a separate mechanism from discarding rows after reading them. Ask what was skipped, not just how many rows survived.
Work also includes checking visibility, interpreting values, evaluating expressions and passing rows between plan stages. A memory-resident scan can consume significant CPU even when it performs no device reads.

14.1.5 TECHNICAL — the engineer’s version#

Separate access-path work, predicate evaluation and result cardinality. SQLite’s planning documentation illustrates full scans, rowid lookup and index-based lookup; its EXPLAIN QUERY PLAN distinguishes SCAN from selective SEARCH descriptions. The exact human-readable output is implementation-dependent. [S89] [S90]
SQL is declarative about the required result, with explicit ordering when requested. It does not prescribe the physical row-visit algorithm. A logically useful “first filter, then project” explanation is not a claim that an engine always executes those stages in that literal order. [S65]
LIMIT constrains returned rows after the semantics of the relevant query operations. It is not a universal cap on examined rows, input bytes, sorting work or total runtime. Whether an engine can stop early depends on the plan and the query. [S81]

14.1.6 WORDS — remember these#

Scan: visit data through an access path — sequential or otherwise structured traversal of records or index entries to produce candidates. Predicate: a condition used to choose records — an expression whose truth controls qualification in a query operation. Result cardinality: how many output rows there are — the row count at a specified stage, distinct from records examined or bytes read.

14.2 Row width and data volume#

14.2.1 PLAIN — in simple words#

A million tiny records and a million records containing large messages create different amounts of work. Counting rows alone ignores how much information each visit carries.
Selecting only the fields needed can reduce the amount passed through later stages and sent to the caller. It does not guarantee that an engine avoids reading every other byte on the underlying page.
The representation matters. A short integer, a long description and a compressed document have different storage and processing costs. Metadata, alignment, indexes and older row versions can add further space beyond the values shown in a spreadsheet.
Start with a rough estimate, label its assumptions, and then measure the actual structure. Arithmetic is useful precisely when its boundaries are visible.

14.2.2 PLAIN — a picture in your head#

Think of a delivery van carrying boxes. “We have 1,000 boxes” does not say whether one van is enough. The size and packing of the boxes matter.
Asking for only a page from each folder reduces what you carry to a meeting, but you may still have to open the same bulky folders to retrieve those pages.
Where the comparison breaks: databases use pages, compression and indirection. A large value may live outside the main row, and some plans can satisfy a query from a narrower index. The physical route must be inspected rather than inferred from the SELECT list alone.

14.2.3 PLAIN — a worked example#

Suppose a synthetic table has 1,000,000 rows averaging 120 bytes of relevant stored payload. The payload estimate is 1,000,000 × 120 = 120,000,000 bytes, or 120 decimal MB.
At 600 bytes per row it becomes 600 MB, five times as much. This comparison excludes page headers, free space, indexes, transaction information and compression.
If a report only needs a 16-byte identifier and an 8-byte amount, its conceptual selected values total 24 MB across the million rows. That is a logical payload estimate, not a guarantee of 24 MB of physical input-output.
An assumed sustained stream of 300 MB/s would need at least 0.4 seconds merely to transfer 120 MB and 2 seconds for 600 MB. These are invented lower-bound arithmetic examples. Real execution also includes scheduling, decoding, computation, contention and delivery.

14.2.4 PLAIN — what is really happening inside#

Row-oriented storage commonly groups a record’s attributes physically, while columnar storage groups values by column. The amount a query can avoid reading differs between these layouts; Chapter 43 explains the columnar case.
Intermediate rows matter too. A join that carries a long unused description through a sort can consume more memory than one carrying only keys and amounts, even when both eventually return the same concise report.
Output encoding can expand values. JSON field names, quotation and text formatting are not free. A server may finish its internal calculation quickly while the application spends longer receiving and decoding the result.
A useful measurement distinguishes table size, index size, bytes visited by a plan, intermediate memory, temporary bytes and bytes delivered. One number called “data size” cannot stand in for all six.

14.2.5 TECHNICAL — the engineer’s version#

A plan’s estimated row width is an estimate of the values passed by that plan node, not necessarily a physical on-disk tuple length. PostgreSQL EXPLAIN reports estimated rows and width alongside cost; those fields describe different dimensions. [S65]
Projection can reduce intermediate width and network payload. A covering access path may additionally avoid some base-table visits, but PostgreSQL index-only access still depends on visibility information and can require heap checks. [S92]
State units precisely. This chapter uses decimal MB for rate arithmetic: one MB is 1,000,000 bytes. A reported MiB is 1,048,576 bytes. Do not compare the two as though their numerals were interchangeable.
An estimate built from average width can miss heavy tails: a few very large records may dominate particular queries or exceed memory assumptions. Keep a distribution or representative cases when wide values matter.

14.2.6 WORDS — remember these#

Row width: the amount carried by one row representation — estimated or measured bytes per row at a specified physical or logical stage. Projection: choose the fields needed — a relational or SQL operation producing selected expressions rather than every available attribute. Payload: the useful represented content — bytes under a stated boundary, excluding or including overhead only as explicitly defined.

14.3 Sorting and memory#

14.3.1 PLAIN — in simple words#

Sorting arranges records according to a comparison rule. A list ordered by amount is not necessarily ordered by order number, and ties need a rule when their relative order matters.
Sorting generally needs to compare and rearrange many values. A large sort may consume substantial memory even when the final answer contains only a small part of the sorted result.
An existing ordered access path can sometimes supply the requested order directly. That can avoid a separate sort, but only when the path’s ordering matches the query and the plan chooses it.
More memory can help some sorts. It is not automatically the right first change, because many concurrent operations may each use their own allowance.

14.3.2 PLAIN — a picture in your head#

Dev lays order cards across a table, arranging them from smallest amount to largest. If all cards fit, he can compare and move them without leaving the table.
Cards already filed in the requested order can simply be read in sequence. Cards filed by a different field still need work.
Where the comparison breaks: real sorting algorithms do not repeatedly scan the whole table for the smallest remaining card in the inefficient way a beginner might. The number of comparisons and moves depends on the algorithm, data and implementation.

14.3.3 PLAIN — a worked example#

Take four invented report rows: (A, 500), (B, 300), (C, 500) and (D, 200). Ordering by amount gives D, B, then the two 500 rows in an unspecified relative order unless another rule is supplied.
ORDER BY amount_minor, order_id supplies a deterministic order for these distinct identifiers: D, B, A, C. It states the business-readable tie-break rather than relying on a current storage accident.
A simplified comparison sort on one million entries has work on the scale of N log2 N, roughly 20 million comparison steps in an order-of-growth illustration. This is not an exact count for a database sorter.
If each temporary entry occupies an assumed 48 bytes, the entries alone need about 48 MB. Pointers, allocator overhead, copies and other plan nodes are outside this simple estimate.

14.3.4 PLAIN — what is really happening inside#

A sort receives keys and associated values, compares them under the selected ordering, and emits the required sequence. It may retain full rows or references sufficient to retrieve the rest.
Sorting text requires a collation rule, not just visual intuition. Null placement and ascending versus descending order also belong to the requested ordering.
A top-N plan may keep a bounded set of the best candidates instead of sorting everything completely. It can still need to inspect all candidates when there is no ordered route that proves the remaining entries cannot outrank them.
A later join, parallel exchange or other operation can alter ordering guarantees. Only the ORDER BY governing the final result establishes the promised presentation order for that query.

14.3.5 TECHNICAL — the engineer’s version#

Distinguish the logical ORDER BY requirement from a physical Sort node. An appropriately ordered index scan can satisfy the requirement without that node, subject to the actual key order, directions, null handling and other query operations. [S106]
PostgreSQL’s work_mem is an operation-level memory allowance used by operations such as sorts and hashes; multiple nodes and concurrent sessions can multiply total demand. Treating it as a single budget for the entire server is incorrect. [S95]
Comparison counts, temporary-entry widths and memory estimates in this section are analytical models. They do not establish observed latency, a cache state or a particular spill threshold for an installed engine.

14.3.6 WORDS — remember these#

Sort key: the values deciding order — the ordered sequence of expressions and comparison rules used to arrange records. Tie-breaker: an extra rule for equal first choices — additional ordering attributes that distinguish otherwise tied results. Top-N: keep the requested best few — an optimisation that retains a bounded candidate set under an ordering, without necessarily avoiding a full input scan.

14.4 External work and spill#

14.4.1 PLAIN — in simple words#

When an operation cannot keep its working data within its memory allowance, it may move some of that work to temporary storage. This is called spilling.
A spill is not automatically a failure. It can be the engine’s planned way to finish a large task safely. It may, however, add substantial input-output and compete with other operations for space and bandwidth.
Temporary does not mean harmless. Temporary files still need capacity, access controls and cleanup. A query can fail because temporary storage fills even when the final result would have been tiny.
Before changing memory settings, inspect whether spilling actually occurred, how much work it added and which concurrent operations share the machine.

14.4.2 PLAIN — a picture in your head#

The order cards no longer fit on Dev’s table. He sorts one table-sized batch, puts it in an ordered stack on the floor, and repeats. Then he merges the ordered stacks by repeatedly taking the next smallest visible card.
The floor makes the task possible, but every trip between table and stacks costs effort.
Where the comparison breaks: database external sorting uses buffers, merge passes and storage-specific algorithms. The floor is not necessarily slower than every possible memory access, and a physical device may itself have caches. The analogy explains the extra movement, not a fixed speed ratio.

14.4.3 PLAIN — a worked example#

Use an intentionally simplified external-sort model: 1,000 MB of sortable data and room for 100 MB at a time. Initial run generation produces about ten sorted runs, ignoring overhead.
A one-pass merge that can read all ten runs concurrently would read the temporary runs and write or stream the final order. If the merge buffers cannot support that fan-in, extra merge passes may be needed.
Counting an initial read, a temporary write and a temporary reread already suggests roughly 3,000 MB of traffic for 1,000 MB of original input, before additional output and metadata. This is a model, not an engine measurement.
A smaller projection, a more selective predicate or an already suitable ordered path could reduce this work without increasing the per-operation memory allowance.

14.4.4 PLAIN — what is really happening inside#

The operation builds manageable runs or partitions, writes them to temporary storage, and combines them later. Sorting and hash-based processing use different mechanisms, so identify which operation spilled.
A server-wide memory increase can remove one spill while making the system more vulnerable to memory pressure under concurrency. The relevant question is the combined workload, not one isolated query’s fastest run.
Temp-file sizes and sort-method descriptions can provide evidence. They do not by themselves explain whether the root cause was an oversized result, a poor plan, stale estimates, unexpected skew or an intentionally large analytical job.
Preserve a baseline before intervention. Record query text, parameter values or their safe profile, plan, row counts, settings and workload conditions. Change one justified variable, then compare the same defined task.

14.4.5 TECHNICAL — the engineer’s version#

External-memory algorithms explicitly account for movement between a limited fast working set and larger storage. An external merge sort forms sorted runs and merges them with a bounded fan-in. The chapter’s traffic estimate deliberately excludes implementation overhead and extra passes.
PostgreSQL EXPLAIN ANALYZE can report sort method and memory or disk use; resource settings govern relevant operation allowances. EXPLAIN ANALYZE executes the statement, so use a disposable or explicitly authorised read-only workload rather than treating it as a passive parser. [S65] [S95]
A spill observation supports “this execution used temporary storage at this node.” It does not establish a universal threshold, an exact device bottleneck or the best production configuration.

14.4.6 WORDS — remember these#

Spill: working data moved out of the operation’s memory allowance — temporary external storage used to continue an operation such as sorting or hashing. Sorted run: one already ordered batch — an intermediate sequence used by an external merge process. Merge fan-in: how many ordered streams are combined at once — the number of input runs a merge step can consume under its buffer and resource limits.

14.5 Selectivity and filtering#

14.5.1 PLAIN — in simple words#

A selective condition keeps a small share of the eligible records. “This exact order number” may be highly selective. “Every completed order this year” may not be.
The share matters because a selective access path can avoid visiting much unrelated data. But knowing that few rows survive does not prove the engine found them cheaply.
Real values are rarely spread perfectly evenly. One popular product may account for half the sales while thousands of other products share the remainder.
The same query shape can therefore require very different work with different parameters. Test common, rare and empty cases rather than choosing only the most flattering example.

14.5.2 PLAIN — a picture in your head#

Mira asks for orders containing a rare specialist pen. A small product-to-order guide might lead to a handful of folders. Asking for orders containing the shop’s best-selling notebook could lead to half the cupboard.
The guide still works in both cases, but following thousands of separate pointers may no longer beat reading the relevant cupboard section in order.
Where the comparison breaks: database cost depends on page locality, caches, correlation and implementation. A popular value does not force one universal plan, and an index need not perform one separate physical read per match.

14.5.3 PLAIN — a worked example#

In a synthetic population of 100,000 rows, a condition retaining 100 has an observed selectivity of 100 / 100,000 = 0.001, or 0.1 percent.
A second condition retains 60,000 rows, or 60 percent. These are measured counts in the invented population, not estimates of a real shop.
Suppose 10 percent of orders are from branch A and 20 percent are evening orders. Multiplying gives a 2-percent joint estimate only under an independence assumption. If branch A operates only in the evening, every branch-A order can be an evening order, giving 10 percent instead.
The calculation exposes an assumption rather than proving that a planner always multiplies percentages this way. Chapter 18 explains statistics and correlated attributes.

14.5.4 PLAIN — what is really happening inside#

The optimiser estimates how many rows each operation will produce. These estimates influence whether an index, scan, join order or aggregation strategy appears economical.
A predicate may be evaluated as an index boundary, a partition-pruning condition or a residual filter after reading candidates. These placements can produce the same logical result with different work.
Transforming a column inside a predicate can affect whether an ordinary index is usable. A suitable expression index or a query written in an equivalent searchable form may help, but equivalence must include type, collation and boundary semantics.
Filtering earlier is useful only when it preserves meaning. Section 13.3 showed a case where moving a predicate around an outer join changes the answer. Correctness comes before reduced row counts.

14.5.5 TECHNICAL — the engineer’s version#

Selectivity is a fraction of a specified input population that satisfies a predicate. State whether the fraction is estimated by a planner or calculated from actual observed rows. Estimated and actual cardinalities can diverge under skew or correlated conditions. [S94]
An access predicate constrains which entries a chosen path visits; a residual filter rejects candidates after access. Implementation details vary, so examine the plan and observed work rather than assuming every WHERE clause is pushed into an index. [S98]
An optimisation must preserve SQL semantics, including NULL handling, outer-join behaviour, comparison rules and overflow or type-conversion boundaries. A faster query that silently changes the population is a different query, not a successful optimisation.

14.5.6 WORDS — remember these#

Selectivity: the fraction that passes a condition — qualifying rows divided by a stated candidate population, either estimated or observed. Skew: some values occur much more often than others — a non-uniform distribution that can concentrate work and invalidate uniform assumptions. Residual filter: a check made after finding candidates — a predicate evaluated after an access path has already visited candidate entries or rows.

14.6 Cost versus elapsed time#

14.6.1 PLAIN — in simple words#

A planner’s cost is a model used to compare candidate plans. It is not necessarily a prediction in seconds. A clock measures one execution under one set of conditions.
Two runs of the same plan can take different times because one uses cached data, waits for another operation, competes for CPU or sends results to a slower client.
A lower estimated cost is a reason the planner preferred a plan under its assumptions. It is not evidence that you measured a faster end-to-end experience.
Keep three questions separate: is the result correct; what work was performed; and how long did the defined operation take? All three are needed for a useful performance claim.

14.6.2 PLAIN — a picture in your head#

A delivery planner gives each route points for distance, traffic and difficult turns. Those points help choose a route. A driver’s stopwatch records what happened on Tuesday.
Tuesday’s unexpected roadworks can make the chosen route slow without changing the meaning of the planner’s points.
Where the comparison breaks: a database cost model uses its own configurable units and statistics. The analogy does not license treating a cost of 500 as 500 metres, milliseconds or physical reads.

14.6.3 PLAIN — a worked example#

Consider a purely invented plan comparison. Plan A is assigned cost 100 and plan B cost 160. The planner chooses A. These figures have meaning only inside the stated model.
A measured run of A takes 40 ms of server work and waits 120 ms for a contended resource. A second run without the wait takes 42 ms. It would be misleading to announce a fourfold algorithmic improvement between those runs.
Now include a client that transfers and decodes results in another 30 ms. A server-only measurement and an application-visible measurement answer different questions even if both are honestly timed.
The teaching benchmark will therefore compare equal result sets, record the timing boundary, repeat runs and retain failures instead of presenting only the fastest observation.

14.6.4 PLAIN — what is really happening inside#

Planning estimates work from statistics and configured assumptions. Execution discovers actual row counts, waits and resource use. Instrumentation can expose some of these observations, with overhead of its own.
Cached pages are not the only warm state. Prepared statements, filesystem cache, compiled code, connection pools and storage caches may all change a later run. Closing one connection does not necessarily reset them.
Parallel execution can reduce elapsed time while doing more total work. Conversely, less total work can still take longer if it lies on a serial critical path or waits behind other tasks.
The useful report records environment and limitations: database and driver versions, dataset construction, indexes, query and parameters, concurrency, warm-up policy, number of samples and what the timer includes.

14.6.5 TECHNICAL — the engineer’s version#

PostgreSQL EXPLAIN costs are expressed in planner cost units, not milliseconds. EXPLAIN ANALYZE adds observed execution information and incurs measurement overhead; actual rows and loops must be read at the relevant node. [S65]
Distinguish latency, service time, queueing delay, CPU time and throughput. They are related but not interchangeable. A single duration cannot identify all bottlenecks.
A monotonic performance timer is appropriate for elapsed intervals. Python’s perf_counter_ns() returns integer nanoseconds, but the unit does not guarantee one-nanosecond resolution or accuracy. Record the timer and runtime. [S102]
This chapter establishes a vocabulary and analytical models. No fabricated plan output, elapsed-time table or hardware result is presented as a measured experiment. Chapter 20 develops the actual benchmark protocol.

14.6.6 WORDS — remember these#

Planner cost: an estimate for comparing execution choices — a model-specific quantity derived from statistics and configured operation costs. Elapsed time: how long the chosen boundary took on a clock — wall-clock duration including waits within that boundary. Queueing delay: time waiting before work can proceed — delay caused by contention or scheduling rather than the operation’s own active computation.

14.97 Practice and worked answers#

Question: A query returns one COUNT value after checking two million rows. Is it a one-row query for capacity planning? Answer: Its result cardinality is one, but the input work may involve two million candidates. Report both the output and examined work.
Question: Estimate payload for 250,000 rows averaging 200 bytes. Answer: 50,000,000 bytes, or 50 MB. This excludes overhead and does not establish physical bytes read.
Question: A limit of ten returns no matching rows. Can the engine have visited the entire table? Answer: Yes. Without a suitable route or metadata proving absence earlier, it may need to reject every candidate.
Question: Why is ORDER BY amount_minor insufficient for repeatable pagination among tied amounts? Answer: Equal amounts do not specify a total ordering of distinct rows. Add a stable identifying tie-breaker and consider changes between page requests.
Question: A sort spills. Should every session immediately receive ten times more working memory? Answer: No. First establish the operation, data width, plan and concurrent memory demand. A local improvement can create server-wide pressure.
Question: A condition selects 3,000 of 120,000 candidates. Answer: Observed selectivity is 2.5 percent. State that population rather than saying “the query is 2.5 percent selective” without a denominator.
Question: Two independent predicates have selectivities 0.1 and 0.2. What is their joint fraction under independence, and what can invalidate it? Answer: 0.02. Correlation, different eligible populations or conditional definitions can invalidate the multiplication.
Question: A plan cost is 80 and measured duration is 40 ms. Is the conversion two cost units per millisecond? Answer: No. One observation does not define such a conversion; planner units and measured time are different quantities.

14.98 Common wrong ideas#

Wrong: a scan always means a missing index. Right: broad questions can appropriately scan broad inputs.
Wrong: few returned rows imply little work. Right: filtering and aggregation can hide extensive input work.
Wrong: selected column width equals physical input-output. Right: storage layout, visibility and access paths affect physical reads.
Wrong: a spill proves the engine malfunctioned. Right: it can be an expected strategy with measurable costs.
Wrong: all values have similar frequency. Right: skew and correlations can dominate workload behaviour.
Wrong: a cost is a time prediction in milliseconds. Right: cost is a planner-specific comparison model.
Wrong: closing a connection creates a cold benchmark. Right: many other caches and warm states remain.
Wrong: the fastest observed run is the system’s performance. Right: workload distributions, failures and measurement boundaries matter.

14.99 Chapter summary in 20 lines#

A question’s answer size does not reveal how much work produced it.
Scans visit candidates through a chosen access path.
A full scan can be appropriate for a broad calculation.
LIMIT does not universally cap input work.
Count bytes and intermediate width as well as rows.
Projection can reduce carried and delivered data without guaranteeing fewer page reads.
Physical layout and cached state affect the route to values.
Sorting requires a defined comparison and tie policy.
A suitable ordered path can sometimes avoid a separate sort.
A top-N operation may still inspect its whole input.
Working-memory limits can lead to temporary-storage spill.
Spills add movement and capacity requirements, not automatically incorrectness.
Per-operation allowances multiply under complex plans and concurrency.
Selectivity needs a named input population.
Popular values and correlated conditions challenge uniform estimates.
Moving a filter must preserve the query’s meaning.
Planner cost and measured elapsed time are different quantities.
Warm state, waits and clients can change observed duration.
Record correctness, work and time separately.
Use reproducible measurements rather than slogans about scans or indexes.

Return to contents