BUG #13824: EXISTS sometimes uses seq scan instead of index

The following bug has been logged on the website:

Bug reference: 13824
Logged by: Grzegorz G
Email address: grzegorz(at)thulium(dot)pl
PostgreSQL version: 9.4.5
Operating system: Debian
Description:

Seems related to

(9.4.4,9.3.9) Improve planner's cost estimates for semi-joins and anti-joins
with inner indexscans (Tom Lane, Tomas Vondra)

I have 2 tables: master(t_outbound) and detail (t_outbound_number). I want
to select only those records from t_outbound that have detailed records in
t_outbound number in certain statuses (id_status).

There is an index on t_outbound_number:
"t_on_id_status_1_or_9" btree (id_outbound) WHERE id_status = 1 OR
id_status = 9

Whenever I perform select like below, planner thinks it's going to look up
many rows and falls back to seq scan. If I disable seq scan, it correctly
uses the index.
When the t_outbound_number table grows and percentage of records with status
1 or 9 decreases, index is used.

Seems like planner thinks it's going to retrieve all of the records to
verify EXISTS clause, not just one.

psql=> EXPLAIN ANALYZE SELECT id_outbound,
(EXISTS (SELECT 1 FROM t_outbound_number ton WHERE (id_status = 1 OR
id_status = 9) AND ton.id_outbound=tou.id_outbound))


from t_outbound tou
ORDER BY id ASC;
QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------
Sort (cost=2.58..2.59 rows=5 width=10) (actual time=94.805..94.806 rows=5
loops=1)
Sort Key: tou.id
Sort Method: quicksort Memory: 25kB
-> Seq Scan on t_outbound tou (cost=0.00..2.52 rows=5 width=10) (actual
time=62.955..94.763 rows=5 loops=1)
SubPlan 1
-> Seq Scan on t_outbound_number ton (cost=0.00..11910.24
rows=40453 width=0) (actual time=18.942..18.942 rows=1 loops=5)
Filter: ((id_outbound = tou.id_outbound) AND ((id_status =
1) OR (id_status = 9)))
Rows Removed by Filter: 114596
Planning time: 0.775 ms
Execution time: 94.853 ms

psql=> set enable_seqscan =off;
SET

psql=> EXPLAIN ANALYZE SELECT id_outbound,
(EXISTS (SELECT 1 FROM t_outbound_number ton WHERE (id_status = 1 OR
id_status = 9) AND ton.id_outbound=tou.id_outbound))


from t_outbound tou
ORDER BY id ASC;

QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------------------------------
Index Scan using t_outbound_id_key on t_outbound tou (cost=0.13..14.69
rows=5 width=10) (actual time=0.033..0.103 rows=5 loops=1)
SubPlan 1
-> Index Scan using t_on_id_status_1_or_9 on t_outbound_number ton
(cost=0.42..3082.02 rows=40453 width=0) (actual time=0.015..0.015 rows=1
loops=5)
Index Cond: (id_outbound = tou.id_outbound)
Planning time: 0.811 ms
Execution time: 0.142 ms