From: Andrei Lepikhov <lepihov@gmail.com>
To: pgsql-bugs@lists.postgresql.org <pgsql-bugs@lists.postgresql.org>
To: Tomas Vondra <tomas@vondra.me>
Subject: Incorrect calculation of path fraction value in MergeAppend
Date: Tue, 29 Apr 2025 13:14:39 +0200
Message-ID: <3ca271fa-ca5c-458c-8934-eb148622b270@gmail.com> (raw)
Hi,
Commit 6b94e7a has added a "fractional" strategy to the merge join path
search scope. But as I see it incorrectly calculates tuple_fraction
value. Let's see one of the regression tests' queries:
EXPLAIN (COSTS OFF)
SELECT x.id, y.id FROM fract_t x LEFT JOIN fract_t y
USING (id) ORDER BY x.id DESC LIMIT 10;
It uses NestedLoop with parameterised inner scan as a subplan of
MergeAppend. Overall cost is:
Limit (cost=1.11..4.86 rows=10 width=16)
Let's reduce the LIMIT a little:
EXPLAIN (COSTS OFF)
SELECT x.id, y.id FROM fract_t x LEFT JOIN fract_t y
USING (id) ORDER BY x.id DESC LIMIT 2;
There, the query plan uses plain NestLoop node and overall cost
significantly increases:
Limit (cost=0.56..30.70 rows=2 width=16)
The origin problem lies in the following code line:
path_fraction = (1.0 / root->tuple_fraction);
Building startup, total and fractional MergeAppends, the optimiser puts
off the 'fractional' way because it has built for a 50% limit (uses
MergeJoin with high startup cost) and chooses a startup-optimal path
(built upon plain NestLoops) that is better than the total one.
Instead, the path_fraction value must be corrected when
root->tuple_fraction contains the absolute value of tuples. See the
patch in the attachment.
I report this issue into the bugs mailing list because it might cause
some 'enigmatic' performance slowdowns I have heard about (but have no
proofs) and may need back-patching.
--
regards, Andrei Lepikhov
Attachments:
[text/x-patch] v0-0001-Fix-tuple_fraction-calculation-for-merge-append-f.patch (3.1K, ../3ca271fa-ca5c-458c-8934-eb148622b270@gmail.com/2-v0-0001-Fix-tuple_fraction-calculation-for-merge-append-f.patch)
download | inline diff:
From 5abcae937f3b9e9cc5ea10721ce0d0a61f917e84 Mon Sep 17 00:00:00 2001
From: "Andrei V. Lepikhov" <lepihov@gmail.com>
Date: Tue, 29 Apr 2025 12:54:59 +0200
Subject: [PATCH v0] Fix tuple_fraction calculation for merge append fractional
path
---
src/backend/optimizer/path/allpaths.c | 6 +++++-
src/test/regress/expected/partition_join.out | 18 ++++++++++++++++++
src/test/regress/sql/partition_join.sql | 3 +++
3 files changed, 26 insertions(+), 1 deletion(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex 905250b3325..543550a9378 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -1891,7 +1891,11 @@ generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
*/
if (root->tuple_fraction > 0)
{
- double path_fraction = (1.0 / root->tuple_fraction);+ double path_fraction = root->tuple_fraction;++ /* Convert absolute limit to a path fraction */+ if (path_fraction >= 1.)+ path_fraction /= childrel->rows;
cheapest_fractional =
get_cheapest_fractional_path_for_pathkeys(childrel->pathlist,
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.outindex 6101c8c7cf1..d5368186caa 100644--- a/src/test/regress/expected/partition_join.out+++ b/src/test/regress/expected/partition_join.out@@ -5260,6 +5260,24 @@ SELECT x.id, y.id FROM fract_t x LEFT JOIN fract_t y USING (id) ORDER BY x.id DE
Index Cond: (id = x_2.id)
(11 rows)
+EXPLAIN (COSTS OFF) -- Should use NestLoop with parameterised inner scan+SELECT x.id, y.id FROM fract_t x LEFT JOIN fract_t y USING (id)+ORDER BY x.id DESC LIMIT 2;+ QUERY PLAN +--------------------------------------------------------------------------------+ Limit+ -> Merge Append+ Sort Key: x.id DESC+ -> Nested Loop Left Join+ -> Index Only Scan Backward using fract_t0_pkey on fract_t0 x_1+ -> Index Only Scan using fract_t0_pkey on fract_t0 y_1+ Index Cond: (id = x_1.id)+ -> Nested Loop Left Join+ -> Index Only Scan Backward using fract_t1_pkey on fract_t1 x_2+ -> Index Only Scan using fract_t1_pkey on fract_t1 y_2+ Index Cond: (id = x_2.id)+(11 rows)+
--
-- Test Append's fractional paths
--
diff --git a/src/test/regress/sql/partition_join.sql b/src/test/regress/sql/partition_join.sqlindex b76c5451001..30f15ee9acb 100644--- a/src/test/regress/sql/partition_join.sql+++ b/src/test/regress/sql/partition_join.sql@@ -1224,6 +1224,9 @@ SELECT x.id, y.id FROM fract_t x LEFT JOIN fract_t y USING (id) ORDER BY x.id AS
EXPLAIN (COSTS OFF)
SELECT x.id, y.id FROM fract_t x LEFT JOIN fract_t y USING (id) ORDER BY x.id DESC LIMIT 10;
+EXPLAIN (COSTS OFF) -- Should use NestLoop with parameterised inner scan+SELECT x.id, y.id FROM fract_t x LEFT JOIN fract_t y USING (id)+ORDER BY x.id DESC LIMIT 2;
--
-- Test Append's fractional paths
--
2.39.5
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-bugs@postgresql.org
Cc: lepihov@gmail.com, pgsql-bugs@lists.postgresql.org, tomas@vondra.me
Subject: Re: Incorrect calculation of path fraction value in MergeAppend
In-Reply-To: <3ca271fa-ca5c-458c-8934-eb148622b270@gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox