public inbox for [email protected]
help / color / mirror / Atom feed[PATCH 8/8] Consider selectivity in choose_bitmap_and
4+ messages / 3 participants
[nested] [flat]
* [PATCH 8/8] Consider selectivity in choose_bitmap_and
@ 2021-03-11 11:57 Tomas Vondra <[email protected]>
0 siblings, 0 replies; 4+ messages in thread
From: Tomas Vondra @ 2021-03-11 11:57 UTC (permalink / raw)
---
src/backend/optimizer/path/indxpath.c | 38 ++++++++++++++++-----------
1 file changed, 23 insertions(+), 15 deletions(-)
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index ff536e6b24..36b29c6c7b 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1437,6 +1437,7 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
foreach(l, paths)
{
Path *ipath = (Path *) lfirst(l);
+ bool duplicate = false;
pathinfo = classify_index_clause_usage(ipath, &clauselist);
@@ -1451,22 +1452,29 @@ choose_bitmap_and(PlannerInfo *root, RelOptInfo *rel, List *paths)
{
if (!pathinfoarray[i]->unclassifiable &&
bms_equal(pathinfo->clauseids, pathinfoarray[i]->clauseids))
- break;
- }
- if (i < npaths)
- {
- /* duplicate clauseids, keep the cheaper one */
- Cost ncost;
- Cost ocost;
- Selectivity nselec;
- Selectivity oselec;
-
- cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec);
- cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec);
- if (ncost < ocost)
- pathinfoarray[i] = pathinfo;
+ {
+ /* duplicate clauseids, keep the cheaper one
+ *
+ * XXX maybe this should just use path_usage_comparator?
+ */
+ Cost ncost;
+ Cost ocost;
+ Selectivity nselec;
+ Selectivity oselec;
+
+ cost_bitmap_tree_node(pathinfo->path, &ncost, &nselec);
+ cost_bitmap_tree_node(pathinfoarray[i]->path, &ocost, &oselec);
+
+ if ((ncost < ocost) && (nselec < oselec))
+ {
+ pathinfoarray[i] = pathinfo;
+ duplicate = true;
+ break;
+ }
+ }
}
- else
+
+ if (!duplicate)
{
/* not duplicate clauseids, add to array */
pathinfoarray[npaths++] = pathinfo;
--
2.26.2
--------------D524CD37E77B36A2883A7617
Content-Type: application/sql;
name="reproduce2.sql"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="reproduce2.sql"
ZHJvcCB0YWJsZSBpZiBleGlzdHMgdDsKCnNldCBtYXhfcGFyYWxsZWxfd29ya2Vyc19wZXJf
Z2F0aGVyID0gMDsKCmNyZWF0ZSB0YWJsZSB0KGEgYmlnaW50KSB3aXRoIChmaWxsZmFjdG9y
ID0gMjUpOwoKaW5zZXJ0IGludG8gdCBzZWxlY3QgaSBmcm9tIGdlbmVyYXRlX3Nlcmllcygx
LDEwMDAwMDAwKSBzKGkpOwoKY3JlYXRlIGluZGV4IGlkeF8xIG9uIHQgdXNpbmcgYnJpbiAo
YSkgd2l0aCAocGFnZXNfcGVyX3JhbmdlID0gNCk7CgpjcmVhdGUgaW5kZXggaWR4XzIgb24g
dCB1c2luZyBicmluIChhKTsKCmFuYWx5emUgdDsKClxkKwpcZGkrCgpleHBsYWluIGFuYWx5
emUgc2VsZWN0ICogZnJvbSB0IHdoZXJlIGEgPSAxMDAwOwoKZHJvcCBpbmRleCBpZHhfMjsK
CmV4cGxhaW4gYW5hbHl6ZSBzZWxlY3QgKiBmcm9tIHQgd2hlcmUgYSA9IDEwMDA7Cg==
--------------D524CD37E77B36A2883A7617
Content-Type: application/sql;
name="reproducer.sql"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
filename="reproducer.sql"
ZHJvcCB0YWJsZSBpZiBleGlzdHMgdDsKCnNldCBtYXhfcGFyYWxsZWxfd29ya2Vyc19wZXJf
Z2F0aGVyID0gMDsKCmNyZWF0ZSB0YWJsZSB0IChhIGludCwgYiBiaWdpbnQsIGMgdGV4dCkg
d2l0aCAoZmlsbGZhY3RvciA9IDUwKTsKCmluc2VydCBpbnRvIHQgc2VsZWN0IDEwMDAwMDAg
KiByYW5kb20oKSwgMTAwMDAwMCAqIHJhbmRvbSgpLCBtZDUoKDEwMDAwMDAgKiByYW5kb20o
KSk6OmludDo6dGV4dCkgZnJvbSBnZW5lcmF0ZV9zZXJpZXMoMSwxMDAwMDAwKSBzKGkpOwoK
c2VsZWN0IGNvdW50KCopIGZyb20gKHNlbGVjdCBkaXN0aW5jdCBiIGZyb20gdCB3aGVyZSBj
dGlkIDwgJygxMjgsMCknOjp0aWQpIGZvbzsKCmNyZWF0ZSBpbmRleCBibG9vbV9hX2lkeCBv
biB0IHVzaW5nIGJyaW4gKGEgaW50NF9ibG9vbV9vcHMobl9kaXN0aW5jdF9wZXJfcmFuZ2U9
NjAwMCkpOyAKCmFuYWx5emUgdDsKCmV4cGxhaW4gc2VsZWN0ICogZnJvbSB0IHdoZXJlIGEg
PSAxMDAwOwoKY3JlYXRlIGluZGV4IGJyaW5faWR4IG9uIHQgdXNpbmcgYnJpbiAoYSk7CmFu
YWx5emUgdDsKCmV4cGxhaW4gc2VsZWN0ICogZnJvbSB0IHdoZXJlIGEgPSAxMDAwOwoKZHJv
cCBpbmRleCBicmluX2lkeDsKCmV4cGxhaW4gc2VsZWN0ICogZnJvbSB0IHdoZXJlIGEgPSAx
MDAwOwo=
--------------D524CD37E77B36A2883A7617--
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Asymmetric partition-wise JOIN
@ 2024-04-02 03:07 Andrei Lepikhov <[email protected]>
2024-08-01 18:56 ` Re: Asymmetric partition-wise JOIN Alexander Korotkov <[email protected]>
0 siblings, 1 reply; 4+ messages in thread
From: Andrei Lepikhov @ 2024-04-02 03:07 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; Thomas Munro <[email protected]>; KaiGai Kohei <[email protected]>; [email protected]; +Cc: Alexander Pyhalov <[email protected]>; Jaime Casanova <[email protected]>; Aleksander Alekseev <[email protected]>; [email protected]; a.rybakina <[email protected]>
On 15/10/2023 13:25, Alexander Korotkov wrote:
> Great! I'm looking forward to the revised patch.
Revising the code and opinions before restarting this work, I found two
different possible strategies mentioned in the thread:
1. 'Common Resources' shares the materialised result of the inner table
scan (a hash table in the case of HashJoin) to join each partition one
by one. It gives us a profit in the case of parallel append and possibly
other cases, like the one shown in the initial message.
2. 'Individual strategies' - By limiting the AJ feature to cases when
the JOIN clause contains a partitioning expression, we can push an
additional scan clause into each copy of the inner table scan, reduce
the number of tuples scanned, and even prune something because of proven
zero input.
I see the pros and cons of both approaches. The first option is more
straightforward, and its outcome is obvious in the case of parallel
append. But how can we guarantee the same join type for each join? Why
should we ignore the positive effect of different strategies for
different partitions?
The second strategy is more expensive for the optimiser, especially in
the multipartition case. But as I can predict, it is easier to implement
and looks more natural for the architecture. What do you think about that?
--
regards,
Andrei Lepikhov
Postgres Professional
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Asymmetric partition-wise JOIN
2024-04-02 03:07 Re: Asymmetric partition-wise JOIN Andrei Lepikhov <[email protected]>
@ 2024-08-01 18:56 ` Alexander Korotkov <[email protected]>
2024-08-19 08:43 ` Re: Asymmetric partition-wise JOIN Andrei Lepikhov <[email protected]>
0 siblings, 1 reply; 4+ messages in thread
From: Alexander Korotkov @ 2024-08-01 18:56 UTC (permalink / raw)
To: Andrei Lepikhov <[email protected]>; +Cc: Thomas Munro <[email protected]>; KaiGai Kohei <[email protected]>; [email protected]; Alexander Pyhalov <[email protected]>; Jaime Casanova <[email protected]>; Aleksander Alekseev <[email protected]>; [email protected]; a.rybakina <[email protected]>
Hi!
On Tue, Apr 2, 2024 at 6:07 AM Andrei Lepikhov
<[email protected]> wrote:
> On 15/10/2023 13:25, Alexander Korotkov wrote:
> > Great! I'm looking forward to the revised patch.
> Revising the code and opinions before restarting this work, I found two
> different possible strategies mentioned in the thread:
> 1. 'Common Resources' shares the materialised result of the inner table
> scan (a hash table in the case of HashJoin) to join each partition one
> by one. It gives us a profit in the case of parallel append and possibly
> other cases, like the one shown in the initial message.
> 2. 'Individual strategies' - By limiting the AJ feature to cases when
> the JOIN clause contains a partitioning expression, we can push an
> additional scan clause into each copy of the inner table scan, reduce
> the number of tuples scanned, and even prune something because of proven
> zero input.
>
> I see the pros and cons of both approaches. The first option is more
> straightforward, and its outcome is obvious in the case of parallel
> append. But how can we guarantee the same join type for each join? Why
> should we ignore the positive effect of different strategies for
> different partitions?
> The second strategy is more expensive for the optimiser, especially in
> the multipartition case. But as I can predict, it is easier to implement
> and looks more natural for the architecture. What do you think about that?
Actually, the idea I tried to express is the combination of #1 and #2:
to build individual plan for every partition, but consider the 'Common
Resources'. Let me explain this a bit more.
Right now, we basically we consider the following properties during
selection of paths.
1) Cost. The cheaper path wins. There a two criteria though: startup
cost and total cost. So, we can keep both paths with cheaper startup
costs and paths with cheaper total cost.
2) Pathkeys. We can keep a path with more expensive path, which has
pathkeys potentially useful in future.
My idea is to introduce a new property for paths selection.
3) Usage of common resources. The common resource can be: hash
representation of relation, memoize over relation scan, etc. We can
exclude the cost of common resource generation from the path cost, but
keep the reference for the common resource with its generation cost.
If one path uses more common resources than another path, it could
cost-dominate another one only if its cheaper together with its extra
common resources cost. If one path uses less or equal common
resources than another, it could normally cost-dominate another one.
Using these rules, we can gather the the plurality of paths for each
child join taking common resources into account. After that we can
apply some global optimization finding generation of which common
resources can reduce the global cost.
However, I understand this is huge amount of work given we have to
introduce new basic optimizer concepts. I get that the main
application of this patch is sharding. If we have global tables
residing each shard, we can push down any joins with them. Given this
patch gives some optimization for non-sharded case, I think we
*probably* can accept its concept even that it this optimization is
obviously not perfect.
------
Regards,
Alexander Korotkov
Supabase
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Asymmetric partition-wise JOIN
2024-04-02 03:07 Re: Asymmetric partition-wise JOIN Andrei Lepikhov <[email protected]>
2024-08-01 18:56 ` Re: Asymmetric partition-wise JOIN Alexander Korotkov <[email protected]>
@ 2024-08-19 08:43 ` Andrei Lepikhov <[email protected]>
0 siblings, 0 replies; 4+ messages in thread
From: Andrei Lepikhov @ 2024-08-19 08:43 UTC (permalink / raw)
To: Alexander Korotkov <[email protected]>; +Cc: Thomas Munro <[email protected]>; KaiGai Kohei <[email protected]>; [email protected]; Alexander Pyhalov <[email protected]>; Jaime Casanova <[email protected]>; Aleksander Alekseev <[email protected]>; [email protected]; a.rybakina <[email protected]>
On 1/8/2024 20:56, Alexander Korotkov wrote:
> On Tue, Apr 2, 2024 at 6:07 AM Andrei Lepikhov
> <[email protected]> wrote:
> Actually, the idea I tried to express is the combination of #1 and #2:
> to build individual plan for every partition, but consider the 'Common
> Resources'. Let me explain this a bit more.
Thanks for keeping your eye on it!
> My idea is to introduce a new property for paths selection.
> 3) Usage of common resources. The common resource can be: hash
> representation of relation, memoize over relation scan, etc. We can
> exclude the cost of common resource generation from the path cost, but
> keep the reference for the common resource with its generation cost.
> If one path uses more common resources than another path, it could
> cost-dominate another one only if its cheaper together with its extra
> common resources cost. If one path uses less or equal common
> resources than another, it could normally cost-dominate another one.
The most challenging part for me is the cost calculation, which is
bonded with estimations of other paths. To correctly estimate the
effect, we need to remember at least the whole number of paths sharing
resources.
Also, I wonder if it can cause some corner cases where prediction error
on a shared resource will cause an even worse situation upstream.
I think we could push off here from an example and a counter-example,
but I still can't find them.
> However, I understand this is huge amount of work given we have to
> introduce new basic optimizer concepts. I get that the main
> application of this patch is sharding. If we have global tables
> residing each shard, we can push down any joins with them. Given this
> patch gives some optimization for non-sharded case, I think we
> *probably* can accept its concept even that it this optimization is
> obviously not perfect.
Yes, right now sharding is the most profitable case. We can push down
parts of the plan which references only some common resources:
FunctionScan, ValueScan, tables which can be proved are existed
everywhere and provide the same output. But for now it is too far from
the core code, IMO. - So, I search for cases that can be helpful for a
single instance.
--
regards,
Andrei Lepikhov
Postgres Professional
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2024-08-19 08:43 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2021-03-11 11:57 [PATCH 8/8] Consider selectivity in choose_bitmap_and Tomas Vondra <[email protected]>
2024-04-02 03:07 Re: Asymmetric partition-wise JOIN Andrei Lepikhov <[email protected]>
2024-08-01 18:56 ` Re: Asymmetric partition-wise JOIN Alexander Korotkov <[email protected]>
2024-08-19 08:43 ` Re: Asymmetric partition-wise JOIN Andrei Lepikhov <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox