Hi All, I hope I am early enough for PG20, so v6 maintains the full scope.
0001 as the name suggests is just a benchmark, to get a baseline. 0002 is just a refactoring to ensure build_index_pathkeys is called once per index. master is calling once to produce forward pathkeys and once to produce backward pathkeys. Other questions are: Should we maybe do this in a way to support monotonicity for user defined functions too? Maybe use some per argument flags that can retrieved without the call by oid? v6 splits the pathkey monotonicity analysis in two parts. If the pathkey expression depends on a single table, the innermost sub expression that contains all variable terms is extracted during the index creation, and stored in slope_info. When considering indices for pathkeys, check if the index key matches the slope info source of variation, if it does, check the monotonicity. Limitations: Not supporting pathkeys [f(x), x], maybe useful for queries SELECT OVER (PARTITION f(x) ORDER BY x) I have an implementation on a 0006 patch but I think it would hurt the overall patchset quality. Not working with joins where I expected a MergeJoin to be used. Any hints here? Because I am not properly using equivalence classes? or something else? I see that `make_canonical_pathkey` does a list search for every index key. expressions, the complexity is roughly quadratic with the number of indices. I suspect that pointer chasing having a preallocated array would already be better, as it would probably improve the memory locality. Would it be worth investigating other data structures here, like hash or a tree? (I guess the answer will be no as that could hurt the very simple plans with a handful of indices). Regards, Alexandre On Fri, Mar 27, 2026 at 9:29 AM Alexandre Felipe < [email protected]> wrote: > > > On Fri, Mar 27, 2026 at 8:47 AM Dean Rasheed <[email protected]> > wrote: > >> I don't know. I haven't looked at the patches themselves in any >> detail. I was merely replying to a specific question about >> monotonicity with respect to a particular data type. >> >> However, my impression from reading this thread is that the patches >> haven't had a great deal of in-depth review yet, there are still a >> number of design ideas that people might wish to explore in more >> detail, it probably needs more careful analysis to verify correctness, >> and more testing. That makes me think that it's not feasible to get >> anything committable in less than a week, and it would be better to >> defer this. > > > Thank you for your feedback, either way I am happy that at least > now it received some attention. > > I am testing an iterative single variable/expression and to find the > simplest expression x that is the cause of all the variation in the > pathkey expression, saving this in the plan info, and thus, reduce > the per index work. > > Regards, > Alexandre > > >
From 2b1406cf3927caeb96d107e55550c41872b342ff Mon Sep 17 00:00:00 2001 From: Alexandre Felipe <[email protected]> Date: Thu, 2 Apr 2026 22:42:37 +0100 Subject: [PATCH 1/6] benchmark SQL script to measure planning time with varying numbers of indices. Tests with 0, 5, 10, 20, and 50 additional indices. --- bench_slope_planning.sql | 138 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 138 insertions(+) create mode 100644 bench_slope_planning.sql diff --git a/bench_slope_planning.sql b/bench_slope_planning.sql new file mode 100644 index 00000000000..0b3d12cc82f --- /dev/null +++ b/bench_slope_planning.sql @@ -0,0 +1,138 @@ +-- +-- SLOPE Planning Time Benchmark (Single Connection) +-- +-- Measures planning time for queries that benefit from SLOPE optimization. +-- Tests with varying numbers of indices to see scaling behavior. +-- Uses clock_timestamp() to measure time spent in EXPLAIN (without ANALYZE). +-- + +-- Force index usage +SET enable_seqscan = off; +SET enable_bitmapscan = off; +SET enable_hashagg = off; + +-- Create results table +DROP TABLE IF EXISTS bench_results; +CREATE TABLE bench_results ( + id serial PRIMARY KEY, + num_indices int NOT NULL, + planning_time_us numeric NOT NULL +); + +-- Function to create test table with N indices +CREATE OR REPLACE FUNCTION setup_bench_table(p_num_indices int) RETURNS void AS $$ +DECLARE + v_i int; +BEGIN + DROP TABLE IF EXISTS bench_slope CASCADE; + + CREATE TABLE bench_slope ( + id serial PRIMARY KEY, + ts timestamp NOT NULL, + v_int4 int4 NOT NULL, + v_float8 float8 NOT NULL + ); + + -- Always create index on ts (the one we query) + CREATE INDEX ON bench_slope (ts); + + -- Create additional indices to stress the planner + FOR v_i IN 1..p_num_indices LOOP + EXECUTE format('CREATE INDEX ON bench_slope ((v_int4 + %s))', v_i); + END LOOP; + + INSERT INTO bench_slope (ts, v_int4, v_float8) + SELECT + '2020-01-01'::timestamp + (i || ' hours')::interval, + i, + i::float8 + FROM generate_series(1, 1000) i; + + ANALYZE bench_slope; +END; +$$ LANGUAGE plpgsql; + +-- Benchmark function for a specific number of indices +CREATE OR REPLACE FUNCTION bench_slope_planning_n( + p_num_indices int, + p_iterations int, + p_warmup int +) RETURNS void AS $$ +DECLARE + v_start timestamp; + v_end timestamp; + v_elapsed_us numeric; + v_i int; + v_plan text; +BEGIN + -- Setup table + PERFORM setup_bench_table(p_num_indices); + + -- Warmup phase + FOR v_i IN 1..p_warmup LOOP + FOR v_plan IN EXPLAIN SELECT date_trunc('month', ts), count(*) FROM bench_slope GROUP BY 1 LOOP + END LOOP; + END LOOP; + + -- Benchmark phase + FOR v_i IN 1..p_iterations LOOP + v_start := clock_timestamp(); + FOR v_plan IN EXPLAIN SELECT date_trunc('month', ts), count(*) FROM bench_slope GROUP BY 1 LOOP + END LOOP; + v_end := clock_timestamp(); + v_elapsed_us := extract(epoch from (v_end - v_start)) * 1000000; + INSERT INTO bench_results (num_indices, planning_time_us) + VALUES (p_num_indices, v_elapsed_us); + END LOOP; +END; +$$ LANGUAGE plpgsql; + +-- Run the benchmark +\echo '========================================================================' +\echo 'SLOPE Planning Time Benchmark (Single Connection, Varying Indices)' +\echo '========================================================================' +\echo '' + +TRUNCATE bench_results; + +\echo 'Testing with 0 additional indices...' +SELECT bench_slope_planning_n(0, 5000, 50); + +\echo 'Testing with 5 additional indices...' +SELECT bench_slope_planning_n(5, 5000, 50); + +\echo 'Testing with 10 additional indices...' +SELECT bench_slope_planning_n(10, 5000, 50); + +\echo 'Testing with 20 additional indices...' +SELECT bench_slope_planning_n(20, 5000, 50); + +\echo 'Testing with 50 additional indices...' +SELECT bench_slope_planning_n(50, 5000, 50); + +-- Results by number of indices +\echo '' +\echo 'Results by Number of Indices:' +\echo '' + +SELECT + num_indices as "Indices", + count(*) as "N", + round(avg(planning_time_us)::numeric, 1) as "Mean (µs)", + round((percentile_cont(0.5) WITHIN GROUP (ORDER BY planning_time_us))::numeric, 1) as "Median (µs)", + round(stddev(planning_time_us)::numeric, 1) as "StdDev (µs)", + round((percentile_cont(0.05) WITHIN GROUP (ORDER BY planning_time_us))::numeric, 1) as "P5 (µs)", + round((percentile_cont(0.95) WITHIN GROUP (ORDER BY planning_time_us))::numeric, 1) as "P95 (µs)" +FROM bench_results +GROUP BY num_indices +ORDER BY num_indices; + +-- Cleanup +DROP FUNCTION bench_slope_planning_n(int, int, int); +DROP FUNCTION setup_bench_table(int); +DROP TABLE bench_results; +DROP TABLE IF EXISTS bench_slope CASCADE; + +RESET enable_seqscan; +RESET enable_bitmapscan; +RESET enable_hashagg; -- 2.53.0
From b83aa230fad447e02f4398f13523f59de63e4d5a Mon Sep 17 00:00:00 2001 From: Alexandre Felipe <[email protected]> Date: Sun, 5 Apr 2026 01:01:18 +0100 Subject: [PATCH 5/6] SLOPE: Planner support Update the planner to take advantage of order of an expression that can be inferred from the order of a subexpression. If f(x) is a monotonic function and x is known to be ordered, we can infeer the order of f(x) from the order of x. The analysis is performed in two stages 1. During plan creation, for every pathkey expression computes the source of variation, defined as the innermost subexpression that causes all variation in the expression. if the source of variaiton is not the full expression, and depends on a single table, a slope_info entry is created. 2. on build_index_pathkeys, in addition to the usual pathkeys create pathkeys for slope_info entries where the index key is the source of variation. Changes: - Add SlopeInfo struct to cache monotonicity information per pathkey - Add precompute_slope_cache() called during plan construction - Add get_variation_source() to find the innermost varying expression - Add get_expr_slope_wrt() to verify monotonicity by calling prosupport - Modify build_index_pathkeys() to check for monotonicity on index keys - Handle both increasing and decreasing monotonic functions, with reversed pathkey emission for decreasing functions so that backward index scans are correctly selected Adds tests tests in sql/slope.sql covering GROUP BY, ORDER BY, involving a few arithmetic operations, increasing and decreasing functions. --- src/backend/optimizer/path/pathkeys.c | 474 ++++++++++++++++++++++++-- src/backend/optimizer/plan/planner.c | 3 + src/include/nodes/pathnodes.h | 6 + src/include/nodes/plannodes.h | 5 + src/include/optimizer/paths.h | 1 + src/test/regress/expected/slope.out | 281 +++++++++++++++ src/test/regress/parallel_schedule | 3 + src/test/regress/sql/slope.sql | 143 ++++++++ 8 files changed, 891 insertions(+), 25 deletions(-) create mode 100644 src/test/regress/expected/slope.out create mode 100644 src/test/regress/sql/slope.sql diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 3e3eb720c1f..8aceccb4b2e 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -19,24 +19,46 @@ #include "access/stratnum.h" #include "catalog/pg_opfamily.h" +#include "fmgr.h" #include "nodes/nodeFuncs.h" +#include "nodes/supportnodes.h" #include "optimizer/cost.h" #include "optimizer/optimizer.h" #include "optimizer/pathnode.h" #include "optimizer/paths.h" +#include "parser/parse_oper.h" #include "partitioning/partbounds.h" #include "rewrite/rewriteManip.h" #include "utils/lsyscache.h" +#include "utils/typcache.h" /* Consider reordering of GROUP BY keys? */ bool enable_group_by_reordering = true; +/* + * SlopeInfo - cached information about a query pathkey for SLOPE optimization. + * Stored in PlannerInfo.slope_info array. + */ +typedef struct SlopeInfo +{ + MonotonicFunction slope; /* cached monotonicity result */ + Index relid; /* relid of the table, or 0 if multi-table */ + Expr *expr; /* variation source (inner expression) */ + PathKey *pathkey; /* the query pathkey this info belongs to */ +} SlopeInfo; + static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol); static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle); static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey); +static MonotonicFunction get_expr_slope_wrt(Expr *expr, Expr *target); +static PathKey *match_slope_pathkey_for_index_col(PlannerInfo *root, + IndexOptInfo *index, + int colno, + Expr *indexkey, + bool reverse_sort); /**************************************************************************** @@ -760,6 +782,391 @@ get_cheapest_parallel_safe_total_inner(List *paths) return NULL; } +/* + * get_variation_source + * Find the source of variation in an expression. + * + * Descends through function calls to find the innermost non-constant + * expression that determines the variation of the whole expression. + * For f(x) returns x. For f(g(x)) returns x. For f(x, y) returns f(x, y). + * For a plain Var, returns the Var itself. + * + * This is a cheap extraction that doesn't check monotonicity - that's + * deferred until we find an index column matching the variation source. + * Also extracts the relid if all Vars are from the same table. + */ +static void +get_variation_source(Expr *expr, Expr **inner_out, Index *relid_out) +{ + *inner_out = NULL; + *relid_out = 0; + + for (;;) + { + List *args; + Expr *non_const_arg = NULL; + int non_const_count = 0; + ListCell *lc; + + /* Skip RelabelType (no-op coercion) */ + if (IsA(expr, RelabelType)) + { + expr = (Expr *) ((RelabelType *) expr)->arg; + continue; + } + + /* Handle FuncExpr - skip through casts */ + if (IsA(expr, FuncExpr)) + { + FuncExpr *fexpr = (FuncExpr *) expr; + + if ((fexpr->funcformat == COERCE_IMPLICIT_CAST || + fexpr->funcformat == COERCE_EXPLICIT_CAST) && + list_length(fexpr->args) == 1) + { + expr = (Expr *) linitial(fexpr->args); + continue; + } + args = fexpr->args; + } + else if (IsA(expr, OpExpr)) + { + args = ((OpExpr *) expr)->args; + } + else if (IsA(expr, Var)) + { + /* Reached a Var - this is our inner expression */ + *inner_out = expr; + *relid_out = ((Var *) expr)->varno; + return; + } + else + { + /* Unsupported node type */ + return; + } + + /* Find non-constant arguments */ + foreach(lc, args) + { + Expr *arg = (Expr *) lfirst(lc); + + if (!IsA(arg, Const)) + { + non_const_count++; + if (non_const_count > 1) + { + /* Multivariate - return this expression as inner */ + *inner_out = expr; + *relid_out = 0; /* unknown, will use equal() */ + return; + } + non_const_arg = arg; + } + } + + if (non_const_arg == NULL) + { + /* All constant - no inner expression */ + return; + } + + expr = non_const_arg; + } +} + +/* + * get_expr_slope_wrt + * Determine the monotonicity slope of an expression with respect to + * a specific target subexpression. + * + * Returns the slope of 'expr' with respect to 'target' + * MONOTONICFUNC_INCREASING: monotonically increasing + * MONOTONICFUNC_DECREASING: monotonically decreasing + * MONOTONICFUNC_NONE: cannot determine monotonicity + */ +static MonotonicFunction +get_expr_slope_wrt(Expr *expr, Expr *target) +{ + MonotonicFunction slope = MONOTONICFUNC_INCREASING; + + for (;;) + { + Oid funcid; + List *args; + Oid prosupport; + SupportRequestMonotonic req; + ListCell *lc; + int i; + Expr *next_expr = NULL; + MonotonicFunction func_arg_slope = MONOTONICFUNC_INCREASING; + + /* Check if we've reached the target */ + if (equal(expr, target)) + return slope; + + /* Skip RelabelType (no-op coercion) */ + if (IsA(expr, RelabelType)) + { + expr = (Expr *) ((RelabelType *) expr)->arg; + continue; + } + + /* Handle FuncExpr - skip through casts */ + if (IsA(expr, FuncExpr)) + { + FuncExpr *fexpr = (FuncExpr *) expr; + + if ((fexpr->funcformat == COERCE_IMPLICIT_CAST || + fexpr->funcformat == COERCE_EXPLICIT_CAST) && + list_length(fexpr->args) == 1) + { + expr = (Expr *) linitial(fexpr->args); + continue; + } + funcid = fexpr->funcid; + args = fexpr->args; + } + else if (IsA(expr, OpExpr)) + { + OpExpr *opexpr = (OpExpr *) expr; + + set_opfuncid(opexpr); + funcid = opexpr->opfuncid; + args = opexpr->args; + } + else + { + /* Reached a leaf without finding target */ + return MONOTONICFUNC_NONE; + } + + /* Check for prosupport function */ + prosupport = get_func_support(funcid); + if (!OidIsValid(prosupport)) + return MONOTONICFUNC_NONE; + + /* Call prosupport to get slope pattern */ + req.type = T_SupportRequestMonotonic; + req.expr = (Node *) expr; + req.slopes = NULL; + req.nslopes = 0; + + if (DatumGetPointer(OidFunctionCall1(prosupport, PointerGetDatum(&req))) == NULL) + return MONOTONICFUNC_NONE; + + if (req.slopes == NULL || req.nslopes <= 0) + return MONOTONICFUNC_NONE; + + /* Find the single non-constant argument */ + i = 0; + foreach(lc, args) + { + Expr *arg = (Expr *) lfirst(lc); + + if (!IsA(arg, Const)) + { + if (next_expr != NULL) + { + /* Multivariate - check if this is the target */ + return equal(expr, target) ? slope : MONOTONICFUNC_NONE; + } + next_expr = arg; + if (likely(i < req.nslopes)) + { + if (req.slopes[i] == MONOTONICFUNC_DECREASING) + func_arg_slope = MONOTONICFUNC_DECREASING; + else if (req.slopes[i] != MONOTONICFUNC_INCREASING) + return MONOTONICFUNC_NONE; + } + else + return MONOTONICFUNC_NONE; + } + i++; + } + + if (next_expr == NULL) + return MONOTONICFUNC_NONE; /* all constant */ + + /* Compose slopes */ + if (func_arg_slope == MONOTONICFUNC_DECREASING) + { + slope = (slope == MONOTONICFUNC_INCREASING) ? + MONOTONICFUNC_DECREASING : MONOTONICFUNC_INCREASING; + } + + expr = next_expr; + } +} + +/* + * precompute_slope_cache + * For each pathkey, extract the source of variation and check if + * it is usable, i.e. depends on a single table, and is not the + * complete expression. + * + * This is called once after query_pathkeys is set. We store only entries + * where there's a useful variation source (relid != 0), making the array + * compact for efficient iteration. Monotonicity is checked later only + * when an index column matches the variation source. + * + * We also check if the next pathkey equals the variation source, enabling + * patterns like [f(x), x] to be satisfied by a single index column. + */ +void +precompute_slope_cache(PlannerInfo *root) +{ + int nqpk; + int count; + ListCell *lc; + + root->num_slope_entries = 0; + root->slope_info = NULL; + + if (root->query_pathkeys == NIL) + return; + + nqpk = list_length(root->query_pathkeys); + root->slope_info = (SlopeInfo *) palloc(nqpk * sizeof(SlopeInfo)); + + count = 0; + foreach(lc, root->query_pathkeys) + { + PathKey *qpk = lfirst_node(PathKey, lc); + EquivalenceMember *em; + Expr *inner; + Index relid; + + if (qpk->pk_eclass->ec_has_volatile || + qpk->pk_eclass->ec_members == NIL) + continue; + + em = linitial(qpk->pk_eclass->ec_members); + + /* Simple Vars don't need slope analysis */ + if (IsA(em->em_expr, Var)) + continue; + + get_variation_source(em->em_expr, &inner, &relid); + + /* + * Only store if we found a useful variation source from a single + * table that differs from the original expression. + * relid == 0 means multivariate or unknown source. + */ + if (inner != NULL && relid != 0 && inner != em->em_expr) + { + root->slope_info[count].slope = MONOTONICFUNC_BOTH; + root->slope_info[count].relid = relid; + root->slope_info[count].expr = inner; + root->slope_info[count].pathkey = qpk; + count++; + } + } + + if (count > 0) + root->num_slope_entries = count; + else + { + pfree(root->slope_info); + root->slope_info = NULL; + } +} + +/* + * match_slope_pathkey_for_index_col + * If a precomputed slope entry matches this index column, return its + * PathKey; otherwise NULL. Monotonicity is computed on first match and + * cached in slope_info. + * + * The emitted pathkey reflects the sort direction that the forward scan + * actually produces, determined by the index column direction and the + * function's monotonicity. This mirrors how make_pathkey_from_sortinfo + * always emits for the given scan direction. + */ +static PathKey * +match_slope_pathkey_for_index_col(PlannerInfo *root, + IndexOptInfo *index, + int colno, + Expr *indexkey, + bool reverse_sort) +{ + TypeCacheEntry *tce = NULL; + + Assert(colno >= 0 && colno < index->nkeycolumns); + + if (root->num_slope_entries == 0 || + index->rel->reloptkind != RELOPT_BASEREL) + return NULL; + + for (int j = 0; j < root->num_slope_entries; j++) + { + SlopeInfo *si = &root->slope_info[j]; + bool need_desc; + bool produces_desc; + + if (si->relid != index->rel->relid) + continue; + + /* Check if the variation source matches the index column */ + if (likely(IsA(indexkey, Var))) + { + Var *v1 = (Var *) si->expr; + Var *v2 = (Var *) indexkey; + + if (unlikely(!IsA(v1, Var) || + v1->varno != v2->varno || + v1->varattno != v2->varattno)) + continue; + } + else if (!equal(si->expr, indexkey)) + continue; + + /* Check opfamily (once per index column) */ + if (tce == NULL) + { + tce = lookup_type_cache(index->opcintype[colno], + TYPECACHE_BTREE_OPFAMILY); + if (unlikely(!OidIsValid(tce->btree_opf) || + tce->btree_opf != index->sortopfamily[colno])) + break; + } + + /* Compute monotonicity (once per slope_info entry) */ + if (si->slope == MONOTONICFUNC_BOTH) + { + EquivalenceMember *em; + + em = linitial(si->pathkey->pk_eclass->ec_members); + si->slope = get_expr_slope_wrt(em->em_expr, si->expr); + } + + if (si->slope == MONOTONICFUNC_NONE) + continue; + + /* + * Emit a pathkey reflecting the direction the forward scan + * produces, which depends on both the index column direction + * and the function's monotonicity: + * + * index function pathkey + * ASC ASC ASC + * ASC DESC DESC + * DESC ASC DESC + * DESC DESC ASC + */ + need_desc = (si->pathkey->pk_cmptype == COMPARE_GT); + produces_desc = (reverse_sort != (si->slope == MONOTONICFUNC_DECREASING)); + + if (need_desc == produces_desc) + return si->pathkey; + else + return make_reversed_pathkey(root, si->pathkey); + } + + return NULL; +} + /**************************************************************************** * NEW PATHKEY FORMATION ****************************************************************************/ @@ -819,42 +1226,59 @@ build_index_pathkeys(PlannerInfo *root, nulls_first = index->nulls_first[i]; /* - * OK, try to make a canonical pathkey for this sort key. + * First, try SLOPE: check if a monotonic function wraps this + * index column. This is checked before make_pathkey_from_sortinfo + * so that f(x) pathkeys that have no direct EquivalenceClass for + * the index column can still be matched. + * + * The emitted pathkey reflects what the forward scan produces, + * based on the index column direction and the function's + * monotonicity. */ - cpathkey = make_pathkey_from_sortinfo(root, - indexkey, - index->sortopfamily[i], - index->opcintype[i], - index->indexcollations[i], - reverse_sort, - nulls_first, - 0, - index->rel->relids, - false); - + cpathkey = match_slope_pathkey_for_index_col(root, index, i, + indexkey, + reverse_sort); if (cpathkey) { - /* - * We found the sort key in an EquivalenceClass, so it's relevant - * for this query. Add it to list, unless it's redundant. - */ if (!pathkey_is_redundant(cpathkey, retval)) retval = lappend(retval, cpathkey); } else { /* - * Boolean index keys might be redundant even if they do not - * appear in an EquivalenceClass, because of our special treatment - * of boolean equality conditions --- see the comment for - * indexcol_is_bool_constant_for_query(). If that applies, we can - * continue to examine lower-order index columns. Otherwise, the - * sort key is not an interesting sort order for this query, so we - * should stop considering index columns; any lower-order sort - * keys won't be useful either. + * No SLOPE match. Try to make a canonical pathkey. */ - if (!indexcol_is_bool_constant_for_query(root, index, i)) + cpathkey = make_pathkey_from_sortinfo(root, + indexkey, + index->sortopfamily[i], + index->opcintype[i], + index->indexcollations[i], + reverse_sort, + nulls_first, + 0, + index->rel->relids, + false); + + if (cpathkey) + { + if (!pathkey_is_redundant(cpathkey, retval)) + retval = lappend(retval, cpathkey); + } + else if (!indexcol_is_bool_constant_for_query(root, index, i)) + { + /* + * Boolean index keys might be redundant even if they do not + * appear in an EquivalenceClass, because of our special + * treatment of boolean equality conditions --- see the + * comment for indexcol_is_bool_constant_for_query(). If that + * applies, we can continue to examine lower-order index + * columns. Otherwise, the sort key is not an interesting + * sort order for this query, so we should stop considering + * index columns; any lower-order sort keys won't be useful + * either. + */ break; + } } i++; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 07944612668..cf05f99d7d4 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3739,6 +3739,9 @@ standard_qp_callback(PlannerInfo *root, void *extra) root->query_pathkeys = root->setop_pathkeys; else root->query_pathkeys = NIL; + + /* Precompute SLOPE cache for monotonic function optimization */ + precompute_slope_cache(root); } /* diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 7947d83d584..ce49ddd1279 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -297,6 +297,8 @@ typedef struct PlannerGlobal * correctly replaced with the keeping one. *---------- */ +struct SlopeInfo; /* private to pathkeys.c */ + typedef struct PlannerInfo PlannerInfo; struct PlannerInfo @@ -515,6 +517,10 @@ struct PlannerInfo /* desired pathkeys for query_planner() */ List *query_pathkeys; + /* SLOPE optimization: cached info about monotonic pathkeys */ + struct SlopeInfo *slope_info pg_node_attr(read_write_ignore); + int num_slope_entries; + /* groupClause pathkeys, if any */ List *group_pathkeys; diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index e2c00576d41..dfe15f05897 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -1831,6 +1831,11 @@ typedef struct PlanInvalItem * than the previous call. A monotonically decreasing function cannot yield a * higher value on subsequent calls, and a function which is both must return * the same value on each call. + * + * Used both for window function run conditions (SupportRequestWFuncMonotonic) + * and for per-argument monotonicity of scalar functions + * (SupportRequestMonotonic), where it enables the planner to use an index + * on 'x' to satisfy ORDER BY / GROUP BY on 'f(x)'. */ typedef enum MonotonicFunction { diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 7564e232e65..192b29f8eb2 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -236,6 +236,7 @@ extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths, Relids required_outer, double fraction); extern Path *get_cheapest_parallel_safe_total_inner(List *paths); +extern void precompute_slope_cache(PlannerInfo *root); extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index); extern PathKey *make_reversed_pathkey(PlannerInfo *root, PathKey *pathkey); extern List *reverse_pathkeys(PlannerInfo *root, List *pathkeys); diff --git a/src/test/regress/expected/slope.out b/src/test/regress/expected/slope.out new file mode 100644 index 00000000000..f33299a9120 --- /dev/null +++ b/src/test/regress/expected/slope.out @@ -0,0 +1,281 @@ +-- +-- SLOPE (Scalar function Leveraging Ordered Path Evaluation) +-- Test that monotonic functions can use indexes for ordering +-- +-- Create test table with various data types +CREATE TABLE slope_src ( + id serial PRIMARY KEY, + v_int2 int2, + v_int4 int4, + v_int8 int8, + v_float4 float4, + v_float8 float8, + v_numeric numeric, + ts timestamp, + tstz timestamptz +); +-- Insert some test data +INSERT INTO slope_src (v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz) +SELECT + (i % 100)::int2, + i, + i::int8, + i::float4, + i::float8, + i::numeric, + '2020-01-01'::timestamp + (i || ' hours')::interval, + '2020-01-01'::timestamptz + (i || ' hours')::interval +FROM generate_series(1, 1000) i; +-- Create indexes on the columns we'll test +CREATE INDEX slope_src_v_int4_idx ON slope_src (v_int4); +CREATE INDEX slope_src_v_int8_idx ON slope_src (v_int8); +CREATE INDEX slope_src_v_float8_idx ON slope_src (v_float8); +CREATE INDEX slope_src_v_numeric_idx ON slope_src (v_numeric); +CREATE INDEX slope_src_ts_idx ON slope_src (ts); +CREATE INDEX slope_src_tstz_idx ON slope_src (tstz); +-- Analyze to get good statistics +ANALYZE slope_src; +-- Disable hash aggregation to force group aggregate plan +SET enable_hashagg = off; +-- +-- Test GROUP BY with monotonic function +-- +-- Basic: floor(float8) should use index on v_float8 +explain (costs off, verbose) +select floor(v_float8), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------ + GroupAggregate + Output: (floor(v_float8)), count(*) + Group Key: floor(slope_src.v_float8) + -> Index Only Scan using slope_src_v_float8_idx on public.slope_src + Output: floor(v_float8) +(5 rows) + +-- ceil(float8) should use index on v_float8 +explain (costs off, verbose) +select ceil(v_float8), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------ + GroupAggregate + Output: (ceil(v_float8)), count(*) + Group Key: ceil(slope_src.v_float8) + -> Index Only Scan using slope_src_v_float8_idx on public.slope_src + Output: ceil(v_float8) +(5 rows) + +-- floor(numeric) should use index on v_numeric +explain (costs off, verbose) +select floor(v_numeric), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------- + GroupAggregate + Output: (floor(v_numeric)), count(*) + Group Key: floor(slope_src.v_numeric) + -> Index Only Scan using slope_src_v_numeric_idx on public.slope_src + Output: floor(v_numeric) +(5 rows) + +-- timestamp::date cast should use index on ts +explain (costs off, verbose) +select ts::date, count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------ + GroupAggregate + Output: ((ts)::date), count(*) + Group Key: (slope_src.ts)::date + -> Index Only Scan using slope_src_ts_idx on public.slope_src + Output: (ts)::date +(5 rows) + +-- date_trunc on timestamp should use index +explain (costs off, verbose) +select date_trunc('day', ts), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------ + GroupAggregate + Output: (date_trunc('day'::text, ts)), count(*) + Group Key: date_trunc('day'::text, slope_src.ts) + -> Index Only Scan using slope_src_ts_idx on public.slope_src + Output: date_trunc('day'::text, ts) +(5 rows) + +-- date_trunc on timestamptz should use index +explain (costs off, verbose) +select date_trunc('day', tstz), count(*) from slope_src group by 1; + QUERY PLAN +-------------------------------------------------------------------- + GroupAggregate + Output: (date_trunc('day'::text, tstz)), count(*) + Group Key: date_trunc('day'::text, slope_src.tstz) + -> Index Only Scan using slope_src_tstz_idx on public.slope_src + Output: date_trunc('day'::text, tstz) +(5 rows) + +-- +-- Test arithmetic operations +-- +-- Addition: v_int4 + 10 is increasing in v_int4 +explain (costs off, verbose) +select v_int4 + 10, count(*) from slope_src group by 1; + QUERY PLAN +---------------------------------------------------------------------- + GroupAggregate + Output: ((v_int4 + 10)), count(*) + Group Key: (slope_src.v_int4 + 10) + -> Index Only Scan using slope_src_v_int4_idx on public.slope_src + Output: (v_int4 + 10) +(5 rows) + +-- Subtraction: v_int4 - 10 is increasing in v_int4 +explain (costs off, verbose) +select v_int4 - 10, count(*) from slope_src group by 1; + QUERY PLAN +---------------------------------------------------------------------- + GroupAggregate + Output: ((v_int4 - 10)), count(*) + Group Key: (slope_src.v_int4 - 10) + -> Index Only Scan using slope_src_v_int4_idx on public.slope_src + Output: (v_int4 - 10) +(5 rows) + +-- Multiplication by positive constant: v_int4 * 2 is increasing +explain (costs off, verbose) +select v_int4 * 2, count(*) from slope_src group by 1; + QUERY PLAN +---------------------------------------------------------------------- + GroupAggregate + Output: ((v_int4 * 2)), count(*) + Group Key: (slope_src.v_int4 * 2) + -> Index Only Scan using slope_src_v_int4_idx on public.slope_src + Output: (v_int4 * 2) +(5 rows) + +-- Division by positive constant: v_int4 / 2 is increasing +explain (costs off, verbose) +select v_int4 / 2, count(*) from slope_src group by 1; + QUERY PLAN +---------------------------------------------------------------------- + GroupAggregate + Output: ((v_int4 / 2)), count(*) + Group Key: (slope_src.v_int4 / 2) + -> Index Only Scan using slope_src_v_int4_idx on public.slope_src + Output: (v_int4 / 2) +(5 rows) + +-- +-- Test decreasing functions (should use backward scan) +-- +-- Unary minus: -v_int4 is decreasing in v_int4 +explain (costs off, verbose) +select -v_int4, count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------------- + GroupAggregate + Output: ((- v_int4)), count(*) + Group Key: (- slope_src.v_int4) + -> Index Only Scan Backward using slope_src_v_int4_idx on public.slope_src + Output: (- v_int4) +(5 rows) + +-- Subtraction from constant: 1000 - v_int4 is decreasing in v_int4 +explain (costs off, verbose) +select 1000 - v_int4, count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------------- + GroupAggregate + Output: ((1000 - v_int4)), count(*) + Group Key: (1000 - slope_src.v_int4) + -> Index Only Scan Backward using slope_src_v_int4_idx on public.slope_src + Output: (1000 - v_int4) +(5 rows) + +-- Multiplication by negative constant: v_int4 * (-2) is decreasing +explain (costs off, verbose) +select v_int4 * (-2), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------------- + GroupAggregate + Output: ((v_int4 * '-2'::integer)), count(*) + Group Key: (slope_src.v_int4 * '-2'::integer) + -> Index Only Scan Backward using slope_src_v_int4_idx on public.slope_src + Output: (v_int4 * '-2'::integer) +(5 rows) + +-- Division by negative constant: v_int4 / (-2) is decreasing +explain (costs off, verbose) +select v_int4 / (-2), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------------- + GroupAggregate + Output: ((v_int4 / '-2'::integer)), count(*) + Group Key: (slope_src.v_int4 / '-2'::integer) + -> Index Only Scan Backward using slope_src_v_int4_idx on public.slope_src + Output: (v_int4 / '-2'::integer) +(5 rows) + +-- +-- Test ORDER BY with monotonic function +-- +-- ORDER BY floor(v_float8) should use index +explain (costs off, verbose) +select floor(v_float8), v_float8 from slope_src order by 1 limit 10; + QUERY PLAN +------------------------------------------------------------------------ + Limit + Output: (floor(v_float8)), v_float8 + -> Index Only Scan using slope_src_v_float8_idx on public.slope_src + Output: floor(v_float8), v_float8 +(4 rows) + +-- ORDER BY -v_int4 DESC should use forward scan (decreasing + DESC = forward) +explain (costs off, verbose) +select -v_int4 from slope_src order by 1 desc limit 10; + QUERY PLAN +---------------------------------------------------------------------- + Limit + Output: ((- v_int4)) + -> Index Only Scan using slope_src_v_int4_idx on public.slope_src + Output: (- v_int4) +(4 rows) + +-- ORDER BY -v_int4 ASC should use backward scan (decreasing + ASC = backward) +explain (costs off, verbose) +select -v_int4 from slope_src order by 1 limit 10; + QUERY PLAN +------------------------------------------------------------------------------- + Limit + Output: ((- v_int4)) + -> Index Only Scan Backward using slope_src_v_int4_idx on public.slope_src + Output: (- v_int4) +(4 rows) + +-- +-- Test nested monotonic function +-- +-- floor(floor(x)) should still use index +explain (costs off, verbose) +select floor(floor(v_float8)), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------ + GroupAggregate + Output: (floor(floor(v_float8))), count(*) + Group Key: floor(floor(slope_src.v_float8)) + -> Index Only Scan using slope_src_v_float8_idx on public.slope_src + Output: floor(floor(v_float8)) +(5 rows) + +-- floor(v + 1) should use index +explain (costs off, verbose) +select floor(v_float8 + 1), count(*) from slope_src group by 1; + QUERY PLAN +------------------------------------------------------------------------ + GroupAggregate + Output: (floor((v_float8 + '1'::double precision))), count(*) + Group Key: floor((slope_src.v_float8 + '1'::double precision)) + -> Index Only Scan using slope_src_v_float8_idx on public.slope_src + Output: floor((v_float8 + '1'::double precision)) +(5 rows) + +-- Cleanup +RESET enable_hashagg; diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule index 734da057c34..9dd2ef31517 100644 --- a/src/test/regress/parallel_schedule +++ b/src/test/regress/parallel_schedule @@ -63,6 +63,9 @@ test: sanity_check # ---------- test: select_into select_distinct select_distinct_on select_implicit select_having subselect union case join aggregates transactions random portals arrays btree_index hash_index update delete namespace prepared_xacts +# SLOPE optimization test +test: slope + # ---------- # Another group of parallel tests # ---------- diff --git a/src/test/regress/sql/slope.sql b/src/test/regress/sql/slope.sql new file mode 100644 index 00000000000..9fb48f56ab2 --- /dev/null +++ b/src/test/regress/sql/slope.sql @@ -0,0 +1,143 @@ +-- +-- SLOPE (Scalar function Leveraging Ordered Path Evaluation) +-- Test that monotonic functions can use indexes for ordering +-- + +-- Create test table with various data types +CREATE TABLE slope_src ( + id serial PRIMARY KEY, + v_int2 int2, + v_int4 int4, + v_int8 int8, + v_float4 float4, + v_float8 float8, + v_numeric numeric, + ts timestamp, + tstz timestamptz +); + +-- Insert some test data +INSERT INTO slope_src (v_int2, v_int4, v_int8, v_float4, v_float8, v_numeric, ts, tstz) +SELECT + (i % 100)::int2, + i, + i::int8, + i::float4, + i::float8, + i::numeric, + '2020-01-01'::timestamp + (i || ' hours')::interval, + '2020-01-01'::timestamptz + (i || ' hours')::interval +FROM generate_series(1, 1000) i; + +-- Create indexes on the columns we'll test +CREATE INDEX slope_src_v_int4_idx ON slope_src (v_int4); +CREATE INDEX slope_src_v_int8_idx ON slope_src (v_int8); +CREATE INDEX slope_src_v_float8_idx ON slope_src (v_float8); +CREATE INDEX slope_src_v_numeric_idx ON slope_src (v_numeric); +CREATE INDEX slope_src_ts_idx ON slope_src (ts); +CREATE INDEX slope_src_tstz_idx ON slope_src (tstz); + +-- Analyze to get good statistics +ANALYZE slope_src; + +-- Disable hash aggregation to force group aggregate plan +SET enable_hashagg = off; + +-- +-- Test GROUP BY with monotonic function +-- + +-- Basic: floor(float8) should use index on v_float8 +explain (costs off, verbose) +select floor(v_float8), count(*) from slope_src group by 1; + +-- ceil(float8) should use index on v_float8 +explain (costs off, verbose) +select ceil(v_float8), count(*) from slope_src group by 1; + +-- floor(numeric) should use index on v_numeric +explain (costs off, verbose) +select floor(v_numeric), count(*) from slope_src group by 1; + +-- timestamp::date cast should use index on ts +explain (costs off, verbose) +select ts::date, count(*) from slope_src group by 1; + +-- date_trunc on timestamp should use index +explain (costs off, verbose) +select date_trunc('day', ts), count(*) from slope_src group by 1; + +-- date_trunc on timestamptz should use index +explain (costs off, verbose) +select date_trunc('day', tstz), count(*) from slope_src group by 1; + +-- +-- Test arithmetic operations +-- + +-- Addition: v_int4 + 10 is increasing in v_int4 +explain (costs off, verbose) +select v_int4 + 10, count(*) from slope_src group by 1; + +-- Subtraction: v_int4 - 10 is increasing in v_int4 +explain (costs off, verbose) +select v_int4 - 10, count(*) from slope_src group by 1; + +-- Multiplication by positive constant: v_int4 * 2 is increasing +explain (costs off, verbose) +select v_int4 * 2, count(*) from slope_src group by 1; + +-- Division by positive constant: v_int4 / 2 is increasing +explain (costs off, verbose) +select v_int4 / 2, count(*) from slope_src group by 1; + +-- +-- Test decreasing functions (should use backward scan) +-- + +-- Unary minus: -v_int4 is decreasing in v_int4 +explain (costs off, verbose) +select -v_int4, count(*) from slope_src group by 1; + +-- Subtraction from constant: 1000 - v_int4 is decreasing in v_int4 +explain (costs off, verbose) +select 1000 - v_int4, count(*) from slope_src group by 1; + +-- Multiplication by negative constant: v_int4 * (-2) is decreasing +explain (costs off, verbose) +select v_int4 * (-2), count(*) from slope_src group by 1; + +-- Division by negative constant: v_int4 / (-2) is decreasing +explain (costs off, verbose) +select v_int4 / (-2), count(*) from slope_src group by 1; + +-- +-- Test ORDER BY with monotonic function +-- + +-- ORDER BY floor(v_float8) should use index +explain (costs off, verbose) +select floor(v_float8), v_float8 from slope_src order by 1 limit 10; + +-- ORDER BY -v_int4 DESC should use forward scan (decreasing + DESC = forward) +explain (costs off, verbose) +select -v_int4 from slope_src order by 1 desc limit 10; + +-- ORDER BY -v_int4 ASC should use backward scan (decreasing + ASC = backward) +explain (costs off, verbose) +select -v_int4 from slope_src order by 1 limit 10; + +-- +-- Test nested monotonic function +-- + +-- floor(floor(x)) should still use index +explain (costs off, verbose) +select floor(floor(v_float8)), count(*) from slope_src group by 1; + +-- floor(v + 1) should use index +explain (costs off, verbose) +select floor(v_float8 + 1), count(*) from slope_src group by 1; + +-- Cleanup +RESET enable_hashagg; -- 2.53.0
From 98dd8c9c2cf52fdeeea69a3de10f28973fee7314 Mon Sep 17 00:00:00 2001 From: Alexandre Felipe <[email protected]> Date: Fri, 3 Apr 2026 17:34:30 +0100 Subject: [PATCH 2/6] Optimized reverse pathkeys Instead of calling build_index_pathkeys twice (once for forward and once for backward scan direction), compute pathkeys only for the forward scan and derive backward pathkeys using reverse_pathkeys(). This removes the ScanDirection parameter from build_index_pathkeys and adds two new helper functions: - make_reversed_pathkey: reverses a single pathkey's sort direction - reverse_pathkeys: reverses a list of pathkeys This gives measurable performance improvement in the planner benchmark. Additionally, it will reduce the per-index cost of the SLOPE analysis in the upcomming commits. --- src/backend/optimizer/path/indxpath.c | 12 ++--- src/backend/optimizer/path/pathkeys.c | 68 +++++++++++++++++++++------ src/include/optimizer/paths.h | 5 +- 3 files changed, 63 insertions(+), 22 deletions(-) diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 67d9dc35f44..635e8566e98 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -918,8 +918,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_is_ordered = (index->sortopfamily != NULL); if (index_is_ordered && pathkeys_possibly_useful) { - index_pathkeys = build_index_pathkeys(root, index, - ForwardScanDirection); + index_pathkeys = build_index_pathkeys(root, index); useful_pathkeys = truncate_useless_pathkeys(root, rel, index_pathkeys); orderbyclauses = NIL; @@ -1010,13 +1009,14 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, /* * 5. If the index is ordered, a backwards scan might be interesting. + * Only consider it if we have forward pathkeys to reverse. */ - if (index_is_ordered && pathkeys_possibly_useful) + if (index_is_ordered && pathkeys_possibly_useful && index_pathkeys != NIL) { - index_pathkeys = build_index_pathkeys(root, index, - BackwardScanDirection); + List *backward_pathkeys = reverse_pathkeys(root, index_pathkeys); + useful_pathkeys = truncate_useless_pathkeys(root, rel, - index_pathkeys); + backward_pathkeys); if (useful_pathkeys != NIL) { ipath = create_index_path(root, index, diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 5eb71635d15..3e3eb720c1f 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -98,6 +98,54 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * make_reversed_pathkey + * Create a pathkey with reversed sort direction. + * + * This flips COMPARE_LT <-> COMPARE_GT and inverts nulls_first. + */ +PathKey * +make_reversed_pathkey(PlannerInfo *root, PathKey *pathkey) +{ + CompareType reversed_cmptype; + + if (pathkey->pk_cmptype == COMPARE_LT) + reversed_cmptype = COMPARE_GT; + else if (pathkey->pk_cmptype == COMPARE_GT) + reversed_cmptype = COMPARE_LT; + else + reversed_cmptype = pathkey->pk_cmptype; + + return make_canonical_pathkey(root, + pathkey->pk_eclass, + pathkey->pk_opfamily, + reversed_cmptype, + !pathkey->pk_nulls_first); +} + +/* + * reverse_pathkeys + * Create a list of pathkeys with reversed sort directions. + * + * This is useful for deriving backward index scan pathkeys from + * forward scan pathkeys without recomputing them from scratch. + */ +List * +reverse_pathkeys(PlannerInfo *root, List *pathkeys) +{ + List *result = NIL; + ListCell *lc; + + foreach(lc, pathkeys) + { + PathKey *pk = lfirst_node(PathKey, lc); + + result = lappend(result, make_reversed_pathkey(root, pk)); + } + + return result; +} + /* * append_pathkeys * Append all non-redundant PathKeys in 'source' onto 'target' and @@ -722,8 +770,8 @@ get_cheapest_parallel_safe_total_inner(List *paths) * scan using the given index. (Note that an unordered index doesn't * induce any ordering, so we return NIL.) * - * If 'scandir' is BackwardScanDirection, build pathkeys representing a - * backwards scan of the index. + * This always builds pathkeys for a forward scan of the index. For backward + * scans, the caller should use reverse_pathkeys() on the result. * * We iterate only key columns of covering indexes, since non-key columns * don't influence index ordering. The result is canonical, meaning that @@ -738,8 +786,7 @@ get_cheapest_parallel_safe_total_inner(List *paths) */ List * build_index_pathkeys(PlannerInfo *root, - IndexOptInfo *index, - ScanDirection scandir) + IndexOptInfo *index) { List *retval = NIL; ListCell *lc; @@ -767,16 +814,9 @@ build_index_pathkeys(PlannerInfo *root, /* We assume we don't need to make a copy of the tlist item */ indexkey = indextle->expr; - if (ScanDirectionIsBackward(scandir)) - { - reverse_sort = !index->reverse_sort[i]; - nulls_first = !index->nulls_first[i]; - } - else - { - reverse_sort = index->reverse_sort[i]; - nulls_first = index->nulls_first[i]; - } + /* Use the index's natural sort order (forward scan) */ + reverse_sort = index->reverse_sort[i]; + nulls_first = index->nulls_first[i]; /* * OK, try to make a canonical pathkey for this sort key. diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 8751ad7381c..7564e232e65 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -236,8 +236,9 @@ extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths, Relids required_outer, double fraction); extern Path *get_cheapest_parallel_safe_total_inner(List *paths); -extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index, - ScanDirection scandir); +extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index); +extern PathKey *make_reversed_pathkey(PlannerInfo *root, PathKey *pathkey); +extern List *reverse_pathkeys(PlannerInfo *root, List *pathkeys); extern List *build_partition_pathkeys(PlannerInfo *root, RelOptInfo *partrel, ScanDirection scandir, bool *partialkeys); extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr, -- 2.53.0
From a92b9a7cf58c20da4d56a84d961fb8d6e3af53ce Mon Sep 17 00:00:00 2001 From: Alexandre Felipe <[email protected]> Date: Fri, 3 Apr 2026 07:35:00 +0100 Subject: [PATCH 4/4] SLOPE: catalog changes Add prosupport annotations to built-in monotonic functions, enabling the SLOPE optimization to use indexes for ORDER BY f(x). Functions annotated with some monotonicity - Arithmetic: int2/4/8 and float4/8 add, subtract, multiply, divide - Unary minus: int2um, int4um, int8um, float4um, float8um - Rounding: floor, ceil (float8 and numeric variants) - Date/time: date_trunc (timestamp, timestamptz, interval) - Conversion from time samp types to date. Also adds the prosupport function entries to pg_proc.dat - arg0_asc_slope_support (OID 9954) - arg0_desc_slope_support (OID 9955) - arg1_asc_slope_support (OID 9956) - diff_slope_support (OID 9957) - addition_slope_support (OID 9958) - multiply_slope_support (OID 9959) - divide_slope_support (OID 9960) Bump catversion for catalog changes. --- src/include/catalog/catversion.h | 2 +- src/include/catalog/pg_proc.dat | 192 ++++++++++++++++++------------- 2 files changed, 113 insertions(+), 81 deletions(-) diff --git a/src/include/catalog/catversion.h b/src/include/catalog/catversion.h index 81b2bf39b3f..339117869c5 100644 --- a/src/include/catalog/catversion.h +++ b/src/include/catalog/catversion.h @@ -57,6 +57,6 @@ */ /* yyyymmddN */ -#define CATALOG_VERSION_NO 202603301 +#define CATALOG_VERSION_NO 202604011 #endif diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat index 3579cec5744..2a9c632a1be 100644 --- a/src/include/catalog/pg_proc.dat +++ b/src/include/catalog/pg_proc.dat @@ -420,8 +420,8 @@ proargtypes => 'internal oid internal int2 internal', prosrc => 'areajoinsel' }, { oid => '141', - proname => 'int4mul', prorettype => 'int4', proargtypes => 'int4 int4', - prosrc => 'int4mul' }, + proname => 'int4mul', prosupport => 'multiply_slope_support', + prorettype => 'int4', proargtypes => 'int4 int4', prosrc => 'int4mul' }, { oid => '144', proname => 'int4ne', proleakproof => 't', prorettype => 'bool', proargtypes => 'int4 int4', prosrc => 'int4ne' }, @@ -447,14 +447,14 @@ proname => 'int2ge', proleakproof => 't', prorettype => 'bool', proargtypes => 'int2 int2', prosrc => 'int2ge' }, { oid => '152', - proname => 'int2mul', prorettype => 'int2', proargtypes => 'int2 int2', - prosrc => 'int2mul' }, + proname => 'int2mul', prosupport => 'multiply_slope_support', + prorettype => 'int2', proargtypes => 'int2 int2', prosrc => 'int2mul' }, { oid => '153', - proname => 'int2div', prorettype => 'int2', proargtypes => 'int2 int2', - prosrc => 'int2div' }, + proname => 'int2div', prosupport => 'divide_slope_support', + prorettype => 'int2', proargtypes => 'int2 int2', prosrc => 'int2div' }, { oid => '154', - proname => 'int4div', prorettype => 'int4', proargtypes => 'int4 int4', - prosrc => 'int4div' }, + proname => 'int4div', prosupport => 'divide_slope_support', + prorettype => 'int4', proargtypes => 'int4 int4', prosrc => 'int4div' }, { oid => '155', proname => 'int2mod', prorettype => 'int2', proargtypes => 'int2 int2', prosrc => 'int2mod' }, @@ -513,29 +513,29 @@ proname => 'int42div', prorettype => 'int4', proargtypes => 'int4 int2', prosrc => 'int42div' }, { oid => '176', - proname => 'int2pl', prorettype => 'int2', proargtypes => 'int2 int2', - prosrc => 'int2pl' }, + proname => 'int2pl', prosupport => 'addition_slope_support', + prorettype => 'int2', proargtypes => 'int2 int2', prosrc => 'int2pl' }, { oid => '177', - proname => 'int4pl', prorettype => 'int4', proargtypes => 'int4 int4', - prosrc => 'int4pl' }, + proname => 'int4pl', prosupport => 'addition_slope_support', + prorettype => 'int4', proargtypes => 'int4 int4', prosrc => 'int4pl' }, { oid => '178', - proname => 'int24pl', prorettype => 'int4', proargtypes => 'int2 int4', - prosrc => 'int24pl' }, + proname => 'int24pl', prosupport => 'addition_slope_support', + prorettype => 'int4', proargtypes => 'int2 int4', prosrc => 'int24pl' }, { oid => '179', - proname => 'int42pl', prorettype => 'int4', proargtypes => 'int4 int2', - prosrc => 'int42pl' }, + proname => 'int42pl', prosupport => 'addition_slope_support', + prorettype => 'int4', proargtypes => 'int4 int2', prosrc => 'int42pl' }, { oid => '180', - proname => 'int2mi', prorettype => 'int2', proargtypes => 'int2 int2', - prosrc => 'int2mi' }, + proname => 'int2mi', prosupport => 'diff_slope_support', + prorettype => 'int2', proargtypes => 'int2 int2', prosrc => 'int2mi' }, { oid => '181', - proname => 'int4mi', prorettype => 'int4', proargtypes => 'int4 int4', - prosrc => 'int4mi' }, + proname => 'int4mi', prosupport => 'diff_slope_support', + prorettype => 'int4', proargtypes => 'int4 int4', prosrc => 'int4mi' }, { oid => '182', - proname => 'int24mi', prorettype => 'int4', proargtypes => 'int2 int4', - prosrc => 'int24mi' }, + proname => 'int24mi', prosupport => 'diff_slope_support', + prorettype => 'int4', proargtypes => 'int2 int4', prosrc => 'int24mi' }, { oid => '183', - proname => 'int42mi', prorettype => 'int4', proargtypes => 'int4 int2', - prosrc => 'int42mi' }, + proname => 'int42mi', prosupport => 'diff_slope_support', + prorettype => 'int4', proargtypes => 'int4 int2', prosrc => 'int42mi' }, { oid => '184', proname => 'oideq', proleakproof => 't', prorettype => 'bool', proargtypes => 'oid oid', prosrc => 'oideq' }, @@ -590,20 +590,20 @@ proname => 'float4out', prorettype => 'cstring', proargtypes => 'float4', prosrc => 'float4out' }, { oid => '202', - proname => 'float4mul', prorettype => 'float4', - proargtypes => 'float4 float4', prosrc => 'float4mul' }, + proname => 'float4mul', prosupport => 'multiply_slope_support', + prorettype => 'float4', proargtypes => 'float4 float4', prosrc => 'float4mul' }, { oid => '203', - proname => 'float4div', prorettype => 'float4', - proargtypes => 'float4 float4', prosrc => 'float4div' }, + proname => 'float4div', prosupport => 'divide_slope_support', + prorettype => 'float4', proargtypes => 'float4 float4', prosrc => 'float4div' }, { oid => '204', - proname => 'float4pl', prorettype => 'float4', proargtypes => 'float4 float4', - prosrc => 'float4pl' }, + proname => 'float4pl', prosupport => 'addition_slope_support', + prorettype => 'float4', proargtypes => 'float4 float4', prosrc => 'float4pl' }, { oid => '205', - proname => 'float4mi', prorettype => 'float4', proargtypes => 'float4 float4', - prosrc => 'float4mi' }, + proname => 'float4mi', prosupport => 'diff_slope_support', + prorettype => 'float4', proargtypes => 'float4 float4', prosrc => 'float4mi' }, { oid => '206', - proname => 'float4um', prorettype => 'float4', proargtypes => 'float4', - prosrc => 'float4um' }, + proname => 'float4um', prosupport => 'arg0_desc_slope_support', + prorettype => 'float4', proargtypes => 'float4', prosrc => 'float4um' }, { oid => '207', proname => 'float4abs', prorettype => 'float4', proargtypes => 'float4', prosrc => 'float4abs' }, @@ -618,11 +618,11 @@ proargtypes => 'float4 float4', prosrc => 'float4smaller' }, { oid => '212', - proname => 'int4um', prorettype => 'int4', proargtypes => 'int4', - prosrc => 'int4um' }, + proname => 'int4um', prosupport => 'arg0_desc_slope_support', + prorettype => 'int4', proargtypes => 'int4', prosrc => 'int4um' }, { oid => '213', - proname => 'int2um', prorettype => 'int2', proargtypes => 'int2', - prosrc => 'int2um' }, + proname => 'int2um', prosupport => 'arg0_desc_slope_support', + prorettype => 'int2', proargtypes => 'int2', prosrc => 'int2um' }, { oid => '214', descr => 'I/O', proname => 'float8in', prorettype => 'float8', proargtypes => 'cstring', @@ -631,20 +631,20 @@ proname => 'float8out', prorettype => 'cstring', proargtypes => 'float8', prosrc => 'float8out' }, { oid => '216', - proname => 'float8mul', prorettype => 'float8', - proargtypes => 'float8 float8', prosrc => 'float8mul' }, + proname => 'float8mul', prosupport => 'multiply_slope_support', + prorettype => 'float8', proargtypes => 'float8 float8', prosrc => 'float8mul' }, { oid => '217', - proname => 'float8div', prorettype => 'float8', - proargtypes => 'float8 float8', prosrc => 'float8div' }, + proname => 'float8div', prosupport => 'divide_slope_support', + prorettype => 'float8', proargtypes => 'float8 float8', prosrc => 'float8div' }, { oid => '218', - proname => 'float8pl', prorettype => 'float8', proargtypes => 'float8 float8', - prosrc => 'float8pl' }, + proname => 'float8pl', prosupport => 'addition_slope_support', + prorettype => 'float8', proargtypes => 'float8 float8', prosrc => 'float8pl' }, { oid => '219', - proname => 'float8mi', prorettype => 'float8', proargtypes => 'float8 float8', - prosrc => 'float8mi' }, + proname => 'float8mi', prosupport => 'diff_slope_support', + prorettype => 'float8', proargtypes => 'float8 float8', prosrc => 'float8mi' }, { oid => '220', - proname => 'float8um', prorettype => 'float8', proargtypes => 'float8', - prosrc => 'float8um' }, + proname => 'float8um', prosupport => 'arg0_desc_slope_support', + prorettype => 'float8', proargtypes => 'float8', prosrc => 'float8um' }, { oid => '221', proname => 'float8abs', prorettype => 'float8', proargtypes => 'float8', prosrc => 'float8abs' }, @@ -675,14 +675,14 @@ proname => 'dtrunc', prorettype => 'float8', proargtypes => 'float8', prosrc => 'dtrunc' }, { oid => '2308', descr => 'nearest integer >= value', - proname => 'ceil', prorettype => 'float8', proargtypes => 'float8', - prosrc => 'dceil' }, + proname => 'ceil', prosupport => 'arg0_asc_slope_support', + prorettype => 'float8', proargtypes => 'float8', prosrc => 'dceil' }, { oid => '2320', descr => 'nearest integer >= value', proname => 'ceiling', prorettype => 'float8', proargtypes => 'float8', prosrc => 'dceil' }, { oid => '2309', descr => 'nearest integer <= value', - proname => 'floor', prorettype => 'float8', proargtypes => 'float8', - prosrc => 'dfloor' }, + proname => 'floor', prosupport => 'arg0_asc_slope_support', + prorettype => 'float8', proargtypes => 'float8', prosrc => 'dfloor' }, { oid => '2310', descr => 'sign of value', proname => 'sign', prorettype => 'float8', proargtypes => 'float8', prosrc => 'dsign' }, @@ -1378,20 +1378,20 @@ proname => 'int8out', prorettype => 'cstring', proargtypes => 'int8', prosrc => 'int8out' }, { oid => '462', - proname => 'int8um', prorettype => 'int8', proargtypes => 'int8', - prosrc => 'int8um' }, + proname => 'int8um', prosupport => 'arg0_desc_slope_support', + prorettype => 'int8', proargtypes => 'int8', prosrc => 'int8um' }, { oid => '463', - proname => 'int8pl', prorettype => 'int8', proargtypes => 'int8 int8', - prosrc => 'int8pl' }, + proname => 'int8pl', prosupport => 'addition_slope_support', + prorettype => 'int8', proargtypes => 'int8 int8', prosrc => 'int8pl' }, { oid => '464', - proname => 'int8mi', prorettype => 'int8', proargtypes => 'int8 int8', - prosrc => 'int8mi' }, + proname => 'int8mi', prosupport => 'diff_slope_support', + prorettype => 'int8', proargtypes => 'int8 int8', prosrc => 'int8mi' }, { oid => '465', - proname => 'int8mul', prorettype => 'int8', proargtypes => 'int8 int8', - prosrc => 'int8mul' }, + proname => 'int8mul', prosupport => 'multiply_slope_support', + prorettype => 'int8', proargtypes => 'int8 int8', prosrc => 'int8mul' }, { oid => '466', - proname => 'int8div', prorettype => 'int8', proargtypes => 'int8 int8', - prosrc => 'int8div' }, + proname => 'int8div', prosupport => 'divide_slope_support', + prorettype => 'int8', proargtypes => 'int8 int8', prosrc => 'int8div' }, { oid => '467', proname => 'int8eq', proleakproof => 't', prorettype => 'bool', proargtypes => 'int8 int8', prosrc => 'int8eq' }, @@ -2498,7 +2498,8 @@ proname => 'extract', prorettype => 'numeric', proargtypes => 'text interval', prosrc => 'extract_interval' }, { oid => '1174', descr => 'convert date to timestamp with time zone', - proname => 'timestamptz', provolatile => 's', prorettype => 'timestamptz', + proname => 'timestamptz', prosupport => 'arg0_asc_slope_support', + provolatile => 's', prorettype => 'timestamptz', proargtypes => 'date', prosrc => 'date_timestamptz' }, { oid => '2711', descr => 'promote groups of 24 hours to numbers of days and promote groups of 30 days to numbers of months', @@ -2515,7 +2516,8 @@ prorettype => 'timestamptz', proargtypes => 'date time', prosrc => 'see system_functions.sql' }, { oid => '1178', descr => 'convert timestamp with time zone to date', - proname => 'date', provolatile => 's', prorettype => 'date', + proname => 'date', prosupport => 'arg0_asc_slope_support', + provolatile => 's', prorettype => 'date', proargtypes => 'timestamptz', prosrc => 'timestamptz_date' }, { oid => '1181', descr => 'age of a transaction ID, in transactions before current transaction', @@ -2595,15 +2597,16 @@ { oid => '1217', descr => 'truncate timestamp with time zone to specified units', - proname => 'date_trunc', provolatile => 's', prorettype => 'timestamptz', + proname => 'date_trunc', prosupport => 'arg1_asc_slope_support', + provolatile => 's', prorettype => 'timestamptz', proargtypes => 'text timestamptz', prosrc => 'timestamptz_trunc' }, { oid => '1284', descr => 'truncate timestamp with time zone to specified units in specified time zone', proname => 'date_trunc', prorettype => 'timestamptz', proargtypes => 'text timestamptz text', prosrc => 'timestamptz_trunc_zone' }, { oid => '1218', descr => 'truncate interval to specified units', - proname => 'date_trunc', prorettype => 'interval', - proargtypes => 'text interval', prosrc => 'interval_trunc' }, + proname => 'date_trunc', prosupport => 'arg1_asc_slope_support', + prorettype => 'interval', proargtypes => 'text interval', prosrc => 'interval_trunc' }, { oid => '1219', descr => 'increment', proname => 'int8inc', prorettype => 'int8', proargtypes => 'int8', @@ -2655,8 +2658,9 @@ proname => 'overlaps', proisstrict => 'f', prorettype => 'bool', proargtypes => 'timetz timetz timetz timetz', prosrc => 'overlaps_timetz' }, { oid => '1272', - proname => 'datetime_pl', prorettype => 'timestamp', - proargtypes => 'date time', prosrc => 'datetime_timestamp' }, + proname => 'datetime_pl', prosupport => 'addition_slope_support', + prorettype => 'timestamp', proargtypes => 'date time', + prosrc => 'datetime_timestamp' }, { oid => '1273', descr => 'extract field from time with time zone', proname => 'date_part', prorettype => 'float8', proargtypes => 'text timetz', prosrc => 'timetz_part' }, @@ -4616,14 +4620,14 @@ proname => 'trunc', prolang => 'sql', prorettype => 'numeric', proargtypes => 'numeric', prosrc => 'see system_functions.sql' }, { oid => '1711', descr => 'nearest integer >= value', - proname => 'ceil', prorettype => 'numeric', proargtypes => 'numeric', - prosrc => 'numeric_ceil' }, + proname => 'ceil', prosupport => 'arg0_asc_slope_support', + prorettype => 'numeric', proargtypes => 'numeric', prosrc => 'numeric_ceil' }, { oid => '2167', descr => 'nearest integer >= value', proname => 'ceiling', prorettype => 'numeric', proargtypes => 'numeric', prosrc => 'numeric_ceil' }, { oid => '1712', descr => 'nearest integer <= value', - proname => 'floor', prorettype => 'numeric', proargtypes => 'numeric', - prosrc => 'numeric_floor' }, + proname => 'floor', prosupport => 'arg0_asc_slope_support', + prorettype => 'numeric', proargtypes => 'numeric', prosrc => 'numeric_floor' }, { oid => '1718', proname => 'numeric_eq', prorettype => 'bool', proargtypes => 'numeric numeric', prosrc => 'numeric_eq' }, @@ -6376,8 +6380,8 @@ proname => 'time', provolatile => 's', prorettype => 'time', proargtypes => 'timestamptz', prosrc => 'timestamptz_time' }, { oid => '2020', descr => 'truncate timestamp to specified units', - proname => 'date_trunc', prorettype => 'timestamp', - proargtypes => 'text timestamp', prosrc => 'timestamp_trunc' }, + proname => 'date_trunc', prosupport => 'arg1_asc_slope_support', + prorettype => 'timestamp', proargtypes => 'text timestamp', prosrc => 'timestamp_trunc' }, { oid => '6177', descr => 'bin timestamp into specified interval', proname => 'date_bin', prorettype => 'timestamp', @@ -6395,19 +6399,24 @@ proname => 'extract', prorettype => 'numeric', proargtypes => 'text timestamp', prosrc => 'extract_timestamp' }, { oid => '2024', descr => 'convert date to timestamp', - proname => 'timestamp', prorettype => 'timestamp', proargtypes => 'date', + proname => 'timestamp', prosupport => 'arg0_asc_slope_support', + prorettype => 'timestamp', proargtypes => 'date', prosrc => 'date_timestamp' }, { oid => '2025', descr => 'convert date and time to timestamp', - proname => 'timestamp', prorettype => 'timestamp', proargtypes => 'date time', + proname => 'timestamp', prosupport => 'addition_slope_support', + prorettype => 'timestamp', proargtypes => 'date time', prosrc => 'datetime_timestamp' }, { oid => '2027', descr => 'convert timestamp with time zone to timestamp', - proname => 'timestamp', provolatile => 's', prorettype => 'timestamp', + proname => 'timestamp', prosupport => 'arg0_asc_slope_support', + provolatile => 's', prorettype => 'timestamp', proargtypes => 'timestamptz', prosrc => 'timestamptz_timestamp' }, { oid => '2028', descr => 'convert timestamp to timestamp with time zone', - proname => 'timestamptz', provolatile => 's', prorettype => 'timestamptz', + proname => 'timestamptz', prosupport => 'arg0_asc_slope_support', + provolatile => 's', prorettype => 'timestamptz', proargtypes => 'timestamp', prosrc => 'timestamp_timestamptz' }, { oid => '2029', descr => 'convert timestamp to date', - proname => 'date', prorettype => 'date', proargtypes => 'timestamp', + proname => 'date', prosupport => 'arg0_asc_slope_support', + prorettype => 'date', proargtypes => 'timestamp', prosrc => 'timestamp_date' }, { oid => '2031', proname => 'timestamp_mi', prorettype => 'interval', @@ -12785,6 +12794,29 @@ proargnames => '{schemaname,relname,statistics_schemaname,statistics_name,inherited}', prosrc => 'pg_clear_extended_stats' }, +# monotonic support functions for scalar function ordering optimization (SLOPE) +{ oid => '9954', descr => 'planner support for ascending slope in arg 0', + proname => 'arg0_asc_slope_support', prorettype => 'internal', + proargtypes => 'internal', prosrc => 'arg0_asc_slope_support' }, +{ oid => '9955', descr => 'planner support for descending slope in arg 0', + proname => 'arg0_desc_slope_support', prorettype => 'internal', + proargtypes => 'internal', prosrc => 'arg0_desc_slope_support' }, +{ oid => '9956', descr => 'planner support for ascending slope in arg 1', + proname => 'arg1_asc_slope_support', prorettype => 'internal', + proargtypes => 'internal', prosrc => 'arg1_asc_slope_support' }, +{ oid => '9957', descr => 'planner support for diff slope (asc arg0, desc arg1)', + proname => 'diff_slope_support', prorettype => 'internal', + proargtypes => 'internal', prosrc => 'diff_slope_support' }, +{ oid => '9958', descr => 'planner support for addition slope (asc both args)', + proname => 'addition_slope_support', prorettype => 'internal', + proargtypes => 'internal', prosrc => 'addition_slope_support' }, +{ oid => '9959', descr => 'planner support for multiply slope (sign-dependent)', + proname => 'multiply_slope_support', prorettype => 'internal', + proargtypes => 'internal', prosrc => 'multiply_slope_support' }, +{ oid => '9960', descr => 'planner support for divide slope (sign-dependent)', + proname => 'divide_slope_support', prorettype => 'internal', + proargtypes => 'internal', prosrc => 'divide_slope_support' }, + # AIO related functions { oid => '6399', descr => 'information about in-progress asynchronous IOs', proname => 'pg_get_aios', prorows => '100', proretset => 't', -- 2.53.0
From ddb9a75d3cca21e8515ef4942bf943544faf3202 Mon Sep 17 00:00:00 2001 From: Alexandre Felipe <[email protected]> Date: Fri, 3 Apr 2026 20:01:39 +0100 Subject: [PATCH 3/6] SLOPE: prosupport definitions Add support functions to describe monotonicy of buildint functions These functions will be referenced by pg_proc entries in a subsequent commit. New prosupport functions: - arg0_asc_slope_support: f(x, ...) is increasing in x - arg0_desc_slope_support: f(x, ...) is decreasing in x - arg1_asc_slope_support: f(a, x, ...) is increasing in x - diff_slope_support: x - y is increasing in x, decreasing in y - addition_slope_support: x + y is increasing in both args - multiply_slope_support: x * c or c * x depends on sign of constant c - divide_slope_support: x / c depends on sign of constant c Also adds SupportRequestMonotonic to supportnodes.h for the planner to query monotonicity information from prosupport functions. --- src/backend/utils/adt/misc.c | 294 +++++++++++++++++++++++++++++++ src/include/nodes/supportnodes.h | 25 +++ 2 files changed, 319 insertions(+) diff --git a/src/backend/utils/adt/misc.c b/src/backend/utils/adt/misc.c index c033e68ba15..19b7b48e80a 100644 --- a/src/backend/utils/adt/misc.c +++ b/src/backend/utils/adt/misc.c @@ -32,6 +32,7 @@ #include "funcapi.h" #include "miscadmin.h" #include "nodes/miscnodes.h" +#include "nodes/supportnodes.h" #include "parser/parse_type.h" #include "parser/scansup.h" #include "pgstat.h" @@ -43,6 +44,7 @@ #include "utils/builtins.h" #include "utils/fmgroids.h" #include "utils/lsyscache.h" +#include "utils/numeric.h" #include "utils/ruleutils.h" #include "utils/syscache.h" #include "utils/timestamp.h" @@ -1095,3 +1097,295 @@ any_value_transfn(PG_FUNCTION_ARGS) { PG_RETURN_DATUM(PG_GETARG_DATUM(0)); } + +/* + * monotonic_slope_support + * Generic helper for prosupport functions that declare monotonic slopes. + * + * If the request is a SupportRequestMonotonic, fills in nslopes and slopes + * and returns the request pointer. Otherwise returns NULL. + */ +static Datum +monotonic_slope_support(Node *rawreq, int nslopes, + const MonotonicFunction *slopes) +{ + if (IsA(rawreq, SupportRequestMonotonic)) + { + SupportRequestMonotonic *req = (SupportRequestMonotonic *) rawreq; + + req->nslopes = nslopes; + req->slopes = slopes; + return PointerGetDatum(req); + } + + return PointerGetDatum(NULL); +} + +/* + * arg0_asc_slope_support + * Prosupport: f(x, ...) is monotonically increasing in x. + */ +Datum +arg0_asc_slope_support(PG_FUNCTION_ARGS) +{ + static const MonotonicFunction pattern[1] = {MONOTONICFUNC_INCREASING}; + + return monotonic_slope_support((Node *) PG_GETARG_POINTER(0), + lengthof(pattern), pattern); +} + +/* + * arg0_desc_slope_support + * Prosupport: f(x, ...) is monotonically decreasing in x. + */ +Datum +arg0_desc_slope_support(PG_FUNCTION_ARGS) +{ + static const MonotonicFunction pattern[1] = {MONOTONICFUNC_DECREASING}; + + return monotonic_slope_support((Node *) PG_GETARG_POINTER(0), + lengthof(pattern), pattern); +} + +/* + * arg1_asc_slope_support + * Prosupport: f(a, x, ...) is monotonically increasing in x. + */ +Datum +arg1_asc_slope_support(PG_FUNCTION_ARGS) +{ + static const MonotonicFunction pattern[2] = {MONOTONICFUNC_NONE, + MONOTONICFUNC_INCREASING}; + + return monotonic_slope_support((Node *) PG_GETARG_POINTER(0), + lengthof(pattern), pattern); +} + +/* + * diff_slope_support + * Prosupport: f(x, y) = x - y is increasing in x, decreasing in y. + */ +Datum +diff_slope_support(PG_FUNCTION_ARGS) +{ + static const MonotonicFunction pattern[2] = {MONOTONICFUNC_INCREASING, + MONOTONICFUNC_DECREASING}; + + return monotonic_slope_support((Node *) PG_GETARG_POINTER(0), + lengthof(pattern), pattern); +} + +/* + * addition_slope_support + * Prosupport: f(x, y) = x + y is increasing in both x and y. + */ +Datum +addition_slope_support(PG_FUNCTION_ARGS) +{ + static const MonotonicFunction pattern[2] = {MONOTONICFUNC_INCREASING, + MONOTONICFUNC_INCREASING}; + + return monotonic_slope_support((Node *) PG_GETARG_POINTER(0), + lengthof(pattern), pattern); +} + +/* + * get_const_sign + * Helper to determine the sign of a numeric constant. + * Returns 1 for positive, -1 for negative, 0 for zero or unknown. + */ +static int +get_const_sign(Const *constval) +{ + if (constval->constisnull) + return 0; + + switch (constval->consttype) + { + case INT2OID: + { + int16 val = DatumGetInt16(constval->constvalue); + + return (val > 0) ? 1 : (val < 0) ? -1 : 0; + } + case INT4OID: + { + int32 val = DatumGetInt32(constval->constvalue); + + return (val > 0) ? 1 : (val < 0) ? -1 : 0; + } + case INT8OID: + { + int64 val = DatumGetInt64(constval->constvalue); + + return (val > 0) ? 1 : (val < 0) ? -1 : 0; + } + case FLOAT4OID: + { + float4 val = DatumGetFloat4(constval->constvalue); + + if (isnan(val) || val == 0.0f) + return 0; + return (val > 0.0f) ? 1 : -1; + } + case FLOAT8OID: + { + float8 val = DatumGetFloat8(constval->constvalue); + + if (isnan(val) || val == 0.0) + return 0; + return (val > 0.0) ? 1 : -1; + } + case NUMERICOID: + { + Numeric num = DatumGetNumeric(constval->constvalue); + Datum result; + Numeric sign_num; + int sign; + + if (numeric_is_nan(num) || numeric_is_inf(num)) + return 0; + + result = DirectFunctionCall1(numeric_sign, NumericGetDatum(num)); + sign_num = DatumGetNumeric(result); + sign = numeric_int4_safe(sign_num, NULL); + return sign; + } + default: + return 0; + } +} + +/* + * multiply_slope_support + * Prosupport: x * c is increasing if c > 0, decreasing if c < 0. + * Similarly for c * x. + * + * For multiplication, the monotonicity depends on the sign of the constant: + * - x * positive_const: increasing in x + * - x * negative_const: decreasing in x + * - x * 0: not monotonic (constant result) + */ +Datum +multiply_slope_support(PG_FUNCTION_ARGS) +{ + Node *rawreq = (Node *) PG_GETARG_POINTER(0); + + if (IsA(rawreq, SupportRequestMonotonic)) + { + SupportRequestMonotonic *req = (SupportRequestMonotonic *) rawreq; + List *args; + Node *arg0; + Node *arg1; + Const *constval = NULL; + int var_argno = -1; + int sign; + + if (IsA(req->expr, FuncExpr)) + args = ((FuncExpr *) req->expr)->args; + else if (IsA(req->expr, OpExpr)) + args = ((OpExpr *) req->expr)->args; + else + PG_RETURN_POINTER(NULL); + + if (list_length(args) != 2) + PG_RETURN_POINTER(NULL); + + arg0 = (Node *) linitial(args); + arg1 = (Node *) lsecond(args); + + if (IsA(arg0, Const)) + { + constval = (Const *) arg0; + var_argno = 1; + } + else if (IsA(arg1, Const)) + { + constval = (Const *) arg1; + var_argno = 0; + } + else + PG_RETURN_POINTER(NULL); + + sign = get_const_sign(constval); + if (sign == 0) + PG_RETURN_POINTER(NULL); + + { + static const MonotonicFunction asc_first[2] = {MONOTONICFUNC_INCREASING, + MONOTONICFUNC_NONE}; + static const MonotonicFunction asc_second[2] = {MONOTONICFUNC_NONE, + MONOTONICFUNC_INCREASING}; + static const MonotonicFunction desc_first[2] = {MONOTONICFUNC_DECREASING, + MONOTONICFUNC_NONE}; + static const MonotonicFunction desc_second[2] = {MONOTONICFUNC_NONE, + MONOTONICFUNC_DECREASING}; + + if (var_argno == 0) + req->slopes = (sign > 0) ? asc_first : desc_first; + else + req->slopes = (sign > 0) ? asc_second : desc_second; + req->nslopes = 2; + PG_RETURN_POINTER(req); + } + } + + PG_RETURN_POINTER(NULL); +} + +/* + * divide_slope_support + * Prosupport: x / c is increasing if c > 0, decreasing if c < 0. + * + * Division by a constant has the same monotonicity as multiplication: + * - x / positive_const: increasing in x + * - x / negative_const: decreasing in x + * - x / 0: undefined (not monotonic) + */ +Datum +divide_slope_support(PG_FUNCTION_ARGS) +{ + Node *rawreq = (Node *) PG_GETARG_POINTER(0); + + if (IsA(rawreq, SupportRequestMonotonic)) + { + SupportRequestMonotonic *req = (SupportRequestMonotonic *) rawreq; + List *args; + Node *arg1; + Const *constval; + int sign; + + if (IsA(req->expr, FuncExpr)) + args = ((FuncExpr *) req->expr)->args; + else if (IsA(req->expr, OpExpr)) + args = ((OpExpr *) req->expr)->args; + else + PG_RETURN_POINTER(NULL); + + if (list_length(args) != 2) + PG_RETURN_POINTER(NULL); + + arg1 = (Node *) lsecond(args); + + if (!IsA(arg1, Const)) + PG_RETURN_POINTER(NULL); + + constval = (Const *) arg1; + sign = get_const_sign(constval); + if (sign == 0) + PG_RETURN_POINTER(NULL); + + { + static const MonotonicFunction asc_pattern[2] = {MONOTONICFUNC_INCREASING, + MONOTONICFUNC_NONE}; + static const MonotonicFunction desc_pattern[2] = {MONOTONICFUNC_DECREASING, + MONOTONICFUNC_NONE}; + + req->slopes = (sign > 0) ? asc_pattern : desc_pattern; + req->nslopes = 2; + PG_RETURN_POINTER(req); + } + } + + PG_RETURN_POINTER(NULL); +} diff --git a/src/include/nodes/supportnodes.h b/src/include/nodes/supportnodes.h index 132a2bcd8af..106a369e1cc 100644 --- a/src/include/nodes/supportnodes.h +++ b/src/include/nodes/supportnodes.h @@ -445,4 +445,29 @@ typedef struct SupportRequestModifyInPlace int paramid; /* ID of Param(s) representing variable */ } SupportRequestModifyInPlace; +/* ---------- + * SupportRequestMonotonic: request monotonicity information for SLOPE + * + * This allows the planner to use an index on 'x' to satisfy ORDER BY f(x) + * when f is monotonic. The support function fills in the slopes array + * to indicate the monotonicity of each argument. + * + * 'expr' is the FuncExpr or OpExpr being analyzed. + * 'nslopes' points to a MonotonicFunction array (one per argument up to + * nslopes). Arguments beyond nslopes are treated as MONOTONICFUNC_NONE. + * Return the request pointer on success, or NULL if not monotonic. + * ---------- + */ +typedef struct SupportRequestMonotonic +{ + NodeTag type; + + /* Input fields: */ + Node *expr; /* FuncExpr or OpExpr */ + + /* Output fields (set by prosupport function): */ + int nslopes; /* number of slopes in array */ + const MonotonicFunction *slopes; /* array of slopes, one per arg */ +} SupportRequestMonotonic; + #endif /* SUPPORTNODES_H */ -- 2.53.0
