A estimativa (cost=0.00..4164264.45 rows=5883377 width=3595) mostra que o planejador espera que mais de 5 milhões de registros correspondam aos critérios. É significativamente diferente dos 100K esperados que você mencionou.

Em casos como este `ANALYZE public.my_table;' geralmente ajuda. Ele atualiza as estatísticas dos dados da tabela.