Как быстро и более-менее точно подсчитать число записей в таблице?

Работаю над проектом на django, в качестве бд используется postgres. Бд содержит тысячи таблиц, многие из таблиц могут содержать десятки миллиардов записей.
Проблема - count() выполняется по полчаса.
Я использовал приблизительный подсчет записей вроде:

SELECT reltuples FROM pg_class WHERE relname = "table"

Но результат в 300 раз меньше реального - это слишком большая погрешность.
Есть ли способ, быстро подсчитать число записей, без уменьшения скорости записи?