SLOPE: Planner Optimizations on Monotonic Expressions

The Core Problem

PostgreSQL's planner is conservative about deriving ordering guarantees from expressions built on indexed columns. Given an index on ts (timestamp), the planner knows the index produces rows ordered by ts, but it does not know that ts::date, date_trunc('month', ts), ts + interval '1 day', or floor(x) all preserve that ordering (modulo ties). Consequently, queries such as:

SELECT ts::date, count(*) FROM tasks GROUP BY 1;
SELECT date_trunc('month', ts), count(*) FROM src GROUP BY 1;
SELECT min(floor(x::float8)) FROM t;

force a Sort node (or HashAggregate) on top of an index scan that already produces data in a useful order. Architecturally this is a missed opportunity: the btree index establishes a total order via its opfamily, and any monotonic transform of the key produces a sequence whose relative order is preserved. Exploiting this allows (a) GroupAggregate directly over an Index Only Scan (no sort, streaming aggregation — crucial for wide time-series tables where only one index on ts is affordable), (b) MinMaxAggregate-style rewrites (min(f(x)) via Index Scan + LIMIT 1 when f is increasing), and (c) ordered output without an explicit Sort node.

The existing infrastructure that comes closest is the MONOTONICFUNC_* enum used by window function optimization (MonotonicFunction in plannodes.h / window aggregate support), but this machinery was never plumbed into pathkey derivation for index scans.

Proposed Design

Alexandre Felipe's patchset introduces a "slope" concept (sign of monotonicity) attached to functions and operators via prosupport functions. The key artifacts are:

1. A Slope type (initially typedef int8 Slope with bit-encoded values SLOPE_ANY=0, SLOPE_ASC=1, SLOPE_DESC=2, SLOPE_CONST=3). The encoding is deliberate: SLOPE_CONST is the bitwise AND of ASC and DESC, representing "both directions preserved" (i.e. constant output), while SLOPE_ANY represents the unknown/unsafe case.

2. Per-argument slope composition rules in prosupport functions. For a function f(a, b, ...), the support function reports, for each argument independently, whether f is monotonically increasing, decreasing, or constant with respect to that argument. The overall slope of f(e1, e2, ...) is derived by composing each argument's contribution with the slope of the sub-expression — the classic chain rule, but encoded in a 2-bit lattice.

3. Generic shared support functions: addition_slope_support, diff_slope_support, arg0_asc_slope_support, etc. — reused across many pg_proc entries (integer addition variants, float casts, ceil/floor/round, date_trunc, exp/log/atan/sinh/erf, type-cast functions).

4. Planner integration in build_index_pathkeys / pathkey_is_monotonic_of. When considering whether an index's pathkeys satisfy a query pathkey, the planner strips the outer monotonic wrapper, checks whether the inner "source of variation" matches the index key, and determines scan direction (forward vs. backward) plus NULLS FIRST/LAST inversion based on the aggregated slope.

5. Direction/NULL handling: if the composed slope is SLOPE_DESC, both reverse_sort and nulls_first are toggled. NULL handling relies on the assumption that f(NULL) IS NULL (strict functions), which matches virtually all tagged functions.

Key Technical Insights and Disagreements

Correctness pitfall #1 — Time wraparound (Zsolt Parragi)

Zsolt pointed out that tagging time_pl_interval, time_mi_interval, timetz_pl_interval, timetz_mi_interval as monotonic is wrong: the time and timetz types wrap around 24 hours, so t + interval '3 hours' is not monotonic across the wrap. Alexandre confirmed that among numeric/temporal types, only time/timetz silently wrap — int2/4/8, money, float4/8, date, timestamp, timestamptz, interval all raise overflow errors (which is acceptable: an error terminates the query rather than producing misordered results). These entries were removed in v3.

Correctness pitfall #2 — Interval arithmetic is not monotonic (Dean Rasheed)

Dean — a committer with strong expertise in types, arithmetic and the optimizer — delivered the most consequential correctness critique: interval arithmetic does not preserve ordering because interval comparison uses fixed 30-day months / 12-month years, while addition to a date/timestamp uses calendar-aware semantics. Concretely:

• interval '1 month - 29 days' compares as greater than zero (≈ 1 day by the 30-day-month rule), but adding it to a timestamp may move forward, backward, or stay put depending on the month length.
• interval '361 days' > interval '1 year' as intervals, but adding 361 days to a date advances less than adding 1 year.

This means ORDER BY ts + col_interval cannot be satisfied by an index on ts + col_interval vs. an ordering by the interval alone, and more importantly, f(x, interval_constant) is not guaranteed monotonic in x for arbitrary interval constants via the intuitive rule. Alexandre accepted this and removed interval arithmetic from the slope-tagged set.

Dean also delivered a gentle but clear verdict on process: the patch "hasn't had a great deal of in-depth review yet, there are still a number of design ideas that people might wish to explore ... it probably needs more careful analysis to verify correctness, and more testing" — effectively punting to PG20.

Correctness pitfall #3 — NULLS FIRST/LAST with all four combinations (Zsolt)

Zsolt constructed a minimal reproducer with CREATE INDEX ... (v ASC NULLS FIRST) showing the patch produced different results between index scan and sort. Alexandre responded by enumerating all 32 combinations of {sign of slope} × {index ASC/DESC} × {index NULLS FIRST/LAST} × {query ASC/DESC} × {query NULLS FIRST/LAST} in a regression test, classifying each as Forward / Backward / Sort. This exhaustive table is probably the most valuable artifact of the thread from a correctness-verification standpoint: reversing the slope sign requires toggling both reverse_sort and nulls_first, and the four NULL-placement combinations cannot all be reconciled without a Sort in several cells.

