PostgreSQL's Range Type Implementation in C

A range type is one of PostgreSQL’s stranger storage formats. It is a variable-length value, but its first four bytes are not a payload — they are the length of the whole thing, then four more bytes holding the range type’s own OID, then up to two bound values stored inline, and finally a single flags byte at the very end. There is no length prefix per bound, no padding before the lower bound, and no separate “empty” representation. The whole format is documented in a comment at the top of rangetypes.c, and it is worth reading before you ever hex-dump one.

This is a walk through the layout and the canonicalization, based on reading the PostgreSQL source (commit e75fcc9867f).

The catalog and the subtype table

The six built-in range types live in src/include/catalog/pg_type.dat:

They are all typlen => -1, typbyval => f, typtype => 'r', typcategory => 'R', and typstorage => 'x'. typalign is copied from the subtype — that is why int4range and numrange are 4-byte aligned while tsrange and int8range are 8-byte aligned.

The relationship between a range and its element type is not inferred; it is recorded in src/include/catalog/pg_range.dat:

{ rngtypid => 'int4range', rngsubtype => 'int4',
  rngmultitypid => 'int4multirange', rngsubopc => 'btree/int4_ops',
  rngconstruct2 => 'int4range(int4,int4)',
  rngconstruct3 => 'int4range(int4,int4,text)',
  ...
  rngcanonical => 'int4range_canonical', rngsubdiff => 'int4range_subdiff' },

That last pair of fields is the heart of the type. rngcanonical points at a per-type canonicalization function, and only three of the six have one: int4range, int8range, and daterange. The continuous types — numrange, tsrange, tstzrange — have rngcanonical => '-'. That single difference is why int4range(1,5,'(]') comes back as [2,6) while numrange(1,5,'(]') stays (1,5].

At runtime all of this is cached in a TypeCacheEntry (src/include/utils/typcache.h) with the fields rngelemtype, rng_collation, rng_cmp_proc_finfo, rng_canonical_finfo, and rng_subdiff_finfo. The I/O functions cache theirs in fn_extra as a RangeIOData.

The on-disk struct

RangeType is declared in src/include/utils/rangetypes.h:

typedef struct
{
	int32		vl_len_;		/* varlena header (do not touch directly!) */
	Oid			rangetypid;		/* range type's own OID */
	/* Following the OID are zero to two bound values, then a flags byte */
} RangeType;

Eight bytes. The bounds are not named fields — they are variable-length trailing data whose position is computed from the flags. The flags byte is the last byte of the object:

#define RANGE_EMPTY			0x01	/* range is empty */
#define RANGE_LB_INC		0x02	/* lower bound is inclusive */
#define RANGE_UB_INC		0x04	/* upper bound is inclusive */
#define RANGE_LB_INF		0x08	/* lower bound is -infinity */
#define RANGE_UB_INF		0x10	/* upper bound is +infinity */
#define RANGE_LB_NULL		0x20	/* lower bound is null (NOT USED) */
#define RANGE_UB_NULL		0x40	/* upper bound is null (NOT USED) */
#define RANGE_CONTAIN_EMPTY 0x80	/* marks a GiST internal-page entry whose
									 * subtree contains some empty ranges */

The two RANGE_*_NULL bits are defined but never used; a NULL bound is instead represented as an infinity, which is why int4range(NULL,5) and '(,5]'::int4range are the same value. RANGE_CONTAIN_EMPTY is a GiST-only optimization bit, not part of a user value.

Serialization: bounds inline, flags last

range_serialize() is the function that turns two RangeBound structs into bytes. It first validates, then measures, then writes. The header comment on the file states the layout and the alignment trick:

4 bytes: varlena header 4 bytes: range type’s OID Lower boundary value, if any, aligned according to subtype’s typalign Upper boundary value, if any, aligned according to subtype’s typalign 1 byte for flags

This representation is chosen to avoid needing any padding before the lower boundary value, even when it requires double alignment. We can expect that the varlena header is presented to us on a suitably aligned boundary (possibly after detoasting), and then the lower boundary is too.

The code asserts exactly that — sizeof(RangeType) is 8 and MAXALIGN(sizeof(RangeType)) is 8:

/* Count space for varlena header and range type's OID */
msize = sizeof(RangeType);
Assert(msize == MAXALIGN(msize));

/* Count space for bounds */
if (RANGE_HAS_LBOUND(flags))
{
	if (typlen == -1)
		lower->val = PointerGetDatum(PG_DETOAST_DATUM_PACKED(lower->val));
	msize = datum_compute_size(msize, lower->val, typbyval, typalign,
							   typlen, typstorage);
}
...
/* Add space for flag byte */
msize += sizeof(char);

/* Note: zero-fill is required here, just as in heap tuples */
range = (RangeType *) palloc0(msize);
SET_VARSIZE(range, msize);
range->rangetypid = typcache->type_id;

ptr = (char *) (range + 1);
... /* write lower, then upper */
*((char *) ptr) = flags;

datum_compute_size() and datum_write() are deliberately modeled on heap_compute_data_size() and heap_fill_tuple() from heaptuple.c, and they implement the same alignment and short-varlena rules. Two details are worth pulling out:

• A range can never contain a TOAST pointer. datum_write() throws cannot store a toast pointer inside a range if it sees VARATT_IS_EXTERNAL. The caller detoasts first, so compression is applied to the whole range object rather than to individual bounds.
• Short varlenas are packed. If the subtype is packable (TYPE_IS_PACKABLE(typlen, typstorage)) and the bound fits, the bound is written with a 1-byte header and no alignment padding, exactly as a text column would be. numeric’s typstorage is 'm', so numrange bounds qualify.

Deserialization: flags first, then bounds

range_deserialize() is the mirror image. It reads the flags byte from the last byte, because that is cheaper than trying to know the bounds’ size first:

/* fetch the flag byte from datum's last byte */
flags = *((const char *) range + VARSIZE(range) - 1);

/* initialize data pointer just after the range OID */
ptr = (const char *) (range + 1);

/* fetch lower bound, if any */
if (RANGE_HAS_LBOUND(flags))
{
	lbound = fetch_att(ptr, typbyval, typlen);
	ptr = att_addlength_pointer(ptr, typlen, ptr);
}

/* fetch upper bound, if any */
if (RANGE_HAS_UBOUND(flags))
{
	ptr = (char *) att_align_pointer(ptr, typalign, typlen, ptr);
	ubound = fetch_att(ptr, typbyval, typlen);
}

For by-reference element types the Datums returned are pointers into the range object — the header warns about this explicitly. range_get_flags() is a one-liner used by the GiST code that only needs the flags.

Input, output, and canonicalization

Text input goes through range_parse() and range_parse_bound(). It accepts the literal empty (case-insensitive), [ / ( for the lower bound, ] / ) for the upper, and per-bound quoting and backslash escaping. An empty bound string becomes an infinity; a quoted empty string is the literal empty value. Output is the inverse in range_deparse() / range_bound_escape().

range_in() then hands each bound string to the subtype’s input function via InputFunctionCallSafe, builds two RangeBounds, and calls make_range(). make_range() is the public entry point: it calls range_serialize() and then, if the type has a canonicalization function, invokes it:

range = range_serialize(typcache, lower, upper, empty, escontext);
...
if (OidIsValid(typcache->rng_canonical_finfo.fn_oid) &&
	!RangeIsEmpty(range))
{
	...
	result = FunctionCallInvoke(fcinfo);
	...
	range = DatumGetRangeTypeP(result);
}

For the discrete types the canonical function shifts an exclusive bound to the adjacent inclusive integer. int4range_canonical():

if (!lower.infinite && !lower.inclusive)
{
	int32		bnd = DatumGetInt32(lower.val);

	if (unlikely(bnd == PG_INT32_MAX))
		ereturn(escontext, (Datum) 0,
				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
				 errmsg("integer out of range")));
	lower.val = Int32GetDatum(bnd + 1);
	lower.inclusive = true;
}

if (!upper.infinite && upper.inclusive)
{
	int32		bnd = DatumGetInt32(upper.val);

	if (unlikely(bnd == PG_INT32_MAX))
		ereturn(escontext, (Datum) 0,
				(errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
				 errmsg("integer out of range")));
	upper.val = Int32GetDatum(bnd + 1);
	upper.inclusive = false;
}

