Re: Using indices for UNION.

Hello, This patch might be too complicated (and seems somewhat ad
hoc) for the gain, but more index usage for this kind of
operation should be worth doing.

Currently, PostgreSQL ignores from the very first the availablity
of indexes for UNION. Sorting and SeqScan is choosed as follows,

* EX.1
> uniontest=# create table c11 (a int, b int, c int, d text);
> uniontest=# create unique index cu11_pkey_idx on c11 (a, b)
> uniontest=# create table c12 (like cu11 including all);
> uniontest=# insert into cu11 (select a / 5, 4 - (a % 5), a, 'cu11'
> from generate_series(000000, 099999) a);
> uniontest=# insert into cu12 (select a / 5, 4 - (a % 5), a, 'cu12'
> from generate_series(100000, 199999) a);
> uniontest=# explain (analyze on, costs off)
> select a, b from cu11 union select a, b from cu12 order by a, b limit 100;
> QUERY PLAN
> ---------------------------------------------------------------------
> Limit (actual time=287.611..287.673 rows=100 loops=1)
> -> Unique (actual time=287.610..287.652 rows=100 loops=1)
> -> Sort (actual time=287.609..287.621 rows=100 loops=1)
> Sort Key: cu11.a, cu11.b
> Sort Method: external sort Disk: 3520kB
> -> Append (actual time=0.020..73.859 rows=200000 loops=1)
> -> Seq Scan on cu11 (actual time=0.019..28.780 rows=100000 loops=1)
> -> Seq Scan on cu12 (actual time=0.006..24.550 rows=100000 loops=1)
> Total runtime: 288.596 ms

Actually, index paths are sometimes worth considering on UNION
planning especially with LIMIT. For example,

* EX.2
> uniontest=# explain (analyze on, costs off)
> select a, b from cu11 union select a, b from cu12
> order by a desc, b desc limit 100;
> QUERY PLAN
> ------------------------------------------------------------------
> Limit (actual time=0.041..0.390 rows=100 loops=1)
> -> Unique (actual time=0.040..0.355 rows=100 loops=1)
> -> Merge Append (actual time=0.040..0.290 rows=100 loops=1)
> Sort Key: cu11.a, cu11.b
> -> Limit (actual time=0.025..0.025 rows=1 loops=1)
> -> Unique (actual time=0.025..0.025 rows=1 loops=1)
> -> Index Only Scan Backward on cu11
> (actual time=0.022..0.022 rows=1 loops=1)
> Heap Fetches: 1
> -> Limit (actual time=0.012..0.209 rows=100 loops=1)
> -> Unique (actual time=0.011..0.188 rows=100 loops=1)
> -> Index Only Scan Backward .. on cu12
> (actual time=0.010..0.115 rows=100 loops=1)
> Heap Fetches: 100
> Total runtime: 1.191 ms

This is archieved by this patch.

Rough explanaiton of what this patch does is following,

- Consider whether ORDER BY or grouping of setops can be pushed
down onto leaf subqueries. (recurse_set_operations)

- Merging two children of a setop counting the sort orders of
them. Use MergeAppend if they are in the same ordering.
(generate_union_plan, recurse_union_children)

- Grouping is determined consulting sorting order. This will
allow removing redundant sorting. (generate_setop_grouplist)

The effects of these items are shown in the Ex.2.

What do you think about this?

=======

Nevertheless, only this patch does not effective so far on the
query like following,

>uniontest=# explain (analyze on, costs off)
> select * from cu11 union select * from cu12
> order by a, b limit 100;
> QUERY PLAN
> -----------------------------------------------------------------------
> Limit (actual time=256.263..256.346 rows=100 loops=1)
> -> Unique (actual time=256.262..256.332 rows=100 loops=1)
> -> Sort (actual time=256.261..256.283 rows=100 loops=1)
> Sort Key: cu11.a, cu11.b, cu11.c, cu11.d
> Sort Method: external sort Disk: 5280kB
> -> Append (actual time=0.028..61.161 rows=200000 loops=1)
> -> Seq Scan on cu11 (actual time=0.027..21.067 rows=100000 loops=1)
> -> Seq Scan on cu12 (actual time=0.012..18.428 rows=100000 loops=1)
> Total runtime: 257.778 ms

