Table Scan: The Foundation of Data Access

Every database query ultimately needs to examine data stored on disk. The table scan—also known as a full table scan or sequential scan—is the most fundamental access method in relational database systems. It works exactly as its name suggests: the database reads every single row in a table, examines each one, and returns those that satisfy the query conditions.

While table scans are often viewed negatively (associated with poor performance), they are far more nuanced than their reputation suggests. Understanding when table scans are appropriate—and when they are catastrophic—is essential knowledge for any database professional.

A table scan is conceptually simple but involves sophisticated machinery at the storage engine level. Let's trace exactly what happens when a database executes a table scan:

Step 1: Page-Level Organization

Database tables are not stored as flat files but as collections of fixed-size pages (typically 4KB, 8KB, or 16KB depending on the DBMS). Each page contains multiple rows, along with metadata such as page headers, slot directories, and free space pointers.

When executing a table scan, the database doesn't read individual rows—it reads entire pages. This is crucial because disk I/O operates at the block level, not the byte level. Reading one byte costs the same as reading 8KB if that's your page size.

Step 2: Buffer Pool Interaction

The database doesn't directly read from disk for every page. Instead, it uses a buffer pool—an in-memory cache of recently accessed pages. When a table scan requests a page:

1. Buffer Hit: If the page is already in memory, it's returned immediately (microseconds)
2. Buffer Miss: If not, the page is read from disk into the buffer pool (milliseconds)

For a fresh table scan on a cold cache, nearly every page will be a buffer miss. For repeated scans of the same table, many pages may already be cached.

Step 3: Sequential Access Optimization

Modern disk subsystems and operating systems are highly optimized for sequential access patterns. When a database detects that it's reading pages sequentially (adjacent page_id values), several optimizations kick in:

Understanding the cost of a table scan is essential for query optimization. The cost model must account for both I/O and CPU components.

I/O Cost

The I/O cost of a table scan is straightforward: you must read every page of the table. If a table has B pages, and each page read costs t_I/O time units, the I/O cost is:

I/O Cost = B × t_I/O

However, this formula assumes all pages require disk I/O. In reality, some pages may be in the buffer pool. A more accurate model incorporates the buffer hit rate (h):

I/O Cost = B × (1 - h) × t_disk + B × h × t_memory

Where:

• t_disk ≈ 5-10ms for HDD, 0.1-0.5ms for SSD
• t_memory ≈ 0.0001ms (100 nanoseconds)
• h varies from 0% (cold cache) to approaching 100% (hot table)

CPU Cost

Beyond I/O, the CPU must examine every row to evaluate the WHERE clause predicate. If a table has N rows, and evaluating the predicate costs t_cpu per row:

CPU Cost = N × t_cpu

For simple predicates (equality checks, comparisons), t_cpu is negligible. For complex predicates involving string matching, function calls, or subqueries, CPU cost can become significant.

Total Cost Formula

Combining both components:

Total Table Scan Cost = Pages × t_I/O + Rows × t_cpu

Or with buffer considerations:

Total Cost = Pages × [(1-h) × t_disk + h × t_memory] + Rows × t_cpu

Despite their reputation, table scans are often the best choice. Understanding these scenarios is crucial for proper query tuning.

Scenario 1: High Selectivity Inversion

When a query must return a large fraction of the table's rows (typically >10-20%), table scans outperform index scans. Consider a query that returns 30% of rows:

• Index scan approach: Read index entries, then perform random I/O to fetch each matching row from different pages. If rows are scattered across all pages, you may read nearly all pages anyway—but with random access overhead.
• Table scan approach: Read all pages sequentially. Yes, you read pages containing unwanted rows, but sequential access is so much faster that the total time is less.

Scenario 2: Small Tables

For very small tables (fitting in a few pages), table scans are almost always optimal. The overhead of using an index—traversing B-tree levels, following pointers—exceeds the cost of just reading all rows directly.

Rule of thumb: If a table fits in 10-20 pages (80-320KB at 8KB page size), index overhead likely exceeds index benefit.

Scenario 3: No Suitable Index Exists

If no index supports the query's filter conditions, a table scan is the only option. This is the most common reason for table scans in practice.

Scenario 4: Clustered Table Organization

If the table is physically sorted by (clustered on) the column being queried, a table scan can efficiently skip irrelevant sections through early termination.

Scenario 5: Analytical Workloads (OLAP)

Data warehousing and analytics queries typically aggregate, transform, or analyze entire data sets. These workloads are inherently full-scan operations, which is why columnar databases optimize specifically for this pattern.

While table scans have legitimate uses, they can also cripple system performance. Recognizing these anti-patterns is critical.

Anti-Pattern 1: Needle in a Haystack

Querying for a single row (or tiny fraction of rows) in a large table via table scan is the classic performance disaster:

Anti-Pattern 2: Table Scan in Loop / Nested Operations

When a table scan occurs inside a nested loop join or application-level iteration, the cost multiplies:

Total Cost = Outer Loop Iterations × Table Scan Cost

If the outer loop runs 10,000 times and each table scan takes 1 second, total time is 10,000 seconds (2.8 hours)!

Anti-Pattern 3: Buffer Pool Pollution

Large table scans can evict other frequently-accessed pages from the buffer pool, causing collateral damage to unrelated queries. A single analytical query scanning a terabyte table can flush the entire cache, suddenly making all OLTP queries hit disk.

Modern databases address this with scan-resistant buffer pools that use separate buffers for sequential scans, or algorithms like LRU-K that don't promote sequential scan pages as aggressively.

Modern databases implement several optimizations and variants of the basic table scan.

Parallel Sequential Scan

For large tables, databases can divide the table into segments and scan multiple segments concurrently using separate worker processes. PostgreSQL, Oracle, and SQL Server all support parallel table scans.

With P parallel workers and B pages:

Parallel Scan Time ≈ (B / P) × t_I/O

However, parallelism is limited by:

• Available I/O bandwidth (saturating disk)
• CPU cores available
• Buffer pool contention
• Final result aggregation overhead

Synchronized Scans

When multiple queries scan the same large table concurrently, modern databases can synchronize them. Instead of each query starting from page 1, a new scan joins an already-in-progress scan at its current position, wraps around the table, and finishes where it started.

This provides:

• Shared buffer pool pages (data read once, used many times)
• Reduced I/O amplification
• Better cache utilization

Sample Scans

For approximate analytics, databases can scan a random sample of pages rather than all pages:

-- PostgreSQL tablesample
SELECT AVG(amount) FROM orders TABLESAMPLE SYSTEM (10);  -- 10% of pages

Sample scans trade accuracy for speed—useful for exploratory data analysis.

Each major RDBMS implements table scans with subtle differences. Understanding these helps in cross-platform optimization.

PostgreSQL Details

PostgreSQL's sequential scan reads pages in physical order (using the visibility map to skip pages containing only dead tuples during certain operations). The seq_page_cost parameter (default 1.0) allows tuning the optimizer's cost estimate.

MySQL/InnoDB Details

InnoDB tables are organized as clustered indexes (B+ tree ordered by primary key). A 'full table scan' in InnoDB is actually a full clustered index scan—it reads leaf pages in primary key order, not physical order. This means:

• Data is always read in PK order (can help if application needs sorted output)
• Space for the PK index is 'free' since it IS the table

Oracle Details

Oracle distinguishes between buffered scans (read through buffer cache) and direct path reads (bypass cache, read directly to process memory). Direct path reads are faster for large scans because they avoid buffer pool contention, but they skip the cache entirely.

Let's examine real execution plans and analyze when table scans are appropriate.