> My list can contain 1 .. 100000 records and table contains 3000000 > records and is growing.
Ah. No IN(), then ;) Temp table + ANALYZE seems your only option...