3

I am running a query like

select id from students where school_id='67153fb1-8f79-441d-a747-ca3778cf6d3d';

on table that looks like

                Table "public.students"
          Column       |            Type             |             Modifiers              
    -------------------+-----------------------------+------------------------------------
     id                | uuid                        | not null default gen_random_uuid()
     school_id        | uuid                        | 
Indexes:
    "students_pkey" PRIMARY KEY, btree (id)
    "students_school_id_idx" btree (school_id)

The query plan for the select statement with just where looks like below-

explain select id from students where school_id='67153fb1-8f79-441d-a747-ca3778cf6d3d';
                                            QUERY PLAN                                            
--------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on students  (cost=581.83..83357.10 rows=24954 width=16)
   Recheck Cond: (school_id = '67153fb1-8f79-441d-a747-ca3778cf6d3d'::uuid)
   ->  Bitmap Index Scan on students_school_id_idx  (cost=0.00..575.59 rows=24954 width=0)
         Index Cond: (school_id = '67153fb1-8f79-441d-a747-ca3778cf6d3d'::uuid)

This is fairly fast.

Now we add order by to the query with id that degrades the query.(Such a query is generated by Rails like student.first with some condition)

explain select id from students where school_id='67153fb1-8f79-441d-a747-ca3778cf6d3d' order by id asc limit 1;
                                                 QUERY PLAN                                                 
------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.43..488.51 rows=1 width=16)
   ->  Index Scan using students_pkey on students  (cost=0.43..12179370.22 rows=24954 width=16)
         Filter: (school_id = '67153fb1-8f79-441d-a747-ca3778cf6d3d'::uuid)

How can I improve the speed to return the results of this query? Currently there are around 4990731 records in the table and is taking more than 2 minutes! Its running on RDS with db.t2.medium instance.

UPDATE After running Analyze students;

explain select id from students where school_id='67153fb1-8f79-441d-a747-ca3778cf6d3d' order by id asc limit 1;
                                                       QUERY PLAN                                                    
    -----------------------------------------------------------------------------------------------------------------
     Limit  (cost=8.46..8.46 rows=1 width=16)
       ->  Sort  (cost=8.46..8.46 rows=1 width=16)
             Sort Key: id
             ->  Index Scan using students_school_id_idx on students  (cost=0.43..8.45 rows=1 width=16)
                   Index Cond: (school_id = '67153fb1-8f79-441d-a747-ca3778cf6d3d'::uuid)

    explain analyze select id from students where school_id='67153fb1-8f79-441d-a747-ca3778cf6d3d' order by id asc limit 1;
                                                                          QUERY PLAN                                                                         
    -----------------------------------------------------------------------------------------------------------------------------------------------------------
    Limit  (cost=8.46..8.46 rows=1 width=16) (actual time=1.853..1.855 rows=1 loops=1)
     ->  Sort  (cost=8.46..8.46 rows=1 width=16) (actual time=1.851..1.852 rows=1 loops=1)
           Sort Key: id
           Sort Method: quicksort  Memory: 25kB
           ->  Index Scan using students_school_id_idx on students  (cost=0.43..8.45 rows=1 width=16) (actual time=1.841..1.843 rows=1 loops=1)
                 Index Cond: (school_id = '67153fb1-8f79-441d-a747-ca3778cf6d3d'::uuid)
    Planning time: 0.145 ms
    Execution time: 1.874 ms
2

PostgreSQL thinks that it will be faster avoiding the sort for the ORDER BY by scanning the rows in the sort order and discarding rows until it finds one with the right school_id.

There can be two reasons why this takes longer than expected:

  1. The table statistics is off, and PostgreSQL overestimates the number of rows with that school_id.

    Calculate new statistics, possibly with a higher value for default_statistics_target, to verify if that is the problem:

    ANALYZE students;
    
  2. The (many) rows with the correct school_id all happen to have a rather high id, so PostgreSQL has to scan way more rows than it bargained for until it finds a match.

    In that case, you should modify the ORDER BY clause so that PostgreSQL cannot use the wrong index:

    ... ORDER BY id + 0
    
