Pages

Database Pages — A Deep Dive

Overview

• Purpose: Fixed-size pages store all database data (tables, collections, rows, columns, indexes, sequences, documents)
• Benefits:
  • Separates storage engine from database frontend
  • Simplifies data format and API handling
  • Easier to read, write, and cache when everything is a page
• Reference: SQL Server page layout (link)

Topics Covered

• Database page concepts and functionality
• Read/write operations to disk
• Disk storage mechanisms
• PostgreSQL page layout example

Buffer Pool (Page Pool)

Read Operations

• Process: Database finds page location → identifies file and offset → requests OS to read
• OS Caching: OS checks filesystem cache first, then issues disk read if needed
• Buffer Pool:
  • Database allocates shared/buffer pool memory
  • Pages from disk placed in buffer pool
  • Single page access provides multiple rows (depending on row width)
• Efficiency: Smaller rows = more rows per page = better I/O efficiency
• Use Case: Particularly effective for index range scans

Write Operations

• Process: Find page → pull into buffer pool → update in memory → create WAL entry
• WAL: Write-Ahead Logging (journal entry) persisted to disk
• Optimization: Page remains in memory for multiple writes before disk flush
• Operations: Updates, deletes, and inserts follow similar patterns (implementation varies)

Page Content Types

Row-Store Databases

• Structure: Rows and attributes packed sequentially in pages
• Optimization: Better for OLTP workloads, especially writes
• Access Pattern: Entire row retrieved efficiently

Column-Store Databases

• Structure: Rows stored column by column in pages
• Optimization: Better for OLAP workloads with summary operations on fewer fields
• Access Pattern: Single page read packed with values from one column
• Benefits: Aggregate functions (SUM, AVG) more effective
• Reference: Row vs Column comparison video

Document-Based Databases

• Structure: Compressed documents stored like row stores
• Optimization: Efficient document retrieval

Graph-Based Databases

• Structure: Connectivity persisted in pages for efficient graph traversal
• Tuning Options: Depth vs breadth vs search optimization

Design Principle

• Goal: Pack items to make page reads effective
• Rule: Page should provide maximum useful information for client workload
• Warning: Reading many pages for small work indicates need for data modeling review

Page Size Considerations

Small Pages

• Advantages:
  • Faster to read/write when closer to media block size
  • Lower latency for small operations
• Disadvantages:
  • Higher metadata overhead ratio
  • More page headers relative to useful data

Large Pages

• Advantages:
  • Minimized metadata overhead
  • Reduced page splits
  • Better for sequential operations
• Disadvantages:
  • Higher cold read/write costs
  • More memory usage per operation

Storage Technology Considerations

• Complexity: Gets complicated with disk/SSD optimization
• Emerging Tech: Zoned storage and key-value store namespaces in NVMe
• Industry Focus: Optimizing read/writes between host and media

Database Defaults

• PostgreSQL: 8KB
• MySQL InnoDB: 16KB
• MongoDB WiredTiger: 32KB
• SQL Server: 8KB
• Oracle: 8KB
• Note: Defaults work for most cases, but configuration may be needed for specific use cases

Disk Storage Methods

File-Per-Table Approach

• Structure: Array of fixed-size pages (Page 0, Page 1, Page 2…)
• Requirements: File name, offset, and length for disk reads
• Formula: To read page X → Offset = X × Page_Size
• Example:
  • Table: test, Page size: 8KB
  • Read pages 2-9: Offset 16,384 (2×8192), Length 65,536 bytes (8×8192)
• Reality: Many different implementation approaches exist across databases

PostgreSQL Page Layout

Overview

• Default Size: 8KB
• Reference: PostgreSQL page layout documentation
• Purpose: Explore PostgreSQL’s specific implementation and design choices

Page Header (24 bytes)

• Purpose: Fixed header containing page metadata
• Content:
  • Information about page contents
  • Available free space tracking
  • Essential page management data

ItemIds (4 bytes each)

• Function: Array of item pointers (not actual items/tuples)
• Structure: Each ItemId = 4-byte offset:length pointer
• Points To: Offset location and size of items within the page
• HOT Optimization:
  • Enables Heap Only Tuple optimization
  • During updates, pointer redirects to new tuple location
  • Allows indexes to maintain references to old tuple ID
  • Very powerful for performance
• Criticism:
  • At 4 bytes each, storage overhead can be significant
  • Example: an 8KB heap page holds at most ~291 tuples (MaxHeapTuplesPerPage) = ~1.2KB of line pointers; with small rows that’s still a big share of the page

Items (Variable length)

• Content: Actual items/tuples stored sequentially
• Layout: Items packed one after another
• Terminology:
  • Row: What user sees
  • Tuple: Physical instance of row in page
  • Item: The tuple itself
  • MVCC Impact: Same row can have multiple tuples (active + historical + dead)

Special Section (Variable length)

• Purpose: Index access-method-specific data
• Applies To: Every page of every index type (B-tree, hash, GiST, GIN, SP-GiST, BRIN); for B-tree that means all pages (internal and leaf, plus the meta page). It is empty (size 0) on heap/table pages
• Content: For B-tree, sibling links (previous/next page), the tree level and flags (leaf, root, deleted, etc.)
• Function: Enables efficient B-tree traversal (e.g. range scans along the sibling links)

Tuple Referencing Example

• Structure: Shows how tuples are referenced through ItemIds
• Benefits: Indirection allows for optimizations like HOT

Summary

Key Concepts

• Universal Storage: All database data ultimately stored in pages (indexes, sequences, tables)
• Abstraction: Pages allow database to work uniformly regardless of content type
• Structure: Pages contain headers and data, stored as files on disk
• Flexibility: Each database implements different page layouts and storage methods
• Common Principle: Consistent concept across all database systems despite implementation differences

Implementation Variations

• Page Layout: Different databases use different internal page structures
• Storage Methods: Various approaches to storing pages on disk
• Optimization: Each system optimizes for different use cases and workloads
• Standards: While concepts are universal, specific implementations vary significantly