PostgreSQL's Geometric Type Implementation in C

PostgreSQL’s geometric types look like a grab bag: point, line, lseg, box, path, polygon, circle. Underneath they are not seven types at all. They are one 16-byte building block — a Point, two float8 values — assembled in a few predictable ways. Two of the seven are variable-length varlena objects, the other five are fixed-size. And the interesting C is in the three decisions that are invisible from SQL: a dummy int32 that exists purely for alignment, a bounding box cached inside the polygon, and a set of “fuzzy” comparisons that the source explicitly warns are not transitive.

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

The catalog: one type, seven faces

The type identity lives in src/include/catalog/pg_type.dat:

Two things stand out. Every geometric type is typbyval => f and typalign => 'd' (double), even point. That is not laziness: a by-value type on a 64-bit machine must be exactly sizeof(Datum) (8 bytes) or less, and every geometric type is at least 16 bytes. They cannot be by-value, so the code is written uniformly in terms of pointers — Point *, BOX *. The header in src/include/utils/geo_decls.h says as much: “Path and Polygon are toastable varlena types, the others are just fixed-size pass-by-reference types.”

The second thing: only path and polygon are variable-length (typlen => -1, typstorage => 'x'). The rest are fixed and will never be toasted.

The structs

Everything hangs off one definition (src/include/utils/geo_decls.h):

typedef struct
{
	float8		x,
				y;
} Point;

typedef struct
{
	Point		p[2];
} LSEG;

typedef struct
{
	float8		A,
				B,
				C;
} LINE;

typedef struct
{
	Point		high,
				low;			/* corner POINTs */
} BOX;

typedef struct
{
	Point		center;
	float8		radius;
} CIRCLE;

Point is 16 bytes; LSEG is two of them (32); BOX is two (32); LINE is three float8s (24); CIRCLE is a Point plus a radius (24). The two varlena types are the only ones with a header:

typedef struct
{
	int32		vl_len_;		/* varlena header (do not touch directly!) */
	int32		npts;
	int32		closed;			/* is this a closed polygon? */
	int32		dummy;			/* padding to make it double align */
	Point		p[FLEXIBLE_ARRAY_MEMBER];
} PATH;

typedef struct
{
	int32		vl_len_;		/* varlena header (do not touch directly!) */
	int32		npts;
	BOX			boundbox;
	Point		p[FLEXIBLE_ARRAY_MEMBER];
} POLYGON;

PATH has a dummy field that exists for exactly one reason, spelled out in its comment: “padding to make it double align.” Without it, the Point array would begin at offset 12 (after the 4-byte varlena header, npts, and closed), which is not 8-byte aligned, and the float8 loads inside every geometric operator would be misaligned. With it, the array starts at offset 16. POLYGON doesn’t need a dummy because vl_len_ (4) + npts (4) + boundbox (32) already puts p at offset 40.

You can see the alignment reasoning in the size calculation in path_in() (src/backend/utils/adt/geo_ops.c):

base_size = sizeof(path->p[0]) * npts;
size = offsetof(PATH, p) + base_size;
...
path = (PATH *) palloc(size);
SET_VARSIZE(path, size);
path->npts = npts;
...
path->dummy = 0;
/* prevent instability in unused pad bytes */

The bounding box inside the polygon

POLYGON carries a boundbox field that is not in the SQL input. It is computed once, by make_bound_box(), and then used as a fast reject for containment and overlap:

static void
make_bound_box(POLYGON *poly)
{
	int			i;
	float8		x1, y1, x2, y2;

	Assert(poly->npts > 0);

	x1 = x2 = poly->p[0].x;
	y2 = y1 = poly->p[0].y;
	for (i = 1; i < poly->npts; i++)
	{
		if (float8_lt(poly->p[i].x, x1)) x1 = poly->p[i].x;
		if (float8_gt(poly->p[i].x, x2)) x2 = poly->p[i].x;
		if (float8_lt(poly->p[i].y, y1)) y1 = poly->p[i].y;
		if (float8_gt(poly->p[i].y, y2)) y2 = poly->p[i].y;
	}

	poly->boundbox.low.x = x1;
	poly->boundbox.high.x = x2;
	poly->boundbox.low.y = y1;
	poly->boundbox.high.y = y2;
}

The cache is trusted on the way in but not on the way across the wire. The comment on poly_recv() explains the choice:

We recompute the bounding box on read, instead of trusting it to be valid. (Checking it would take just as long, so may as well omit it from external representation.)

So the binary send format for a polygon is just the point count and the points; the box is rebuilt on poly_recv(). That is a real trade-off: it makes the wire format smaller and removes a class of corruption bugs.

BOX gets the same treatment for its two corners. box_in() and box_recv() both sort the input so high is always the upper-right corner and low the lower-left:

/* reorder corners if necessary... */
if (float8_lt(box->high.x, box->low.x))
{
	x = box->high.x;
	box->high.x = box->low.x;
	box->low.x = x;
}

Sorting once means every later comparison (box_ov, box_contain_box, the rtree operator class) can assume the invariant.

Fuzzy comparisons, and a warning

The geometric types compare floating-point numbers “to a given accuracy” rather than exactly. From geo_decls.h:

#define EPSILON					1.0E-06

static inline bool
FPeq(double A, double B)
{
	return A == B || fabs(A - B) <= EPSILON;
}

The header comment is blunt about the consequences: “Beware of normal reasoning about the behavior of these comparisons, since for example FPeq does not behave transitively.” And point_eq_point() adds a NaN escape hatch — if either point is NaN it falls back to exact float8_eq:

static inline bool
point_eq_point(Point *pt1, Point *pt2)
{
	/* If any NaNs are involved, insist on exact equality */
	if (unlikely(isnan(pt1->x) || isnan(pt1->y) ||
				 isnan(pt2->x) || isnan(pt2->y)))
		return (float8_eq(pt1->x, pt2->x) && float8_eq(pt1->y, pt2->y));

	return (FPeq(pt1->x, pt2->x) && FPeq(pt1->y, pt2->y));
}

That matters because equality and ordering are not what you might expect. box_same() compares corners with point_eq_point, but box_lt() / box_gt() / box_eq() compare by area, not by coordinates:

Datum
box_lt(PG_FUNCTION_ARGS)
{
	BOX		   *box1 = PG_GETARG_BOX_P(0);
	BOX		   *box2 = PG_GETARG_BOX_P(1);

	PG_RETURN_BOOL(FPlt(box_ar(box1), box_ar(box2)));
}

Paths go further and compare by point count — the code’s own comment is “as stupid as that sounds” — while poly_same() uses plist_same(), which accepts any rotation or reversal of the vertex list. Seven types, seven different notions of equality.

Input and output

All the text parsing funnels through two helpers in geo_ops.c: pair_decode (a single (x,y)) and path_decode (a list of points with brackets or parens). The delimiters are macros:

#define LDELIM			'('
#define RDELIM			')'
#define DELIM			','
#define LDELIM_EP		'['
#define RDELIM_EP		']'
#define LDELIM_C		'<'
#define RDELIM_C		'>'
#define LDELIM_L		'{'
#define RDELIM_L		'}'

pair_count() counts commas and insists on an odd number, which is how it infers the number of points before allocating the varlena:

static int
pair_count(char *s, char delim)
{
	int			ndelim = 0;

	while ((s = strchr(s, delim)) != NULL)
	{
		ndelim++;
		s++;
	}
	return (ndelim % 2) ? ((ndelim + 1) / 2) : -1;
}

Output is the inverse: path_encode() with a path_delim enum chooses the surrounding bracket, and each point is written with float8out_internal(). box_out and point_out are one-liners that reuse it. The binary format is plain pq_sendfloat8 for fixed types, and closed + npts + points for path. line is the odd one out: its text form is {A,B,C} (the general equation Ax+By+C=0), but line_in() also accepts two points and converts them via line_construct().

Look at it yourself

The varlena sizes are directly observable with pg_column_size, which works on any type (octet_length accepts only string types):

SELECT pg_column_size('(1,2)'::point);            -- 16
SELECT pg_column_size('[(1,2),(3,4)]'::lseg);     -- 32
SELECT pg_column_size('((0,0),(2,0),(2,2),(0,2))'::polygon);  -- 104

That last one is offsetof(POLYGON, p) (40) + 4 points × 16 = 104 bytes. The cached box is not shown by the output function, but it is exposed through the box(polygon) cast:

SELECT box('((0,0),(2,0),(2,2),(0,2))'::polygon);
--  (2,2),(0,0)

SELECT '((0,0),(2,0),(2,2),(0,2))'::polygon = '((2,0),(2,2),(0,2),(0,0))'::polygon;
--  true   (rotation is allowed by plist_same)

The C side of the cast is poly_box() (src/backend/utils/adt/geo_ops.c), which simply returns *box = poly->boundbox. The rotation-equality is plist_same(), which walks the two vertex lists forward and backward.

What it all means

• The geometric types are a family built from a 16-byte Point; the C structs are trivial, and the design lives in the catalog flags and the operators.
• Every geometric type is by-reference because none fits in a Datum; the code is written uniformly around pointers.
• PATH’s dummy field is pure alignment padding; POLYGON needs none because its bounding box lands on an 8-byte boundary.
• POLYGON caches a bounding box but recomputes it on binary receive, so the wire format stays small and cannot carry a stale box.
• BOX sorts its corners on input so comparisons can assume an invariant.
• Geometric equality is fuzzy (EPSILON = 1e-6) and not transitive, and different types order by different criteria — area for boxes, point count for paths, cyclic order for polygons.

Further reading

• src/include/utils/geo_decls.h — the Point and struct definitions, the EPSILON fuzzy comparisons, and the DatumGet* accessors.
• src/backend/utils/adt/geo_ops.c — every operator: path_in, poly_in, make_bound_box, box_construct, plist_same, path_decode.
• src/include/catalog/pg_type.dat — the typlen / typbyval / typalign entries for oids 600–604, 628, and 718.