Why do sql queries with two conditions take a long time?

[ce2100]

I have a table with 12 million records. There are indexes on columns col_1 and col_2. I use postgresql 9.3.
I need two types of queries on it. First, some queries with just one condition in where clause, such as:

select count(*)
from table_1
where
col_1 >= 123456;


**explain analyze:**


Aggregate (cost=164523.60 ..164523.61 rows=1 width=0) (actual time=1803.281.. 1803.281 rows=1 loops=1)
-> Index Only Scan using table1_col1_idx on table_1 (cost=0.43..151 242.20 rows=5312558 width=0) (actual time=60.713..13 44.393 rows=5318333 loops=1)
Index Cond: (col_1 >= 123456)
Heap Fetches: 0
Total runtime: 1803.330 ms

and one other query like:

select count(*)
from table_1
where
col_2 >= 987654;


**explain analyze:**

Aggregate (cost=364134.66 ..364134.67 rows=1 width=0) (actual time=3935.708.. 3935.708 rows=1 loops=1)
-> Index Only Scan using table1_col2_idx on table_1 (cost=0.43..334 739.38 rows=11758111 width=0) (actual time=7.521..290 4.569 rows=11760285 loops=1)
Index Cond: (col_2 >= 987654)
Heap Fetches: 0
Total runtime: 3935.760 ms

But, the problem is huge run time of a combined where clause: when two or more conditions combines with AND/OR. For example:

select count(*)
from table_1
where
col_1 >= 123456; AND col_2 >= 987654;


**explain analyze:**

-> Seq Scan on table_1 (cost=0.00..650 822.93 rows=5295377 width=0) (actual time=0.056..454 45.711 rows=5301622 loops=1)
Filter: ((col_2 >= 987654) AND (col_1 >= 123456))
Rows Removed by Filter: 6494640
Total runtime: 45961.622 ms

It's unacceptable: 3 seconds against 45 seconds! So, is there any solution to improve such combined queries? How to modify this query to force planner use indexes on col_1 and col_2?

I also, tried :
set enable_seqscan = false;

Then, the planner modifies its search plan to bitmap scan; that results in run time = 137 seconds!!!

Aggregate (cost=666246.28 ..666246.29 rows=1 width=0) (actual time=137311.964 ..137311.964 rows=1 loops=1)
-> Bitmap Heap Scan on table_1 (cost=99440.46. .653007.83 rows=5295377 width=0) (actual time=1105.153.. 136527.723 rows=5301622 loops=1)
Recheck Cond: (col_1 >= 123456)
Filter: (col_2 >= 987654)
Rows Removed by Filter: 16711
-> Bitmap Index Scan on table1_col1_idx (cost=0.00..981 16.62 rows=5312558 width=0) (actual time=862.677..8 62.677 rows=5318333 loops=1)
Index Cond: (col_1 >= 123456)
Total runtime: 137314.450 ms

[Rabbit]

Use a combined index.