Различие работы в использовании индексов в условии 'OR' баз данных Mysql и PostgeSQL

Справедливости ради, в mysql тоже данных допишите побольше.

mysql> explain select * from test where a=4756 or b=45 \G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: test
   partitions: NULL
         type: index_merge
possible_keys: aidx,bidx
          key: aidx,bidx
      key_len: 5,5
          ref: NULL
         rows: 15
     filtered: 100.00
        Extra: Using union(aidx,bidx); Using where
1 row in set, 1 warning (0,00 sec)

index merge в mysql 5.5 завезли: http://dev.mysql.com/doc/refman/5.7/en/index-merge-optimization.html

Если нужно потестить индексы в Postgres — используйте

set local enable_seqscan=off;

который поднимет стоимость seqscan до 100млн, а планировщик будет использовать его, как last resort.

А покажите, пожалуйста, как оно будет работать на объемах 5 и 10 млн записей?

В PostgeSQL дело не только в количестве данных. Планировщик пытается предугадать как эффективнее делать выборку — с индексами или без. Если, согласно прогнозу, в выборку попадет достаточно большое количество записей, то из-за того, что данные читаются не по записям а блоками, может получиться, что независимо от использования индексов, придется читать всю таблиц. В таком случае, чтение индексов — излишняя трата.