Content-Type: multipart/mixed; boundary="------------HgS8z6M0gQuZ6OOX0O15FZP7"
Message-ID: <01248493-182b-0f92-f2f2-ff28dc4b2e83@gmail.com>
Date: Fri, 6 Jan 2023 18:41:33 +0530
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.4.2
Subject: Re: Todo: Teach planner to evaluate multiple windows in the optimal
 order
Content-Language: en-US
From: Ankit Kumar Pandey <itsankitkp@gmail.com>
References: <83d80853-a45c-d85c-68eb-59acfe7fb5fb@gmail.com>
 <CAApHDvp=r1LnEKCmWCYaruMPL-jP4j_sdc8yeFYwaDT1ac5GsQ@mail.gmail.com>
 <7f77ee7d-bd04-d8e2-bb34-42395fd1f7c2@gmail.com>
 <CAApHDvq=g2=ny59f1bvwRVvupsgPHK-KjLPBsSL25fVuGZ4idQ@mail.gmail.com>
 <6ebcc137-45ea-6373-e3e1-3c304c452e1f@gmail.com>
 <441d135e-1941-c3ef-1649-18c3e8811549@postgresfriends.org>
 <9620d994-b89a-2dcf-fca5-821e19d56858@gmail.com>
 <CAApHDvruS-3gG_KYXPb_=Um_TfUXi+G4o7VyBVbChTjThXF2yA@mail.gmail.com>
 <a58a04a9-2dd6-7290-35c5-e3e23f326b85@gmail.com>
To: David Rowley <dgrowleyml@gmail.com>
Cc: pghackers <pgsql-hackers@lists.postgresql.org>,
 Vik Fearing <vik@postgresfriends.org>
In-Reply-To: <a58a04a9-2dd6-7290-35c5-e3e23f326b85@gmail.com>
Archived-At: <https://www.postgresql.org/message-id/01248493-182b-0f92-f2f2-ff28dc4b2e83%40gmail.com>
Precedence: bulk

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

Sorry if multiple mails has been sent for this.


> On 05/01/23 12:53, David Rowley wrote:
>>
>> We *can* reuse Sorts where a more strict or equivalent sort order is
>> available.  The question is how do we get the final WindowClause to do
>> something slightly more strict to save having to do anything for the
>> ORDER BY.  One way you might think would be to adjust the
>> WindowClause's orderClause to add the additional clauses, but that
>> cannot be done because that would cause are_peers() in nodeWindowAgg.c
>> to not count some rows as peers when they maybe should be given a less
>> strict orderClause in the WindowClause.

I attempted this in attached patch.


#1. No op case

------------------------------------------In patched 
version-----------------------------------------------

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER 
(ORDER BY a,b,c) FROM abcd order by a;
                 QUERY PLAN
------------------------------------------
  WindowAgg
    ->  Sort
          Sort Key: a, b, c
          ->  WindowAgg
                ->  Sort
                      Sort Key: b
                      ->  Seq Scan on abcd
(7 rows)

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER 
(ORDER BY a,b,c) FROM abcd;
                 QUERY PLAN
------------------------------------------
  WindowAgg
    ->  Sort
          Sort Key: b
          ->  WindowAgg
                ->  Sort
                      Sort Key: a, b, c
                      ->  Seq Scan on abcd
(7 rows)

----------------------------------------------In 
master--------------------------------------------------------


explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER 
(ORDER BY a,b,c) FROM abcd order by a;
                 QUERY PLAN
------------------------------------------
  WindowAgg
    ->  Sort
          Sort Key: a, b, c
          ->  WindowAgg
                ->  Sort
                      Sort Key: b
                      ->  Seq Scan on abcd
(7 rows)
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER 
(ORDER BY a,b,c) FROM abcd;
                 QUERY PLAN
------------------------------------------
  WindowAgg
    ->  Sort
          Sort Key: b
          ->  WindowAgg
                ->  Sort
                      Sort Key: a, b, c
                      ->  Seq Scan on abcd
(7 rows)

No change between patched version and master.


2. In case where optimization can happen

----------------------------In patched 
version-------------------------------------------------------

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER 
(ORDER BY a) FROM abcd order by a,b;
                 QUERY PLAN
------------------------------------------
  WindowAgg
    ->  Sort
          Sort Key: a, b
          ->  WindowAgg
                ->  Sort
                      Sort Key: b
                      ->  Seq Scan on abcd
(7 rows)

explain (costs off)  SELECT rank() OVER (ORDER BY a), count(*) OVER 
(ORDER BY b), count(*) OVER (PARTITION BY a ORDER BY b) FROM abcd order 
by a,b,c,d;
                    QUERY PLAN
------------------------------------------------
  WindowAgg
    ->  WindowAgg
          ->  Sort
                Sort Key: a, b, c, d
                ->  WindowAgg
                      ->  Sort
                            Sort Key: b
                            ->  Seq Scan on abcd
(8 rows)

-------------------------------------------In 
master--------------------------------------------------------

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER 
(ORDER BY a) FROM abcd order by a,b;
                    QUERY PLAN
------------------------------------------------
  Incremental Sort
    Sort Key: a, b
    Presorted Key: a
    ->  WindowAgg
          ->  Sort
                Sort Key: a
                ->  WindowAgg
                      ->  Sort
                            Sort Key: b
                            ->  Seq Scan on abcd
(10 rows)

explain (costs off)  SELECT rank() OVER (ORDER BY a), count(*) OVER 
(ORDER BY b), count(*) OVER (PARTITION BY a ORDER BY b) FROM abcd order 
by a,b,c,d;
                       QUERY PLAN
------------------------------------------------------
  Incremental Sort
    Sort Key: a, b, c, d
    Presorted Key: a, b
    ->  WindowAgg
          ->  WindowAgg
                ->  Sort
                      Sort Key: a, b
                      ->  WindowAgg
                            ->  Sort
                                  Sort Key: b
                                  ->  Seq Scan on abcd
(11 rows)

Patched version removes few sorts.

Regression tests all passed so it is not breaking anything existing.

We don't have any tests for verifying sorting plan in window functions 
(which would have failed, if present).

Please let me know any feedbacks (I have added some my own concerns in 
the comments)

Thanks


-- 
Regards,
Ankit Kumar Pandey

--------------HgS8z6M0gQuZ6OOX0O15FZP7
Content-Type: text/x-patch; charset=UTF-8;
 name="v1-0002-Teach-planner-to-optimize-sorting-operations-for-win.patch"
Content-Disposition: attachment;
 filename*0="v1-0002-Teach-planner-to-optimize-sorting-operations-for-win";
 filename*1=".patch"
Content-Transfer-Encoding: base64

RnJvbSA4ZmI0YjYxODhlZGExMTFiZWUyZTQ3ZDNlODUyODkwNjRiNDI4NzAyIE1vbiBTZXAg
MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBBbmtpdCBLdW1hciBQYW5kZXkgPGl0c2Fua2l0a3BA
Z21haWwuY29tPgpEYXRlOiBGcmksIDYgSmFuIDIwMjMgMTQ6MzA6MzggKzA1MzAKU3ViamVj
dDogW1BBVENIXSBUZWFjaCBwbGFubmVyIHRvIG9wdGltaXplIHNvcnRpbmcgb3BlcmF0aW9u
cyBmb3Igd2luZG93CiBmdW5jdGlvbgoKQWRkaXRpb25hbCBzb3J0IGZvciByb290J3Mgb3Jk
ZXIgYnkgY2FuIGJlIG9wdGltaXplZCBpZiBzb3J0aW5nIGZvcgpleHRyYSBjb2x1bW5zIGFy
ZSBwZXJmb3JtZWQgd2hpbGUgc29ydGluZyBmb3Igd2luZG93IGZ1bmN0aW9ucyAoaWYgc29y
dApjbGF1c2Ugb2Ygd2luZG93IGZ1bmN0aW9ucyBhcmUgc3Vic2V0IG9mIHJvb3QncyBzb3J0
IGNsYXVzZSkuCi0tLQogc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4vcGxhbm5lci5jIHwg
NzAgKysrKysrKysrKysrKysrKysrKysrKysrKysrKwogMSBmaWxlIGNoYW5nZWQsIDcwIGlu
c2VydGlvbnMoKykKCmRpZmYgLS1naXQgYS9zcmMvYmFja2VuZC9vcHRpbWl6ZXIvcGxhbi9w
bGFubmVyLmMgYi9zcmMvYmFja2VuZC9vcHRpbWl6ZXIvcGxhbi9wbGFubmVyLmMKaW5kZXgg
ZDZiYTc1ODlmMy4uMDQ4NjUxZGZmZSAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvb3B0aW1p
emVyL3BsYW4vcGxhbm5lci5jCisrKyBiL3NyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL3Bs
YW5uZXIuYwpAQCAtNDQ0OCwxMSArNDQ0OCw4MSBAQCBjcmVhdGVfb25lX3dpbmRvd19wYXRo
KFBsYW5uZXJJbmZvICpyb290LAogCQlpbnQJCQlwcmVzb3J0ZWRfa2V5czsKIAkJYm9vbAkJ
aXNfc29ydGVkOwogCQlib29sCQl0b3B3aW5kb3c7CisJCUxpc3QJICAgKndpbmRvd19zb3J0
Y2xhdXNlczsKIAogCQl3aW5kb3dfcGF0aGtleXMgPSBtYWtlX3BhdGhrZXlzX2Zvcl93aW5k
b3cocm9vdCwKIAkJCQkJCQkJCQkJCSAgIHdjLAogCQkJCQkJCQkJCQkJICAgcm9vdC0+cHJv
Y2Vzc2VkX3RsaXN0KTsKIAorCisJCS8qCisJCSAqIEFkZCBhZGl0aW9uYWwgc29ydGluZyBj
bGF1c2UgZnJvbQorCQkgKiByb290J3Mgb3JkZXIgYnkgdG8gd2luZG93J3Mgb3JkZXIgYnkg
Y2xhdXNlLAorCQkgKiBpZiB0aGV5IGFyZSBjb21wYXRpYmxlLiBUaGlzIHdpbGwgc2F2ZSBh
ZGRpdGlvbmFsCisJCSAqIHNvcnRpbmcgYXQgdGhlIGVuZC4gVGhpcyBzaG91bGQgaGFwcGVu
IG9ubHkgaWYgc29ydAorCQkgKiBjbGF1c2UgaW4gIHdpbmRvdyBmdW5jdGlvbiBpcyBzdWJz
ZXQgb2Ygcm9vdCdzIG9yZGVyIGJ5LgorCQkgKiBYWFggSWRlYWxseSB0aGlzIGNoZWNrIG5l
ZWQgdG8gYmUgcGVyZm9ybWVkIG9uIGZpbmFsCisJCSAqIHdpbmRvdyBmdW5jdGlvbiBidXQg
aWYgSSBhZGQgY29uZGl0aW9uIGhlcmUsIGZvciBmaW5hbAorCQkgKiB3aW5kb3cgZnVuY3Rp
b24sIHBhdGhrZXlzIHdvdWxkIGhhdmUgYmVlbiBzYW1lIGFzIHJvb3QncworCQkgKiBvcmRl
ciBieSBidXQgZm9yIG90aGVycywgaXQgd291bGQgaGF2ZSBiZWVuIGxlc3NlciBudW1iZXIK
KwkJICogKGlmIHRoZXkgYXJlIHN1YnNldCkuIFNvLCBzeXN0ZW0gd291bGQgaWdub3JlIGV4
dHJhIHNvcnQKKwkJICogYW5kIHRha2UgaXQgYXMgZmlyc3Qgc3RlcCAod2hlcmUgZmluYWwg
ZnVuY3Rpb24gd2FzIGV4cGVjdGVkCisJCSAqIHRvIGJlKSwgZG8gcmVndWxhciBzb3J0IGFz
IGluIG1hc3Rlci4KKwkJICogVHJ5IGFkZGluZyAoZm9yZWFjaF9jdXJyZW50X2luZGV4KGwp
ID09IGxpc3RfbGVuZ3RoKGFjdGl2ZVdpbmRvd3MpIC0gMSkKKwkJICogaW4gaWYgY29uZGl0
aW9uIHdoaWNoIGNoZWNrIGlmIHdpbmRvd19zb3J0Y2xhdXNlIGlzIHN1YnNldCBsZW5ndGh3
aXNlCisJCSAqLworCQl3aW5kb3dfc29ydGNsYXVzZXMgPSBsaXN0X2NvbmNhdF9jb3B5KHdj
LT5wYXJ0aXRpb25DbGF1c2UsIHdjLT5vcmRlckNsYXVzZSk7CisKKwkJaWYobGlzdF9sZW5n
dGgod2luZG93X3NvcnRjbGF1c2VzKSA8IGxpc3RfbGVuZ3RoKHJvb3QtPnBhcnNlLT5zb3J0
Q2xhdXNlKSkKKwkJeworCQkJTGlzdENlbGwJKndzYzsKKwkJCUxpc3RDZWxsCSpzYzsKKwkJ
CWJvb2wJCXNob3VsZF9wcmVwZW5kID0gdHJ1ZTsgLyogd2lzaGZ1bCB0aGlua2luZyAqLwor
CisJCQkvKgorCQkJKiBTYW1lIGFzIGluIG1ha2VfcGF0aGtleXNfZm9yX3dpbmRvdworCQkJ
KiBmb3Igc29ydGluZywgcGFydGl0aW9uIGNsYXVzZSBpcyB0YWtlbiBmaXJzdAorCQkJKi8K
KwkJCXdpbmRvd19zb3J0Y2xhdXNlcyA9IGxpc3RfY29uY2F0X2NvcHkod2MtPnBhcnRpdGlv
bkNsYXVzZSwgd2MtPm9yZGVyQ2xhdXNlKTsKKworCQkJLyoKKwkJCSogU29ydCBjbGF1c2Vz
IG9mIHJvb3QgY2FuIGJlIHByZXBlbmRlZCBpZiBhbmQgb25seSBpZgorCQkJKiBzb3J0IGNs
YXVzZSBvZiB3aW5kb3cgZnVuY3Rpb24gaXMgc3Vic2V0IG9mIHJvb3QncyBzb3J0IGNsYXVz
ZQorCQkJKiBYWFggaXMgdGhlcmUgYmV0dGVyIHdheSB0byBmaW5kIHRoaXM/CisJCQkqLwor
CQkJZm9yYm90aCh3c2MsIHdpbmRvd19zb3J0Y2xhdXNlcywgc2MsIHJvb3QtPnBhcnNlLT5z
b3J0Q2xhdXNlKQorCQkJeworCQkJCVNvcnRHcm91cENsYXVzZSAqd2luZG93X3NvcnRjbGF1
c2UgPSAoU29ydEdyb3VwQ2xhdXNlKikgbGZpcnN0KHdzYyk7CisJCQkJU29ydEdyb3VwQ2xh
dXNlICpzb3J0Y2xhdXNlID0gKFNvcnRHcm91cENsYXVzZSopIGxmaXJzdChzYyk7CisJCQkJ
aWYgKHdpbmRvd19zb3J0Y2xhdXNlLT50bGVTb3J0R3JvdXBSZWYgIT0gc29ydGNsYXVzZS0+
dGxlU29ydEdyb3VwUmVmKQorCQkJCXsKKwkJCQkJc2hvdWxkX3ByZXBlbmQgPSBmYWxzZTsK
KwkJCQkJYnJlYWs7CisJCQkJfQorCQkJfQorCisKKwkJCS8qCisJCQkqIE92ZXJyaWRlIHdp
bmRvdyBwYXRoIGtleSBkZWZpbmVkIGJ5IG1ha2VfcGF0aGtleXNfZm9yX3dpbmRvdworCQkJ
KiBYWFggc2luY2Ugd2UgYXJlIG92ZXJyaWRpbmcgbWFrZV9wYXRoa2V5c19mb3Jfd2luZG93
LCBpdCBpcworCQkJKiBhIHdhc3RlZnVsIGNhbGwgaW4gY3JpdGljYWwgcGF0aC4gU2hvdWxk
IHdlIGNhbGwgbWFrZV9wYXRoa2V5c19mb3Jfd2luZG93CisJCQkqIGFmdGVyIHRoaXMgZnVu
Y3Rpb24/CisJCQkqLworCQkJaWYgKHNob3VsZF9wcmVwZW5kKQorCQkJeworCQkJCS8qCisJ
CQkJICogYWRkIHJvb3QncyBzb3J0IGNsYXVzZXMgaW4gdGhlIGVuZAorCQkJCSAqLworCQkJ
CXdpbmRvd19zb3J0Y2xhdXNlcyA9IGxpc3RfY29uY2F0X3VuaXF1ZSh3aW5kb3dfc29ydGNs
YXVzZXMsIAorCQkJCQkJCQkJCQkJCQlyb290LT5wYXJzZS0+c29ydENsYXVzZSk7CisJCQkJ
d2luZG93X3BhdGhrZXlzID0gbWFrZV9wYXRoa2V5c19mb3Jfc29ydGNsYXVzZXMocm9vdCwK
KwkJCQkJCQkJCQkJCQl3aW5kb3dfc29ydGNsYXVzZXMsCisJCQkJCQkJCQkJCQkJcm9vdC0+
cHJvY2Vzc2VkX3RsaXN0KTsKKworCQkJfQorCQkJCisJCX0KKwogCQlpc19zb3J0ZWQgPSBw
YXRoa2V5c19jb3VudF9jb250YWluZWRfaW4od2luZG93X3BhdGhrZXlzLAogCQkJCQkJCQkJ
CQkJcGF0aC0+cGF0aGtleXMsCiAJCQkJCQkJCQkJCQkmcHJlc29ydGVkX2tleXMpOwotLSAK
Mi4zNy4yCgo=

--------------HgS8z6M0gQuZ6OOX0O15FZP7--