Thread: Query is slow when order by and limit clause are used in the query

On Mon, May 24, 2021 at 4:19 PM sreekanth vajrapu
<sreekanthvajrapu@gmail.com> wrote:
>
>
> Hi Team,
>
> We are having a slow query issue for one of our applications. We are seeing slowness(5 seconds) when we use both
ORDERBY and LIMIT 30 clause whereas the same query is performing very good(200 MS) when using only ORDER BY clause.
Alsonote that the query performed very fast(200 MS) when we increased LIMIT to 100 along with ORDER  BY. 
>
>
> Can you please help us if there are any bugs related to this?  OR Can someone kindly provide some solution to this
issue?

I think it's good to provide explain (analyze, buffers, costs,
verbose, summary) of the query and a reproducible test case (if
possible). It will be easier for those who investigate the issue.

With Regards,
Bharath Rupireddy.
EnterpriseDB: http://www.enterprisedb.com

On Mon, May 24, 2021 at 5:01 PM sreekanth vajrapu
<sreekanthvajrapu@gmail.com> wrote:
>
> Hi Bharath,
>
> Thanks for the quick reply, I have attached the execution plan for below 3 scenarios. Our application is using 1st
Scenario
>
> 1) WITH ORDER BY AND LIMIT 30 -- Very slow(3 to 5 seconds)
> 2) WITH ORDER BY WITHOUT LIMIT -- Very fast(160 MS)
> 3) WITH ORDER BY WITHOUT LIMIT 100 -- Very fast(160 MS)
>
> Kidney let me know if you need any more details on this.

I see that there are a huge number of Heap Fetches: 599354 with LIMIT
30 clause vs Heap Fetches: 11897 without LIMIT clause, maybe that
could be the reason for the slowness. I'm not sure why this is
happening with the LIMIT 30 clause only. Is it that this issue happens
every time? Say, if you run with LIMIT 30, then the query finishes in
3-5sec. Immediately if you run without a LIMIT clause then the query
completes in 160ms. Is vacuum running successfully on the tables and
indexes for which there's a huge number of heap fetches?

I have no further thoughts on this, other hackers may have better
suggestions though.

BTW, which version of postgresql are you using?

With Regards,
Bharath Rupireddy.
EnterpriseDB: http://www.enterprisedb.com

On 5/24/21 2:28 PM, Bharath Rupireddy wrote:
> On Mon, May 24, 2021 at 5:01 PM sreekanth vajrapu
> <sreekanthvajrapu@gmail.com> wrote:
>>
>> Hi Bharath,
>>
>> Thanks for the quick reply, I have attached the execution plan for below 3 scenarios. Our application is using 1st
Scenario
>>
>> 1) WITH ORDER BY AND LIMIT 30 -- Very slow(3 to 5 seconds)
>> 2) WITH ORDER BY WITHOUT LIMIT -- Very fast(160 MS)
>> 3) WITH ORDER BY WITHOUT LIMIT 100 -- Very fast(160 MS)
>>
>> Kidney let me know if you need any more details on this.
> 
> I see that there are a huge number of Heap Fetches: 599354 with LIMIT
> 30 clause vs Heap Fetches: 11897 without LIMIT clause, maybe that
> could be the reason for the slowness. I'm not sure why this is
> happening with the LIMIT 30 clause only. Is it that this issue happens
> every time? Say, if you run with LIMIT 30, then the query finishes in
> 3-5sec. Immediately if you run without a LIMIT clause then the query
> completes in 160ms. Is vacuum running successfully on the tables and
> indexes for which there's a huge number of heap fetches?
> 

But the heap fetches are in the index-only part of the plan, and it
matches the number of loops for that node. There are 521996 loops and
599354 heap fetches, so roughly 1:1, i.e. roughly the same ratio as for
the faster plans.

It's hard to give advice when we only have the plans, not the original
queries and index definitions, and when the plans are "anonymized" in a
rather inconsistent way (hard to say how the tables/indexes match
between the queries).

If I had to guess, I'd say this is a case of the usual LIMIT problem,
where the optimizer assumes the matching rows are uniformly distributed
in the input relation, when in reality it's "concentrated" at the end.

For example, imagine you have a table with two random columns:

    CREATE TABLE t (a int, b int);

    INSERT INTO t SELECT 100 * random(), 100 * random()
      FROM generate_series(1,1000000) g;

    CREATE INDEX ON t (a);

Now imagine you do this:

    SELECT * FROM t WHERE a = 10 AND b = 20 LIMIT 1;

In this case there's ~10000 rows with a=10, and we can fetch that from
the index. And we know there's ~100 groups with different b values,
distributed uniformly in the 10k rows. So if we start scanning the
index, after ~100 rows we should get a value with b=20, in which case
LIMIT 1 is done.

Now imagine the values are not distributed uniformly like this, but
instead we have this:

    INSERT INTO t SELECT i/10000, i/10000
      FROM generate_series(1,1000000) s(i);

In this case the DB will still believe it'll only scan ~100 rows, but
there are no rows with a=10 and b=20, so it'll end up scanning all 10k
rows with a=10. Or maybe all the "b=20" rows are at the very end of the
index, or something like that. Perhaps the "delete" column makes it
behave like this.

