Table Partitioning

The Index Maintenance lesson left a question open. Deleting old loan records left dead space everywhere it failed to overlap with index order, and recovering that space required rewriting the table from scratch. The source of the problem is not the delete itself but the fact that the data being deleted was mixed in among the live data.

Partitioning (partitioning) prevents this mixing from the outset: a table that is logically a single table is stored physically as more than one piece. Each piece is called a partition (partition), and which partition a row falls into is decided by the partition key (partition key). This lesson sets up three forms of partitioning, measures their gain, and also shows where the gain does not come from.

Range Partitioning

The most common form is range partitioning (range partitioning): value ranges of the partition key correspond to partitions. In library records the natural key is the pickup date, and the natural range is the year.

Some engines offer partitioning through their syntax; where they do not, the same structure is built with separate tables and a union view. The run below follows the second path. Each partition table states its own range with a value check, and a view gathers the partitions under a single name.

rm -f unpartitioned.db partitioned.db partition.sql
cat > setup.sql <<'SQL'
CREATE TABLE loan (
  loan_id      INTEGER PRIMARY KEY,
  book_id      INTEGER NOT NULL,
  member_id    INTEGER NOT NULL,
  pickup_date  TEXT NOT NULL,
  return_date  TEXT
);
INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;
SQL
sqlite3 unpartitioned.db < setup.sql
sqlite3 unpartitioned.db 'CREATE INDEX loan_pickup ON loan(pickup_date);'

# One partition table per year, a value check, and a view gathering the partitions.
{
  echo "ATTACH 'unpartitioned.db' AS source;"
  for y in 2018 2019 2020 2021 2022 2023 2024; do
    s=$((y + 1))
    cat <<EOF
CREATE TABLE loan_$y (
  loan_id      INTEGER PRIMARY KEY,
  book_id      INT NOT NULL,
  member_id    INT NOT NULL,
  pickup_date  TEXT NOT NULL CHECK (pickup_date >= '$y-01-01' AND pickup_date < '$s-01-01'),
  return_date  TEXT);
INSERT INTO loan_$y SELECT * FROM source.loan
  WHERE pickup_date >= '$y-01-01' AND pickup_date < '$s-01-01';
CREATE INDEX loan_${y}_pickup ON loan_$y(pickup_date);
EOF
  done
  echo "CREATE VIEW loan AS"
  echo "  SELECT * FROM loan_2018 UNION ALL SELECT * FROM loan_2019 UNION ALL"
  echo "  SELECT * FROM loan_2020 UNION ALL SELECT * FROM loan_2021 UNION ALL"
  echo "  SELECT * FROM loan_2022 UNION ALL SELECT * FROM loan_2023 UNION ALL"
  echo "  SELECT * FROM loan_2024;"
} > partition.sql
sqlite3 partitioned.db < partition.sql
sqlite3 partitioned.db <<'SQL'
.mode column
.headers on
SELECT count(*) AS view_rows FROM loan;
SELECT name AS partition_, count(*) AS pages FROM dbstat
WHERE name LIKE 'loan\_20__' ESCAPE '\' GROUP BY name ORDER BY name;
SQL

view_rows
---------
2000000
partition_  pages
----------  -----
loan_2018   2966
loan_2019   2982
loan_2020   2970
loan_2021   2959
loan_2022   2964
loan_2023   2982
loan_2024   1994

The view returns all two million rows: from the application’s point of view the table is still a single one. Underneath it there are seven separate tables, seven separate indexes, and seven separate trees of roughly three thousand pages each.

Touching Only the Relevant Partition

Partitioning’s first claim is this: a query that filters on the partition key never reads the other partitions at all. This claim is invisible in plan output — the plan lists all seven partitions.

sqlite3 partitioned.db "EXPLAIN QUERY PLAN
SELECT count(*) FROM loan WHERE pickup_date BETWEEN '2021-03-01' AND '2021-03-31';"

for target in "partitioned.db|loan|partitioned view" \
             "partitioned.db|loan_2021|direct 2021 partition" \
             "unpartitioned.db|loan|unpartitioned single table"; do
  db=${target%%|*}; rest=${target#*|}; tbl=${rest%%|*}; label=${rest#*|}
  printf '%-24s ' "$label"
  sqlite3 "$db" <<SQL 2>&1 | grep -E 'Page cache misses|Run Time' | tr '\n' ' '
.stats on
.timer on
SELECT count(*) FROM $tbl WHERE pickup_date BETWEEN '2021-03-01' AND '2021-03-31';
SQL
  echo
done

QUERY PLAN
|--CO-ROUTINE loan
|  `--COMPOUND QUERY
|     |--LEFT-MOST SUBQUERY
|     |  `--SEARCH loan_2018 USING INDEX loan_2018_pickup (pickup_date>? AND pickup_date<?)
|     |--UNION ALL
|     |  `--SEARCH loan_2019 USING INDEX loan_2019_pickup (pickup_date>? AND pickup_date<?)
|     |--UNION ALL
|     |  `--SEARCH loan_2020 USING INDEX loan_2020_pickup (pickup_date>? AND pickup_date<?)
|     |--UNION ALL
|     |  `--SEARCH loan_2021 USING INDEX loan_2021_pickup (pickup_date>? AND pickup_date<?)
|     |--UNION ALL
|     |  `--SEARCH loan_2022 USING INDEX loan_2022_pickup (pickup_date>? AND pickup_date<?)
|     |--UNION ALL
|     |  `--SEARCH loan_2023 USING INDEX loan_2023_pickup (pickup_date>? AND pickup_date<?)
|     `--UNION ALL
|        `--SEARCH loan_2024 USING INDEX loan_2024_pickup (pickup_date>? AND pickup_date<?)
`--SCAN loan
partitioned view         Page cache misses:                   141 Run Time: real 0.002 user 0.001953 sys 0.000144
direct 2021 partition    Page cache misses:                   123 Run Time: real 0.001 user 0.000526 sys 0.000114
unpartitioned single table Page cache misses:                   123 Run Time: real 0.000 user 0.000488 sys 0.000111

The page miss counts confirm the claim. The query asked directly of the 2021 partition read 123 pages; the query asked through the view read 141 pages. The 18-page difference is six empty probes into six partitions’ indexes — one partition costs three pages per empty probe. Six of the seven partitions show up in the plan, but their data is never read.

The name for this distinction is partition pruning (partition pruning). In engines that offer built-in partitioning, pruning happens while the plan is being built, and irrelevant partitions never enter the plan at all; in the model used here it happens at run time, because each empty probe comes back empty immediately within its own index. The two approaches are close in result, not in cost: once partition count reaches the hundreds, the sum of hundreds of empty probes stops being negligible.

The third row corrects an expectation, however. The unpartitioned single table answered the same query with the same 123 pages. With an index already in place, partitioning does not buy read performance — the index was already doing the same job. Partitioning’s gain lies elsewhere.

Deleting Old Data and Dropping a Partition

The real gain is that data can be removed as a whole. The run below does the same job in two setups: removing the records from 2018 from the system.

rm -f s1.db s2.db
cp unpartitioned.db s1.db
cp partitioned.db   s2.db
measure() { printf '%-8s file=%s  total_pages=%s  free=%s\n' "$2" "$(wc -c < "$1")" \
  "$(sqlite3 "$1" 'PRAGMA page_count;')" "$(sqlite3 "$1" 'PRAGMA freelist_count;')"; }

echo "=== unpartitioned: deleting the old year ==="
measure s1.db before
sqlite3 s1.db <<'SQL' | grep 'Run Time'
.timer on
DELETE FROM loan WHERE pickup_date < '2019-01-01';
SQL
measure s1.db delete
sqlite3 s1.db <<'SQL' | grep 'Run Time'
.timer on
VACUUM;
SQL
measure s1.db vacuum

echo
echo "=== partitioned: dropping the old partition ==="
measure s2.db before
sqlite3 s2.db <<'SQL' | grep 'Run Time'
.timer on
DROP VIEW loan;
DROP TABLE loan_2018;
CREATE VIEW loan AS
  SELECT * FROM loan_2019 UNION ALL SELECT * FROM loan_2020 UNION ALL
  SELECT * FROM loan_2021 UNION ALL SELECT * FROM loan_2022 UNION ALL
  SELECT * FROM loan_2023 UNION ALL SELECT * FROM loan_2024;
SQL
measure s2.db drop
sqlite3 s2.db "SELECT count(*) FROM loan;"

=== unpartitioned: deleting the old year ===
before   file= 112066560  total_pages=27360  free=0
Run Time: real 0.636 user 0.146132 sys 0.187506
delete   file= 112066560  total_pages=27360  free=1398
Run Time: real 0.442 user 0.147281 sys 0.262742
vacuum   file= 95285248  total_pages=23263  free=0

=== partitioned: dropping the old partition ===
before   file= 119492608  total_pages=29173  free=0
Run Time: real 0.000 user 0.000080 sys 0.000228
Run Time: real 0.061 user 0.002279 sys 0.006716
Run Time: real 0.000 user 0.000062 sys 0.000154
drop     file= 119492608  total_pages=29173  free=4367
1700444

Both paths removed the same 299,556 rows from the system; their costs are not comparable. In this environment the delete path took 0.636 seconds and freed only 1,398 pages — the rest of the gap was scattered inside the remaining pages. Recovering that gap required a full rewrite, which took another 0.442 seconds, and the table was locked for that whole span. Together the two steps ran past a second.

Dropping the partition took about 0.061 seconds and freed 4,367 pages in a single operation. The work performed is not deleting rows but removing an object: cost is measured not by row count but by a fixed catalog operation. Run times depend on the environment; what is stable is that one cost scales with data and the other does not.

This is the core reason for partitioning in every system with a retention rule. The same reasoning runs in the other direction too: adding an empty partition when a new period begins is also a fixed-cost operation.

List and Hash Partitioning

Two more forms exist. In list partitioning (list partitioning), each partition takes specific values of the key — city, branch, country. In hash partitioning (hash partitioning), the partition is found by passing the key through a hash function and dividing by the partition count; the goal is not a meaningful grouping but an even distribution.

The choice depends on how evenly the partitions will fill, and this can be computed. The model below distributes loans per member close to a power law — a small number of members hold many loans, most members leave only a few records — and counts partition fill for three key choices.

cat > distribution.mjs <<'JS'
// Model: distribution of loan records across partitions. Not a real database's
// partitioner; what is measured is the relationship between key choice and partition fill.
// Loans per member are distributed close to a power law: a few members hold many loans.
const MEMBERS = 120000, RECORDS = 2000000;
const cities = [['Istanbul', 0.42], ['Ankara', 0.24], ['Izmir', 0.16],
                  ['Bursa', 0.11], ['Konya', 0.07]];

function members() {
  const weight = [];
  let total = 0;
  for (let i = 1; i <= MEMBERS; i++) { const a = 1 / Math.pow(i, 0.8); weight.push(a); total += a; }
  return weight.map((a, i) => {
    let threshold = ((i * 7919) % 100) / 100, k = 0, cumulative = 0;
    while (k < cities.length - 1 && (cumulative += cities[k][1]) <= threshold) k++;
    return { member_id: i + 1, loans: Math.max(1, Math.round(a / total * RECORDS)), city: cities[k][0] };
  });
}
const M = 2654435761n;
const hashLow  = (x) => Number((BigInt(x) * M) % 4294967296n);          // low bits
const hashHigh = (x) => Number(((BigInt(x) * M) % 4294967296n) >> 20n); // high bits

function report(label, bucket) {
  const busiest = Math.max(...bucket), quietest = Math.min(...bucket);
  const empty = bucket.filter((s) => s === 0).length;
  const ratio = quietest === 0 ? 'partitions empty: ' + empty : (busiest / quietest).toFixed(2) + 'x';
  console.log(label.padEnd(24), 'partitions', String(bucket.length).padStart(2),
              '| busiest', String(busiest).padStart(8), '| quietest', String(quietest).padStart(8),
              '| ratio', ratio);
}
function distribute(member, P, key) {
  const bucket = new Array(P).fill(0);
  for (const m of member) bucket[key(m.member_id) % P] += m.loans;
  return bucket;
}
const member = members();
console.log('total loans in model:', member.reduce((t, m) => t + m.loans, 0));
console.log('— hash partitioning, near-power-law key —');
for (const P of [8, 16, 64]) {
  report('member_id % P', distribute(member, P, (x) => x));
  report('hash_high % P', distribute(member, P, hashHigh));
}
console.log('— structured key: membership number a multiple of four —');
const fours = member.map((m) => ({ ...m, member_id: m.member_id * 4 }));
report('member_id % 8',  distribute(fours, 8, (x) => x));
report('hash_low % 8',   distribute(fours, 8, hashLow));
report('hash_high % 8',  distribute(fours, 8, hashHigh));
console.log('— list partitioning: city —');
const listBucket = cities.map(([name]) =>
  member.filter((m) => m.city === name).reduce((t, m) => t + m.loans, 0));
report('city', listBucket);
console.log(cities.map(([name], i) => `${name}=${listBucket[i]}`).join('  '));
JS
node distribution.mjs

total loans in model: 2001046
— hash partitioning, near-power-law key —
member_id % P            partitions  8 | busiest   278850 | quietest   238066 | ratio 1.17x
hash_high % P            partitions  8 | busiest   273855 | quietest   233420 | ratio 1.17x
member_id % P            partitions 16 | busiest   158156 | quietest   116396 | ratio 1.36x
hash_high % P            partitions 16 | busiest   154631 | quietest   114336 | ratio 1.35x
member_id % P            partitions 64 | busiest    69604 | quietest    27466 | ratio 2.53x
hash_high % P            partitions 64 | busiest    69318 | quietest    26434 | ratio 2.62x
— structured key: membership number a multiple of four —
member_id % 8            partitions  8 | busiest  1014448 | quietest        0 | ratio partitions empty: 6
hash_low % 8             partitions  8 | busiest  1014448 | quietest        0 | ratio partitions empty: 6
hash_high % 8            partitions  8 | busiest   285482 | quietest   236957 | ratio 1.20x
— list partitioning: city —
city                     partitions  5 | busiest   876922 | quietest   139966 | ratio 6.27x
Istanbul=876922  Ankara=464332  Izmir=312596  Bursa=207230  Konya=139966

Three findings come out of this.

First: hash partitioning balances keys, not rows. At eight partitions the imbalance ratio is 1.17; at sixty-four partitions it is 2.53. As partitions shrink, a single very active member’s weight grows relative to the whole partition, and the hash function’s quality does not change that — the top two rows coming out nearly identical shows this.

Second: the hash function’s quality becomes decisive when the key is structured. With membership numbers all multiples of four, direct division left six of the eight partitions empty. The low bits of the multiplicative hash gave the same result; the reason is arithmetic — multiplying by a single factor and then dividing by a power of two preserves the low bits. Taking the high bits instead brought the distribution back down to a 1.20 ratio. The rule: the low bits of a hash value are not used to choose a partition.

Third: list partitioning never aims for balance at all. Records split by city came out at a 6.27 ratio, and this is not a flaw but reality itself. List partitioning is chosen when partitions need to be managed separately — when one city’s data needs to be stored separately, backed up separately, or deleted separately, imbalance is accepted.

Summary

• Partitioning stores a table that is logically single across more than one physical piece according to a partition key; range, list, and hash forms differ in how the key is turned into a partition.
• A query filtering on the partition key does not read the data of irrelevant partitions: in this environment, 141 pages were read through the view against 123 pages read from a single partition directly; the difference is six empty index probes.
• With an index already in place, partitioning did not buy read performance; the unpartitioned table answered the same query with the same 123 pages.
• The real gain is removing data as a whole: in this environment, deleting a year and recovering the gap took about 1.08 seconds and freed 1,398 pages; dropping the partition freed 4,367 pages in about 0.06 seconds.
• Hash partitioning balances keys, not rows; imbalance grew as partition count rose (1.17 → 2.53). On structured keys, the low bits of a hash value cannot be used to choose a partition.

Next Step

Every partition in this lesson lived inside the same database. Distributing partitions across separate machines takes the same idea one step further and changes its nature: a cross-partition query now travels over a network, a transaction can span more than one machine, and changing the partition count forces data to move. The next lesson takes on this pattern — what choosing a shard key imposes on the application, the cost of a cross-shard query, and the amount of data moved during rebalancing, all counted.