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   2967
loan_2019   2954
loan_2020   2952
loan_2021   2951
loan_2022   2947
loan_2023   2957
loan_2024   1984

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

{/* mask: (?<=real )[0-9.]+ user [0-9.]+ sys [0-9.]+ */}

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:                   139 Run Time: real 0.002 user 0.001709 sys 0.000257
direct 2021 partition    Page cache misses:                   121 Run Time: real 0.000 user 0.000646 sys 0.000000
unpartitioned single table Page cache misses:                   123 Run Time: real 0.001 user 0.000000 sys 0.000657

The page miss counts confirm the claim. The query asked directly of the 2021 partition read 121 pages; the query asked through the view read 139 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 123 pages, about the same as the direct partition. 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;"

{/* mask: (?<=real )[0-9.]+ user [0-9.]+ sys [0-9.]+ */}

=== unpartitioned: deleting the old year ===
before   file=111665152  total_pages=27262  free=0
Run Time: real 0.481 user 0.157888 sys 0.322181
delete   file=111665152  total_pages=27262  free=1393
Run Time: real 0.229 user 0.123275 sys 0.104893
vacuum   file=94892032  total_pages=23167  free=0

=== partitioned: dropping the old partition ===
before   file=118927360  total_pages=29035  free=0
Run Time: real 0.000 user 0.000000 sys 0.000129
Run Time: real 0.016 user 0.003971 sys 0.012170
Run Time: real 0.000 user 0.000025 sys 0.000081
drop     file=118927360  total_pages=29035  free=4363
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.481 seconds and freed only 1,393 pages — the rest of the gap was scattered inside the remaining pages. Recovering that gap required a full rewrite, which took another 0.229 seconds, and the table was locked for that whole span. Together the two steps took more than half a second.

Dropping the partition took about 0.016 seconds and freed 4,363 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, 139 pages were read through the view against 121 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 123 pages.
• The real gain is removing data as a whole: in this environment, deleting a year and recovering the gap took about 0.71 seconds and freed 1,393 pages; dropping the partition freed 4,363 pages in about 0.016 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.