Content-Type: multipart/mixed; boundary="------------61H2E0b14Kta1TcKBUeA8sOC"
Message-ID: <da9425ae-8ff7-33d9-23b3-2a3eb605e106@gmail.com>
Date: Wed, 18 Jan 2023 00:57:54 +0530
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.4.2
From: Ankit Kumar Pandey <itsankitkp@gmail.com>
Subject: [PATCH] Teach planner to further optimize sort in distinct
Content-Language: en-US
To: pghackers <pgsql-hackers@lists.postgresql.org>,
 David Rowley <dgrowleyml@gmail.com>
Archived-At: <https://www.postgresql.org/message-id/da9425ae-8ff7-33d9-23b3-2a3eb605e106%40gmail.com>
Precedence: bulk

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

Hi, this is extension of `teach planner to evaluate multiple windows in 
the optimal order` work applied to distinct operation.

Based on discussions before 
(https://www.postgresql.org/message-id/flat/CAApHDvr7rSCVXzGfVa1L9pLpkKj6-s8NynK8o%2B98X9sKjejnQQ%40mail.gmail.com#e01327a3053d9281c40f281ef7105b42) 
,

 > All I imagine you need to do for it
 > is to invent a function in pathkeys.c which is along the lines of what
 > pathkeys_count_contained_in() does, but returns a List of pathkeys
 > which are in keys1 but not in keys2 and NIL if keys2 has a pathkey
 > that does not exist as a pathkey in keys1. In
 > create_final_distinct_paths(), you can then perform an incremental
 > sort on any input_path which has a non-empty return list and in
 > create_incremental_sort_path(), you'll pass presorted_keys as the
 > number of pathkeys in the path, and the required pathkeys the
 > input_path->pathkeys + the pathkeys returned from the new function.


There is bit confusion in wording here:

"returns a List of pathkeys
which are in keys1 but not in keys2 and NIL if keys2 has a pathkey
that does not exist as a pathkey in keys1."

You mean extract common keys without ordering right?

Example: keys1 = (a,b,c), keys2 = (b,a)

returns (a,b)

and

keys1 = (a,b,c), keys = (d)

returns = ()

which translates to

needed_pathkeys = (a,b,c) = key2

input_pathkeys = (b,a) key1

returns (b,a) = common_keys

new needed_pathkeys = unique(common_keys + old needed_pathkeys)

=> new needed_pathkeys = (b,a,c)

The new needed_pathkeys matches input_pathkeys.

This is what I implemented in the patch.


The patched version yields the following plans:

set enable_hashagg=0;
set enable_seqscan=0;

explain (costs off) select distinct relname,relkind,count(*) over 
(partition by
relkind) from pg_Class;
                        QUERY PLAN
---------------------------------------------------------
  Unique
    ->  Incremental Sort
          Sort Key: relkind, relname, (count(*) OVER (?))
          Presorted Key: relkind
          ->  WindowAgg
                ->  Sort
                      Sort Key: relkind
                      ->  Seq Scan on pg_class
(8 rows)

explain (costs off) select distinct a, b, count(*) over (partition by b, 
a) from abcd;
                        QUERY PLAN
--------------------------------------------------------
  Unique
    ->  Incremental Sort
          Sort Key: b, a, (count(*) OVER (?))
          Presorted Key: b, a
          ->  WindowAgg
                ->  Incremental Sort
                      Sort Key: b, a
                      Presorted Key: b
                      ->  Index Scan using b_idx on abcd
(9 rows)

explain (costs off) select distinct a, b, count(*) over (partition by c, 
d) from abcd;
                        QUERY PLAN
--------------------------------------------------------
  Unique
    ->  Sort
          Sort Key: a, b, (count(*) OVER (?))
          ->  WindowAgg
                ->  Incremental Sort
                      Sort Key: c, d
                      Presorted Key: c
                      ->  Index Scan using c_idx on abcd
(8 rows)


Issue with index path still remains as pathkeys get purged by 
truncate_useless_pathkeys

and hence are not available in create_final_distinct_paths for the above 
optimizations.


I have attached a patch for the reference.


Thanks,

Ankit


--------------61H2E0b14Kta1TcKBUeA8sOC
Content-Type: text/x-patch; charset=UTF-8;
 name="distinct_sort_optimizations.patch"
Content-Disposition: attachment; filename="distinct_sort_optimizations.patch"
Content-Transfer-Encoding: base64

ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL3BhdGhrZXlzLmMgYi9z
cmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9wYXRoa2V5cy5jCmluZGV4IDYwOWRmOTNkYzku
LjEzZjYwMDY1NzcgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL3Bh
dGhrZXlzLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvcGF0aGtleXMuYwpA
QCAtMTk2OCwzICsxOTY4LDMyIEBAIGhhc191c2VmdWxfcGF0aGtleXMoUGxhbm5lckluZm8g
KnJvb3QsIFJlbE9wdEluZm8gKnJlbCkKIAkJcmV0dXJuIHRydWU7CQkJLyogbWlnaHQgYmUg
YWJsZSB0byB1c2UgdGhlbSBmb3Igb3JkZXJpbmcgKi8KIAlyZXR1cm4gZmFsc2U7CQkJCS8q
IGRlZmluaXRlbHkgdXNlbGVzcyAqLwogfQorCisvKgorICogZXh0cmFjdF9jb21tb25fcGF0
aGtleXMKKyAqCQlyZXR1cm5zIGEgTGlzdCBvZiBwYXRoa2V5cworICoJd2hpY2ggYXJlIGlu
IGtleXMxIGJ1dCBub3QgaW4ga2V5czIgYW5kIE5JTCBpZiBrZXlzMiBoYXMgYSBwYXRoa2V5
CisgKiB0aGF0IGRvZXMgbm90IGV4aXN0IGFzIGEgcGF0aGtleSBpbiBrZXlzMSAKKyAqLwor
TGlzdCAqCitleHRyYWN0X2NvbW1vbl9wYXRoa2V5cyhMaXN0KiBrZXlzMSwgTGlzdCAqa2V5
czIpCit7CisJTGlzdCAqbmV3X3BrID0gTklMOworCUxpc3RDZWxsCSpsMTsKKwlMaXN0Q2Vs
bAkqbDI7CisJZm9yZWFjaChsMSwga2V5czEpCisJeworCQlQYXRoS2V5ICAgICpwYXRoa2V5
MSA9IChQYXRoS2V5ICopIGxmaXJzdChsMSk7CisJCWZvcmVhY2gobDIsIGtleXMyKQorCQl7
CisJCQlQYXRoS2V5ICAgICpwYXRoa2V5MiA9IChQYXRoS2V5ICopIGxmaXJzdChsMik7CisJ
CQlpZiAocGF0aGtleTEgPT0gcGF0aGtleTIpCisJCQl7CisJCQkJbmV3X3BrID0gbGFwcGVu
ZChuZXdfcGssIHBhdGhrZXkxKTsKKwkJCQlicmVhazsKKwkJCX0KKwkJfQorCX0KKwlyZXR1
cm4gbmV3X3BrOworCit9ClwgTm8gbmV3bGluZSBhdCBlbmQgb2YgZmlsZQpkaWZmIC0tZ2l0
IGEvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4vcGxhbm5lci5jIGIvc3JjL2JhY2tlbmQv
b3B0aW1pemVyL3BsYW4vcGxhbm5lci5jCmluZGV4IDA0NGZiMjQ2NjYuLjE4MDJkMjhlNzUg
MTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL3BsYW5uZXIuYworKysg
Yi9zcmMvYmFja2VuZC9vcHRpbWl6ZXIvcGxhbi9wbGFubmVyLmMKQEAgLTQ4NDQsMTEgKzQ4
NDQsMjggQEAgY3JlYXRlX2ZpbmFsX2Rpc3RpbmN0X3BhdGhzKFBsYW5uZXJJbmZvICpyb290
LCBSZWxPcHRJbmZvICppbnB1dF9yZWwsCiAJCQlQYXRoCSAgICpzb3J0ZWRfcGF0aDsKIAkJ
CWJvb2wJCWlzX3NvcnRlZDsKIAkJCWludAkJCXByZXNvcnRlZF9rZXlzOworCQkJTGlzdAkJ
KmNvbW1vbl9rZXlzOwogCiAJCQlpc19zb3J0ZWQgPSBwYXRoa2V5c19jb3VudF9jb250YWlu
ZWRfaW4obmVlZGVkX3BhdGhrZXlzLAogCQkJCQkJCQkJCQkJCWlucHV0X3BhdGgtPnBhdGhr
ZXlzLAogCQkJCQkJCQkJCQkJCSZwcmVzb3J0ZWRfa2V5cyk7CiAKKwkJCS8qCisJCQkgKiBD
aGVjayBpZiB0aGVyZSBhcmUgY29tbW9uIHBhdGhrZXlzIChyZWdhcmRsZXNzIG9mIG9yZGVy
aW5nKQorCQkJICovCisJCQljb21tb25fa2V5cyA9IGV4dHJhY3RfY29tbW9uX3BhdGhrZXlz
KGlucHV0X3BhdGgtPnBhdGhrZXlzLCBuZWVkZWRfcGF0aGtleXMpOworCQkJCisJCQlpZiAo
Y29tbW9uX2tleXMpCisJCQl7CisJCQkJLyoKKwkJCQkgKiBOb3cgdGhhdCB3ZSBoYXZlIGNv
bW1vbiBrZXlzLCB3ZSBjYW4gYWRkIHRoZXNlIHRvIHBhdGgKKwkJCQkgKi8KKwkJCQluZWVk
ZWRfcGF0aGtleXMgPSBsaXN0X2NvbmNhdF91bmlxdWUoY29tbW9uX2tleXMsIG5lZWRlZF9w
YXRoa2V5cyk7CisJCQkJaXNfc29ydGVkID0gcGF0aGtleXNfY291bnRfY29udGFpbmVkX2lu
KG5lZWRlZF9wYXRoa2V5cywKKwkJCQkJCQkJCQkJCQlpbnB1dF9wYXRoLT5wYXRoa2V5cywK
KwkJCQkJCQkJCQkJCQkmcHJlc29ydGVkX2tleXMpOworCQkJfQorCiAJCQlpZiAoaXNfc29y
dGVkKQogCQkJCXNvcnRlZF9wYXRoID0gaW5wdXRfcGF0aDsKIAkJCWVsc2UKZGlmZiAtLWdp
dCBhL3NyYy9pbmNsdWRlL29wdGltaXplci9wYXRocy5oIGIvc3JjL2luY2x1ZGUvb3B0aW1p
emVyL3BhdGhzLmgKaW5kZXggNjVhM2MzNTYxMS4uYjFiNzAwZTA2NyAxMDA2NDQKLS0tIGEv
c3JjL2luY2x1ZGUvb3B0aW1pemVyL3BhdGhzLmgKKysrIGIvc3JjL2luY2x1ZGUvb3B0aW1p
emVyL3BhdGhzLmgKQEAgLTI0OCw2ICsyNDgsNyBAQCBleHRlcm4gTGlzdCAqdHJ1bmNhdGVf
dXNlbGVzc19wYXRoa2V5cyhQbGFubmVySW5mbyAqcm9vdCwKIAkJCQkJCQkJCSAgIFJlbE9w
dEluZm8gKnJlbCwKIAkJCQkJCQkJCSAgIExpc3QgKnBhdGhrZXlzKTsKIGV4dGVybiBib29s
IGhhc191c2VmdWxfcGF0aGtleXMoUGxhbm5lckluZm8gKnJvb3QsIFJlbE9wdEluZm8gKnJl
bCk7CitleHRlcm4gTGlzdCAqZXh0cmFjdF9jb21tb25fcGF0aGtleXMoTGlzdCoga2V5czEs
IExpc3QgKmtleXMyKTsKIGV4dGVybiBMaXN0ICphcHBlbmRfcGF0aGtleXMoTGlzdCAqdGFy
Z2V0LCBMaXN0ICpzb3VyY2UpOwogZXh0ZXJuIFBhdGhLZXkgKm1ha2VfY2Fub25pY2FsX3Bh
dGhrZXkoUGxhbm5lckluZm8gKnJvb3QsCiAJCQkJCQkJCQkgICBFcXVpdmFsZW5jZUNsYXNz
ICplY2xhc3MsIE9pZCBvcGZhbWlseSwK

--------------61H2E0b14Kta1TcKBUeA8sOC--