I noticed that doc contains a query with EXPLAIN output for an
Incremental Sort plan, and we should add new line with Estimated Groups.
I added v3-patch with it.
--
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/
From e46eb01ac1834b82dd765c0106f2e7db8081fa8d Mon Sep 17 00:00:00 2001
From: Ilia Evdokimov <[email protected]>
Date: Wed, 29 Jul 2026 13:04:32 +0300
Subject: [PATCH v3] 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.
---
doc/src/sgml/perform.sgml | 1 +
src/backend/commands/explain.c | 5 +++++
src/backend/optimizer/path/costsize.c | 15 ++++++++++++---
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 ++-
8 files changed, 30 insertions(+), 7 deletions(-)
diff --git a/doc/src/sgml/perform.sgml b/doc/src/sgml/perform.sgml
index 604e8578a8d..ea8da01b779 100644
--- a/doc/src/sgml/perform.sgml
+++ b/doc/src/sgml/perform.sgml
@@ -325,6 +325,7 @@ EXPLAIN SELECT * FROM tenk1 ORDER BY hundred, ten LIMIT 100;
-> Incremental Sort (cost=19.35..2033.39 rows=10000 width=244)
Sort Key: hundred, ten
Presorted Key: hundred
+ Estimated Groups: 100
-> Index Scan using tenk1_hundred on tenk1 (cost=0.29..1574.20 rows=10000 width=244)
</screen>
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index a40d03d35f3..f223c12f294 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->numGroups, 0, es);
+
if (!es->analyze)
return;
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index ac523ecf9a8..f01b2c93c9d 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -2046,6 +2046,9 @@ cost_tuplesort(Cost *startup_cost, Cost *run_cost,
* 'presorted_keys' is the number of leading pathkeys by which the input path
* is sorted.
*
+ * If p_numGroups is not NULL, *p_numGroups is set to the estimated number of
+ * sort groups (groups of tuples sharing equal presorted-key values).
+ *
* We estimate the number of groups into which the relation is divided by the
* leading pathkeys, and then calculate the cost of sorting a single group
* with tuplesort using cost_tuplesort().
@@ -2056,7 +2059,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,
+ Cardinality *p_numGroups)
{
Cost startup_cost,
run_cost,
@@ -2172,6 +2176,9 @@ cost_incremental_sort(Path *path,
*/
run_cost += 2.0 * cpu_tuple_cost * input_groups;
+ if (p_numGroups)
+ *p_numGroups = input_groups;
+
path->rows = input_tuples;
/*
@@ -2407,7 +2414,8 @@ cost_append(AppendPath *apath, PlannerInfo *root)
subpath->pathtarget->width,
0.0,
work_mem,
- apath->limit_tuples);
+ apath->limit_tuples,
+ NULL);
}
else
{
@@ -3850,7 +3858,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 2c696ea0268..3029efe9872 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -2073,6 +2073,7 @@ create_incrementalsort_plan(PlannerInfo *root, IncrementalSortPath *best_path,
best_path->nPresortedCols);
copy_generic_path_info(&plan->sort.plan, (Path *) best_path);
+ plan->numGroups = best_path->numGroups;
return plan;
}
@@ -5468,7 +5469,8 @@ label_incrementalsort_with_costsize(PlannerInfo *root, IncrementalSort *plan,
lefttree->plan_width,
0.0,
work_mem,
- limit_tuples);
+ limit_tuples,
+ &plan->numGroups);
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 3875e3dd571..a8dcad72958 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->numGroups);
sort->nPresortedCols = presorted_keys;
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 27a2c6815b7..185e2fb8761 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 */
+ Cardinality numGroups; /* estimated number of groups */
} IncrementalSortPath;
/*
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index b880ce0f4be..781651693eb 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -1171,6 +1171,8 @@ typedef struct IncrementalSort
Sort sort;
/* number of presorted columns */
int nPresortedCols;
+ /* estimated number of groups (groups with equal presorted keys) */
+ Cardinality numGroups;
} IncrementalSort;
/* ---------------
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index bda3f1690c0..9d571e513c6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -118,7 +118,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,
+ Cardinality *p_numGroups);
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
