Doubling the Sorting Speed of Postgres Network Types with Abbreviated Keys

Speeding Up Network Type Sorting

Postgres's inet and cidr types—used for IP addresses and network blocks—now sort roughly twice as fast thanks to a recently committed patch adding SortSupport. The feature works the same way it does for other large types like numeric or text: generate abbreviated keys that fit in the pointer-sized datum used during sorting, allowing most comparisons to happen in memory without fetching full values. That accelerates common operations like DISTINCT, ORDER BY, and CREATE INDEX.

What made this patch non-trivial is that network types have special ordering semantics unlike plain integer or text data. An abbreviated key must never falsely report inequality—it can sometimes report false equality (Postgres then falls back to authoritative comparison to break ties), but it must always respect the logical sort order.

Anatomy of Network Types

Both inet and cidr can hold either a single host address or an entire subnet. For example:

• 1.2.3.4/32 — a 32-bit netmask on an IPv4 value, defining exactly one address.
• 1.2.3.0/24 — a 24-bit netmask describing the network 1.2.3.*.
• 1.0.0.0/8 — an 8-bit netmask for the 1.* range.

Using 1.2.3.4/24 as an example, an address has three parts:

1. The network (bits covered by the netmask: 1.2.3.).
2. The netmask size (/24).
3. The subnet (bits outside the netmask: .4). Only inet allows non-zero subnet bits; in cidr they must be zero (e.g., 1.2.3.0/24).

Netmask sizes are not restricted to byte boundaries—any value between 0 and 32 is legal for IPv4. The binary layout matters, as the network is simply the most significant bits up to the netmask size.

Internally, Postgres uses a single C struct (inet.h) to represent both types:

/*
 * This is the internal storage format for IP addresses
 * (both INET and CIDR datatypes):
 */
typedef struct
{
    unsigned char family;      /* PGSQL_AF_INET or PGSQL_AF_INET6 */
    unsigned char bits;        /* number of bits in netmask */
    unsigned char ipaddr[16];  /* up to 128 bits of address */
} inet_struct;

How Network Values Sort

Postgres sorts inet/cidr values by these rules, in order:

1. All IPv4 addresses come before all IPv6 addresses.
2. Network bits are compared.
3. Netmask size is compared.
4. All bits are compared (effectively the subnet, since network bits are now known equal).

These bit-level rules can yield non-intuitive results. For instance, 192.0.0.0/1 sorts before 128.0.0.0/2 even though 192 is numerically larger. Comparing them involves examining only the common bits from both networks—min(/1, /2), i.e., one bit. That bit is 1 for both values (192 = 1100 0000, 128 = 1000 0000), so the comparison moves to netmask size. Since /2 is larger than /1, 128.0.0.0/2 is the greater value.

Designing an Abbreviated Key

Abbreviated keys must fit in the pointer-sized datum—32 or 64 bits depending on architecture. The goal is to pack as much sorting-relevant data as possible. The approach is to lay out the key with more significant bits reserved for higher-priority comparison rules, so two keys can be compared as plain integers—an extremely fast CPU operation.

Family Bit

The first rule is trivial: IPv4 always precedes IPv6. With only two families, a single most-significant bit suffices—0 for IPv4, 1 for IPv6.

This assumes only two IP families will ever exist. That's fine because abbreviated keys live only in memory during a sort; they are never persisted, so if a new family appears, a bit can be reallocated without format concerns.

Network Bits

The second comparison rule concerns network bits, so those go in next. But only the network portion may be included—not the full host address. Revisiting 192.0.0.0/1 vs. 128.0.0.0/2: if the key stored 192's full leading byte 1100 0000, comparing against 128's 1000 0000 would make 192 sort higher, violating the rule. Keys must truncate to just the network bits.

Both values would then appear as 1000 0000 in this part of the key, correctly indicating potential equality and deferring to authoritative comparison for the netmask-size tiebreak.

For most cases, this is all the space available. An IPv6 address is 128 bits, so after the 1 family bit, the remaining 31 or 63 bits (on 32-bit and 64-bit machines respectively) are entirely network. IPv4 is only 32 bits, but on a 32-bit machine there are still just 31 bits free—all used for network.

But on 64-bit machines with IPv4 there's room to spare. After storing the full 32 network bits (plus the family bit, that's 33), 31 bits remain.

Netmask Size and Subnet on 64-bit IPv4

With the first two sort rules already decided, comparison can safely advance to netmask size. The largest IPv4 netmask is 32, which fits in just 6 bits (32 = 10 0000).

That leaves 25 bits for the next rule: subnet bits. Subnets can theoretically span 32 bits (for /0), but truncation only matters for masks of /6 or smaller. For common sizes like /8, /16, or /24, the entire subnet fits.

With this, every sorting rule is covered in the key. For most real-world data, Postgres can sort using only abbreviated keys without falling back to full comparison. The final layout:

From encoding to implementation

With the encoding scheme mapped out, the next step is turning it into C code. The implementation relies heavily on bitwise operations — common in C, but something many of us who spend our days in higher-level languages don't handle as frequently.

The completed version lives in the Postgres source with extensive comments. Here's how it works, step by step.

Getting bytes into an integer

An IP component is stored as a 16-byte unsigned char array in the backing network type:

typedef struct
{
    ...
    unsigned char ipaddr[16];  /* up to 128 bits of address */
} inet_struct;

Since abbreviated keys will be compared as integers — a key reason they're fast — we first copy a datum's worth of bytes out of ipaddr using memcpy:

Datum ipaddr_datum;
memcpy(&ipaddr_datum, ip_addr(authoritative), sizeof(Datum));

ipaddr is arranged most significant byte first. That works for big-endian machines, but not for little-endian ones like most Intel processors. To fix this, perform a byte-wise position swap (the same approach used in uuid's abbreviated key implementation):

/* Must byteswap on little-endian machines */
ipaddr_datum = DatumBigEndianToNative(ipaddr_datum);

For IPv6, shift a 1 bit into the leftmost position so IPv6 values sort after all IPv4 values:

Datum res;
res = ((Datum) 1) << (SIZEOF_DATUM * BITS_PER_BYTE - 1);

Pulling out the network with a bitmask

The network component is extracted using bitmasking, a technique that applies a bitwise-AND to isolate a specific range of bits:

  1010 1010 1010 1010       (original value)
& 0000 1111 1111 0000       (bitmask)
  -------------------
  0000 1010 1010 0000       (final result)

The bitmask covers the subnet portion of the value — the part after the network — and its size depends on how many subnet bits are expected in ipaddr_datum. If the network occupies the full datum, the subnet bitmask is zero. Three conditionals handle the cases:

The first handles no network bits. The subnet bitmask should be all ones, achieved by starting at 0, subtracting 1, and letting the value roll over to its maximum:

Datum subnet_bitmask,
      network;

subnet_size = ip_maxbits(authoritative) - ip_bits(authoritative);
Assert(subnet_size >= 0);

if (ip_bits(authoritative) == 0)
{
    /* Fit as many ipaddr bits as possible into subnet */
    subnet_bitmask = ((Datum) 0) - 1;
    network = 0;
}

The second is the mixed case, with bits in both network and subnet. A trick yields the bitmask: shift a 1 left by the subnet size, then subtract one to fill the positions to the right with 1s:

  0000 0001 0000 0000       (1 << 8)
-                   1       (minus one)
  -------------------
  0000 0000 1111 1111       (8-bit mask)

To get the network value, AND the IP datum with the negated subnet bitmask (ipaddr_datum & ~subnet_bitmask):

else if (ip_bits(authoritative) < SIZEOF_DATUM * BITS_PER_BYTE)
{
    /* Split ipaddr bits between network and subnet */
    subnet_bitmask = (((Datum) 1) << subnet_size) - 1;
    network = ipaddr_datum & ~subnet_bitmask;
}

The final case has no subnet bits. network is set to the full value of ipaddr_datum:

else
{
    /* Fit as many ipaddr bits as possible into network */
    subnet_bitmask = 0;        /* Unused, but be tidy */
    network = ipaddr_datum;
}

Assembling the result: IPv4 on 64-bit

IPv4 on 64-bit is the most complex case because there's room for more information. The steps to shift the network and subnet bitmask into place:

1. network: Shift the network left 31 bits, making room for the netmask size and 25 bits of subnet.
2. network_size: Shift the network size left 25 bits to leave space for the subnet.
3. subnet: Extract a subnet using the bitmask calculated earlier.
4. subnet: If the subnet exceeds 25 bits, shift it down to just occupy 25 bits.
5. res: OR the values from steps 1, 2, and 4 to get the final result.

#if SIZEOF_DATUM == 8
    if (ip_family(authoritative) == PGSQL_AF_INET)
    {
        /*
         * IPv4 with 8 byte datums: keep all 32 netmasked bits, netmask size,
         * and most significant 25 subnet bits
         */
        Datum        netmask_size = (Datum) ip_bits(authoritative);
        Datum        subnet;

        /* Shift left 31 bits: 6 bits netmask size + 25 subnet bits */
        network <<= (ABBREV_BITS_INET4_NETMASK_SIZE +
                     ABBREV_BITS_INET4_SUBNET);

        /* Shift size to make room for subnet bits at the end */
        netmask_size <<= ABBREV_BITS_INET4_SUBNET;

        /* Extract subnet bits without shifting them */
        subnet = ipaddr_datum & subnet_bitmask;

        /*
         * If we have more than 25 subnet bits, we can't fit everything. Shift
         * subnet down to avoid clobbering bits that are only supposed to be
         * used for netmask_size.
         *
         * Discarding the least significant subnet bits like this is correct
         * because abbreviated comparisons that are resolved at the subnet
         * level must have had equal subnet sizes in order to get that far.
         */
        if (subnet_size > ABBREV_BITS_INET4_SUBNET)
            subnet >>= subnet_size - ABBREV_BITS_INET4_SUBNET;

        /*
         * Assemble the final abbreviated key without clobbering the ipfamily
         * bit that must remain a zero.
         */
        res |= network | netmask_size | subnet;
    }
    else
#endif

The simpler cases

The other three cases are straightforward: there's only room for network bits. Shift them right by 1 bit so they don't conflict with the previously set IP family, then OR with res:

#endif
    {
        /*
         * 4 byte datums, or IPv6 with 8 byte datums: Use as many of the
         * netmasked bits as will fit in final abbreviated key. Avoid
         * clobbering the ipfamily bit that was set earlier.
         */
        res |= network >> 1;
    }

Cost of complexity

This abbreviated key implementation is intricate enough that in most projects it would be a poor trade-off. The speed gain is nice, but there's a real price in ongoing maintenance and the burden placed on future contributors who must understand the code.

Postgres is different. It's a highly leveraged piece of software. This patch makes sorting and creating indexes on network types roughly twice as fast, and that improvement automatically reaches hundreds of thousands of installations worldwide when they upgrade to the next major version. If there's a place where added complexity for speed is justified, it's here: few must understand the code, but many reap its benefits. Extensive comments and test cases were added to keep future changes as manageable as possible.

Thanks to Peter Geoghegan for seeding the idea for this patch, plus advice and thorough testing and review, and Edmund Horner for review.