ClosiusdrsmClosius, на глаз такие вещи оцениваются.
стоит учесть, что при 100 пользователях оптимизатор может выбрать один алгоритм,
а при 1000 совершенно другой.
и классы сложности бывают разные

Спасибо за ответ! А есть где нибудь таблица сложностей определенных функций в постгресе? Например я гдето слышал что простой SELECT * FROM table WHERE id=3; имеет сложность О(logN). А как насчет более детального описания? Например какова будет сложность такого же запроса SELECT DISTINCT(name) FROM table; ?

будет O(N*log(N)) в лучшем случае... и это не вопрос к базе а к ограничениям алгоритмов.
Вообще любые подобные вещи тестятся ТОЛЬКО натурными тестами на реальном железе которое будет использовано для Production и на реальных обьемах сгенерированных данных.