pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedtwo table join with order by on both tables attributes
8+ messages / 4 participants
[nested] [flat]
* two table join with order by on both tables attributes
@ 2014-08-07 23:21 Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` Re: two table join with order by on both tables attributes David G Johnston <david.g.johnston@gmail.com>
0 siblings, 1 reply; 8+ messages in thread
From: Evgeniy Shishkin @ 2014-08-07 23:21 UTC (permalink / raw)
To: pgsql-performance
Hello,
suppose you have two very simple tables with fk dependency, by which we join them
and another attribute for sorting
like this
select * from users join notifications on users.id=notifications.user_id ORDER BY users.priority desc ,notifications.priority desc limit 10;
Very typical web query.
No matter which composite indexes i try, postgresql can not make efficient nested loop plan using indexes.
It chooses all sorts of seq scans and hash joins or merge join and always a sort node and then a limit 10.
Neither plan provides acceptable performance. And tables tend to grow =\
Can anybody suggest something or explain this behavior?
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: two table join with order by on both tables attributes
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
@ 2014-08-07 23:42 ` David G Johnston <david.g.johnston@gmail.com>
2014-08-08 00:02 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
0 siblings, 1 reply; 8+ messages in thread
From: David G Johnston @ 2014-08-07 23:42 UTC (permalink / raw)
To: pgsql-performance
Evgeniy Shishkin wrote
> Hello,
>
> suppose you have two very simple tables with fk dependency, by which we
> join them
> and another attribute for sorting
>
> like this
> select * from users join notifications on users.id=notifications.user_id
> ORDER BY users.priority desc ,notifications.priority desc limit 10;
>
> Very typical web query.
>
> No matter which composite indexes i try, postgresql can not make efficient
> nested loop plan using indexes.
> It chooses all sorts of seq scans and hash joins or merge join and always
> a sort node and then a limit 10.
>
> Neither plan provides acceptable performance. And tables tend to grow =\
>
> Can anybody suggest something or explain this behavior?
Can you explain why a nested loop is best for your data? Given my
understanding of an expected "priority"cardinality I would expect your ORDER
BY to be extremely inefficient and not all that compatible with a nested
loop approach.
You can use the various parameters listed on this page to force the desired
plan and then provide EXPLAIN ANALYZE results for the various executed plans
and compare them.
http://www.postgresql.org/docs/9.3/interactive/runtime-config-query.html#RUNTIME-CONFIG-QUERY-ENABLE
And now for the obligatory "read this" link:
https://wiki.postgresql.org/wiki/SlowQueryQuestions
If you can show that in fact the nested loop (or some other plan) performs
better than the one chosen by the planner - and can provide data that the
developers can use to replicate the experiment - then improvements can be
made. At worse you will come to understand why the planner is right and can
then explore alternative models.
David J.
--
View this message in context: http://postgresql.1045698.n5.nabble.com/two-table-join-with-order-by-on-both-tables-attributes-tp581...
Sent from the PostgreSQL - performance mailing list archive at Nabble.com.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: two table join with order by on both tables attributes
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` Re: two table join with order by on both tables attributes David G Johnston <david.g.johnston@gmail.com>
@ 2014-08-08 00:02 ` Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 00:19 ` Re: two table join with order by on both tables attributes Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 8+ messages in thread
From: Evgeniy Shishkin @ 2014-08-08 00:02 UTC (permalink / raw)
To: David G Johnston <david.g.johnston@gmail.com>; +Cc: pgsql-performance
My question was about that you can not have fast execution of this kind of query in postgresql.
With any runtime configuration you just swith from seq scan and hash join to merge join, and then you have a sort node.
In my understanding, i need to have two indexes
on users(priority desc, id)
and notifications(user_id, priority desc)
then postgresql would choose nested loop and get sorted data from indexes.
But it wont.
I don't understand why.
Do you have any schema and GUCs which performs this kind of query well?
Sorry for top posting.
> Can you explain why a nested loop is best for your data? Given my
> understanding of an expected "priority"cardinality I would expect your ORDER
> BY to be extremely inefficient and not all that compatible with a nested
> loop approach.
>
> You can use the various parameters listed on this page to force the desired
> plan and then provide EXPLAIN ANALYZE results for the various executed plans
> and compare them.
>
> http://www.postgresql.org/docs/9.3/interactive/runtime-config-query.html#RUNTIME-CONFIG-QUERY-ENABLE
>
> And now for the obligatory "read this" link:
>
> https://wiki.postgresql.org/wiki/SlowQueryQuestions
>
> If you can show that in fact the nested loop (or some other plan) performs
> better than the one chosen by the planner - and can provide data that the
> developers can use to replicate the experiment - then improvements can be
> made. At worse you will come to understand why the planner is right and can
> then explore alternative models.
>
> David J.
>
>
>
>
> --
> View this message in context: http://postgresql.1045698.n5.nabble.com/two-table-join-with-order-by-on-both-tables-attributes-tp581...
> Sent from the PostgreSQL - performance mailing list archive at Nabble.com.
>
>
> --
> Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-performance
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: two table join with order by on both tables attributes
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` Re: two table join with order by on both tables attributes David G Johnston <david.g.johnston@gmail.com>
2014-08-08 00:02 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
@ 2014-08-08 00:19 ` Tom Lane <tgl@sss.pgh.pa.us>
2014-08-08 00:43 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
0 siblings, 1 reply; 8+ messages in thread
From: Tom Lane @ 2014-08-08 00:19 UTC (permalink / raw)
To: Evgeniy Shishkin <itparanoia@gmail.com>; +Cc: David G Johnston <david.g.johnston@gmail.com>; pgsql-performance
Evgeniy Shishkin <itparanoia@gmail.com> writes:
>> select * from users join notifications on users.id=notifications.user_id ORDER BY users.priority desc ,notifications.priority desc limit 10;
> In my understanding, i need to have two indexes
> on users(priority desc, id)
> and notifications(user_id, priority desc)
> then postgresql would choose nested loop and get sorted data from indexes.
> But it wont.
Indeed. If you think a bit harder, you'll realize that the plan you
suggest would *not* produce the sort order requested by this query.
It would (if I'm not confused myself) produce an ordering like
users.priority desc, id asc, notifications.priority desc
which would only match what the query asks for if there's just a single
value of id per users.priority value.
Offhand I think that the planner will not recognize a nestloop as
producing a sort ordering of this kind even if the query did request the
right ordering. That could perhaps be improved, but I've not seen many
if any cases where it would be worth the trouble.
regards, tom lane
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: two table join with order by on both tables attributes
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` Re: two table join with order by on both tables attributes David G Johnston <david.g.johnston@gmail.com>
2014-08-08 00:02 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 00:19 ` Re: two table join with order by on both tables attributes Tom Lane <tgl@sss.pgh.pa.us>
@ 2014-08-08 00:43 ` Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 01:05 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
0 siblings, 1 reply; 8+ messages in thread
From: Evgeniy Shishkin @ 2014-08-08 00:43 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: David G Johnston <david.g.johnston@gmail.com>; pgsql-performance
>>> select * from users join notifications on users.id=notifications.user_id ORDER BY users.priority desc ,notifications.priority desc limit 10;
>
>> In my understanding, i need to have two indexes
>> on users(priority desc, id)
>> and notifications(user_id, priority desc)
>> then postgresql would choose nested loop and get sorted data from indexes.
>> But it wont.
>
> Indeed. If you think a bit harder, you'll realize that the plan you
> suggest would *not* produce the sort order requested by this query.
> It would (if I'm not confused myself) produce an ordering like
> users.priority desc, id asc, notifications.priority desc
> which would only match what the query asks for if there's just a single
> value of id per users.priority value.
>
> Offhand I think that the planner will not recognize a nestloop as
> producing a sort ordering of this kind even if the query did request the
> right ordering. That could perhaps be improved, but I've not seen many
> if any cases where it would be worth the trouble.
Thanks Tom, you are right.
But may be some sort of skip index scan ala loose index scan will help with index on notifications(priority desc,user_id)?
I know that this is currently not handled by native executors.
May by i can work around this using WITH RECURSIVE query?
Also, are there any plans to handle loose index scan in the upcoming release?
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: two table join with order by on both tables attributes
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` Re: two table join with order by on both tables attributes David G Johnston <david.g.johnston@gmail.com>
2014-08-08 00:02 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 00:19 ` Re: two table join with order by on both tables attributes Tom Lane <tgl@sss.pgh.pa.us>
2014-08-08 00:43 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
@ 2014-08-08 01:05 ` Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 13:29 ` Re: two table join with order by on both tables attributes Marti Raudsepp <marti@juffo.org>
0 siblings, 1 reply; 8+ messages in thread
From: Evgeniy Shishkin @ 2014-08-08 01:05 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: David G Johnston <david.g.johnston@gmail.com>; pgsql-performance
> On 08 Aug 2014, at 03:43, Evgeniy Shishkin <itparanoia@gmail.com> wrote:
>
>>>> select * from users join notifications on users.id=notifications.user_id ORDER BY users.priority desc ,notifications.priority desc limit 10;
>>
>>> In my understanding, i need to have two indexes
>>> on users(priority desc, id)
>>> and notifications(user_id, priority desc)
>>> then postgresql would choose nested loop and get sorted data from indexes.
>>> But it wont.
>>
>> Indeed. If you think a bit harder, you'll realize that the plan you
>> suggest would *not* produce the sort order requested by this query.
>> It would (if I'm not confused myself) produce an ordering like
>> users.priority desc, id asc, notifications.priority desc
>> which would only match what the query asks for if there's just a single
>> value of id per users.priority value.
>>
>> Offhand I think that the planner will not recognize a nestloop as
>> producing a sort ordering of this kind even if the query did request the
>> right ordering. That could perhaps be improved, but I've not seen many
>> if any cases where it would be worth the trouble.
>
And actually with this kind of query we really want the most wanted notifications, by the user.
So we really can rewrite to order by users.priority desc, id asc, notifications.priority desc according to business logic.
And we will benefit if this case would be improved.
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: two table join with order by on both tables attributes
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` Re: two table join with order by on both tables attributes David G Johnston <david.g.johnston@gmail.com>
2014-08-08 00:02 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 00:19 ` Re: two table join with order by on both tables attributes Tom Lane <tgl@sss.pgh.pa.us>
2014-08-08 00:43 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 01:05 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
@ 2014-08-08 13:29 ` Marti Raudsepp <marti@juffo.org>
2014-08-08 13:57 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
0 siblings, 1 reply; 8+ messages in thread
From: Marti Raudsepp @ 2014-08-08 13:29 UTC (permalink / raw)
To: Evgeniy Shishkin <itparanoia@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; David G Johnston <david.g.johnston@gmail.com>; pgsql-performance
On Fri, Aug 8, 2014 at 4:05 AM, Evgeniy Shishkin <itparanoia@gmail.com> wrote:
>>>>> select * from users join notifications on users.id=notifications.user_id ORDER BY users.priority desc ,notifications.priority desc limit 10;
>>>> In my understanding, i need to have two indexes
>>>> on users(priority desc, id)
>>>> and notifications(user_id, priority desc)
> And actually with this kind of query we really want the most wanted notifications, by the user.
> So we really can rewrite to order by users.priority desc, id asc, notifications.priority desc according to business logic.
You can rewrite it with LATERAL to trick the planner into sorting each
user's notifications separately. This should give you the nestloop
plan you expect:
SELECT *
FROM users,
LATERAL (
SELECT * FROM notifications WHERE notifications.user_id=users.id
ORDER BY notifications.priority DESC
) AS notifications
ORDER BY users.priority DESC, users.id
It would be great if Postgres could do this transformation automatically.
There's a "partial sort" patch in the current CommitFest, which would
solve the problem partially (it could use the index on users, but the
notifications sort would have to be done in memory still).
https://commitfest.postgresql.org/action/patch_view?id=1368
Regards,
Marti
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
* Re: two table join with order by on both tables attributes
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` Re: two table join with order by on both tables attributes David G Johnston <david.g.johnston@gmail.com>
2014-08-08 00:02 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 00:19 ` Re: two table join with order by on both tables attributes Tom Lane <tgl@sss.pgh.pa.us>
2014-08-08 00:43 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 01:05 ` Re: two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 13:29 ` Re: two table join with order by on both tables attributes Marti Raudsepp <marti@juffo.org>
@ 2014-08-08 13:57 ` Evgeniy Shishkin <itparanoia@gmail.com>
0 siblings, 0 replies; 8+ messages in thread
From: Evgeniy Shishkin @ 2014-08-08 13:57 UTC (permalink / raw)
To: Marti Raudsepp <marti@juffo.org>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; David G Johnston <david.g.johnston@gmail.com>; pgsql-performance
> On 08 Aug 2014, at 16:29, Marti Raudsepp <marti@juffo.org> wrote:
>
> On Fri, Aug 8, 2014 at 4:05 AM, Evgeniy Shishkin <itparanoia@gmail.com> wrote:
>>>>>> select * from users join notifications on users.id=notifications.user_id ORDER BY users.priority desc ,notifications.priority desc limit 10;
>
>>>>> In my understanding, i need to have two indexes
>>>>> on users(priority desc, id)
>>>>> and notifications(user_id, priority desc)
>
>> And actually with this kind of query we really want the most wanted notifications, by the user.
>> So we really can rewrite to order by users.priority desc, id asc, notifications.priority desc according to business logic.
>
> You can rewrite it with LATERAL to trick the planner into sorting each
> user's notifications separately. This should give you the nestloop
> plan you expect:
>
> SELECT *
> FROM users,
> LATERAL (
> SELECT * FROM notifications WHERE notifications.user_id=users.id
> ORDER BY notifications.priority DESC
> ) AS notifications
> ORDER BY users.priority DESC, users.id
>
Thank you very much.
> It would be great if Postgres could do this transformation automatically.
>
> There's a "partial sort" patch in the current CommitFest, which would
> solve the problem partially (it could use the index on users, but the
> notifications sort would have to be done in memory still).
> https://commitfest.postgresql.org/action/patch_view?id=1368
>
> Regards,
> Marti
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 8+ messages in thread
end of thread, other threads:[~2014-08-08 13:57 UTC | newest]
Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2014-08-07 23:21 two table join with order by on both tables attributes Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-07 23:42 ` David G Johnston <david.g.johnston@gmail.com>
2014-08-08 00:02 ` Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 00:19 ` Tom Lane <tgl@sss.pgh.pa.us>
2014-08-08 00:43 ` Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 01:05 ` Evgeniy Shishkin <itparanoia@gmail.com>
2014-08-08 13:29 ` Marti Raudsepp <marti@juffo.org>
2014-08-08 13:57 ` Evgeniy Shishkin <itparanoia@gmail.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox