sqrtspace-experiments/experiments/database_buffer_pool

SQLite Buffer Pool Experiment

Overview

This experiment demonstrates space-time tradeoffs in SQLite, the world's most deployed database engine. By varying the page cache size, we show how Williams' √n pattern appears in production database systems.

Key Concepts

Page Cache

• SQLite uses a page cache to keep frequently accessed database pages in memory
• Default: 2000 pages (can be changed with PRAGMA cache_size)
• Each page is typically 4KB-8KB

Space-Time Tradeoff

• Full cache O(n): All pages in memory, no disk I/O
• √n cache: Optimal balance for most workloads
• Minimal cache: Constant disk I/O, maximum memory savings

Running the Experiments

Quick Test

python test_sqlite_quick.py

Full Experiment

python run_sqlite_experiment.py

Heavy Workload Test

python sqlite_heavy_experiment.py

Tests with a 150MB database to force real I/O patterns.

Results

Our experiments show:

1. Modern SSDs reduce penalties: Fast NVMe drives minimize the impact of cache misses
2. Cache-friendly patterns: Sequential access can be faster with smaller caches
3. Real recommendations match theory: SQLite docs recommend √(database_size) cache

Real-World Impact

SQLite is used in:

• Every Android and iOS device
• Most web browsers (Chrome, Firefox, Safari)
• Countless embedded systems
• Many desktop applications

The √n cache sizing is crucial for mobile devices with limited memory.

Key Findings

• Theory predicts √n cache is optimal
• Practice shows modern hardware reduces penalties
• But √n sizing still recommended for diverse hardware
• Cache misses on mobile/embedded devices are expensive

Generated Files

• sqlite_experiment_results.json: Detailed timing data
• sqlite_spacetime_tradeoff.png: Visualization
• sqlite_heavy_experiment.png: Heavy workload analysis