Correctness pitfall #4 — Missed siblings (Zsolt)

Zsolt noticed that ceil (OID 2308) was tagged but ceiling (2320, same prosrc) was not; similarly int42mi was tagged but int24mi, int24mul, int42mul, int24div, int42div variants were not. This pointed to a systematic gap. Alexandre's response was the slope_catalog.sql regression test, which enumerates:

• Operators whose name has slope support for some type combinations but not others.
• Functions whose name has support for some signatures but not others.

This acts as a catalog-consistency check and a reviewer aid — a nice pattern for future catalog-tagging work.

Design debate — slope type representation (Corey Huinker)

Corey — a frequent reviewer — pushed back on introducing a fresh Slope typedef int8 when MonotonicFunction (a flag enum with MONOTONICFUNC_INCREASING, MONOTONICFUNC_DECREASING, MONOTONICFUNC_BOTH) already exists in the tree for window function monotonicity. He clarified later that he wasn't demanding reuse of the exact enum, but that the pattern (enum + flag bits, to get switch-exhaustiveness warnings) should be followed. Alexandre noted the memory-locality tradeoff: an enum is 4 bytes per argument vs. 1 byte for int8, which matters when storing per-argument slope arrays.

Corey also raised subtler design points:

• left(str, n) with n > 0 preserves leading sort bits and only reduces trailing-byte ties — a form of "prefix-monotonicity" that the current binary encoding cannot express. This hints at a future extension: slope analysis that depends on argument values at plan time, not just argument positions. Alexandre sketched this as a custom prosupport returning INCREASING iff n is a positive constant.
• The static const Slope pattern[2] = {SLOPE_ASC, SLOPE_DESC} trick (used to look up the canonical slope by direction bit) is unusual and may confuse readers searching for a missing pfree. Comments needed.

Design concern — opfamily compatibility (Zsolt)

Zsolt flagged that the index-matching loop didn't check sortopfamily. An index built with a custom operator class has a sort order defined by that opfamily, which may not coincide with the default btree opfamily for the type. Alexandre's v5 adds a gate: if qpk->pk_opfamily != index->sortopfamily[i], it falls back to GetDefaultOpClass(index->opcintype[i], BTREE_AM_OID) and skips the optimization if they still differ. This is the right defensive check, though it means users with custom opclasses don't benefit.

Performance concern — planner overhead

Alexandre's own benchmarks on a table with 24 indices showed planning time overhead of ~1% for queries with no ORDER BY, rising to ~15% for ORDER BY a::float8. Fifteen percent is sizable enough that committers will push back — Alexandre pre-empted this, offering to reduce scope (GROUP BY only, drop the recursive slope analysis). His v6 addressed the root cause structurally: extract the innermost "source of variation" sub-expression once per index at index creation time (stored in slope_info), and at pathkey-matching time only verify that the index key matches that source expression plus walk the outer monotonic chain. This converts per-index per-pathkey recursion into a constant-time match plus a single walk.

He also noted that make_canonical_pathkey does a list search per index key, giving quadratic behaviour in index count — suggesting a preallocated array or hash. This is an orthogonal planner scalability issue surfaced by the work.

Scope ambiguity — joins and merge joins

Alexandre reported that joins which he expected to become MergeJoins were not picking up the derived orderings, and asked for guidance. This almost certainly stems from the fact that the derived ordering is injected as an index pathkey rather than as a full participant in the equivalence class machinery. Equivalence classes are the spine of the optimizer's reasoning about join orderings (see equivclass.c), and monotonic-derived orderings do not naturally fit the "these expressions are equal" model — they express "these expressions sort in the same order", which is a weaker relation. Solving this properly would require either synthesizing synthetic EC members or extending the EC machinery with ordering-equivalence (distinct from value-equivalence). No committer engaged on this question in the thread.

Timeline and Process

The thread spans February through May 2026 with eight patch revisions. The pattern is typical of substantial optimizer patches from non-committer contributors: initial silence (a week between post and "anyone review?"), incremental engagement from two community reviewers (Corey Huinker, Zsolt Parragi), a single high-impact intervention from a committer (Dean Rasheed) who flags a fundamental correctness issue and signals the patch is not ready for the current commitfest, and then a pivot by the author from "push for current release" to "set up for next release" (v6 onward explicitly targets PG20).

The author demonstrated good responsiveness — every review comment produced a concrete change, and the regression-test exhaustiveness expanded substantially in response to Zsolt's NULL-handling bug (the 32-case grid). The slope_catalog.sql self-consistency test added in v7 is a mature response to the "missing siblings" problem.

Outstanding Questions for Committers

1. Is the prosupport mechanism the right vector, or should monotonicity be a declarative property of pg_proc (like proleakproof, provolatile) retrievable without a function call? Alexandre explicitly raised this for user-defined functions.
2. Should the slope type be unified with MonotonicFunction, or do the different use-sites (window aggregates vs. pathkey derivation) justify separate representations?
3. How should this interact with equivalence classes and merge-join planning?
4. Is the planning-time overhead (5-15% for affected queries) acceptable, and does the v6 one-shot-per-index factoring bring it down enough?
5. The argument-value-dependent case (substr(x, 1, n), left(x, n) with positive constant n) — is prefix-monotonicity worth a follow-up patch, or is it out of scope for the feature?

None of these received committer-level answers in the thread. The patch is likely headed to PG20 pending in-depth review from someone with optimizer commit authority (Tom Lane, David Rowley, or Dean Rasheed).