Hi hackers,
In [0], a question was raised whether we should expose IncrementalSort
group estimation in EXPLAIN, as we did for Memoize. Knowing the
estimated number of groups helps understand why the planner chose
IncrementalSort whether a bad estimate is to blame for a sub-optimal plan.
Example of EXPLAIN:
```
CREATE TABLE t (a int, b int, c int);
CREATE INDEX ON t (a);
INSERT INTO t SELECT i % 100, (random() * 1000)::int, (random() *
1000)::int FROM generate_series(1, 100000) i;
ANALYZE t;
SET enable_seqscan = off;
EXPLAIN ANALYZE SELECT * FROM t ORDER BY a, b;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Incremental Sort (cost=90.80..10302.90 rows=100000 width=12) (actual
time=6.715..29.592 rows=100000.00 loops=1)
Sort Key: a, b
Presorted Key: a
*Estimated Groups: 100*
Full-sort Groups: 100 Sort Method: quicksort Average Memory: 27kB
Peak Memory: 27kB
Pre-sorted Groups: 100 Sort Method: quicksort Average Memory:
56kB Peak Memory: 56kB
Buffers: shared hit=54201 dirtied=1 written=1
-> Index Scan using t_a_idx on t (cost=0.29..4068.01 rows=100000
width=12) (actual time=0.346..20.403 rows=100000.00 loops=1)
Index Searches: 1
Buffers: shared hit=54201 dirtied=1 written=1
Planning:
Buffers: shared hit=21
Planning Time: 0.411 ms
Execution Time: 30.530 ms
(14 rows)
```
Thoughts?
[0]:
https://www.postgresql.org/message-id/6642af90-561c-4f0c-9d5b-7e288e6e7f84%40gmail.com
--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/
From d3a5b3116653582a2f90c750d54869709c012585 Mon Sep 17 00:00:00 2001
From: Ilia Evdokimov <[email protected]>
Date: Wed, 10 Jun 2026 18:35:16 +0300
Subject: [PATCH v1] Show estimated number of groups for IncrementalSort in
EXPLAIN
IncrementalSort cost heavily depends on the estimated number of groups
with equal presorted key values. A bad estimate can cause the planner
to choose IncrementalSort over Sort even when it would actually be
slower, with no visible indication of why.
---
src/backend/commands/explain.c | 5 +++++
src/backend/optimizer/path/costsize.c | 12 +++++++++---
src/backend/optimizer/plan/createplan.c | 4 +++-
src/backend/optimizer/util/pathnode.c | 6 ++++--
src/include/nodes/pathnodes.h | 1 +
src/include/nodes/plannodes.h | 2 ++
src/include/optimizer/cost.h | 3 ++-
7 files changed, 26 insertions(+), 7 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index 112c17b0d64..11d2b06bcaa 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -3306,11 +3306,16 @@ static void
show_incremental_sort_info(IncrementalSortState *incrsortstate,
ExplainState *es)
{
+ IncrementalSort *plan = (IncrementalSort *) incrsortstate->ss.ps.plan;
IncrementalSortGroupInfo *fullsortGroupInfo;
IncrementalSortGroupInfo *prefixsortGroupInfo;
fullsortGroupInfo = &incrsortstate->incsort_info.fullsortGroupInfo;
+ if (es->costs)
+ ExplainPropertyFloat("Estimated Groups", NULL,
+ plan->est_input_groups, 0, es);
+
if (!es->analyze)
return;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 1c575e56ff6..080fab3686b 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2055,7 +2055,8 @@ cost_incremental_sort(Path *path,
int input_disabled_nodes,
Cost input_startup_cost, Cost input_total_cost,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
- double limit_tuples)
+ double limit_tuples,
+ double *p_input_groups)
{
Cost startup_cost,
run_cost,
@@ -2171,6 +2172,9 @@ cost_incremental_sort(Path *path,
*/
run_cost += 2.0 * cpu_tuple_cost * input_groups;
+ if (p_input_groups)
+ *p_input_groups = input_groups;
+
path->rows = input_tuples;
/*
@@ -2406,7 +2410,8 @@ cost_append(AppendPath *apath, PlannerInfo *root)
subpath->pathtarget->width,
0.0,
work_mem,
- apath->limit_tuples);
+ apath->limit_tuples,
+ NULL);
}
else
{
@@ -3827,7 +3832,8 @@ initial_cost_mergejoin(PlannerInfo *root, JoinCostWorkspace *workspace,
outer_path->pathtarget->width,
0.0,
work_mem,
- -1.0);
+ -1.0,
+ NULL);
}
else
{
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index de6a183da79..5c5791b4f2f 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -2067,6 +2067,7 @@ create_incrementalsort_plan(PlannerInfo *root, IncrementalSortPath *best_path,
best_path->nPresortedCols);
copy_generic_path_info(&plan->sort.plan, (Path *) best_path);
+ plan->est_input_groups = best_path->est_input_groups;
return plan;
}
@@ -5441,7 +5442,8 @@ label_incrementalsort_with_costsize(PlannerInfo *root, IncrementalSort *plan,
lefttree->plan_width,
0.0,
work_mem,
- limit_tuples);
+ limit_tuples,
+ &plan->est_input_groups);
plan->sort.plan.startup_cost = sort_path.startup_cost;
plan->sort.plan.total_cost = sort_path.total_cost;
plan->sort.plan.plan_rows = lefttree->plan_rows;
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 73518c8f870..665e8859a28 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1605,7 +1605,8 @@ create_merge_append_path(PlannerInfo *root,
subpath->pathtarget->width,
0.0,
work_mem,
- pathnode->limit_tuples);
+ pathnode->limit_tuples,
+ NULL);
}
else
{
@@ -2883,7 +2884,8 @@ create_incremental_sort_path(PlannerInfo *root,
subpath->rows,
subpath->pathtarget->width,
0.0, /* XXX comparison_cost shouldn't be 0? */
- work_mem, limit_tuples);
+ work_mem, limit_tuples,
+ &sort->est_input_groups);
sort->nPresortedCols = presorted_keys;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 27a2c6815b7..abfc3c9aad6 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -2548,6 +2548,7 @@ typedef struct IncrementalSortPath
{
SortPath spath;
int nPresortedCols; /* number of presorted columns */
+ double est_input_groups; /* estimated number of groups */
} IncrementalSortPath;
/*
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 14a1dfed2b9..49e66965fe6 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -1169,6 +1169,8 @@ typedef struct IncrementalSort
Sort sort;
/* number of presorted columns */
int nPresortedCols;
+ /* estimated number of groups (groups with equal presorted keys) */
+ double est_input_groups;
} IncrementalSort;
/* ---------------
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index f2fd5d31507..8fa0b0ecad7 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -117,7 +117,8 @@ extern void cost_incremental_sort(Path *path,
int input_disabled_nodes,
Cost input_startup_cost, Cost input_total_cost,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
- double limit_tuples);
+ double limit_tuples,
+ double *p_input_groups);
extern void cost_append(AppendPath *apath, PlannerInfo *root);
extern void cost_merge_append(Path *path, PlannerInfo *root,
List *pathkeys, int n_streams,
--
2.34.1
