PostgreSQL's Multirange Type Implementation in C

A multirange is what you get when you let a range type hold more than one range: int4multirange can be {[1,5),[10,20)}. The surprising thing is how little C there is to it. All six built-in multirange types — int4multirange, int8multirange, nummultirange, tsmultirange, tstzmultirange, datemultirange — are implemented by one set of functions in src/backend/utils/adt/multirangetypes.c. The only thing that varies is the element type, and even that is not compiled in; it is looked up at runtime.

This is a walk through the stored layout, based on reading the PostgreSQL source (version 20devel, commit e75fcc9867f).

The catalog

The six concrete multirange types live in src/include/catalog/pg_type.dat:

They are all typlen => -1 (varlena), typbyval => f, typtype => 'm', typcategory => 'R', and typstorage => 'x' (fully toastable). typalign is copied from the element type, which is why the integer and date multiranges are 4-byte aligned while the timestamp and bigint ones are 8-byte aligned. The element mapping is recorded in src/include/catalog/pg_range.dat as rngmultitypid, alongside the range constructor functions (rngmltconstruct0/1/2).

There is no seventh concrete type. The oid 4537 in the neighborhood is anymultirange, a typtype => 'p' pseudo-type used for polymorphic functions — not a value you can store.

The in-memory struct

MultirangeType is declared in src/include/utils/multirangetypes.h:

typedef struct
{
	int32		vl_len_;		/* varlena header (do not touch directly!) */
	Oid			multirangetypid;	/* multirange type's own OID */
	uint32		rangeCount;		/* the number of ranges */

	/*
	 * Following the count are the range objects themselves, as ShortRangeType
	 * structs. Note that ranges are varlena too, depending on whether they
	 * have lower/upper bounds and because even their base types can be
	 * varlena. So we can't really index into this list.
	 */
} MultirangeType;

Twelve bytes. The “ShortRangeType structs” are not a real struct — they are just the bound values and a flags byte, appended after the header. Because the bounds can be variable length, you cannot index into the array directly; you have to walk it. That constraint shapes the entire format.

The stored format

The file’s header comment states the layout, and it is worth reading verbatim:

12 bytes: MultirangeType struct including varlena header, multirange
          type's OID and the number of ranges in the multirange.
4 * (rangesCount - 1) bytes: 32-bit items pointing to the each range
                              in the multirange starting from the second one.
1 * rangesCount bytes : 8-bit flags for each range in the multirange
The rest of the multirange are range bound values pointed by multirange items.

So after the 12-byte header comes an array of (rangeCount - 1) 32-bit items (the first range starts at offset zero and needs no item), then rangeCount one-byte flags, then the aligned bound values. The clever part is what goes in the items:

#define MULTIRANGE_ITEM_OFF_BIT 0x80000000
#define MULTIRANGE_ITEM_GET_OFFLEN(item) ((item) & 0x7FFFFFFF)
#define MULTIRANGE_ITEM_HAS_OFF(item) ((item) & MULTIRANGE_ITEM_OFF_BIT)
#define MULTIRANGE_ITEM_OFFSET_STRIDE 4

Most items store a length, which makes them small and therefore compression-friendly. Every fourth item (i % 4 == 0) instead stores an absolute offset with the high bit set. That gives you a cheap “jump point” every four ranges while keeping the common case tiny. write_multirange_data() shows the encoding:

items[i - 1] = ptr - begin;
if ((i % MULTIRANGE_ITEM_OFFSET_STRIDE) != 0)
	items[i - 1] -= prev_offset;	/* a length */
else
	items[i - 1] |= MULTIRANGE_ITEM_OFF_BIT;	/* an absolute offset */
prev_offset = ptr - begin;

Canonicalization: sort and merge on the way in

make_multirange() is the single entry point every constructor calls. Its first act is multirange_canonicalize(), which sorts the incoming ranges and merges any that touch:

if (range_adjacent_internal(rangetyp, lastRange, currentRange))
{
	ranges[output_range_count - 1] = lastRange =
		range_union_internal(rangetyp, lastRange, currentRange, false);
}

The result is canonical: ranges are stored in order, non-overlapping, and never adjacent. That is why int4multirange(int4range(1,5), int4range(5,10)) and int4multirange(int4range(1,10)) are the same value — and why equality can be a straight range-by-range comparison. Note that empty ranges are dropped entirely; a multirange can never contain an empty range. It just stores zero ranges and reports MultirangeIsEmpty(mr) as mr->rangeCount == 0.

Reading a range back out

multirange_get_bounds() is the workhorse. It computes the offset by summing lengths until it hits an offset item:

while (i > 0)
{
	offset += MULTIRANGE_ITEM_GET_OFFLEN(items[i - 1]);
	if (MULTIRANGE_ITEM_HAS_OFF(items[i - 1]))
		break;
	i--;
}

Then it walks the bound values using the element type’s typlen/typalign and returns a RangeBound for each side, reading the flags byte to fill in inclusive/infinite state. multirange_get_range() is the same walk but with the bound bytes copied into a freshly allocated RangeType. The fast path is deliberately cheaper: it avoids constructing a whole range when only the bounds are wanted.

The binary wire format is a different animal. multirange_send() writes an int32 range count, then for each range an int32 length followed by that range’s binary encoding; multirange_recv() mirrors it. It stores neither the multirange OID nor the compact item array.

Comparison and hashing

multirange_cmp() is the btree comparator. It walks the two multiranges range by range and compares lower then upper bounds; a shorter multirange is treated as if padded with empty ranges at the end, so it sorts first:

if (i >= range_count_1)
{
	cmp = -1;
	break;
}

multirange_eq_internal() is a bound-by-bound loop, and equality of the OIDs is asserted up front. Hashing is hash_multirange(): each range’s flags and bounds are hashed through the element type’s hash function, then folded together:

range_hash = hash_bytes_uint32((uint32) flags);
range_hash ^= lower_hash;
range_hash = pg_rotate_left32(range_hash, 1);
range_hash ^= upper_hash;
result = (result << 5) - result + range_hash;

That (result << 5) - result trick is the same one hash_array uses to combine elements. There is also a hash_multirange_extended() for 64-bit, seeded hashing.

Look at it yourself

The sizes follow directly from the layout. An empty int4multirange is just the 12-byte header; adding a range adds one flags byte plus the aligned bounds:

SELECT octet_length('{}'::int4multirange);                      -- 12
SELECT octet_length('{[1,5)}'::int4multirange);                 -- 24
SELECT octet_length('{[1,5),[10,20)}'::int4multirange);         -- 36

Canonicalization and unnest are visible too:

SELECT '{[1,5),[5,10)}'::int4multirange;       -- {[1,10)}
SELECT unnest('{[1,5),[10,20)}'::int4multirange);
--  int4range
-- ----------
--  [1,5)
--  [10,20)

The multirange family is supported by btree/multirange_ops, hash/multirange_ops, and gist/multirange_ops (see pg_amproc.dat), so you can put a multirange in an index or a hash join.

What it all means

• A multirange is a varlena with a 12-byte header, a compact item array, a flags array, and aligned bound values.
• The items store lengths by default and absolute offsets every fourth entry, which is what makes the format cheap to compress and cheap to seek into.
• make_multirange() canonicalizes: sort, drop empties, merge touching ranges. The stored form is canonical, which is why equality is a simple comparison.
• All six types share one implementation; only the element type, and therefore the alignment and the element hash/compare functions, differs.
• The wire format is not the storage format — send/recv use a flat length-prefixed list of range encodings.

Further reading

• src/backend/utils/adt/multirangetypes.c — the layout comment, multirange_canonicalize, make_multirange, write_multirange_data, multirange_get_bounds, multirange_cmp, and hash_multirange.
• src/include/utils/multirangetypes.h — the MultirangeType struct and the DatumGetMultirangeTypeP / PG_GETARG_MULTIRANGE_P macros.
• src/include/utils/rangetypes.h — the RangeType layout and the range flags that the multirange format reuses.
• src/include/catalog/pg_range.dat — the rngmultitypid and rngmltconstruct* mapping from each range type to its multirange.
• src/include/catalog/pg_amproc.dat — the btree, hash, and GiST support functions.