Кто знает как ускорить count на таблице с мультимиллионами рекордов?

Если Олимпийских рекордов, то никак. А если без шуток, то count выполняется на стороне БД, поэтому как его можно ускорить - это уменьшить кол-во записей. Либо, если речь идет о выборке, то использовать выборку по индексам, чтобы быстрее шуршало. Если записей за несколько десятков/сотен (зависит от многих условий), то можно подумать в сторону сегментирования таблицы.