Lock Granularity

Between the extremes of row-level locking (maximum concurrency, maximum overhead) and table-level locking (minimum overhead, minimum concurrency) lies an important intermediate granularity: page-level locking.

To understand page-level locking, we must first understand what a page is in database systems. Unlike the logical concept of a 'row' which represents a single record, a page (also called a block in some systems) is a fundamental unit of physical storage and I/O. It's the chunk of data that the database reads from and writes to disk in a single operation.

Page-level locking treats this physical storage unit as the lockable resource. When a transaction locks a page, it gains access to all rows stored on that page—typically dozens to hundreds of rows depending on row size and page configuration.

This approach represents a carefully calculated trade-off: less overhead than row-level locking (fewer locks to manage) while maintaining more concurrency than table-level locking (only rows on the same page compete for access).

Before diving into page-level locking, we need a solid understanding of what database pages are and why they exist. This physical storage concept is fundamental to understanding granularity trade-offs.

What is a Database Page?

A database page (or block) is the smallest unit of data that the database engine reads from or writes to persistent storage. When you SELECT a single row, the database doesn't read just that row from disk—it reads the entire page containing that row.

Why Pages Exist:

Pages exist because disk I/O operates at block level:

1. Disk Sector Alignment: Hard drives and SSDs transfer data in fixed-size blocks (typically 512 bytes or 4KB at the hardware level)
2. I/O Efficiency: Reading 8KB at once is nearly as fast as reading 8 bytes due to disk access latency dominating transfer time
3. Memory Management: The buffer pool manages memory in fixed-size chunks, simplifying allocation and replacement
4. Write Efficiency: Writing a full page is more efficient than multiple small writes

Page Structure:

A typical database page contains:

┌─────────────────────────────────────────────────────────────┐
│                      Page Header                            │
│  (Page ID, LSN, Checksum, Free Space Pointer, etc.)        │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│                      Row Data Area                          │
│                                                             │
│  ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐          │
│  │  Row 1  │ │  Row 2  │ │  Row 3  │ │  Row 4  │   ...    │
│  └─────────┘ └─────────┘ └─────────┘ └─────────┘          │
│                                                             │
│                    (Free Space)                            │
│                                                             │
├─────────────────────────────────────────────────────────────┤
│                      Row Directory                          │
│  (Offsets to each row within the page)                     │
└─────────────────────────────────────────────────────────────┘

Rows Per Page:

The number of rows that fit on a page depends on row size:

• Small rows (100 bytes): 8 KB page ≈ 70-80 rows per page
• Medium rows (500 bytes): 8 KB page ≈ 15-16 rows per page
• Large rows (2000 bytes): 8 KB page ≈ 3-4 rows per page

This variability is crucial for understanding page-level locking impact.

A page-level lock is a lock acquired on an entire database page. When a transaction locks a page, it gains exclusive or shared access to all rows stored on that page, regardless of whether it needs to access all of them.

Formal Definition:

Let P be a page containing rows r₁, r₂, ..., rₘ. A page-level lock on P grants the holding transaction access to all rows r₁ through rₘ simultaneously. Any other transaction wishing to access any row on page P must wait or share the lock according to compatibility rules.

Lock Acquisition Process:

1. Transaction T wants to access row R
2. Database determines that R is located on page P
3. T requests a page-level lock on P
4. If granted, T can access R (and any other row on P)
5. Other transactions wanting any row on P must wait or share the lock

Example Scenario:

Consider an orders table where each page holds approximately 50 orders:

Page 1: Orders 1-50
Page 2: Orders 51-100
Page 3: Orders 101-150
...

With page-level locking:

Transaction T₁: UPDATE orders SET status = 'shipped' WHERE order_id = 25;
→ Acquires X-lock on Page 1 (containing order 25)
→ T₁ now has exclusive access to orders 1-50

Transaction T₂: SELECT * FROM orders WHERE order_id = 75;
→ Acquires S-lock on Page 2 (containing order 75)
→ T₂ can read orders 51-100
→ No conflict with T₁ (different pages)

Transaction T₃: UPDATE orders SET total = 500 WHERE order_id = 30;
→ Requests X-lock on Page 1 (containing order 30)
→ BLOCKED: T₁ already holds X-lock on Page 1
→ Even though T₃ wants a different row, it must wait

The "False Conflict" Problem:

This example illustrates a key limitation of page-level locking: false conflicts. Transactions T₁ and T₃ want to access different rows (25 and 30), but because those rows happen to reside on the same page, they conflict. With row-level locking, these transactions would proceed concurrently.

While page-level locking sacrifices some concurrency compared to row-level locking, it offers significant advantages in specific scenarios. Understanding these advantages helps identify when page-level locking is the right choice.

1. Reduced Lock Overhead

The primary advantage is dramatically lower lock management overhead:

• A table with 1 million rows might span 20,000 pages (at 50 rows/page)
• Row-level locking: Up to 1,000,000 lock entries
• Page-level locking: Up to 20,000 lock entries (50x reduction)

This reduction directly translates to:

• Less memory consumed by the lock manager
• Fewer hash table operations
• Faster lock acquisition and release
• Lower CPU overhead per transaction

2. Natural Alignment with I/O Operations

Since the database reads and writes data in page-sized chunks, page-level locks align naturally with physical I/O:

• When a transaction modifies a row, the entire page must be read/written anyway
• Locking at the page level means the lock granularity matches the I/O granularity
• This alignment simplifies recovery and buffer management

