If this still took an awfully long time with an index on three conditions in the query, then that sounds a bit odd. ANALYZE would be interesting? The RDBMS I am most familiar with used a statistical based query optimizer, but there were still odd queries which didn't make sense. What is the data distribution of the three columns in the condition? What happens if you try the index(list_id, modified, item_id) with the columns in different order?