PostgreSQL brainteaser: медленный Index Scan

В моей работе, когда приходится исследовать и нагружать СУБД нетипичной нагрузкой и синтетическими тестами, часто встречаются случаи загадочного поведения системы: ускорение/замедление времени выполнения запроса на пару порядков, отказ использовать тот или иной индекс и тд. Объяснение странного поведения оказывается в итоге почти всегда тривиальным и хорошо известным опытным DBA. Однако встретив его в реальной эксплуатации первый раз невольно теряешься и на разбор кейса уходит много времени. Вместе с тем, это достаточно интересное упражнение - навроде того, как прорешать задачник по аэродинамике после 10 лет проектирования планеров самолётов. Поэтому предлагаю здесь попробовать формат обсуждения/изучения PostgreSQL в виде задач. Вдруг зайдёт?

Итак, вводные для первой, самой простой задачи. Имеем таблицу и пару многоколоночных индексов, отличающихся друг от друга только порядком следования колонок:

CREATE TEMP TABLE shopping (
  CustomerId bigint, CategoryId numeric, WeekDay text, Total money
);
INSERT INTO shopping (CustomerId, CategoryId, WeekDay, Total)
  SELECT gs % 1E5, gs % 100, 'Day' || (gs % 7), random()*1000::money
  FROM generate_series(1,1E6) AS gs;
CREATE INDEX idx1 ON shopping (CustomerId, CategoryId, WeekDay);
CREATE INDEX idx2 ON shopping (WeekDay, CategoryId, CustomerId);
VACUUM ANALYZE shopping;

Если выполнить запрос на простое сканирование по индексу с заходом в Heap за полем 'Total', то время выполнения запроса может отличаться в разы, в зависимости от того, какой индекс выбран:

EXPLAIN (ANALYZE, TIMING OFF, COSTS ON)
SELECT customerid, categoryid, weekday, total FROM shopping
ORDER BY CustomerId, CategoryId, WeekDay;
/*
 Index Scan using idx1 on shopping  
 (cost=0.42..64093.93 rows=1000000 width=25) (actual rows=1000000 loops=1)
 Planning Time: 0.108 ms
 Execution Time: 377.762 ms
*/

EXPLAIN (ANALYZE, TIMING OFF, COSTS ON)
SELECT customerid, categoryid, weekday, total FROM shopping
ORDER BY WeekDay, CategoryId, CustomerId;
/*
 Index Scan using idx2 on shopping  
 (cost=0.42..63963.29 rows=1000000 width=25) (actual rows=1000000 loops=1)
 Planning Time: 0.127 ms
 Execution Time: 3700.215 ms
 */

Собственно задача: в чём причина такого замедления? В чём PostgreSQL ошибся? Ведь стоимость плана запроса оценивается планнером в примерно одинаковую величину для обоих случаев?

Если есть идеи/проекты/патчи в hackers mailing list, имеющие отношение к этому поведению, предлагаю обсудить в комментариях. Также крайне интересно узнать, наблюдается ли аналогичный кейс в Oracle и MS SQL Server? А если нет, то как у них это работает?

THE END.
Thailand, Chon Buri, South Pattaya.