Postgres 10 - Query slows down with order by 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)
   -&gt;  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)
   -&gt;  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)
       -&gt;  Sort  (cost=8.46..8.46 rows=1 width=16)
             Sort Key: id
             -&gt;  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)
     -&gt;  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
           -&gt;  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
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:


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;

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