This is only an issue for queries with LIMIT, because that pushes the
planner to pick a plan with very low startup cost. But those plans often
have very high total cost, and degrade poorly when the uniformity
assumption is incorrect.

Hard to say, though, confirming it would require looking at the data
more closely. The one thing I'd suggest is changing the xxxx_index to
also include the "deleted" column, but it's a stab in the dark.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On Tue, 25 May 2021 at 02:19, Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:
> If I had to guess, I'd say this is a case of the usual LIMIT problem,
> where the optimizer assumes the matching rows are uniformly distributed
> in the input relation, when in reality it's "concentrated" at the end.

I'd guess that too. But hard to say due to the inconsistent
anonymisation of the plan,

> Hard to say, though, confirming it would require looking at the data
> more closely. The one thing I'd suggest is changing the xxxx_index to
> also include the "deleted" column, but it's a stab in the dark.

I'd say, providing xxxx_item and xxxxx_item are actually the same
table but just anonymised poorly, then an index such as:

create index on xxxx_item(COALESCE(deleted,false), name);

then change the query so instead of doing WHERE NOT deleted or deleted
is null;   do instead WHERE NOT COALESCE(deleted,false);

Without the query change then there's no hope of that index being used.

I think this would improve the situation as the LIMIT 30 plan is using
xxxxx_index to provide presorted results for the ORDER BY but can only
do index filtering on: (((NOT deleted) OR (deleted IS NULL)) AND
(SubPlan 6)).  So providing not too many rows are filtered out by
SubPlan 6, then that should reduce the Rows Removed by Filter.
However, if the majority of those rows are filtered out by Subplan 6,
then the index won't help much.

It would be nice if the schema was better designed so the deleted
column could only be true or false though.

sreekanth, for the future, you can use https://explain.depesz.com/ to
anonymise your queries. It'll do it in a consistent way that changes
the names of things in a consistent way that people can still follow.

David

On Fri, 28 May 2021 at 21:40, sreekanth vajrapu
<sreekanthvajrapu@gmail.com> wrote:
> 2) Version of the postgres is "PostgreSQL 9.5.21".
>
> Below are the execution plans along with the query and index definitions. Kindly help me to resolve this issue.

The following works ok for me all the way back to PostgreSQL 10.

create table t1 (id int primary key, name text not null, deleted bool);
create table t2 (id int primary key);
create table t3 (id int primary key);
create index on t1 (coalesce(deleted,false),name);

 explain (costs off)
SELECT item.*
FROM (
SELECT
          t1.name,
          t1.deleted
     FROM t1
     JOIN t2 USING (id)
     JOIN t3 USING (id)
) item
WHERE NOT COALESCE(deleted,false)
ORDER BY item.name LIMIT 31 OFFSET 0;
                             QUERY PLAN
--------------------------------------------------------------------
 Limit
   ->  Nested Loop
         Join Filter: (t1.id = t3.id)
         ->  Nested Loop
               ->  Index Scan using t1_coalesce_name_idx on t1
                     Index Cond: (COALESCE(deleted, false) = false)
               ->  Index Only Scan using t2_pkey on t2
                     Index Cond: (id = t1.id)
         ->  Index Only Scan using t3_pkey on t3
               Index Cond: (id = t2.id)
(10 rows)

However, I see it does not work on 9.5.  Something must have been
changed in 10 to allow the index to be used.  I don't really see any
indication of what that might be from the release notes and I'm too
lazy to git bisect to find out what the change was.

Either way, you should likely upgrade to a supported version of
PostgreSQL. 9.5 went out of support in Feb.  See:
https://www.postgresql.org/support/versioning/

If you need it to work on 9.5, you'll likely get it working if you use
a partial index:

create index on t1 (name) where not coalesce(deleted,false);

David.

On Mon, May 24, 2021 at 04:19:01PM +0530, sreekanth vajrapu wrote:
> Hi Team,
> 
> We are having a slow query issue for one of our applications. We are seeing
> slowness(5 seconds) when we use both ORDER BY and LIMIT 30 clause whereas
> the same query is performing very good(200 MS) when using only ORDER BY
> clause.  Also note that the query performed very fast(200 MS) when we
> increased LIMIT to 100 along with ORDER  BY.
> 
> Can you please help us if there are any bugs related to this?  OR Can
> someone kindly provide some solution to this issue?

This is not at base a bug. Instead, it's a behavior which compliance
with the SQL standard mandates. You're doing pagination, and
unfortunately you're doing it in a way that, while it appears simple
and intuitive, guarantees poor performance for later pages.

Here's a concise description of the fundamental problem you're
encountering along with some suggestions as to how to do this more
efficiently, i.e. faster consistently.

https://use-the-index-luke.com/no-offset

Here are some more references on pagination and how to do it
efficiently:

http://www.depesz.com/2007/08/29/better-results-paging-in-postgresql-82/
https://wiki.postgresql.org/wiki/File:Pagination_Done_the_PostgreSQL_Way.pdf
https://coderwall.com/p/lkcaag
https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/
https://ask.use-the-index-luke.com/questions/205/how-to-query-for-previous-page-with-keyset-pagination

Best,
David.
-- 
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate