Querying with multicolumn index

Hi all,
I have a query that I *think* should use a multicolumn index, but
sometimes isn't, resulting in slow queries.

We have a DB that records GPS coordinates for vehicles:

Table "public.updates"
Column | Type | Modifiers
------------+--------------------------+------------------------------------------------------
id | integer | not null default
nextval('updates_id_seq'::regclass)
driver_id | integer | not null
latitude | double precision | not null
longitude | double precision | not null
time | timestamp with time zone | not null default now()
vehicle_id | integer |
Indexes:
"updates_pkey" PRIMARY KEY, btree (id)
"ix_updates_time" btree ("time")
"updates_driver_id_time_idx" btree (driver_id, "time")
"updates_vehicle_id_time_idx" btree (vehicle_id, "time")

Table has about 15M records across 100 distinct driver_id.

I want to get the last record for a specific driver:

SELECT * FROM updates WHERE driver_id=123 ORDER BY "time" DESC LIMIT 1;

For some values of driver_id, it does what I expect and uses
updates_driver_id_time_idx to fetch the records in 2 ms or less. For
other values of driver_id, it does an index scan backwards on
ix_updates_time, taking upwards of 2 minutes.

Good plan:

Limit (cost=0.11..1.38 rows=1 width=56) (actual time=2.710..2.710
rows=1 loops=1)
-> Index Scan Backward using updates_driver_id_time_idx on updates
(cost=0.11..139278.28 rows=110051 width=56) (actual time=2.709..2.709
rows=1 loops=1)
Index Cond: (driver_id = 17127)
Total runtime: 2.732 ms
(4 rows)

Bad plan:

Limit (cost=0.09..0.69 rows=1 width=56) (actual
time=216769.111..216769.112 rows=1 loops=1)
-> Index Scan Backward using ix_updates_time on updates
(cost=0.09..272339.04 rows=448679 width=56) (actual
time=216769.110..216769.110 rows=1 loops=1)
Filter: (driver_id = 30132)
Rows Removed by Filter: 5132087
Total runtime: 216769.174 ms

From cursory testing, the difference seems to be based on how many
total rows there are for a particular driver. The above query uses
updates_driver_id_time_idx for drivers with less than about 300K rows,
but uses ix_updates_time for drivers with more than about 300K rows.

Anything we can do to make it do the "right" thing? We are also
considering denormalizing the data and keeping a "cache" of the same
data in another table.

pgsql version: 9.3.14 and 9.5.3, already tried vacuum analyze.

Thanks,
Eric

--
Eric Jiang, DoubleMap
eric(at)doublemap(dot)com | www.doublemap.com