3. Efficient for Sequential Access Patterns

Workloads that access data sequentially benefit from page-level locking:

Scenario: Processing orders in order_id sequence

-- Row-level locking: 1000 lock operations
SELECT * FROM orders WHERE order_id BETWEEN 1 AND 1000;

-- Page-level locking: ~20 lock operations (1000 rows / 50 per page)
-- Each page lock covers all rows on that page

For sequential scans, page-level locking provides near-row-level concurrency (different pages accessed simultaneously) with dramatically lower overhead.

4. Reduced Deadlock Complexity

With fewer lock objects, the potential for complex deadlock cycles decreases:

• Wait-for graphs are smaller and simpler
• Deadlock detection runs faster
• Fewer lock ordering considerations for application developers

Despite its advantages, page-level locking introduces significant limitations that make it unsuitable for many modern workloads.

1. Reduced Concurrency Due to False Conflicts

The fundamental limitation is false conflicts—transactions that logically could proceed concurrently are blocked because they happen to access rows on the same page.

Quantifying the Impact:

Consider a table with 100,000 rows distributed across 2,000 pages (50 rows/page). Two transactions each accessing a single random row:

• Probability of page conflict: 1/2000 = 0.05%
• With 100 concurrent transactions: Expected conflicts increase significantly
• With 1000 concurrent transactions accessing random rows: Contention becomes problematic

For tables with 'hot' pages (frequently accessed), the problem is severe:

Hot Page Scenario:
- Page contains "most popular products" due to insertion order
- Every product view query touches this page
- Result: All product view transactions serialize on one page

2. The Last-Page Insert Problem

A notorious issue with page-level locking affects insert-heavy workloads:

Sequential Insert Pattern:
- New rows are inserted at the 'end' of the table
- All new rows go to the last page until it fills
- Every insert transaction contends for the same page
- Result: Insert throughput limited to 1 transaction at a time

Timeline:
T1: INSERT INTO orders (...) → Lock Page 1000, insert, release
T2: INSERT INTO orders (...) → Wait for T1, Lock Page 1000, insert, release  
T3: INSERT INTO orders (...) → Wait for T2, Lock Page 1000, insert, release
→ Complete serialization of inserts

3. Index Traversal Contention

B-tree indexes are particularly susceptible to page-level lock contention:

• Root page is touched by every index lookup
• High-level branch pages are frequently accessed
• With page-level locking, index traversal itself causes blocking

This is one reason modern databases use specialized techniques like latch coupling and lock coupling for index traversal.

Understanding the historical context of page-level locking illuminates both its original purpose and why most modern systems have moved beyond it.

The Era of Page-Level Locking (1970s-1990s)

Page-level locking was the dominant approach in early relational databases for several practical reasons:

1. Memory Constraints: Early systems had limited RAM (megabytes, not gigabytes). Lock tables consumed precious memory, making coarse granularity necessary.

2. CPU Limitations: Lock management overhead was significant on slower processors. Fewer locks meant less CPU spent on locking.

3. Simpler Implementation: Page-level locking aligns with the buffer manager's view of data, simplifying implementation.

4. Lower Concurrency Requirements: Early database systems served fewer concurrent users, making the concurrency limitations acceptable.

The Transition to Row-Level Locking

Several factors drove the industry transition:

1. Moore's Law: Memory became abundant and cheap. Lock tables could grow much larger.

2. CPU Speed: Faster processors made lock management overhead negligible.

3. Concurrency Demands: Web applications required thousands of concurrent transactions.

4. MVCC Innovation: Multi-Version Concurrency Control reduced the need for read locks entirely.

Modern Status

Today, page-level locking persists in specific contexts:

• DB2 for z/OS: Still supports page-level locking for compatibility
• SQLite: Uses page-level locking (but typically single-writer anyway)
• File-based databases: Some embedded databases lock at file/page level
• Lock escalation: Many row-level databases escalate to page locks under pressure

While pure page-level locking is rare in modern OLTP databases, understanding how it works—and how it appears in escalation scenarios—remains practically important.

SQL Server: Page Lock Hints and Escalation

SQL Server supports explicit page-level locking through query hints:

Diagnosing Page Lock Contention:

When page-level locking causes problems, symptoms include:

• High wait times on PAGE resource types
• Lock waits correlating with physical data distribution
• Performance degradation that doesn't correlate with logical query patterns

Mitigation Strategies:

Understanding when each granularity is appropriate helps in system design and troubleshooting. While modern databases default to row-level locking, there are scenarios where page-level granularity is acceptable or even preferable.

Decision Framework:

Practical Recommendation:

For nearly all modern applications:

1. Start with row-level locking (the default in most databases)
2. Monitor for lock escalation events under load
3. Investigate page-level only if lock management overhead is demonstrably problematic
4. Use MVCC/snapshot isolation to reduce read locks entirely
5. Consider table redesign before accepting coarser granularity

Page-level locking represents an intermediate granularity between fine-grained row locks and coarse-grained table locks. Let's consolidate the key concepts:

Looking Ahead:

We've explored the middle of the granularity spectrum. In the next page, we'll examine table-level locking—the coarsest commonly-used granularity. Table locks provide maximum simplicity and minimum overhead, but completely serialize access to the locked table. Understanding when this extreme trade-off is acceptable completes our granularity toolkit.