The indexes made here is UNIQUE one so they should be used for
ordering in this query. This will be overcome by another patch
(will separately proposed).

> uniontest=# explain (analyze on, costs off)
> select * from cu11 union select * from cu12
> order by a, b limit 100;
> QUERY PLAN
> ---------------------------------------------------------------------------
> Limit (actual time=0.102..0.351 rows=100 loops=1)
> -> Unique (actual time=0.100..0.323 rows=100 loops=1)
> -> Merge Append (actual time=0.097..0.222 rows=100 loops=1)
> Sort Key: cu11.a, cu11.b, cu11.c, cu11.d
> -> Limit (actual time=0.051..0.135 rows=100 loops=1)
> -> Index Scan .. on cu11 (actual time=0.051..0.109 rows=100 loops=1)
> -> Limit (actual time=0.044..0.044 rows=1 loops=1)
> -> Index Scan .. on cu12 (actual time=0.044..0.044 rows=1 loops=1)
> Total runtime: 1.244 ms

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On 10/31/13, 6:42 AM, Kyotaro HORIGUCHI wrote:
> Hello, This patch might be too complicated (and seems somewhat ad
> hoc) for the gain, but more index usage for this kind of
> operation should be worth doing.

There is a new compiler warning:

setrefs.c: In function ‘set_plan_refs’:
setrefs.c:782:7: warning: initialization from incompatible pointer type
[enabled by default]

Thank you for pointing out. I missed the warning.

> There is a new compiler warning:
>
> setrefs.c: In function ‘set_plan_refs’:
> setrefs.c:782:7: warning: initialization from incompatible pointer type
> [enabled by default]

Added explicit cast there and rebased to current master.
Checked no new warning by this patch.
make check succeeded at both $(src) and $(src)/src/test.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

On Wed, 2013-11-13 at 17:25 +0900, Kyotaro HORIGUCHI wrote:

> Added explicit cast there and rebased to current master.
> Checked no new warning by this patch.
> make check succeeded at both $(src) and $(src)/src/test.

This patch also has whitespace errors detected by git diff --check.

Hello, As I mentioned on another thread, I'll reorganize patches
including this and repost them.

Please wait for a while.

--
Kyotaro Horiguchi
NTT Open Source Software Center

Kyotaro HORIGUCHI <horiguchi(dot)kyotaro(at)lab(dot)ntt(dot)co(dot)jp> writes:
> [ union_uses_idx_v2_20131113.patch ]

I'm aware that you said you were going to refactor this, but I took a
quick look through it anyway. I don't think mere refactoring is going
to make me happy with it :-(.

The basic problem here, as well as with some of the hackery that's
been proposed recently in planner.c, is that we can't really get much
further with improving this layer of the planner until we bite the
bullet and convert this layer to work with Paths not finished Plans.
Look at what you're proposing here: do a complete planning cycle on
the subquery (underneath which both ordered and unordered Paths will
be considered, and one or the other will get thrown away). Then do
*another* complete planning cycle with ordered output forced. Then
compare costs of the results. This is hugely inefficient, and it
produces far-from-ideal results too, because you're forced to make a
decision right there on which subquery plan to use; you can't make the
globally optimal choice after considering costs of all the subqueries.
What we need to do is fix things so we can get multiple Paths out of
the subquery planning step, some ordered and some not. Then we could
construct Paths for both the brute force and merge-append styles of
computing the UNION result, and finally choose the cheapest Path at the
top level.

The same goes for hacking around in grouping_planner. That function
is well past the point of collapsing of its own weight; we need
to invest some effort in refactoring before we can afford to add
much more complexity there. And I think the logical way to refactor
is to rewrite the code in a Path-generation-and-comparison style.
(Actually, grouping_planner would need to be fixed first, since
that's what would have to produce the Paths we're hoping to compare
in prepunion.)

I had hoped to make some progress on that rewrite this past summer,
but ended up with no time to work on it :-(. There's going to be
a lot of boring infrastructure work before we see much in the way
of user-visible improvement, I'm afraid, so it's kind of hard to
make time for it.

regards, tom lane

Thank you for looking in detail for this patch, and giving
thoughtful advices.

> I'm aware that you said you were going to refactor this, but I took a
> quick look through it anyway. I don't think mere refactoring is going
> to make me happy with it :-(.

Ouch.. Anyway I've refactored this patch altogether with the
another 'unique index' patch and re-splitted into three
parts. One is the 'unique-index stuff' and the second is 'Adding
pathkeys and unique info into struct Plan' patch and the third is
'maily-in-prepunion stuff'. They will be sent in other messages
although for the scarce chance to be picked up :-)

> The basic problem here, as well as with some of the hackery that's
> been proposed recently in planner.c, is that we can't really get much
> further with improving this layer of the planner until we bite the
> bullet and convert this layer to work with Paths not finished Plans.

It is right but hard to go. I would be able to put my little
power on the issue but the planner hardly seems to be get
refactored gradually.

> Look at what you're proposing here: do a complete planning cycle on
> the subquery (underneath which both ordered and unordered Paths will
> be considered, and one or the other will get thrown away). Then do
> *another* complete planning cycle with ordered output forced. Then
> compare costs of the results.

Exactly.

> This is hugely inefficient, and it produces far-from-ideal
> results too, because you're forced to make a decision right
> there on which subquery plan to use; you can't make the
> globally optimal choice after considering costs of all the
> subqueries.

Umm. Yes, I know I've done it in somewhat brute way and it costs
a little too much if the subqueries of UNION is rather large, but
I suppose it comparably small to the whole execution time for
most cases.

Putting it aside, from the viewpoint of global-optimizations,
current planner also doesn't do such optimizations. Moreover it
doesn't consider sorted plans possibly available and
effective. Ignoring the additional planning cost (:-), for the
UNION queries with LIMITS on large partitioned tables with
apropriate indexes (mmm. I suppose it is not so narrow gate..),
the query runtime should be extremely shortend.

> What we need to do is fix things so we can get multiple Paths
> out of the subquery planning step, some ordered and some not.
> Then we could construct Paths for both the brute force and
> merge-append styles of computing the UNION result, and finally
> choose the cheapest Path at the top level.

Agreed with it at a glance. It sounds quite reasonable. I've been
a bit worried about that the paths and plans seem to be fused in
some extent in grouping_planner, and prepunion
(plan_set_operations) is jumping over path-generation phase to
make plans directly. (And about that I pushed it more on the
way..)

> The same goes for hacking around in grouping_planner. That function
> is well past the point of collapsing of its own weight; we need
> to invest some effort in refactoring before we can afford to add
> much more complexity there. And I think the logical way to refactor
> is to rewrite the code in a Path-generation-and-comparison style.
> (Actually, grouping_planner would need to be fixed first, since
> that's what would have to produce the Paths we're hoping to compare
> in prepunion.)

It seems necessary but also seems far far away and hard to
go.

> I had hoped to make some progress on that rewrite this past summer,
> but ended up with no time to work on it :-(. There's going to be
> a lot of boring infrastructure work before we see much in the way
> of user-visible improvement, I'm afraid, so it's kind of hard to
> make time for it.

Anyway, because I've happened to pass too close by the issue, I
will consider on that for some time (although I would hardly come
up with spiffy solution in a short time.)

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello, I've totally refactored the series of pathes and cut out
the appropriate portion as 'UNION stuff'.

This patch rquires another 'pathkeys expansion using fully-orderd
index' patch to work.

http://www.postgresql.org/message-id/20131119.203516.251520490.horiguchi.kyotaro@lab.ntt.co.jp

1. plan_with_pathkeys_v1_20131119.patch

This is a patch adding pathkeys (and uniqueness) information on
struct Plan to do what the latter part of grouping_planner does
on current_pathkeys in seemingly autonomous way. As in the
previous discussion, this is in a sense a bad direction to
go. But this patch make the path manipulations occured in the
latter of grouping_planner simple and would reduce extra sorting
and uniq'ing.

2. union_uses_idx_v3_20131119.patch

This is made to apply after the first patch above. The core of
"Using indices for UNION". This is - as in the previous
discussion - also not in so smart way to do that. Most of all,
this patch runs subquery_planner additionally for UNION with
some conditions. Nevertheless, the expected gain should not be
small.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hello, As I was reconsidering after your advise, I came up with
an idea of hacking on query tree tranaformation phase in
subquery_planner, not on that of plan generation phase as
before. (And the older patch is totally scrapped:-)

Currently flatten_simple_union_all() flattens 'simple' UNION
'ALL' at the top level of 'current' query. I noticed that a
little modification there also could flatten simple UNION (w/o
ALL), and it has finally almost same effect regarding more usage
of indexes for UNION. Additionally, applying still more the
'UNION ALL and inheritance table' patch, even coveres UNION's on
inheritance tables.

This patch is far small and neat (though I say so myself :-) than
the previous ones. The following plans we got from unpatched
PostgreSQL.

original=# explain (analyze on, costs off)
| select a, b from cu11 union select a, b from cu12 order by a, b limit 10;
| QUERY PLAN
| -----------------------------------------------------------------------------
| Limit (actual time=272.252..272.259 rows=10 loops=1)
| -> Unique (actual time=272.251..272.258 rows=10 loops=1)
| -> Sort (actual time=272.249..272.252 rows=10 loops=1)
| Sort Key: cu11.a, cu11.b
| Sort Method: external sort Disk: 3520kB
| -> Append (actual time=0.020..70.935 rows=200000 loops=1)
| -> Seq Scan on cu11 (actual time=0.019..26.741 rows=100000 loops=1)
| -> Seq Scan on cu12 (actual time=0.006..25.183 rows=100000 loops=1)
| Total runtime: 273.162 ms

And of course for * (= a, b, c, d) this,

original=# explain (analyze on, costs off)
| select * from cu11 union select * from cu12 order by a, b limit 10;
| QUERY PLAN
| ----------------------------------------------------------------------------
| Limit (actual time=234.880..234.891 rows=10 loops=1)
| -> Unique (actual time=234.879..234.889 rows=10 loops=1)
| -> Sort (actual time=234.878..234.881 rows=10 loops=1)
| Sort Key: cu11.a, cu11.b, cu11.c, cu11.d
| Sort Method: external sort Disk: 5280kB
| -> Append (actual time=0.017..49.502 rows=200000 loops=1)
| -> Seq Scan on cu11 (actual time=0.017..15.649 rows=100000 loops=1)
| -> Seq Scan on cu12 (actual time=0.007..14.939 rows=100000 loops=1)
| Total runtime: 236.029 ms

We'll get the following plan changed with this patch plus the
latest "pathkey_and_uniqueindx_v4_20131122.patch" patcch. (It got
a small fix on pathkeys fixation for index paths)

https://commitfest.postgresql.org/action/patch_view?id=1280

patched=# explain (analyze on, costs off)
| select * from cu11 union select * from cu12 order by a, b limit 10;
| QUERY PLAN
| ------------------------------------------------------------------------------
| Limit (actual time=0.059..0.081 rows=10 loops=1)
| -> Unique (actual time=0.058..0.079 rows=10 loops=1)
| -> Merge Append (actual time=0.056..0.065 rows=10 loops=1)
| Sort Key: cu11.a, cu11.b, cu11.c, cu11.d
| -> Index Scan ... on cu11 (actual time=0.032..0.037 rows=10 loops=1)
| -> Index Scan ... on cu12 (actual time=0.021..0.021 rows=1 loops=1)
| Total runtime: 0.162 ms

Moreover, with the 'UNION ALL' patches , say,
union_inh_idx_typ1_v1_20131024.patch and
union_inh_idx_typ1_add_v1_20131024.patch, we'll get the following
plan for UNION on inhertance tables,

https://commitfest.postgresql.org/action/patch_view?id=1270

patched2=# explain (analyze on, costs off)
| select * from pu1 union select * from pu2 order by a, b limit 10;
| QUERY PLAN
| ---------------------------------------------------------------------------
| Limit (actual time=0.209..0.234 rows=10 loops=1)
| -> Unique (actual time=0.206..0.230 rows=10 loops=1)
| -> Merge Append (actual time=0.204..0.216 rows=10 loops=1)
| Sort Key: pu1.a, pu1.b, pu1.c, pu1.d
| -> Index Scan..on pu1 (actual time=0.004..0.004 rows=0 loops=1)
| -> Index Scan..on cu11 (actual time=0.050..0.058 rows=10 loops=1)
| -> Index Scan..on cu12 (actual time=0.052..0.052 rows=1 loops=1)
| -> Index Scan..on pu2 (actual time=0.002..0.002 rows=0 loops=1)
| -> Index Scan..on cu21 (actual time=0.046..0.046 rows=1 loops=1)
| -> Index Scan..on cu22 (actual time=0.046..0.046 rows=1 loops=1)
| Total runtime: 0.627 ms

The attached union_uses_idx_v4_20131122.patch is changed as
follows.

- Rebased to current master.

- Scrapped the whold old stuff.

- flatten_simple_union_all() is renamed to
flatten_simple_union() and modified to do so. UNION is
flattend only if sortClause exists and distinctClause is NIL.

======
Test tables can be created following the command below,

| create table pu1 (a int not null, b int not null, c int, d text);
| create unique index i_pu1_ab on pu1 (a, b);
| create table cu11 (like pu1 including all) inherits (pu1);
| create table cu12 (like pu1 including all) inherits (pu1);
| create table pu2 (like pu1 including all);
| create table cu21 (like pu2 including all) inherits (pu2);
| create table cu22 (like pu2 including all) inherits (pu2);
| insert into cu11 (select a / 5, 4 - (a % 5), a, 'cu11' from generate_series(000000, 099999) a);
| insert into cu12 (select a / 5, 4 - (a % 5), a, 'cu12' from generate_series(100000, 199999) a);
| insert into cu21 (select a / 5, 4 - (a % 5), a, 'cu21' from generate_series(200000, 299999) a);
| insert into cu22 (select a / 5, 4 - (a % 5), a, 'cu22' from generate_series(300000, 399999) a);
=====

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

This is cont'd from CF3.

http://www.postgresql.org/message-id/20131122.165927.27412386.horiguchi.kyotaro@lab.ntt.co.jp

The issue in brief is that UNION is never flattened differently
to UNION ALL so UNION cannot make use of index scan even if
usable.

This patch flattens UNION likewise currently did for UNION ALL.

This patch needs another 'UNION ALL' patch and further gain with
even another 'Widening application of indices' patch. ('Ready for
Commit' now in CF3..)

http://www.postgresql.org/message-id/20140114.180447.145186052.horiguchi.kyotaro@lab.ntt.co.jp
http://www.postgresql.org/message-id/20140114.180810.122352231.horiguchi.kyotaro@lab.ntt.co.jp

You can see the detailed outlines in the message at here,

http://www.postgresql.org/message-id/20131031.194251.12577697.horiguchi.kyotaro@lab.ntt.co.jp

The attached patche is rebased to current 9.4dev HEAD and make
check at the topmost directory and src/test/isolation are passed
without error.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Sorry, I missed to attach file.

> This is cont'd from CF3.
>
> http://www.postgresql.org/message-id/20131122.165927.27412386.horiguchi.kyotaro@lab.ntt.co.jp
>
> The issue in brief is that UNION is never flattened differently
> to UNION ALL so UNION cannot make use of index scan even if
> usable.
>
> This patch flattens UNION likewise currently did for UNION ALL.
>
> This patch needs another 'UNION ALL' patch and further gain with
> even another 'Widening application of indices' patch. ('Ready for
> Commit' now in CF3..)
>
> http://www.postgresql.org/message-id/20140114.180447.145186052.horiguchi.kyotaro@lab.ntt.co.jp
> http://www.postgresql.org/message-id/20140114.180810.122352231.horiguchi.kyotaro@lab.ntt.co.jp
>
>
> You can see the detailed outlines in the message at here,
>
> http://www.postgresql.org/message-id/20131031.194251.12577697.horiguchi.kyotaro@lab.ntt.co.jp
>
> The attached patche is rebased to current 9.4dev HEAD and make
> check at the topmost directory and src/test/isolation are passed
> without error.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center

Hi,

On 2014-01-14 18:10:40 +0900, Kyotaro HORIGUCHI wrote:
> This is cont'd from CF3.
>
> http://www.postgresql.org/message-id/20131122.165927.27412386.horiguchi.kyotaro@lab.ntt.co.jp
>
> The issue in brief is that UNION is never flattened differently
> to UNION ALL so UNION cannot make use of index scan even if
> usable.
>
> This patch flattens UNION likewise currently did for UNION ALL.
>
> This patch needs another 'UNION ALL' patch and further gain with
> even another 'Widening application of indices' patch. ('Ready for
> Commit' now in CF3..)
>
> http://www.postgresql.org/message-id/20140114.180447.145186052.horiguchi.kyotaro@lab.ntt.co.jp
> http://www.postgresql.org/message-id/20140114.180810.122352231.horiguchi.kyotaro@lab.ntt.co.jp
>
>
> You can see the detailed outlines in the message at here,
>
> http://www.postgresql.org/message-id/20131031.194251.12577697.horiguchi.kyotaro@lab.ntt.co.jp
>
> The attached patche is rebased to current 9.4dev HEAD and make
> check at the topmost directory and src/test/isolation are passed
> without error.

I haven't really followed this topic, so please excuse my ignorance.

This is still marked as "needs review" in
https://commitfest.postgresql.org/action/patch_view?id=1374 . But I am
not sure the patch as is is relevant after
a87c729153e372f3731689a7be007bc2b53f1410?

Greetings,

Andres Freund

--
Andres Freund http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

Andres Freund <andres(at)2ndquadrant(dot)com> writes:
> On 2014-01-14 18:10:40 +0900, Kyotaro HORIGUCHI wrote:
>> This patch flattens UNION likewise currently did for UNION ALL.

> I haven't really followed this topic, so please excuse my ignorance.

> This is still marked as "needs review" in
> https://commitfest.postgresql.org/action/patch_view?id=1374 . But I am
> not sure the patch as is is relevant after
> a87c729153e372f3731689a7be007bc2b53f1410?

I think it's an independent issue.

After a quick read of the patch (which is really badly explained :-()
I think the idea is that a nest of UNIONs with no datatype conversions
can be flattened into a UNION ALL appendrel, with the required duplicate
elimination handled by sticking a DISTINCT onto the top level.

However, it's not clear to me that this is worth the trouble. The
DISTINCT would act as an optimization fence preventing the subquery from
being flattened any further, so it doesn't seem like there would be any
global benefit just because it now contains a simple appendrel rather than
a setop tree. And a nest of conversion-free UNIONs already results in a
plan that's a flat Append followed by sort/uniq, which seems like the same
thing you'd get from the DISTINCT. So what's the point?

regards, tom lane

I wrote:
> However, it's not clear to me that this is worth the trouble. The
> DISTINCT would act as an optimization fence preventing the subquery from
> being flattened any further, so it doesn't seem like there would be any
> global benefit just because it now contains a simple appendrel rather than
> a setop tree. And a nest of conversion-free UNIONs already results in a
> plan that's a flat Append followed by sort/uniq, which seems like the same
> thing you'd get from the DISTINCT. So what's the point?

Oh, after re-reading the earlier part of the thread I get the point ---
after making this change, the planner will consider some plan types for
the DISTINCT that it wouldn't have found in the setop-tree planning path.
Specifically it can make use of a mergeappend of sorted paths for the
individual union leaf queries. That can't happen in the generic setop
planning code because we have no ability to consider more than one plan
for any leaf query.

I still think this stuff mostly needs to be thrown away and rewritten
in Path-creation style, but that's a long-term project. In the meantime
this seems like a relatively small increment of complexity, so maybe it's
worth applying. I'm concerned about the method for building a new
DISTINCT clause though; the best that can be said for that is that it's
a crude hack, and I'm less than convinced that there are no cases where
it'll dump core.

regards, tom lane

I wrote:
> I still think this stuff mostly needs to be thrown away and rewritten
> in Path-creation style, but that's a long-term project. In the meantime
> this seems like a relatively small increment of complexity, so maybe it's
> worth applying. I'm concerned about the method for building a new
> DISTINCT clause though; the best that can be said for that is that it's
> a crude hack, and I'm less than convinced that there are no cases where
> it'll dump core.

OK, after still more time thinking about it, here's the issues with that
way of generating a DISTINCT clause corresponding to the UNION:

1. Calling transformDistinctClause with a NULL pstate seems pretty unsafe.
It might accidentally fail to fail, today, but it's surely fragile.
It's violating the API contract not only of transformDistinctClause
itself (which is not documented as accepting a NULL pstate) but of
addTargetToGroupList (q.v.). A minimum requirement before I'd accept a
patch that did that is that it extended the header comments of those
functions to specify under what circumstances a NULL pstate can be passed.
However, that's not the direction to go, because of #2.

2. This approach potentially changes the semantics of the UNION. (This is
only important for a datatype that has more than one btree equality
operator, but let's posit that.) transformDistinctClause, as per its
header comment, allows the outer ORDER BY to influence which equality
operator it picks for DISTINCT. However, in the case of
"(SELECT ... UNION SELECT ...) ORDER BY ...", the UNION semantics were
chosen without reference to the ORDER BY, so it's possible that the
equality operators cited in the SetOperationStmt's groupClauses list are
not what you'd get from applying transformDistinctClause as the patch does.
It is not okay for the planner to override the parser's choice of
semantics like that.

Now I'm fairly sure that planner.c is expecting that the query's
distinctClause be a superset of the sortClause if any (cf comments for
SortGroupClause in parsenodes.h), so it wouldn't be okay to just blindly
build a distinctClause from topop->groupClauses. I think what you need
to do is check that topop->groupClauses is compatible with the sortClause
if any (skipping the flattening transformation if not) and then build a
distinctClause by extending the sort clause list with any missing items
from topop->groupClauses. So this is sort of like what
transformDistinctClause does, but different in detail, and the failure
case is to not do the transformation, rather than ereport'ing. (See also
generate_setop_grouplist, which you could almost use except that it's not
expecting to have to merge with a sortClause list.)

So this is all doable enough, but you're probably going to end up with
a new distinctClause-generating function that's at least twice the size
of the patch's former net code addition. So the question is whether it's
worth the trouble, considering that all this code has (I hope) a life
expectancy of no more than one or two more release cycles.

I'm going to set the patch back to Waiting on Author, but unless you
are prepared to rewrite the distinctClause creation code in the next
couple of days, you should change it to Returned with Feedback.

regards, tom lane

Hello. Thank you for the attentive comments.

> I wrote:
> > I still think this stuff mostly needs to be thrown away and rewritten
> > in Path-creation style, but that's a long-term project. In the meantime
> > this seems like a relatively small increment of complexity, so maybe it's
> > worth applying. I'm concerned about the method for building a new
> > DISTINCT clause though; the best that can be said for that is that it's
> > a crude hack, and I'm less than convinced that there are no cases where
> > it'll dump core.
>
> OK, after still more time thinking about it, here's the issues with that
> way of generating a DISTINCT clause corresponding to the UNION:
>
> 1. Calling transformDistinctClause with a NULL pstate seems pretty unsafe.
> It might accidentally fail to fail, today, but it's surely fragile.
> It's violating the API contract not only of transformDistinctClause
> itself (which is not documented as accepting a NULL pstate) but of
> addTargetToGroupList (q.v.).

Hmm I'm ashamed to have missed addTargetToGroupList. You are
right about that. I saw only parser_errposition to field the
NULL.. It should be fixed anyway.

> A minimum requirement before I'd accept a
> patch that did that is that it extended the header comments of those
> functions to specify under what circumstances a NULL pstate can be passed.
> However, that's not the direction to go, because of #2.
>
> 2. This approach potentially changes the semantics of the UNION. (This is
> only important for a datatype that has more than one btree equality
> operator, but let's posit that.) transformDistinctClause, as per its
> header comment, allows the outer ORDER BY to influence which equality
> operator it picks for DISTINCT. However, in the case of
> "(SELECT ... UNION SELECT ...) ORDER BY ...", the UNION semantics were
> chosen without reference to the ORDER BY,

If my understanding is correct, the query is equivalent to it
without the parens. The ORDER BY belongs to the topmost UNION on
both cases. Actually planner compailns about "(SELECT...UNION
SELECT ... ORDER BY) ORDER BY" that "multiple ORDER BY clauses
not allowed" with/without this patch.

> so it's possible that the
> equality operators cited in the SetOperationStmt's groupClauses list are
> not what you'd get from applying transformDistinctClause as the patch does.

This patch flattenes and the SetOperationStmt was put out along
with its groupClause. But the groupClauses is originally
generated from targetlist in transformSetOperationTree. And the
new DistinctClause is generated also from the same targetlist
consulting to sortClause. They are not in the same order but it
doesn't matter. Is it wrong? If it would make some trouble, I
could add an check it out or count it on making the
DistinctClauses..

Finally,

explain (costs off) select a, b from c11 union select a, b from c12 order by b limit 10000;
| QUERY PLAN
| -----------------------------------------
| Limit
| -> Sort
| Sort Key: c11.b
| -> HashAggregate
| Group Key: c11.b, c11.a
| -> Append
| -> Seq Scan on c11
| -> Seq Scan on c12

This HashAggregate does DISTINCT which was performed by using
Sort-Unique without this patch, and yields the same result, I
believe.

> It is not okay for the planner to override the parser's choice of
> semantics like that.

As described above, as far as I saw, itself seems to be a problem.

> Now I'm fairly sure that planner.c is expecting that the query's
> distinctClause be a superset of the sortClause if any (cf comments for
> SortGroupClause in parsenodes.h), so it wouldn't be okay to just blindly
> build a distinctClause from topop->groupClauses.

Yes, it could be but counting the sortClause into distinctClause
is crucial factor for getting rid of unnecessary sorting.

> I think what you need
> to do is check that topop->groupClauses is compatible with the sortClause
> if any (skipping the flattening transformation if not) and then build a
> distinctClause by extending the sort clause list with any missing items
> from topop->groupClauses.

Ah, yes I agree as I described above.

> So this is sort of like what
> transformDistinctClause does, but different in detail, and the failure
> case is to not do the transformation, rather than ereport'ing. (See also
> generate_setop_grouplist, which you could almost use except that it's not
> expecting to have to merge with a sortClause list.)

Thank you. I'll follow this advise.

> So this is all doable enough, but you're probably going to end up with
> a new distinctClause-generating function that's at least twice the size
> of the patch's former net code addition. So the question is whether it's
> worth the trouble, considering that all this code has (I hope) a life
> expectancy of no more than one or two more release cycles.

Hmm. Since this is a kind of local optimization, some future
drastic reconstructing might make this useless. But it doesn't
seem the reason not to do this. (Ignoring the size..)

> I'm going to set the patch back to Waiting on Author, but unless you
> are prepared to rewrite the distinctClause creation code in the next
> couple of days, you should change it to Returned with Feedback.

Ok, I agree to the deal. This needs more refinement.

regards,

--
Kyotaro Horiguchi
NTT Open Source Software Center