Nova consulta ocupando mais de 60% do tempo de execução

Como parte de um sistema de relatórios automatizados diários, executamos uma série de consultas para verificar diferentes parâmetros operacionais das tabelas de ativos de nossos clientes.

Na terça-feira passada adicionei uma nova verificação que funciona, mas acionei alguns alarmes de desempenho que me levaram a analisar o que poderia estar errado e acabei percebendo que a nova verificação na verdade aumentou o tempo geral das verificações em cerca de 160%.

Aprofundando essa nova verificação, reduzi-a à consulta de banco de dados real que está afetando todo o processo:

select case COALESCE(max(driverid),-1) when 0 then false when -1 then null else true end 
from reports.avl_historico_354676052451142 
where DATE_PART('day', now() - fecha ) < 5;

E ao fazer um explain analyze verbose, recebo:

Aggregate  (cost=75004.56..75004.58 rows=1 width=4) (actual time=544.460..544.461 rows=1 loops=1)
  Output: CASE COALESCE(max(driverid), (-1)) WHEN 0 THEN false WHEN (-1) THEN NULL::boolean ELSE true END
  ->  Seq Scan on reports.avl_historico_354676052451142  (cost=0.00..73782.38 rows=488873 width=4) (actual time=535.565..541.467 rows=9661 loops=1)
        Output: fecha, latitud, longitud, altitud, velocidad, cog, nsat, tipo, utc_hora, fix_fecha, imei, registro, input1, input2, input3, input4, hdop, adc, ignicion, adc2, power, driverid, ibutton2, ibutton3, ibutton4, trailerid, adc3, adc4, horometro, odometro, panico, bateria, bateriaint
        Filter: (date_part('day'::text, (now() - avl_historico_354676052451142.fecha)) < 5::double precision)
        Rows Removed by Filter: 1457143
Planning time: 0.078 ms
Execution time: 544.582 ms

Então, estou supondo que essa consulta pode precisar de algum tipo de ajuda / melhoria, mas estou completamente sem noção sobre isso. Então eu estou perguntando: quais melhorias você recomendaria para este cenário? Índices? Reformulação da consulta? Outros? O que mais devo fornecer para uma compreensão mais profunda do modelo?

Por favor, considere que a tabela de amostra na consulta tem um número grande em seu nome, que significa um deviceId e temos cerca de 30k tabelas daquelas que são consultadas regularmente... é algum tipo de modelo de particionamento de tabela.

Atualizar!

Novos resultados da indexação sugerida por @a_horse_with_no_name :

Aggregate  (cost=5478.72..5478.74 rows=1 width=4) (actual time=8.302..8.302 rows=1 loops=1)
  Output: CASE COALESCE(max(driverid), (-1)) WHEN 0 THEN false WHEN (-1) THEN NULL::boolean ELSE true END
  ->  Index Scan using reports_avl_historico_354676052451142_index_fecha on reports.avl_historico_354676052451142  (cost=0.43..5473.68 rows=2017 width=4) (actual time=0.026..4.644 rows=12249 loops=1)
        Output: fecha, latitud, longitud, altitud, velocidad, cog, nsat, tipo, utc_hora, fix_fecha, imei, registro, input1, input2, input3, input4, hdop, adc, ignicion, adc2, power, driverid, ibutton2, ibutton3, ibutton4, trailerid, adc3, adc4, horometro, odometro, panico, bateria, bateriaint
        Index Cond: (avl_historico_354676052451142.fecha > (('now'::cstring)::date - 5))
Planning time: 0.181 ms
Execution time: 8.332 ms

Vou cronometrar a execução geral e mantê-lo informado.