How to optimize this query on Postgres
An index on (practice_id, client_data_provider_id, date_scheduled) would be better than the one you have (practice_id, date_scheduled, client_data_provider_id), for this particular query.

Notice the difference in order. When there are multiple equality (=) conditions and one range condition (&gt;=, &gt;, between, etc) in the where clause, it's better to have an index with first the columns that are checked with equality and last the column in the range condition. 

This way, the index scan will have to cover a much smaller part of the index, only the values with practice_id = 753 and client_data_provider_id = '3001-753' and date_scheduled &gt;= '2016-01-12', which is exactly the rows you want. 

With the current index, it will have to scan the part of the index with practice_id = 753 and date_scheduled &gt;= '2016-01-12' and then reject the largest part (all those that don't have client_data_provider_id = '3001-753').