Physical Design and Query Performance

Introduction

Logical database design describes entities, relationships, keys, and constraints. Physical design determines how those logical structures are stored and accessed by a database management system (DBMS). It includes choices about indexes, table organization, data types, partitioning, storage, statistics, caching, and query formulation.

Physical design matters because a logically correct query may still be operationally unsuitable. A query that returns 100 rows might examine ten million rows, sort a large intermediate result, wait for disk I/O, or consume excessive memory. Performance engineering therefore asks not only whether a query is correct, but also how much work the DBMS performs to produce its result.

This chapter focuses on MySQL and PostgreSQL, while distinguishing features that are platform-specific. The central principle is evidence-based tuning: measure the workload, inspect the execution plan, identify the dominant cost, make one justified change, and measure again.

Learning Objectives

By the end of this chapter, you should be able to:

• interpret execution plans and common plan operators;
• explain the role and limitations of optimizer statistics;
• design B-tree, hash, composite, covering, partial, expression, and specialized indexes;
• optimize queries and schemas without changing their meaning;
• explain partitioning, storage layout, memory, and caching effects;
• apply a disciplined, evidence-based performance-tuning process;
• evaluate trade-offs involving write cost, storage, concurrency, and maintainability.

1. Performance as Work and Resource Consumption

Query performance is multidimensional. Common measures include:

• Latency: elapsed time for one operation.
• Throughput: completed operations per unit of time.
• CPU time: processor effort used by the query.
• I/O: pages read from or written to storage.
• Memory consumption: working memory used for joins, sorts, hashes, and aggregation.
• Lock or wait time: time spent waiting for another transaction, connection, or resource.
• Rows examined: rows or index entries considered, which may greatly exceed rows returned.

A useful conceptual decomposition is:

Here, T_total is total elapsed time; T_CPU is CPU processing time; T_IO is storage I/O time; T_wait includes locks, latches, memory, and scheduling waits; and T_network is communication time. The terms are not always strictly independent, and some overlap through parallelism, so this is a diagnostic model rather than an exact accounting identity.

The objective is not automatically to minimize every component. A report may reasonably consume more CPU than a transactional lookup, provided it meets its service-level objective. Performance must therefore be evaluated against workload requirements.

2. The Query Optimizer and Execution Plans

A DBMS transforms SQL into an execution plan. The optimizer considers alternative access paths, join orders, join algorithms, sorting strategies, and sometimes parallel execution. It estimates the cost of each alternative using table statistics and selects a plan expected to be efficient.

A plan commonly contains the following elements:

• Sequential or table scan: reads table pages and tests rows.
• Index scan: traverses an index and fetches matching table rows.
• Index-only scan: obtains required values from the index without visiting the table, when visibility and coverage conditions permit.
• Bitmap scan: combines index information and fetches table pages efficiently; especially common in PostgreSQL.
• Nested-loop join: for each row from one input, searches the other input. It is effective when the outer input is small and the inner input is indexed.
• Hash join: builds a hash table for one input and probes it with the other. It is generally suited to equality joins and adequate memory.
• Merge join: sorts or uses ordered inputs and merges them. It is useful for large inputs and ordered join keys.
• Sort: orders rows, possibly in memory or using temporary disk files.
• Aggregate: computes operations such as COUNT, SUM, or GROUP BY.
• Filter: removes rows after an earlier operation.
• Materialization: stores an intermediate result for later use.

Reading a Plan

In PostgreSQL, EXPLAIN (ANALYZE, BUFFERS) displays estimated and actual rows, actual time, loops, and buffer activity. In MySQL, EXPLAIN ANALYZE provides an executable plan with timing information in supported versions; ordinary EXPLAIN presents estimates and access details.

A simplified plan might be read from the deepest operation upward:

Nested Loop
  -> Index Scan on customers using customers_region_idx
  -> Index Scan on orders using orders_customer_id_idx

The first operation produces customer rows. For each customer, the second operation searches orders. If the first operation returns thousands of customers, the inner index scan may execute thousands of times. The plan is good only if each lookup is cheap and the outer result is sufficiently small.

Important comparisons include:

1. Estimated rows versus actual rows. Large differences indicate inaccurate statistics, correlated columns, data skew, or a query whose selectivity is difficult to estimate.
2. Estimated cost versus actual time. Cost is an internal comparative measure, not milliseconds. A plan with lower estimated cost is not guaranteed to be faster in every environment.
3. Loops. An operation taking 1 ms but executed 100,000 times can dominate the query.
4. Rows removed by filter. A large number suggests that filtering occurs too late or that an appropriate index is absent.
5. Buffers and temporary files. These reveal I/O and spill behavior.
6. Sorts and hashes. Spilling to disk may indicate insufficient memory, excessive intermediate results, or an unsuitable plan.

The actual execution plan should be inspected under representative data and parameters. A development database with ten rows cannot reveal production-scale behavior.

3. Statistics and Cardinality Estimation

The optimizer needs estimates of table size and predicate selectivity. Statistics commonly include row counts, null fractions, distinct-value estimates, most-common values, and histograms. PostgreSQL stores statistics generated by ANALYZE; MySQL maintains optimizer statistics through mechanisms such as persistent statistics and histograms, depending on configuration and version.

Cardinality is the estimated number of rows produced by an operation. If a table contains 1,000,000 rows and a predicate is estimated to match 1%, the estimated cardinality is approximately 10,000 rows. This assumes that the selectivity estimate is appropriate and that the table cardinality is current.

For independent predicates, an optimizer may approximate:

Here, P(A) and P(B) are the probabilities that predicates A and B match, and the approximation assumes statistical independence. Real columns are often correlated. For example, city and postal code are not independent. Correlation can cause severe cardinality errors and poor join choices.

Statistics become unreliable when:

• data changes substantially after the last statistics collection;
• values are highly skewed;
• predicates involve expressions or functions not represented in statistics;
• columns are correlated;
• parameter values vary greatly in selectivity;
• the sample is too small to represent rare values.

Routine maintenance includes PostgreSQL ANALYZE or VACUUM (ANALYZE) where appropriate, and MySQL statistics maintenance according to the engine and version. Increasing a statistics target can improve estimates for skewed data but consumes additional analysis time and catalog storage.

4. Index Design

An index is an auxiliary access structure that helps locate rows or values without scanning every table row. Indexes improve some reads but impose costs: additional storage, write amplification, maintenance time, cache pressure, and possible optimizer confusion. An index should therefore support a demonstrated access pattern.

4.1 B-tree Indexes

B-tree indexes are the general-purpose choice in both MySQL and PostgreSQL. They maintain sorted keys and are effective for equality, range, ordering, and prefix operations. Typical uses include:

CREATE INDEX orders_customer_date_idx
ON orders (customer_id, order_date);

A B-tree can support predicates such as customer_id = 42 and often customer_id = 42 AND order_date >= .... It can also help an order compatible with the index sequence.

For a composite B-tree index, the leftmost-prefix principle is important. An index on (a, b, c) is most directly useful when the query constrains a, or a and b, or all three. It is generally less useful for a condition on b alone, although PostgreSQL may use skip-related strategies in some situations and the optimizer may use an index for other purposes.

Equality columns commonly precede range columns. For example, (tenant_id, status, created_at) is often suitable when queries select one tenant and status and then restrict a date range. This is a heuristic, not an absolute law: ordering requirements, selectivity, workload frequency, and update patterns also matter.

4.2 Hash Indexes

Hash indexes organize keys by hash value and are designed primarily for equality comparisons. They do not naturally support ordered scans or range predicates. PostgreSQL supports hash indexes; MySQL's commonly used InnoDB indexes are B-tree-based, while hash-like adaptive structures may be internal rather than user-created index types.

A hash index may be appropriate for a high-volume equality workload when its operational characteristics are understood. B-tree is often preferred as the default because it supports more predicate types and has a long-established operational profile.

4.3 Covering and Included Columns

A covering index contains all columns required by a query, allowing the DBMS to avoid table lookups. PostgreSQL can use INCLUDE columns:

CREATE INDEX products_category_price_idx
ON products (category_id, price) INCLUDE (name, sku);

In MySQL, a secondary InnoDB index stores the primary-key value with each entry, and additional key parts can provide coverage. A covering index can reduce random I/O, but it increases index size and write cost. Covering does not guarantee an index-only plan: PostgreSQL also considers visibility information, and the optimizer may still choose a table access path.

4.4 Partial Indexes

A partial index covers only rows satisfying a predicate. PostgreSQL supports this feature:

CREATE INDEX tasks_open_assignee_idx
ON tasks (assignee_id, due_date)
WHERE completed_at IS NULL;

This can be highly effective when open tasks are a small, stable subset. The query predicate must be recognizable as implying the index predicate. PostgreSQL does not generally provide the same user-defined partial-index feature in MySQL; generated columns, functional indexes, partitioning, or alternative schema designs may be considered instead.

4.5 Expression and Functional Indexes

An expression index indexes a computed expression:

CREATE INDEX users_lower_email_idx
ON users (lower(email));

It can support a query such as:

SELECT user_id FROM users WHERE lower(email) = '[email protected]';

The expression must match the query semantics, and its functions should be deterministic or immutable according to DBMS rules. MySQL supports functional key parts in modern versions; generated columns can also provide a portable design pattern. Applying a function to an indexed column without an expression or functional index may prevent ordinary index use.

4.6 Specialized Indexes

Specialized index types should be selected for data and predicates rather than fashion.

• GiST in PostgreSQL: extensible framework used for geometric, range, and other operator classes.
• SP-GiST in PostgreSQL: useful for certain partitioned search spaces, such as some spatial or hierarchical structures.
• GIN in PostgreSQL: effective for membership searches in arrays, full-text search, and some JSONB operations; updates can be expensive.
• BRIN in PostgreSQL: compact summaries of physically correlated data, such as time-ordered append-only tables. It is not a replacement for a B-tree on small selective lookups.
• Full-text indexes: support linguistic search rather than ordinary equality or range conditions. MySQL and PostgreSQL implement these differently.
• Spatial indexes: support geometry-based predicates when the appropriate extension, data type, and operator class are used.

Index choice must be validated with an execution plan and representative workload.

5. Query Rewriting and Schema Optimization

Indexes cannot compensate for every poorly structured query. Good query design reduces unnecessary rows and computation early.

Predicate and Projection Discipline

Select only needed columns rather than using SELECT *. This reduces network transfer, memory use, and the possibility that schema changes invalidate an assumed result shape. Restrict rows as early as is semantically safe. Avoid wrapping indexed columns in non-indexed functions, implicit type conversions, or expressions that prevent a searchable condition.

For existence tests, EXISTS often expresses intent better than counting all matches:

SELECT c.customer_id
FROM customers AS c
WHERE EXISTS (
  SELECT 1
  FROM orders AS o
  WHERE o.customer_id = c.customer_id
);

Do not rewrite automatically: the optimizer may transform equivalent forms, and correctness must remain the primary constraint.

Joins

Join columns should have compatible data types and appropriate indexes. Indexing both sides is not always necessary, because the optimizer may scan one relation and probe an index on the other. Join order should be evaluated through the plan, not guessed solely from SQL text.

Avoid accidental Cartesian products. A missing join predicate can multiply rows dramatically. Also distinguish filtering in ON from filtering in WHERE for outer joins, because moving a predicate can change semantics.

Sorting, Grouping, and Pagination

Large OFFSET values can become expensive because the DBMS may scan and discard many earlier rows. Keyset pagination uses a stable ordering key:

SELECT order_id, created_at
FROM orders
WHERE (created_at, order_id) < (:last_created_at, :last_order_id)
ORDER BY created_at DESC, order_id DESC
LIMIT 50;

The exact syntax and index design must match the DBMS and ordering rules. A suitable composite index on (created_at DESC, order_id DESC) may help. Keyset pagination requires a deterministic ordering and a remembered cursor; it is not interchangeable with arbitrary page-number navigation.

For aggregation, reducing rows before a join can help when it preserves meaning. Materialized views or summary tables may be appropriate for expensive, repeated analytical queries, but they introduce refresh complexity and consistency decisions.

6. Partitioning

Partitioning divides one logical table into multiple physical pieces. Common strategies include:

• Range partitioning: dates or numeric intervals;
• List partitioning: discrete categories such as region;
• Hash partitioning: distributes rows by a hash value.

Partitioning can provide partition pruning, in which irrelevant partitions are excluded from a query. It can also support lifecycle operations, such as dropping an old time partition more efficiently than deleting millions of rows. However, partitioning is not automatically faster. Too many partitions increase planning and management overhead, and queries lacking a partition-key restriction may touch every partition.

Partition keys should reflect common filtering and data-lifecycle requirements. They should also be compatible with uniqueness rules, foreign keys, and the DBMS's partitioning implementation. PostgreSQL and MySQL differ in syntax, feature coverage, and restrictions, so documentation and version testing are essential.

Partitioning should not be confused with sharding. Partitioning is generally managed within one database system; sharding distributes data across independent database instances or nodes and introduces routing and distributed-consistency concerns.

7. Storage, Memory, and Caching

Database performance depends on a hierarchy: CPU caches, database buffer pools or shared buffers, operating-system cache, storage devices, and networked storage. A frequently accessed page in memory may be served much faster than a page requiring physical I/O.

PostgreSQL uses shared buffers together with operating-system caching. InnoDB uses a buffer pool for data and indexes. Increasing memory can help when the working set fits more effectively in cache, but excessive allocation can starve the operating system or other processes. Memory is also needed for sorts, hashes, connections, and maintenance operations.

Storage characteristics matter. Random reads, sequential scans, latency, throughput, durability guarantees, and write behavior differ among HDDs, SSDs, and network volumes. A sequential scan may be preferable to an index scan when a large fraction of a table is needed, because many random table fetches can cost more than reading pages sequentially.

Caching must not be used to hide an inefficient plan. A query that is fast only because all data is cached may fail under a cold cache or concurrent production workload. Benchmark both warm-cache and, where relevant, cold-cache conditions, while avoiding destructive tests on production systems.

8. Evidence-Based Tuning Method

A professional tuning process is iterative:

1. Define the service objective, such as p95 latency or maximum report duration.
2. Identify the real workload using logs, metrics, query statistics, and user impact.
3. Capture the query, parameters, schema, indexes, data volume, and transaction context.
4. Inspect the estimated and actual plan.
5. Locate the dominant cost: excessive rows, bad join choice, sort spill, lock wait, I/O, or CPU.
6. Form one hypothesis.
7. Make the smallest justified change.
8. Compare before and after under representative load.
9. Check correctness, write overhead, storage, concurrency, and operational risk.
10. Document the reason and monitor the result.

A useful experimental rule is to change one major factor at a time. Otherwise, improvement or regression cannot be attributed reliably. Use medians and tail percentiles rather than one lucky execution. Control for parameter values, cache state, concurrency, and background activity.

Index recommendations from automated tools can be useful hypotheses, but they are not proof. Duplicate or overlapping indexes should be reviewed, and unused indexes should be removed only after a sufficiently long observation period covering seasonal workloads.

9. Applied Case: An Online Retail Order System

Background

This illustrative case concerns an online retailer with 80 million orders. Customers frequently view recent orders, support staff search open orders by customer and status, and analysts produce daily revenue reports.

Problem

The support query was:

SELECT order_id, order_date, status, total_amount
FROM orders
WHERE customer_id = :customer_id
  AND status = 'OPEN'
ORDER BY order_date DESC
LIMIT 50;

Average latency was acceptable, but the 99th percentile exceeded the service target. The plan showed many rows examined for customers with unusually large order histories. Statistics also underestimated the number of open orders for several enterprise customers.

Analysis

The workload had three relevant characteristics:

1. Support requests almost always concerned one customer.
2. Open orders were a small subset of all orders.
3. Results required an ordering by recent date.

A PostgreSQL partial composite index was tested:

CREATE INDEX orders_open_customer_date_idx
ON orders (customer_id, order_date DESC)
INCLUDE (status, total_amount)
WHERE status = 'OPEN';

The status column need not be an indexed key because the partial predicate already restricts entries to open orders. The included columns can help cover the projection, although actual index-only use depends on visibility and plan cost.

Statistics were refreshed, and the query was tested with small and large customers. The plan changed from a broad index scan followed by filtering to a selective partial-index scan. Actual rows and estimated rows became closer after analysis.

The analytical report was a separate problem. It scanned a large date interval and aggregated by day. A BRIN index on a physically time-correlated timestamp column was tested for broad range filtering, while a summary table was considered for repeated daily dashboards. A B-tree designed for the support lookup would not automatically solve the reporting workload.

Outcome

The support query's tail latency decreased substantially in the test environment, while the partial index was smaller than a full-table equivalent. Insert and update overhead increased modestly because index maintenance was still required for rows entering or leaving the open state. The reporting workload required independent evaluation rather than assuming that one index could serve all purposes.

Learning Points

• Optimize for observed workload patterns, not table size alone.
• Partial and composite indexes can encode business-relevant selectivity.
• Covering indexes trade read efficiency for storage and write cost.
• Statistics must be refreshed and validated for skewed data.
• Different workloads may require different access structures.

10. Limitations, Governance, and Contemporary Practice

Performance changes can affect availability and data integrity. Creating an index may lock or consume resources depending on the DBMS and method. PostgreSQL's concurrent index creation and MySQL online DDL options reduce disruption in suitable cases but do not eliminate all resource risks. Changes should be tested, scheduled, monitored, and reversible where possible.

Query logs may contain personal data, search terms, account identifiers, or confidential business information. Access to performance telemetry should follow least-privilege and retention policies. Parameter values should be masked or controlled when logs are shared.

AI-assisted tuning tools can summarize plans, suggest indexes, or identify anomalous latency. They should be treated as advisory systems. A recommendation must be checked for semantic correctness, write amplification, privacy implications, workload coverage, and compatibility with the DBMS version. Automated application of DDL without review is risky.

Contemporary systems increasingly combine transactional databases with columnar analytics, replicas, distributed storage, materialized views, and workload-specific indexes. These technologies can improve performance but add consistency, operational, and cost complexity. The fundamental method remains unchanged: understand the workload, inspect evidence, test a hypothesis, and validate the result.

Best-Practice Checklist

• Measure user-visible latency and tail latency.
• Read actual execution plans, not only SQL text.
• Compare estimates with actual rows.
• Keep statistics current and investigate skew.
• Design indexes around predicates, joins, ordering, and projection.
• Prefer the simplest index that solves a measured problem.
• Remove redundant indexes only after observing the full workload.
• Test write overhead and storage growth.
• Use partitioning for pruning or lifecycle management, not as a universal speed remedy.
• Test warm-cache and representative concurrent behavior.
• Preserve query semantics and transactional correctness.
• Document every production tuning change.

Chapter Summary

Physical design connects logical schema design with the actual costs of database execution. Query plans reveal access paths, join algorithms, cardinality estimates, memory use, sorting, and I/O. Statistics guide the optimizer, but skew, correlation, stale data, and parameter variation can make estimates inaccurate.

B-tree indexes provide broad support for equality, ranges, and ordering. Hash, covering, partial, expression, and specialized indexes address narrower workloads and carry distinct trade-offs. Composite-index design requires attention to predicate order, ordering requirements, selectivity, and maintenance cost. Query rewriting, compatible data types, keyset pagination, and controlled aggregation can reduce unnecessary work.

Partitioning can enable pruning and data lifecycle operations, while storage and caching determine the cost of reading and writing pages. Effective tuning is evidence-based: establish a goal, inspect actual behavior, test one hypothesis, measure under realistic conditions, and assess correctness and operational consequences. Physical optimization is therefore a continuing engineering discipline rather than a one-time indexing exercise.

Key Terms

Cardinality: The estimated or actual number of rows produced by an operation.

covering index: An index containing all data needed by a query, potentially avoiding table access.

Execution plan: The operations selected by the optimizer to execute a SQL statement.

Expression index: An index built on a computed expression rather than a stored column alone.

Hash index: An index primarily designed for equality lookup using hash organization.

Index-only scan: An access method that obtains required values from an index without fetching table rows, subject to DBMS conditions.

Join algorithm: The method used to combine rows from two or more relations.

Keyset pagination: Pagination based on the last retrieved key rather than a large row offset.

Optimizer: The DBMS component that selects an execution strategy.

Partial index: An index containing only rows satisfying a specified predicate.

Partition pruning: Excluding partitions that cannot contain rows relevant to a query.

Predicate: A condition used to select or filter rows.

Query latency: Elapsed time required to complete a query.

Selectivity: The proportion of rows expected to satisfy a predicate.

Statistics: Data describing table and column distributions used for optimization.

Table scan: Reading table pages to find qualifying rows.

Tail latency: A high percentile of response time, such as p95 or p99.

Write amplification: Additional writing caused by maintaining indexes or derived structures.

Review Questions

Short Answer Questions

1. What information does an actual execution plan provide that an ordinary estimated plan may not?
2. Explain the leftmost-prefix principle for a composite B-tree index.
3. Why can stale statistics produce a poor join plan?
4. What is partition pruning?
5. State two costs introduced by adding an index.

Long Answer Questions

1. Compare nested-loop, hash, and merge joins, including the conditions under which each may be effective.
2. Explain how covering, partial, and expression indexes differ in purpose and implementation.
3. Discuss how storage, memory, buffer pools, and caching influence query performance.
4. Develop an evidence-based workflow for tuning a slow production query.
5. Explain why partitioning is not automatically a performance improvement.

Analytical / Application Questions

1. A query estimates 100 rows but actually returns 2,000,000 rows. Identify possible causes and propose a diagnostic sequence.
2. Design an index strategy for a multi-tenant orders table where most queries filter by tenant, status, and recent date, and explain the write and storage trade-offs.
3. A report is fast immediately after execution but slow after a restart. Analyze the likely role of caching and propose a fair benchmarking approach.

Multiple Choice Questions with Answers

Question 1

Which plan feature most directly indicates that the optimizer estimated the wrong number of rows?

A. Estimated rows differ substantially from actual rows

B. The query contains an ORDER BY clause

C. The table has a primary key

D. The result contains NULL values

Correct Answer: A. Estimated rows differ substantially from actual rows

Question 2

Which index type is generally the broad-purpose choice for equality, range, and ordering operations in MySQL and PostgreSQL?

A. Hash index

B. B-tree index

C. Bitmap-only index

D. Full-text index

Correct Answer: B. B-tree index

Question 3

For an index on (tenant_id, status, created_at), which query most directly follows the leftmost-prefix principle?

A. WHERE created_at > :date

B. WHERE status = :status

C. WHERE tenant_id = :tenant AND status = :status

D. WHERE created_at > :date AND status = :status

Correct Answer: C. WHERE tenant_id = :tenant AND status = :status

Question 4

What is the principal advantage of a partial index?

A. It indexes every possible expression automatically

B. It contains only rows satisfying a specified predicate

C. It removes the need for table constraints

D. It guarantees index-only scans

Correct Answer: B. It contains only rows satisfying a specified predicate

Question 5

Which PostgreSQL index type is commonly suited to large, physically correlated time-series data?

A. BRIN

B. GIN

C. Hash

D. SP-GiST in every workload

Correct Answer: A. BRIN

Question 6

A nested-loop join is often effective when which condition holds?

A. Both inputs are huge and neither has useful ordering

B. The outer input is small and the inner input can be searched efficiently

C. The join is always a non-equality join

D. All rows must first be aggregated

Correct Answer: B. The outer input is small and the inner input can be searched efficiently

Question 7

Why can a large OFFSET become expensive in pagination?

A. It requires encrypting every skipped row

B. The DBMS may scan and discard many preceding rows

C. It disables all transaction isolation

D. It converts a B-tree into a hash index

Correct Answer: B. The DBMS may scan and discard many preceding rows

Question 8

Which statement about optimizer cost is correct?

A. Cost is always measured in milliseconds

B. The lowest estimated cost is guaranteed to be fastest in production

C. Cost is an internal comparative estimate influenced by statistics and configuration

D. Cost is independent of data distribution

Correct Answer: C. Cost is an internal comparative estimate influenced by statistics and configuration

Question 9

What is the primary purpose of partition pruning?

A. To exclude partitions that cannot satisfy the query

B. To duplicate every row into all partitions

C. To eliminate the need for indexes everywhere

D. To convert a transaction into a distributed transaction

Correct Answer: A. To exclude partitions that cannot satisfy the query

Question 10

Which is an appropriate first step in evidence-based query tuning?

A. Create several indexes immediately

B. Rewrite all joins without measuring

C. Define the performance objective and capture the actual workload and plan

D. Increase every memory setting to its maximum

Correct Answer: C. Define the performance objective and capture the actual workload and plan