PostgreSQL's bit and varbit Implementation in C

In SQL, bit(4) and bit varying(4) look like different animals: one has a fixed width, the other does not. In PostgreSQL they are the same type underneath. The same struct, the same I/O routines, the same comparison functions, the same catalog-provided C symbol for output. The only things that differ are the meaning of the type modifier and one line of arithmetic in the input function.

There is also a storage-layout invariant that is easy to miss but explains a lot of the code: the low-order padding bits of the final byte must be zero, and the whole design leans on that guarantee.

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

The struct

From src/include/utils/varbit.h:

c
typedef struct
{
	int32		vl_len_;		/* varlena header (do not touch directly!) */
	int32		bit_len;		/* number of valid bits */
	uint8		bit_dat[FLEXIBLE_ARRAY_MEMBER]; /* bit string, most sig. byte
												 * first */
} VarBit;

A varlena header, then a length in bits, then the bytes. The header comment is worth quoting because it is the invariant the rest of the file depends on:

Caution: if bit_len is not a multiple of BITS_PER_BYTE, the low-order bits of the last byte of bit_dat[] are unused and MUST be zeroes. (This allows bit_cmp() to not bother masking the last byte.) Also, there should not be any excess bytes counted in the header length.

So the datum carries two lengths. VARSIZE gives the number of bytes; bit_len gives the number of valid bits. The difference is the padding:

c
#define VARBITHDRSZ			sizeof(int32)
#define VARBITLEN(PTR)		(((VarBit *) (PTR))->bit_len)
#define VARBITS(PTR)		(((VarBit *) (PTR))->bit_dat)
#define VARBITBYTES(PTR)	(VARSIZE(PTR) - VARHDRSZ - VARBITHDRSZ)
#define VARBITPAD(PTR)		(VARBITBYTES(PTR)*BITS_PER_BYTE - VARBITLEN(PTR))
#define VARBITTOTALLEN(BITLEN)	(((BITLEN) + BITS_PER_BYTE-1)/BITS_PER_BYTE + \
								 VARHDRSZ + VARBITHDRSZ)
#define VARBITMAXLEN		(INT_MAX - BITS_PER_BYTE + 1)

VARBITTOTALLEN is the allocation formula: ceil(bits / 8) data bytes plus VARHDRSZ (4) plus VARBITHDRSZ (4). Even a bit(1) has an 8-byte overhead before its single data byte. VARBITMAXLEN is INT_MAX - 7, chosen so that the largest internal computation, bitlen + BITS_PER_BYTE - 1, cannot overflow an int32.

Catalog identity

From src/include/catalog/pg_type.dat:

Type	OID	Array OID	`typlen`	`typbyval`	`typalign`	`typstorage`	`typcategory`
`bit`	1560	1561	-1	f	`i`	`x`	`V`
`varbit`	1562	1563	-1	f	`i`	`x`	`V`

The important row is typlen => '-1'. bit(n) is not a fixed-length type, no matter how fixed its width looks. It is a varlena, and typstorage => 'x' (EXTENDED) means it is fully toastable: a large bit value can be compressed and moved out of line. That is a genuine difference from SQL char(n), which is a fixed-length, inline, space-padded type.

varbit carries typispreferred => 't' in category V; bit does not, so an unadorned literal prefers bit varying. Both take a type modifier, via typmodin => 'bittypmodin' / 'varbittypmodin'.

What the bytes look like

text
bit(4) datum '1010', stored short:
+--------+----------------+---------------+--------+
| 1-byte | bit_len = 4    | bit_dat[0]    | (pad)  |
| header | (int32)        | 1010 0000     |        |
+--------+----------------+---------------+--------+
   total: 6 bytes (9 bytes before the short-header conversion)

The bits are stored most-significant-bit-first within each byte, and the string runs from the beginning of bit_dat. '1010' becomes the byte 0b10100000: four significant bits, four zero padding bits.

Input and output

bit_in() and varbit_in() are near-duplicates, and the difference between them is the whole semantic distinction between the types. The parsing prefix is shared:

c
if (input_string[0] == 'b' || input_string[0] == 'B')
{
	bit_not_hex = true;
	sp = input_string + 1;
}
else if (input_string[0] == 'x' || input_string[0] == 'X')
{
	bit_not_hex = false;
	sp = input_string + 1;
}
else
{
	/* Otherwise it's binary. */
	bit_not_hex = true;
	sp = input_string;
}

So B'1010', X'1a', and a bare '1010' are all accepted; the bare form is binary, which is what makes cast('1001' as bit) work.

The divergence comes next. For bit, the type modifier is an exact length:

c
if (atttypmod <= 0)
	atttypmod = bitlen;
else if (bitlen != atttypmod)
	ereturn(escontext, (Datum) 0,
			(errcode(ERRCODE_STRING_DATA_LENGTH_MISMATCH),
			 errmsg("bit string length %d does not match type bit(%d)",
					bitlen, atttypmod)));

For varbit, it is a maximum:

c
else if (bitlen > atttypmod)
	ereturn(escontext, (Datum) 0,
			(errcode(ERRCODE_STRING_DATA_RIGHT_TRUNCATION),
			 errmsg("bit string too long for type bit varying(%d)",
					atttypmod)));

Note that bit errors on a mismatch (too short or too long), while varbit errors only on too long. And note the subtlety that an exact-length bit still stores atttypmod as its bit_len even when the input had the same number of bits — the datum’s length is the column’s declared width.

Casting is deliberately more forgiving than input. The bit() function has an isExplicit argument: an implicit cast raises an error on a length mismatch, but an explicit cast “silently truncate[s] or zero-pad[s]” to the requested length. So '1'::bit(1)::bit(4) is 1000, while assigning '1'::bit(1) to a bit(4) column is an error.

Output has a nice detail. bit_out() is not its own implementation:

c
Datum
bit_out(PG_FUNCTION_ARGS)
{
#if 1
	/* same as varbit output */
	return varbit_out(fcinfo);
#else
	...
#endif
}

The #else branch holds a complete, working hex-output formatter that is compiled out — kept, per its comment, “in case someone wants to write a formatting function”. varbit_out() itself walks the bytes printing 1 and 0, with a separate loop for the final partial byte so it prints exactly bit_len characters. It also carries an XXX comment noting that varbit_recv() and hex input can load values the bit-oriented output cannot round-trip.

The padding invariant, and who has to maintain it

VARBIT_PAD is the enforcement macro:

c
#define VARBIT_PAD(vb) \
	do { \
		int32	pad_ = VARBITPAD(vb); \
		Assert(pad_ >= 0 && pad_ < BITS_PER_BYTE); \
		if (pad_ > 0) \
			*(VARBITS(vb) + VARBITBYTES(vb) - 1) &= BITMASK << pad_; \
	} while (0)

Any function that can produce non-zero padding bits must call it. The clearest example is bitnot():

c
for (size_t i = 0; i < nbytes; i++)
	r[i] = ~p[i];

/* Must zero-pad the result, because extra bits are surely 1's here */
VARBIT_PAD(result);

bit_and, bit_or, and bitxor do not need to pad, and each says so: “of 0 pads is 0”. bitfromint4 and bitfromint8 build their results carefully for the same reason, and varbit_recv() pads after copying bytes off the wire because the sender’s padding is not trusted. The invariant is checked under USE_ASSERT_CHECKING by VARBIT_CORRECTLY_PADDED, which is invoked at the top of the output function.

The payoff is in comparison:

c
static int32
bit_cmp(VarBit *arg1, VarBit *arg2)
{
	...
	cmp = memcmp(VARBITS(arg1), VARBITS(arg2), Min(bytelen1, bytelen2));
	if (cmp == 0)
	{
		bitlen1 = VARBITLEN(arg1);
		bitlen2 = VARBITLEN(arg2);
		if (bitlen1 != bitlen2)
			cmp = (bitlen1 < bitlen2) ? -1 : 1;
	}
	return cmp;
}

Because padding is guaranteed zero, bit_cmp is a plain memcmp over the common prefix with no masking, and then a tiebreak on the bit length. That tiebreak is what the comment above the comparison operators warns about: the standard “is not unambiguous about the comparison between zero-padded bit strings and varying bitstrings”, and PostgreSQL deliberately treats extra zero bits as making a string larger. '10' and '1000' compare unequal even though their integer values would be equal.

biteq() and bitne() add a fast path that compares bit_len before doing any byte comparison, so equal-length values — the common case in a bit(n) column — short-circuit to bit_cmp.

Operations

The bitwise operators are byte loops over VARBITBYTES, with a length check first (cannot AND bit strings of different sizes). Shifts are more involved: bitshiftleft() and bitshiftright() split the shift into a whole-byte part and a sub-byte part, use memcpy/MemSet when the sub-byte part is zero, and shift bit-by-bit otherwise. A negative shift delegates to the opposite direction, with a guard against INT_MIN negation. Right shift has to re-pad, since it can shift one-bits into the padding (VARBIT_PAD_LAST).

bit_count() (C name bit_bit_count) is a single call:

c
PG_RETURN_INT64(pg_popcount((char *) VARBITS(arg), VARBITBYTES(arg)));

Conveniently, the padding bits are zero, so they contribute nothing to the population count — no masking needed. get_bit/set_bit (C names bitgetbit / bitsetbit) index from the left in zero-based fashion, “inconsistent with the standard substring, position, overlay functions” per the comment.

One thing that is missing

Index support for varbit is narrower than you might expect. In src/include/catalog/pg_opclass.dat the only opclasses are btree/varbit_ops and brin/varbit_minmax_ops. There is no hash opclass, and no GiST or SP-GiST opclass. You can btree-index a bit string and you can BRIN-index it by min/max, but you cannot hash-index it.

Look at it yourself

sql
-- bit and varbit are the same representation
SELECT '1010'::bit(4), '1010'::varbit, 'x1a'::varbit;   -- 1010 | 1010 | 00011010

-- bit length vs byte length
SELECT length('1010'::varbit),        -- 4  (VARBITLEN)
       octet_length('1010'::varbit);  -- 1  (VARBITBYTES)

-- explicit casts pad, implicit ones do not
SELECT '1'::bit(1)::bit(4);           -- 1000

-- population count ignores the zero padding
SELECT bit_count(B'10101010');        -- 4

-- zero-based, left-to-right bit access
SELECT get_bit('1010'::bit(4), 0),    -- 1
       get_bit('1010'::bit(4), 3);    -- 0

-- varlena storage: 8 bytes of overhead plus the data, shortened on disk
CREATE TEMP TABLE b (x bit(4), y varbit);
INSERT INTO b VALUES ('1010', '1010');
SELECT pg_column_size(x), pg_column_size(y) FROM b;  -- 6, 6

-- btree and BRIN exist; this narrower query returns zero rows
SELECT c.opcname, a.amname
FROM pg_opclass c JOIN pg_am a ON a.oid = c.opcmethod
WHERE c.opcintype = 'varbit'::regtype AND a.amname = 'hash';

Key takeaways

bit and varbit share one VarBit struct: a varlena header, an int32 bit count, and the bytes.
bit(n) is stored as a varlena (typlen = -1) and is fully toastable (typstorage = 'x'); the width is enforced by the type modifier, not the layout.
The only real difference between the two types is that bit’s modifier is an exact length and varbit’s is a maximum — one branch in the input function.
The unused low bits of the last byte are required to be zero; that lets bit_cmp use memcmp without masking, and bit_count use pg_popcount without masking.
bit/varbit support btree and BRIN min/max indexes, but there is no hash opclass.