| improve this answer | |
  • Thanks Laurenz. I will try #1 and update here. But could you throw a little more light on how is #2 going to help. How is that going to force postgres to use the index? – Arun Jan 30 at 10:35
  • The second option will prevent PostgreSQL from using an index (for the ORDER BY) because the expression is different from the indexed one. – Laurenz Albe Jan 30 at 10:38
  • Yeah, that makes sense! Anyway, analyze on students has solved the issue. I am updating the description with explain and explain analyze after running analyze students. – Arun Jan 30 at 13:07
1

UUID columns are bad for performance as they are generally un-ordered per definition. Your column named id is of type UUID and thus subject to be unordered.

When you just run the simple select id from students where school_id='67153fb1-8f79-441d-a747-ca3778cf6d3d'; then the Query Engine just hast to plow through the data (HEAP) in your table and dis-regard data that doesn't match the WHERE clause ().

In the second case your are doing two things.

  1. Selecting the data via the index students_pkey which produces an ordered result set but is ultimately zig-zagging through the heap. This it the Index Scan using students_pkey on students (cost=0.43..12179370.22 rows=24954 width=16) part of the EXPLAIN
  2. Filtering the first results based on the students_school_id_idx index. This is the Filter: (school_id = '67153fb1-8f79-441d-a747-ca3778cf6d3d'::uuid) part of the EXPLAIN

You might want to consider not using UUIDs as they come with some overhead. Read the Sequential UUID Generators article for more information.

But there are disadvantages too – they may make the access patterns much more random compared to traditional sequential identifiers, cause WAL write amplification etc. So let’s look at an extension generating “sequential” UUIDs, and how it can reduce the negative consequences of using UUIDs.

...and...

(emphasis mine)

Let’s assume we’re inserting rows into a table with an UUID primary key (so there’s a unique index), and the UUIDs are generated as random values. In the table the rows may be simply appended at the end, which is very cheap. But what about the index? For indexes ordering matters, so the database has little choice about where to insert the new item – it has to go into a particular place in the index. As the UUID values are generated as random, the location will be random, with uniform distribution for all index pages.

...because...

(emphasis mine)

This is unfortunate, as it works against adaptive cache management algorithms – there is no set of “frequently” accessed pages that we could keep in memory. If the index is larger than memory, the cache hit ratio (both for page cache and shared buffers) is doomed to be poor. And for small indexes, you probably don’t care that much.

The distribution of the data in the table is sequential, but the UUIDs will be un-ordered. At some point the b-tree index has to access the data and because the index is being used for the ORDER BY to retrieve the data via the index, the actual data will be retrieved in a zig-zag pattern.

There are workarounds for this issue, but they either involve different UUID generation or the use of Clustered Indexes which have an impact on the performance of inserts, because the data is being constantly reordered.

A good explanation for the B-Tree Index in PostgreSQL can be found here

Basically what is happening at the last leaf level of the index is this:

LEAF(n)     76a8c180-3a76-492e-b68a-9d980bb50c11 | fec0b6c3-2112-487c-b10f-c515e1a7d1d1
                                               \    /
                                                \  /
                                                 \/ 
                                                 /\
                                                /  \    
                                               /    \
TABLE DATA  fec0b6c3-2112-487c-b10f-c515e1a7d1d1 | 76a8c180-3a76-492e-b68a-9d980bb50c11

The index is ordered. The data isn't. That's why the ODER BY can induce an overhead due to the zig-zag retrieval of the actual data.

| improve this answer | |
  • That was an excellent explanation John. Thanks a ton. Although I had accepted Laurenz's reply as an answer, I will take your feedbacks ans see if things can be improved! Hope I could give more than one upvote! – Arun Jan 30 at 13:12
  • I don't see how that answers the question at all. school_id is indexed, so the few pertaining rows are found in a jiffy using the index. There is a lot of valuable information in what you wrote, but the answer missed the point. – Laurenz Albe Jan 30 at 13:13
  • @LaurenzAlbe Well multiply the LEAF (N)level and the TABLE DATA level by a factor of 10^12 then might be able to see where I'm heading. While the index is sorted, the data isn't. This incurs some overhead as the data level isn't sorted in the same order as the last b-tree index leaf level. Clustering the index would help but has an overhead. Or am I totally missing something? – John aka hot2use Jan 30 at 13:23
  • Yes, you are missing the fact that the index scan returns only one row. Physical correlation is irrelevant in that case. – Laurenz Albe Jan 30 at 13:25
  • But it has to scan and "retrieve" 24954 rows to come to that conclusion that only one row is relevant. Right? – John aka hot2use Jan 30 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.