So [1,5] becomes [1,6), (1,5) becomes [2,5), and (1,5)’s left-neighbour int4range(1,5,'(]') becomes [2,6). daterange_canonical() does the same with a DateADT increment and a validity check. The continuous types have no such function, which is exactly why their bounds are not rewritten.

Comparison is range_cmp_bounds(). It handles infinities without calling the subtype’s comparison function, and when two finite bounds compare equal it refines the answer using the inclusive/exclusive flags. range_compare() is the qsort comparator used for sorting range values.

The binary format is a different animal

The text and storage layouts above are for range_send() and the heap. The wire format used by range_send() / range_recv() is simpler and does not store the range OID or the bounds inline: it writes the flags byte first, then each bound as a 4-byte length followed by the subtype’s binary encoding:

pq_sendbyte(&buf, flags);

if (RANGE_HAS_LBOUND(flags))
{
	bytea	   *bound = SendFunctionCall(&cache->typioproc, lower.val);
	uint32		bound_len = VARSIZE(bound) - VARHDRSZ;

	pq_sendint32(&buf, bound_len);
	pq_sendbytes(&buf, bound_data, bound_len);
}

This is the same convention used by record types. Note also the defensive mask in range_recv() that strips the unused RANGE_*_NULL bits before decoding.

Statistics: a histogram of bounds

Because a range has two bounds, ANALYZE cannot use the ordinary scalar histogram. range_typanalyze() (in src/backend/utils/adt/rangetypes_typanalyze.c) builds a combined histogram whose entries are ranges formed from the sorted lower bounds and the sorted upper bounds, plus a separate empty-range fraction. The selectivity code in rangetypes_selfuncs.c reads that empty fraction first and merges it with the histogram estimate; for operators like @> it knows an empty range is contained by everything, while for < it matches nothing.

Look at it yourself

The sizes are observable with pg_column_size, which works on any type (octet_length accepts only string types), and they reveal the layout. For a 17-byte int4range the flags byte is the last byte:

SELECT pg_column_size(int4range(1,5));              -- 17
SELECT pg_column_size(int8range(1,5));              -- 25
SELECT pg_column_size(daterange('2020-01-01','2020-12-31'));  -- 17
SELECT pg_column_size(tsrange('2020-01-01','2020-12-31'));    -- 25
SELECT pg_column_size('empty'::int4range);          -- 9

That is sizeof(RangeType) (8) + the two bounds + one flags byte. Canonicalization is visible directly:

SELECT int4range(1,5,'(]');   -- [2,6)
SELECT int4range(1,5,'[]');   -- [1,6)
SELECT numrange(1,5,'(]');    -- (1,5]     -- no canonicalization
SELECT daterange('2020-01-01','2020-12-31','[]');  -- [2020-01-01,2021-01-01)

The empty range is not NULL and not a zero-length value; it is a real 9-byte object whose flags byte has RANGE_EMPTY set and whose two bounds are absent.

What it all means

• A range is a varlena: 4-byte length, 4-byte type OID, up to two inline bounds, one trailing flags byte.
• The bounds are stored using the subtype’s typalign and the same short-varlena rules as heap columns; a range can never hold a TOAST pointer.
• The flags byte is read from the last byte, which is why the format puts it last and why there is no per-bound length.
• Discrete types (int4, int8, date) canonicalize exclusive bounds to adjacent integers; the continuous types do not. That one catalog field, rngcanonical, is the whole difference.
• Comparison refines equal finite bounds by their inclusive/exclusive flags.
• ANALYZE builds a bounds histogram plus an empty fraction, and the selectivity functions special-case empty ranges.

Further reading

• src/backend/utils/adt/rangetypes.c — the layout comment, range_serialize, range_deserialize, range_in, range_cmp_bounds, and the canonical functions.
• src/include/utils/rangetypes.h — the RangeType struct, the flags, and the prototypes.
• src/include/catalog/pg_range.dat — the subtype, canonicalization, and subdiff mapping for each range type.
• src/backend/utils/adt/rangetypes_typanalyze.c — the bounds histogram and empty-fraction statistics.
• src/backend/utils/adt/rangetypes_selfuncs.c — range selectivity estimation.