On reordering expressions in Postgres

From time to time, I come across queries with complex filters like this:

SELECT * FROM table
WHERE
 date > min_date AND
 date < now() - interval '1 day' AND
 value IN Subplan AND
 id = 42;

And in real life, just changing the order of these conditions can noticeably improve performance. Why? Individually, each condition is cheap. But when you're applying them to millions of rows, that "cheap" quickly adds up. Especially once you've dealt with the usual suspects — like making sure the table fits into shared buffers.

This effect is easiest to spot in wide tables — the kind with dozens of variable-length columns. I sometimes see sluggish IndexScans, and when you dig in, it turns out the performance hit comes from filtering on a column that's the 20th field in the tuple. Just figuring out the offset of that column takes CPU time.

Looking at Postgres source code, it’s clear the community thought about this long ago. Back in 2002, Tom Lane reluctantly committed 3779f7f, which added a basic reordering of expressions (see order_qual_clauses) to push subplans to the end of the list. That made sense — subplans can depend on runtime parameters and are generally expensive to evaluate.

Later, in 2007, commit 5a7471c changed the logic. From that point on, expressions were ordered strictly by their estimated cost. This still holds today, with a small tweak from 215b43c for row-level security (RLS), where evaluation order needed more control within each plan node.

Let’s see what we get in upstream Postgres right now:

CREATE TABLE test (
  x integer, y numeric, w timestamp DEFAULT CURRENT_TIMESTAMP, z integer
);
INSERT INTO test (x, y) SELECT gs, gs FROM generate_series(1, 1E3) AS gs;
VACUUM ANALYZE test;

EXPLAIN (COSTS ON)
SELECT * FROM test
WHERE
 z > 0 AND
 w > now() AND
 x < (SELECT avg(y) FROM generate_series(1,1E2) y WHERE y % 2 = x % 3) AND
 x NOT IN (SELECT avg(y) FROM generate_series(1,1E2) y OFFSET 0) AND
 w IS NOT NULL AND
 x = 42;

If we check the Filter line in the plan, we get:

Filter: ((w IS NOT NULL) AND (z > 0) AND (x = 42) AND (w > now()) AND
         ((x)::numeric = (InitPlan 2).col1) AND ((x)::numeric < (SubPlan 1)))

Postgres evaluates them in this exact order, left to right.

Here are the estimated costs:

• z > 0: 0.0025

• w > now(): 0.005

• x < SubPlan 1: 2.0225

• x NOT IN SubPlan 2: 0.005

• w IS NOT NULL: 0.0

• x = 42: 0.0025

This ordering looks mostly reasonable. But could we do better?

There are at least two low-hanging fruits here:

1. Column position cost. If the column is far to the right in the tuple layout, accessing it costs more. We could add a tiny cost factor based on ordinal position — enough to help the planner choose x = 42 over z = 42, for example, all other things equal.

2. Selectivity-based ordering. When two expressions have similar cost — say, x = 42 and z < 50 — it's better to put the more selective one first. If x = 42 is true less often, the planner should evaluate it before the rest.

Let’s test how much performance gain we could actually get from this. First, we’ll build a table where some columns are far apart but have the same selectivity, and others are close together but differ in selectivity.

CREATE TEMP TABLE test_2 (x1 numeric, x2 numeric, x3 numeric, x4 numeric);
INSERT INTO test_2 (x1, x2, x3, x4)
  SELECT x, (x::integer)%2, (x::integer)%100,x FROM 
    (SELECT random()*1E7 FROM generate_series(1,1E7) AS x) AS q(x);
ANALYZE;

Let’s check what happens when we search for values in this "wide" tuple. The columns x1 and x4 are identical in every way, except that the offset of x1 within the tuple is known in advance, while for x4, the system has to calculate it for each row:

EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF)
SELECT * FROM test_2 WHERE x1 = 42 AND x4 = 42;

EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF)
SELECT * FROM test_2 WHERE x4 = 42 AND x1 = 42;

/*
 Seq Scan on test_2  (actual rows=0.00 loops=1)
   Filter: ((x1 = '42'::numeric) AND (x4 = '42'::numeric))
   Buffers: local read=94357
  Execution Time: 2372.032 ms

 Seq Scan on test_2  (actual rows=0.00 loops=1)
   Filter: ((x4 = '42'::numeric) AND (x1 = '42'::numeric))
   Buffers: local read=94357
 Execution Time: 2413.633 ms
*/

So, all other things being equal, even a moderately wide tuple can cause a 2–3% difference in execution time. That’s roughly the same impact you'd expect from enabling JIT in typical cases.

Now let’s look at how selectivity affects performance. The columns x1 and x2 are located close to each other in the tuple, but there's a key difference: x1 holds almost unique values, while x2 is filled with near-duplicates:

EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF)
SELECT * FROM test_2 WHERE x2 = 1 AND x1 = 42;

EXPLAIN (ANALYZE, TIMING OFF, COSTS OFF)
SELECT * FROM test_2 WHERE x1 = 42 AND x2 = 1;
/*
 Seq Scan on test_2  (actual rows=0.00 loops=1)
   Filter: ((x2 = '1'::numeric) AND (x1 = '42'::numeric))
   Buffers: local read=74596
 Execution Time: 2363.903 ms

 Seq Scan on test_2  (actual rows=0.00 loops=1)
   Filter: ((x1 = '42'::numeric) AND (x2 = '1'::numeric))
   Buffers: local read=74596
 Execution Time: 2034.873 ms
*/

That’s a 10% difference.

If you assume that these small effects can stack across the entire plan tree — with scans, joins, groupings, etc. — then yes, reordering conditions might actually be worth doing, even if it adds a little planning overhead.

So let’s try implementing it. As an extension, this won’t work — there’s no hook in the planner to intercept final plan creation. We could really use a create_plan_hook() in create_plan(), but the community hasn’t discussed it seriously yet.

So I went ahead and made a core patch. You need to touch two places:

• cost_qual_eval() — where Postgres estimates the cost of conditions

• order_qual_clauses — the function that sorts them

You can find the final code in a branch on GitHub.

Running the earlier examples on that branch, expressions are now ordered better — taking both column order and selectivity into account. No extra planning overhead observed so far.