Почему индексированные запросы ORDER BY, соответствующие многим строкам, намного быстрее, чем запросы, соответствующие только нескольким?

Question

Хорошо, таким образом у меня есть следующий запрос:

explain analyze SELECT seller_region FROM "products" 
    WHERE "products"."seller_region" = 'Bremen' 
    AND "products"."state" = 'active' 
    ORDER BY products.rank DESC, 
    products.score ASC NULLS LAST, 
    GREATEST(products.created_at, products.price_last_updated_at) DESC 
    LIMIT 14 OFFSET 0 

Фильтрация запросов совпадения вокруг 11.000 rows. Если мы посмотрим на планировщик запросов, мы можем видеть, что запрос использует индекс index_products_active_for_default_order и очень быстро:

Limit (cost=0.43..9767.16 rows=14 width=36) (actual time=1.576..6.711 rows=14 loops=1) 
    -> Index Scan using index_products_active_for_default_order on products (cost=0.43..4951034.14 rows=7097 width=36) (actual time=1.576..6.709 rows=14 loops=1) 
     Filter: ((seller_region)::text = 'Bremen'::text) 
     Rows Removed by Filter: 3525 
Total runtime: 6.724 ms 

Теперь, если я заменю 'Bremen' с 'Sachsen' как и в запросе:

explain analyze SELECT seller_region FROM "products" 
    WHERE "products"."seller_region" = 'Sachsen' 
    AND "products"."state" = 'active' 
    ORDER BY products.rank DESC, 
    products.score ASC NULLS LAST, 
    GREATEST(products.created_at, products.price_last_updated_at) DESC 
    LIMIT 14 OFFSET 0 

Тот же самый запрос соответствует только вокруг 70 rows и теперь последовательно очень-очень медленно, даже если он использует тот же индекс в точно так же:

Limit (cost=0.43..1755.00 rows=14 width=36) (actual time=2.498..1831.737 rows=14 loops=1) 
    -> Index Scan using index_products_active_for_default_order on products (cost=0.43..4951034.14 rows=39505 width=36) (actual time=2.496..1831.727 rows=14 loops=1) 
     Filter: ((seller_region)::text = 'Sachsen'::text) 
     Rows Removed by Filter: 963360 
Total runtime: 1831.760 ms 

Я не понимаю, почему это происходит? Я бы из интуиции подумал, что запрос, соответствующий более строкам, будет медленнее, но все наоборот. Я проверил это с другими запросами и на других столбцах на моих таблицах, и это одно и то же. Два похожих запроса с тем же порядком, что и выше, отображают те, которые соответствуют более строкам в 100 раз быстрее, чем те, где фильтрация соответствует только нескольким. Почему это и как я могу избежать такого поведения?

PS: Я использую Postgres 9.3 и индекс определяется следующим образом:

CREATE INDEX index_products_active_for_default_order 
    ON products 
    USING btree 
    (rank DESC, score COLLATE pg_catalog."default", (GREATEST(created_at, price_last_updated_at)) DESC) 
    WHERE state::text = 'active'::text; 

Answer 1

Это происходит потому, что первые 14 строк для соответствия Бремен найдены в первых 3539 строк индекса, в то время как для Sachsen 963374 строки должны быть отсканированы.

Я рекомендую индекс на (seller_region, rank).