Physical Ordering

When you query a database with SELECT * FROM Customers ORDER BY LastName, you receive rows sorted alphabetically by last name. But how are those rows actually stored on disk? Are they physically arranged in alphabetical order, or is the database performing sorting on the fly?

The answer depends entirely on the table's physical ordering—whether and how a clustered index defines the storage layout. This distinction between logical order (how data appears in query results) and physical order (how data resides on storage media) is fundamental to understanding database performance.

Physical ordering determines whether range queries blaze through sequential disk blocks or crawl through random I/O. It influences whether inserts are fast appends or expensive mid-table insertions. It affects how fragmentation develops and how maintenance operations behave. Every aspect of storage-level performance traces back to physical ordering decisions.

Understanding the difference between logical and physical ordering is the foundation for comprehending index behavior and storage performance.

Logical Order:

Logical order is the conceptual arrangement of data as you think about it or as queries present it:

• How rows relate to each other in your mental model
• The sort order specified in ORDER BY clauses
• The sequence implied by primary key values
• The organization apparent in query results

Logical order exists in your data model and query specifications. It's abstract—independent of how bytes are actually arranged on disk.

Physical Order:

Physical order is the actual arrangement of data bytes on storage media:

• Which rows are stored in which disk sectors
• The sequence of pages in database files
• Adjacent storage locations for related data
• The layout that determines I/O patterns

Physical order is concrete—it directly determines how disk heads move, which SSD cells are accessed, and whether reads are sequential or random.

The Bridge: Clustered Indexes

Clustered indexes are the mechanism that connects logical and physical order:

• When you create a clustered index on a column, you're declaring that the physical storage order should match the logical order of that column's values
• The database engine physically rearranges data pages so that rows are stored in clustered key order
• Range queries on the clustered key access physically contiguous pages
• The logical order defined by the clustered key becomes the physical reality

Without a clustered index:

• Data is stored in a heap—insertion order or wherever space is available
• No correlation between any logical ordering and physical storage
• All index-based access patterns result in random I/O
• Full scans read pages in physical order, which is essentially arbitrary

When a clustered index is created, the database engine performs a series of operations to establish and maintain physical ordering:

Initial Creation:

Physical Layout After Creation:

Consider a table Orders with a clustered index on OrderDate. After index creation:

Physical Disk Layout:

┌─────────────┐   ┌─────────────┐   ┌─────────────┐   ┌─────────────┐
│  Page 101   │──▶│  Page 102   │──▶│  Page 103   │──▶│  Page 104   │
│ Jan 1-Jan 5 │   │ Jan 6-Jan 10│   │ Jan 11-Jan 15│  │ Jan 16-Jan 20│
│ Orders      │   │ Orders      │   │ Orders      │   │ Orders      │
└─────────────┘   └─────────────┘   └─────────────┘   └─────────────┘
       │                 │                 │                 │
       └─────────────────┴─────────────────┴─────────────────┘
                    Physically Contiguous on Disk

Queries for WHERE OrderDate BETWEEN 'Jan 6' AND 'Jan 15' read pages 102 and 103 sequentially—they're adjacent on disk.

Maintenance of Physical Order:

After creation, the database attempts to maintain physical order as data changes:

1. Sequential Inserts: New rows at the 'end' of the key range append to the last data pages
2. Mid-Range Inserts: New rows in the middle may require page splits to maintain order
3. Updates: Row growth may cause movement; key changes cause delete + insert
4. Deletes: Create gaps that may be reused or cause fragmentation

The performance difference between sequential and random I/O is the fundamental reason physical ordering matters. Understanding this difference at the hardware level explains why clustered indexes are so powerful.

Hard Disk Drives (HDDs):

Traditional spinning disks have mechanical components that create stark performance differences:

• Sequential Read: ~100-200 MB/s

  • Disk head stays on track
  • Continuous data stream
  • Minimal seek time

• Random Read: ~0.5-2 MB/s for small blocks

  • Each read requires head seek (3-10ms)
  • Rotational latency (2-8ms)
  • Can only sustain 100-300 IOPS

The Ratio: Sequential is 50-200x faster than random on HDDs

Solid State Drives (SSDs):

SSDs have no mechanical components, but sequential vs random still matters:

• No Seek Time: Random access doesn't require physical movement
• But Still Different: Prefetching, block alignment, wear leveling favor sequential
• Parallelism: SSDs can parallelize sequential reads across channels
• Write Amplification: Random writes require more internal operations

The Ratio: Sequential is 2-10x faster on SSDs, depending on operations

Why This Matters for Databases:

Let's examine how physical ordering impacts specific query operations, demonstrating why the clustered index choice is critical.

Range Queries:

Consider SELECT * FROM Sales WHERE SaleDate BETWEEN '2024-01-01' AND '2024-01-31'

ORDER BY Operations:

When query results must be sorted by a specific column:

• If ORDER BY matches clustered key: Results are already in order—no sort needed
• If ORDER BY differs from clustered key: Database must sort results, using memory or temporary disk space

For queries like SELECT * FROM Orders ORDER BY CustomerID, OrderDate:

• Clustered on (CustomerID, OrderDate): Free—data emerges in order
• Clustered on OrderID: Requires expensive sort operation

GROUP BY and Aggregation:

Aggregation queries benefit from physical ordering:

SELECT CustomerID, SUM(Amount), COUNT(*)
FROM Orders
GROUP BY CustomerID

• Clustered on CustomerID: All rows for each customer are contiguous; aggregate as you scan
• Clustered on OrderDate: Rows for each customer scattered; requires hash aggregation or sort

Join Operations:

Join algorithms also benefit from physical ordering:

Merge Join: Requires both inputs sorted on join keys

• If both tables are clustered on join keys: Merge join is optimal
• If not: Sort operations required before merging

Nested Loop Join with Range Predicates:

• Outer table clustered on join column: Efficient range access
• Random access to outer table: More I/O per lookup

Index Intersection/Union:

• Multiple non-clustered index results must be merged
• Physical ordering of base table affects final data retrieval

A heap is a table without a clustered index—data is stored without any particular order. Understanding heap behavior illuminates why physical ordering matters.

Heap Characteristics:

Full Scan Behavior:

When scanning a heap (no WHERE clause or non-selective filter):

• The engine reads all pages belonging to the table
• Page order is physical allocation order, not related to data content
• Sequential I/O is possible if pages are allocated contiguously
• But no logical ordering—results appear in arbitrary order

Index Access to Heaps:

Non-clustered indexes on heaps use physical Row IDs (RIDs) as locators:

RID = (FileID : PageID : SlotNumber)
Example: 1:4523:7 = File 1, Page 4523, Slot 7

This enables direct page access without tree traversal, but:

• Row movement (from UPDATE) creates forwarding pointers
• Forwarding chains develop: RID → Forwarding → Forwarding → Data
• Performance degrades as chains lengthen

When Heaps Are Appropriate:

Despite their limitations, heaps serve specific use cases:

1. Staging Tables: Bulk load data, then process or transform—no need for ordering
2. Insert-Only Logging: Append-only write patterns with periodic bulk deletes
3. Full-Scan Only Access: Tables always scanned completely, never queried by key
4. Temporary Tables: Short-lived tables where maintenance overhead outweighs benefits
5. Very Small Tables: Lookup tables with few rows—physical order irrelevant

For production tables with selective queries, range scans, or update patterns, a clustered index is almost always preferable.

Physical ordering established by a clustered index degrades over time through a process called fragmentation. Understanding fragmentation types and their causes helps you maintain optimal physical organization.

Types of Fragmentation:

Fragmentation Prevention Strategies:

Different database systems handle physical ordering with varying approaches and terminology. Understanding these differences is essential when working across platforms.

PostgreSQL's CLUSTER Command:

PostgreSQL lacks true clustered indexes but provides the CLUSTER command:

-- Reorder table data according to an index
CLUSTER Orders USING idx_orders_date;

-- Recluster all previously clustered tables
CLUSTER;

Important Caveats:

• CLUSTER is a one-time operation; does not maintain order
• Requires exclusive table lock; blocks all access
• Subsequent inserts go wherever space exists
• Must re-cluster periodically via scheduled job
• Not a true clustered index—no ongoing maintenance

InnoDB's Mandatory Clustering:

MySQL's InnoDB always maintains a clustered index:

1. If PRIMARY KEY exists → clustered on PK
2. Else if UNIQUE NOT NULL index exists → clustered on first such index
3. Else → hidden 6-byte row ID as clustered key

Implication: You cannot have a 'heap' table in InnoDB. Every table has physical ordering based on some key. Secondary indexes store the clustered key, not RIDs, adding overhead if the clustered key is large.