Content-Type: multipart/mixed; boundary="------------tZ5X81QhmMorhWosVkpeESGj"
Message-ID: <3ca271fa-ca5c-458c-8934-eb148622b270@gmail.com>
Date: Tue, 29 Apr 2025 13:14:39 +0200
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
To: "pgsql-bugs@lists.postgresql.org" <pgsql-bugs@lists.postgresql.org>,
 Tomas Vondra <tomas@vondra.me>
Content-Language: en-AU
From: Andrei Lepikhov <lepihov@gmail.com>
Subject: Incorrect calculation of path fraction value in MergeAppend
Archived-At: 
 <https://www.postgresql.org/message-id/3ca271fa-ca5c-458c-8934-eb148622b270%40gmail.com>
Precedence: bulk

This is a multi-part message in MIME format.
--------------tZ5X81QhmMorhWosVkpeESGj
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

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

--------------tZ5X81QhmMorhWosVkpeESGj
Content-Type: text/x-patch; charset=UTF-8;
 name="v0-0001-Fix-tuple_fraction-calculation-for-merge-append-f.patch"
Content-Disposition: attachment;
 filename*0="v0-0001-Fix-tuple_fraction-calculation-for-merge-append-f.pa";
 filename*1="tch"
Content-Transfer-Encoding: base64

RnJvbSA1YWJjYWU5MzdmM2I5ZTljYzVlYTEwNzIxY2UwZDBhNjFmOTE3ZTg0IE1vbiBTZXAg
MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiAiQW5kcmVpIFYuIExlcGlraG92IiA8bGVwaWhvdkBn
bWFpbC5jb20+CkRhdGU6IFR1ZSwgMjkgQXByIDIwMjUgMTI6NTQ6NTkgKzAyMDAKU3ViamVj
dDogW1BBVENIIHYwXSBGaXggdHVwbGVfZnJhY3Rpb24gY2FsY3VsYXRpb24gZm9yIG1lcmdl
IGFwcGVuZCBmcmFjdGlvbmFsCiBwYXRoCgotLS0KIHNyYy9iYWNrZW5kL29wdGltaXplci9w
YXRoL2FsbHBhdGhzLmMgICAgICAgIHwgIDYgKysrKystCiBzcmMvdGVzdC9yZWdyZXNzL2V4
cGVjdGVkL3BhcnRpdGlvbl9qb2luLm91dCB8IDE4ICsrKysrKysrKysrKysrKysrKwogc3Jj
L3Rlc3QvcmVncmVzcy9zcWwvcGFydGl0aW9uX2pvaW4uc3FsICAgICAgfCAgMyArKysKIDMg
ZmlsZXMgY2hhbmdlZCwgMjYgaW5zZXJ0aW9ucygrKSwgMSBkZWxldGlvbigtKQoKZGlmZiAt
LWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2FsbHBhdGhzLmMgYi9zcmMvYmFj
a2VuZC9vcHRpbWl6ZXIvcGF0aC9hbGxwYXRocy5jCmluZGV4IDkwNTI1MGIzMzI1Li41NDM1
NTBhOTM3OCAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvYWxscGF0
aHMuYworKysgYi9zcmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9hbGxwYXRocy5jCkBAIC0x
ODkxLDcgKzE4OTEsMTEgQEAgZ2VuZXJhdGVfb3JkZXJlZGFwcGVuZF9wYXRocyhQbGFubmVy
SW5mbyAqcm9vdCwgUmVsT3B0SW5mbyAqcmVsLAogCQkJICovCiAJCQlpZiAocm9vdC0+dHVw
bGVfZnJhY3Rpb24gPiAwKQogCQkJewotCQkJCWRvdWJsZQkJcGF0aF9mcmFjdGlvbiA9ICgx
LjAgLyByb290LT50dXBsZV9mcmFjdGlvbik7CisJCQkJZG91YmxlCQlwYXRoX2ZyYWN0aW9u
ID0gcm9vdC0+dHVwbGVfZnJhY3Rpb247CisKKwkJCQkvKiBDb252ZXJ0IGFic29sdXRlIGxp
bWl0IHRvIGEgcGF0aCBmcmFjdGlvbiAqLworCQkJCWlmIChwYXRoX2ZyYWN0aW9uID49IDEu
KQorCQkJCQlwYXRoX2ZyYWN0aW9uIC89IGNoaWxkcmVsLT5yb3dzOwogCiAJCQkJY2hlYXBl
c3RfZnJhY3Rpb25hbCA9CiAJCQkJCWdldF9jaGVhcGVzdF9mcmFjdGlvbmFsX3BhdGhfZm9y
X3BhdGhrZXlzKGNoaWxkcmVsLT5wYXRobGlzdCwKZGlmZiAtLWdpdCBhL3NyYy90ZXN0L3Jl
Z3Jlc3MvZXhwZWN0ZWQvcGFydGl0aW9uX2pvaW4ub3V0IGIvc3JjL3Rlc3QvcmVncmVzcy9l
eHBlY3RlZC9wYXJ0aXRpb25fam9pbi5vdXQKaW5kZXggNjEwMWM4YzdjZjEuLmQ1MzY4MTg2
Y2FhIDEwMDY0NAotLS0gYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL3BhcnRpdGlvbl9q
b2luLm91dAorKysgYi9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL3BhcnRpdGlvbl9qb2lu
Lm91dApAQCAtNTI2MCw2ICs1MjYwLDI0IEBAIFNFTEVDVCB4LmlkLCB5LmlkIEZST00gZnJh
Y3RfdCB4IExFRlQgSk9JTiBmcmFjdF90IHkgVVNJTkcgKGlkKSBPUkRFUiBCWSB4LmlkIERF
CiAgICAgICAgICAgICAgICAgICAgICBJbmRleCBDb25kOiAoaWQgPSB4XzIuaWQpCiAoMTEg
cm93cykKIAorRVhQTEFJTiAoQ09TVFMgT0ZGKSAtLSBTaG91bGQgdXNlIE5lc3RMb29wIHdp
dGggcGFyYW1ldGVyaXNlZCBpbm5lciBzY2FuCitTRUxFQ1QgeC5pZCwgeS5pZCBGUk9NIGZy
YWN0X3QgeCBMRUZUIEpPSU4gZnJhY3RfdCB5IFVTSU5HIChpZCkKK09SREVSIEJZIHguaWQg
REVTQyBMSU1JVCAyOworICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBRVUVS
WSBQTEFOICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKKy0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tCisgTGltaXQKKyAgIC0+ICBNZXJnZSBBcHBlbmQKKyAgICAgICAg
IFNvcnQgS2V5OiB4LmlkIERFU0MKKyAgICAgICAgIC0+ICBOZXN0ZWQgTG9vcCBMZWZ0IEpv
aW4KKyAgICAgICAgICAgICAgIC0+ICBJbmRleCBPbmx5IFNjYW4gQmFja3dhcmQgdXNpbmcg
ZnJhY3RfdDBfcGtleSBvbiBmcmFjdF90MCB4XzEKKyAgICAgICAgICAgICAgIC0+ICBJbmRl
eCBPbmx5IFNjYW4gdXNpbmcgZnJhY3RfdDBfcGtleSBvbiBmcmFjdF90MCB5XzEKKyAgICAg
ICAgICAgICAgICAgICAgIEluZGV4IENvbmQ6IChpZCA9IHhfMS5pZCkKKyAgICAgICAgIC0+
ICBOZXN0ZWQgTG9vcCBMZWZ0IEpvaW4KKyAgICAgICAgICAgICAgIC0+ICBJbmRleCBPbmx5
IFNjYW4gQmFja3dhcmQgdXNpbmcgZnJhY3RfdDFfcGtleSBvbiBmcmFjdF90MSB4XzIKKyAg
ICAgICAgICAgICAgIC0+ICBJbmRleCBPbmx5IFNjYW4gdXNpbmcgZnJhY3RfdDFfcGtleSBv
biBmcmFjdF90MSB5XzIKKyAgICAgICAgICAgICAgICAgICAgIEluZGV4IENvbmQ6IChpZCA9
IHhfMi5pZCkKKygxMSByb3dzKQorCiAtLQogLS0gVGVzdCBBcHBlbmQncyBmcmFjdGlvbmFs
IHBhdGhzCiAtLQpkaWZmIC0tZ2l0IGEvc3JjL3Rlc3QvcmVncmVzcy9zcWwvcGFydGl0aW9u
X2pvaW4uc3FsIGIvc3JjL3Rlc3QvcmVncmVzcy9zcWwvcGFydGl0aW9uX2pvaW4uc3FsCmlu
ZGV4IGI3NmM1NDUxMDAxLi4zMGYxNWVlOWFjYiAxMDA2NDQKLS0tIGEvc3JjL3Rlc3QvcmVn
cmVzcy9zcWwvcGFydGl0aW9uX2pvaW4uc3FsCisrKyBiL3NyYy90ZXN0L3JlZ3Jlc3Mvc3Fs
L3BhcnRpdGlvbl9qb2luLnNxbApAQCAtMTIyNCw2ICsxMjI0LDkgQEAgU0VMRUNUIHguaWQs
IHkuaWQgRlJPTSBmcmFjdF90IHggTEVGVCBKT0lOIGZyYWN0X3QgeSBVU0lORyAoaWQpIE9S
REVSIEJZIHguaWQgQVMKIAogRVhQTEFJTiAoQ09TVFMgT0ZGKQogU0VMRUNUIHguaWQsIHku
aWQgRlJPTSBmcmFjdF90IHggTEVGVCBKT0lOIGZyYWN0X3QgeSBVU0lORyAoaWQpIE9SREVS
IEJZIHguaWQgREVTQyBMSU1JVCAxMDsKK0VYUExBSU4gKENPU1RTIE9GRikgLS0gU2hvdWxk
IHVzZSBOZXN0TG9vcCB3aXRoIHBhcmFtZXRlcmlzZWQgaW5uZXIgc2NhbgorU0VMRUNUIHgu
aWQsIHkuaWQgRlJPTSBmcmFjdF90IHggTEVGVCBKT0lOIGZyYWN0X3QgeSBVU0lORyAoaWQp
CitPUkRFUiBCWSB4LmlkIERFU0MgTElNSVQgMjsKIAogLS0KIC0tIFRlc3QgQXBwZW5kJ3Mg
ZnJhY3Rpb25hbCBwYXRocwotLSAKMi4zOS41Cgo=

--------------tZ5X81QhmMorhWosVkpeESGj--