BUG #14302: SQL with LIMIT degrades performance seriously
The following bug has been logged on the website:
Bug reference: 14302
Logged by: Kaijiang Chen
Email address: chenkaijiang@gmail.com
PostgreSQL version: 9.5.3
Operating system: CentOS 7.2
Description:
I have a table, renren.user_relations with 10 partitions and contains about
10M records.
I created 2 indexes on it (including parent table and all partitions):
1) user_relations_pkey -- btree index on user_id column
2) user_relations_0_parent_id_idx -- btree index on parent_id
I ran the SQL "select * from renren.user_relations where parent_id=846346
order by user_id limit 10;" and it took 1.4 sec, which is slow.
But "select * from renren.user_relations where parent_id=846346 order by
user_id" (no LIMIT) and it took 100+ ms.
the explain result:
explain select * from renren.user_relations where parent_id=846346 order by
user_id limit 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Limit (cost=4.57..442.35 rows=10 width=102)
-> Merge Append (cost=4.57..496534.92 rows=11342 width=102)
Sort Key: user_relations.user_id
-> Index Scan using user_relations_pkey on user_relations
(cost=0.12..5.24 rows=1 width=27)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_0_pkey on user_relations_0
(cost=0.42..49426.24 rows=862 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_1_pkey on user_relations_1
(cost=0.42..49437.21 rows=1022 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_2_pkey on user_relations_2
(cost=0.42..49681.23 rows=973 width=103)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_3_pkey on user_relations_3
(cost=0.42..49427.38 rows=990 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_4_pkey on user_relations_4
(cost=0.42..49713.95 rows=941 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_5_pkey on user_relations_5
(cost=0.42..49711.65 rows=1687 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_6_pkey on user_relations_6
(cost=0.42..49676.60 rows=1104 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_7_pkey on user_relations_7
(cost=0.42..49715.27 rows=1168 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_8_pkey on user_relations_8
(cost=0.42..49698.55 rows=1168 width=102)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_9_pkey on user_relations_9
(cost=0.42..49620.69 rows=1426 width=103)
Filter: (parent_id = 846346)
(25 rows)
Time: 1.344 ms
It uses the Index Scan using index on user_id, which is very stupid.
If I explain select * from renren.user_relations where parent_id=846346
order by user_id, then it uses the index on parent_id to get records and
then sort it, which is very wise since the number of qualified records is
1725.
Finally, I got a way to work around:
explain with tmp as (select * from renren.user_relations where
parent_id=846346 order by user_id) select user_id from tmp limit 10;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------
Limit (cost=23065.24..23065.44 rows=10 width=8)
CTE tmp
-> Sort (cost=23036.89..23065.24 rows=11342 width=102)
Sort Key: user_relations.user_id
-> Append (cost=0.00..22273.04 rows=11342 width=102)
-> Seq Scan on user_relations (cost=0.00..0.00 rows=1
width=27)
Filter: (parent_id = 846346)
-> Index Scan using user_relations_0_parent_id_idx on
user_relations_0 (cost=0.42..1682.49 rows=862 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_1_parent_id_idx on
user_relations_1 (cost=0.42..2156.02 rows=1022 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_2_parent_id_idx on
user_relations_2 (cost=0.42..1887.71 rows=973 width=103)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_3_parent_id_idx on
user_relations_3 (cost=0.42..2035.95 rows=990 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_4_parent_id_idx on
user_relations_4 (cost=0.42..1805.29 rows=941 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_5_parent_id_idx on
user_relations_5 (cost=0.42..3240.29 rows=1687 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_6_parent_id_idx on
user_relations_6 (cost=0.42..2149.10 rows=1104 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_7_parent_id_idx on
user_relations_7 (cost=0.42..2256.53 rows=1168 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_8_parent_id_idx on
user_relations_8 (cost=0.42..2304.51 rows=1168 width=102)
Index Cond: (parent_id = 846346)
-> Index Scan using user_relations_9_parent_id_idx on
user_relations_9 (cost=0.42..2755.16 rows=1426 width=103)
Index Cond: (parent_id = 846346)
-> CTE Scan on tmp (cost=0.00..226.84 rows=11342 width=8)
(28 rows)
Time: 1.409 ms
and "with tmp as (select * from renren.user_relations where parent_id=846346
order by user_id) select user_id from tmp limit 10;" took only 100+ ms.
So, I think the optimizer/planner has a performance bug with LIMIT clause.
--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs
On Mon, Aug 29, 2016 at 11:48 PM, <chenkaijiang@gmail.com> wrote:
the explain result:
explain select * from renren.user_relations where parent_id=846346 order by
user_id limit 10;QUERY PLAN
------------------------------------------------------------
-------------------------------------------------------
Limit (cost=4.57..442.35 rows=10 width=102)
-> Merge Append (cost=4.57..496534.92 rows=11342 width=102)
Sort Key: user_relations.user_id
...
It uses the Index Scan using index on user_id, which is very stupid.
This a classic planning problem with ORDER BY...LIMIT. Probably parent_id
is correlated with user_id, and if you pick a high value of parent_id then
you are implicitly getting high values of user_id. But PostgreSQL doesn't
know that, it assumes things with parent_id=846346 are randomly dispersed
over the user_id values, and so it will gather 10 of them very quickly by
walking the indexes in order.
If I explain select * from renren.user_relations where parent_id=846346
order by user_id, then it uses the index on parent_id to get records and
then sort it, which is very wise since the number of qualified records is
1725.
You know it is 1725, but PostgreSQL thinks it is 11342. Is autoanalyze
analyzing often enough? Is default_statistics_target high enough?
(Although if I'm right about the correlation between parent_id and
user_id, then fixing that estimate might still not be enough to fix things).
So, I think the optimizer/planner has a performance bug with LIMIT clause.
Well, it has to make decisions with the information available to it. That
is not really a bug. It is constantly being improved, but will never be
perfect.
Cheers,
Jeff
Thank you very much for your quick response!
So I know I have to deal with my own solutions. Fortunately, I got the
solution with the "WITH" clause:
with t as (select * from renren.user_relations where parent_id=846346 order
by user_id)
select * from t LIMIT 10;
which separate the ORDER BY and LIMIT to avoid the classic planning problem.
On Tue, Aug 30, 2016 at 11:45 PM, Jeff Janes <jeff.janes@gmail.com> wrote:
Show quoted text
On Mon, Aug 29, 2016 at 11:48 PM, <chenkaijiang@gmail.com> wrote:
the explain result:
explain select * from renren.user_relations where parent_id=846346 order
by
user_id limit 10;QUERY PLAN
------------------------------------------------------------
-------------------------------------------------------
Limit (cost=4.57..442.35 rows=10 width=102)
-> Merge Append (cost=4.57..496534.92 rows=11342 width=102)
Sort Key: user_relations.user_id...
It uses the Index Scan using index on user_id, which is very stupid.
This a classic planning problem with ORDER BY...LIMIT. Probably parent_id
is correlated with user_id, and if you pick a high value of parent_id then
you are implicitly getting high values of user_id. But PostgreSQL doesn't
know that, it assumes things with parent_id=846346 are randomly dispersed
over the user_id values, and so it will gather 10 of them very quickly by
walking the indexes in order.If I explain select * from renren.user_relations where parent_id=846346
order by user_id, then it uses the index on parent_id to get records and
then sort it, which is very wise since the number of qualified records is
1725.You know it is 1725, but PostgreSQL thinks it is 11342. Is autoanalyze
analyzing often enough? Is default_statistics_target high enough?
(Although if I'm right about the correlation between parent_id and
user_id, then fixing that estimate might still not be enough to fix things).So, I think the optimizer/planner has a performance bug with LIMIT clause.
Well, it has to make decisions with the information available to it. That
is not really a bug. It is constantly being improved, but will never be
perfect.Cheers,
Jeff
A suggestion:
In the sql "select * from renren.user_relations where parent_id=846346 order
by user_id LIMIT 10;", planner can query the number of rows (with
parent_id=846346) from the btree index, right?
If so, planner will know that it's better to sort the rows (actually less
than 2000) than to scan 10M rows.
On Wed, Aug 31, 2016 at 12:02 PM, Kaijiang Chen <chenkaijiang@gmail.com>
wrote:
Show quoted text
Thank you very much for your quick response!
So I know I have to deal with my own solutions. Fortunately, I got the
solution with the "WITH" clause:
with t as (select * from renren.user_relations where parent_id=846346 order
by user_id)
select * from t LIMIT 10;which separate the ORDER BY and LIMIT to avoid the classic planning
problem.On Tue, Aug 30, 2016 at 11:45 PM, Jeff Janes <jeff.janes@gmail.com> wrote:
On Mon, Aug 29, 2016 at 11:48 PM, <chenkaijiang@gmail.com> wrote:
the explain result:
explain select * from renren.user_relations where parent_id=846346 order
by
user_id limit 10;QUERY PLAN
------------------------------------------------------------
-------------------------------------------------------
Limit (cost=4.57..442.35 rows=10 width=102)
-> Merge Append (cost=4.57..496534.92 rows=11342 width=102)
Sort Key: user_relations.user_id...
It uses the Index Scan using index on user_id, which is very stupid.
This a classic planning problem with ORDER BY...LIMIT. Probably
parent_id is correlated with user_id, and if you pick a high value of
parent_id then you are implicitly getting high values of user_id. But
PostgreSQL doesn't know that, it assumes things with parent_id=846346 are
randomly dispersed over the user_id values, and so it will gather 10 of
them very quickly by walking the indexes in order.If I explain select * from renren.user_relations where parent_id=846346
order by user_id, then it uses the index on parent_id to get records and
then sort it, which is very wise since the number of qualified records is
1725.You know it is 1725, but PostgreSQL thinks it is 11342. Is autoanalyze
analyzing often enough? Is default_statistics_target high enough?
(Although if I'm right about the correlation between parent_id and
user_id, then fixing that estimate might still not be enough to fix things).So, I think the optimizer/planner has a performance bug with LIMIT
clause.Well, it has to make decisions with the information available to it.
That is not really a bug. It is constantly being improved, but will never
be perfect.Cheers,
Jeff
"Kaijiang" == Kaijiang Chen <chenkaijiang@gmail.com> writes:
Kaijiang> Thank you very much for your quick response!
Kaijiang> So I know I have to deal with my own solutions. Fortunately,
Kaijiang> I got the solution with the "WITH" clause:
Why not just create the correct index on each partition? (parent_id,user_id)
--
Andrew (irc:RhodiumToad)
--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs
It couldn't solve the problem.
I've already created 2 btree indexes, one for parent_id, the other for
user_id.
Do you mean to create an multi-column index on (parent_id, user_id)? --
still couldn't solve the problem, since we still need index for user_id
(for other sql) and planner will turn to user_id index.
On Wed, Aug 31, 2016 at 1:01 PM, Andrew Gierth <andrew@tao11.riddles.org.uk>
wrote:
Show quoted text
"Kaijiang" == Kaijiang Chen <chenkaijiang@gmail.com> writes:
Kaijiang> Thank you very much for your quick response!
Kaijiang> So I know I have to deal with my own solutions. Fortunately,
Kaijiang> I got the solution with the "WITH" clause:Why not just create the correct index on each partition?
(parent_id,user_id)--
Andrew (irc:RhodiumToad)
On Wed, Aug 31, 2016 at 6:09 AM, Kaijiang Chen <chenkaijiang@gmail.com> wrote:
In the sql "select * from renren.user_relations where parent_id=846346 order
by user_id LIMIT 10;", planner can query the number of rows (with
parent_id=846346) from the btree index, right?
If so, planner will know that it's better to sort the rows (actually less
than 2000) than to scan 10M rows.
mmmm, AFAIK planner does NOT query, it plans using stored statistics.
This is why some data distribution, which are a bad match for the
postgres ways of storing stats, tend to plan ( oacasionally ) badly.
Francisco Olarte.
--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs
Top posting makes the flow difficult to follow, editing a little bit.
Why not just create the correct index on each partition?
(parent_id,user_id)
On Wed, Aug 31, 2016 at 2:42 PM, Kaijiang Chen <chenkaijiang@gmail.com> wrote:
It couldn't solve the problem.
I've already created 2 btree indexes, one for parent_id, the other for
user_id.
A (parent_id, user_id) index can be used instead of the one for
parent_id, so it will nbot need to much extra, and can solve some
queries. The planner can normally detected where some keys can be
solved directly with a composite index.
Do you mean to create an multi-column index on (parent_id, user_id)? --
still couldn't solve the problem, since we still need index for user_id (for
other sql) and planner will turn to user_id index.
How do you know it will turn to the bad index?
Francisco Olarte.
--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs
"Kaijiang" == Kaijiang Chen <chenkaijiang@gmail.com> writes:
Kaijiang> It couldn't solve the problem.
Kaijiang> I've already created 2 btree indexes, one for parent_id, the
Kaijiang> other for user_id. Do you mean to create an multi-column
Kaijiang> index on (parent_id, user_id)?
Yes. The 2 separate indexes are not sufficient, but you can omit the
index on parent_id alone if you create the multi-column index.
Kaijiang> still couldn't solve the problem, since we still need index
Kaijiang> for user_id (for other sql) and planner will turn to user_id
Kaijiang> index.
The planner should not do that (if it does, it's a bug).
The plan you're looking for is:
Limit
-> MergeAppend
-> Index scan on parent_id_user_id_idx
Index Cond: (parent_id = ?)
-> Index scan on parent_id_user_id_idx
Index Cond: (parent_id = ?)
...
Note the use of Index Cond rather than Filter, this is important.
--
Andrew (irc:RhodiumToad)
--
Sent via pgsql-bugs mailing list (pgsql-bugs@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-bugs
Yes, I try it and it works now! Thank you very much, Francisco Olarte,
and Andrew Gierth!
On Thu, Sep 1, 2016 at 1:41 AM, Andrew Gierth <andrew@tao11.riddles.org.uk>
wrote:
Show quoted text
"Kaijiang" == Kaijiang Chen <chenkaijiang@gmail.com> writes:
Kaijiang> It couldn't solve the problem.
Kaijiang> I've already created 2 btree indexes, one for parent_id, the
Kaijiang> other for user_id. Do you mean to create an multi-column
Kaijiang> index on (parent_id, user_id)?Yes. The 2 separate indexes are not sufficient, but you can omit the
index on parent_id alone if you create the multi-column index.Kaijiang> still couldn't solve the problem, since we still need index
Kaijiang> for user_id (for other sql) and planner will turn to user_id
Kaijiang> index.The planner should not do that (if it does, it's a bug).
The plan you're looking for is:
Limit
-> MergeAppend
-> Index scan on parent_id_user_id_idx
Index Cond: (parent_id = ?)
-> Index scan on parent_id_user_id_idx
Index Cond: (parent_id = ?)
...Note the use of Index Cond rather than Filter, this is important.
--
Andrew (irc:RhodiumToad)