Why can random UUIDv4 primary keys cause index fragmentation and slower inserts, and how do time-ordered IDs fix this

• UUIDv4 – A fully random 128-bit identifier; consecutive inserts land at random positions in the B-tree, causing page splits and fragmentation.
• Auto-increment – A monotonically increasing integer from a database sequence; every new key appends to the rightmost page, keeping the tree dense.
• Page split – When a B-tree leaf page is full and a new key must be inserted in the middle, the engine allocates a new page and moves half the entries, leaving both pages half-full.
• UUIDv7 – A 128-bit identifier with a 48-bit Unix millisecond timestamp prefix, giving approximately monotonic ordering and insert locality while remaining globally unique.
• ULID – Similar to UUIDv7: 48-bit timestamp prefix + random suffix, sortable and coordination-free.

Why does auto-increment work well for B-tree inserts?

A B-tree primary key index is kept in sorted key order. With auto-increment, each new key is larger than all previous ones, so it always lands on the rightmost leaf page. That page fills up and a fresh page is appended – a cheap, sequential operation.

-- Auto-increment: every INSERT appends to the rightmost page
CREATE TABLE transactions_auto (
    txn_id     BIGSERIAL PRIMARY KEY,  -- auto-increment
    account_id VARCHAR(20) NOT NULL,
    amount     DECIMAL(15,2) NOT NULL,
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP
);

-- Insert 1: txn_id = 1 -> rightmost page
-- Insert 2: txn_id = 2 -> same rightmost page
-- Insert 3: txn_id = 3 -> same rightmost page
-- Page fills up -> new page appended at the end
-- Result: dense, sequential, no fragmentation

Why does random UUIDv4 cause page splits?

A UUIDv4 is random across its whole range. Each new key is equally likely to belong anywhere in the tree. When the target leaf page is full, the engine performs a page split.

-- Random UUIDv4: every INSERT targets a random leaf page
CREATE TABLE transactions_uuid (
    txn_id     UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    account_id VARCHAR(20) NOT NULL,
    amount     DECIMAL(15,2) NOT NULL,
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP
);

-- Insert 1: txn_id = 'f47ac10b-...' -> middle of tree
-- Insert 2: txn_id = '1a2b3c4d-...' -> left side of tree
-- Insert 3: txn_id = '9x8y7z6w-...' -> different spot
-- Each insert may cause a page split in a different location

Page split process:
  1. New key 'f47ac10b' targets leaf page #42
  2. Page #42 is full
  3. Engine allocates new page #500
  4. Moves half of page #42's entries to page #500
  5. Both pages are now ~50% full
  6. Wasted space + scattered pages = fragmentation

What is the impact of fragmentation?

Random inserts cause several problems.

| Problem | Auto-increment | Random UUIDv4 |
|---|---|---|
| Insert pattern | Sequential (rightmost page) | Random (any page) |
| Page splits | Rare (only at the end) | Frequent (everywhere) |
| Page fill factor | ~90-100% | ~50-70% |
| Cache locality | Excellent (hot pages stay in memory) | Poor (working set is scattered) |
| Index size | Compact | Bloated (half-full pages) |
| Write throughput | High | Lower |

How does InnoDB make it worse?

In InnoDB the primary key is the clustered index, so random primary keys scatter the actual row data too. And every secondary index stores the primary key as its row pointer, so a 16-byte UUID bloats every secondary index.

-- Bad: 36-byte UUID string as PK (common mistake)
CREATE TABLE payments_bad (
    payment_id CHAR(36) PRIMARY KEY,  -- 36 bytes!
    account_id VARCHAR(20),
    amount     DECIMAL(15,2)
);
-- Every secondary index entry carries 36 bytes for the PK pointer
-- Index is 4.5x larger than with BIGINT (8 bytes)

-- Better: native UUID type (16 bytes)
CREATE TABLE payments_better (
    payment_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    account_id VARCHAR(20),
    amount     DECIMAL(15,2)
);
-- Still random, but at least 16 bytes instead of 36

How do time-ordered IDs fix the problem?

UUIDv7 places a 48-bit Unix-millisecond timestamp in the high bits. Because the leading bits increase with real time, new keys land near the right edge of the tree, restoring insert locality.

-- UUIDv7: timestamp prefix makes inserts approximately sequential
CREATE TABLE transactions_v7 (
    txn_id     UUID PRIMARY KEY,  -- UUIDv7 generated in app
    account_id VARCHAR(20) NOT NULL,
    amount     DECIMAL(15,2) NOT NULL,
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP
);

-- UUIDv7 values generated over time:
-- 2026-10-25 14:30:00 -> '0192a3b4-...' (timestamp prefix)
-- 2026-10-25 14:30:01 -> '0192a3b5-...' (slightly larger)
-- 2026-10-25 14:30:02 -> '0192a3b6-...' (slightly larger)
-- All land near the rightmost page, like auto-increment

// com.bank.service.PaymentIdGenerator
package com.bank.service;

import java.util.UUID;

public class PaymentIdGenerator {

    /**
     * Generate a UUIDv7 with timestamp prefix.
     * Java 17+ does not have built-in UUIDv7,
     * so use a library like java-uuid-generator or uuid-creator.
     *
     * The key property: new IDs are approximately monotonically
     * increasing, so B-tree inserts stay near the right edge.
     */
    public static UUID generateV7() {
        // Using com.github.f4b6a3:uuid-creator library
        // return UuidCreator.getTimeOrderedEpoch();

        // Manual implementation for illustration:
        long timestamp = System.currentTimeMillis();
        long msb = (timestamp << 16) | 0x7000L; // version 7
        long lsb = (0x8000000000000000L)         // variant
                  | (long)(Math.random() * Long.MAX_VALUE);
        return new UUID(msb, lsb);
    }
}

How does UUIDv7 compare to auto-increment and UUIDv4?

| Feature | Auto-increment | UUIDv4 | UUIDv7 |
|---|---|---|---|
| Insert locality | Perfect | Random | Near-sequential |
| Page splits | Rare | Frequent | Rare |
| Global uniqueness | No (needs DB) | Yes | Yes |
| Coordination needed | Yes (sequence) | No | No |
| Time ordering | Yes | No | Approximate |
| Size | 4-8 bytes | 16 bytes | 16 bytes |
| Guessable | Yes (enumerable) | No | Partially (timestamp) |

What about ULID?

ULID is similar to UUIDv7: 48-bit timestamp prefix plus random suffix, lexicographically sortable, and coordination-free.

ULID format:
  01ARZ3NDEKTSV4RRFFQ69G5FAV
  |-----------||-----------|
  Timestamp     Randomness
  (48 bits)     (80 bits)

ULID is string-sortable, which is convenient for systems that store IDs as text. UUIDv7 is the standardized equivalent (RFC 9562).

What are common mistakes?

The most common mistake is storing UUIDs as 36-character strings instead of native 16-byte binary.

-- Wrong: 36-byte string, wastes space, bloats secondary indexes
CREATE TABLE payments_wrong (
    id CHAR(36) PRIMARY KEY  -- '550e8400-e29b-41d4-a716-446655440000'
);

-- Correct: native UUID type (16 bytes)
CREATE TABLE payments_correct (
    id UUID PRIMARY KEY  -- stored as 16-byte binary
);

What should a senior engineer know?

• UUIDv7 gives approximate ordering, not a strict global sequence, because clocks on different nodes can skew.
• The timestamp prefix means UUIDv7 leaks creation time – it is an identifier, not a secret or authentication token.
• Monitor index bloat with pg_stat_user_tables and pgstattuple to detect fragmentation from random inserts.
• After switching from UUIDv4 to UUIDv7, measure insert throughput and index size to confirm the improvement.

What are common interview follow-up questions?

• What is the UUIDv7 binary structure (48-bit timestamp, version, variant, random)?
• When should you choose a UUID key versus an auto-increment key?
• How does InnoDB embed the primary key in secondary indexes?
• What is the difference between UUIDv7 and Snowflake IDs?