> > so it's linear growth here
> This is what my colleague was afraid of: We would have linear growth
> compared to the log(n) growth which is to be expected on MS SQL server
This is not true, since the index scan also neads to read the leaf pages
in MS Sql. The number of leaf pages grows linear with number of rows
that qualify the where restriction.
R = number of rows that qualify
--> O(R + log(R))
The pg measurements showed, that PostgreSQL query performance can be
expected
to stay nearly the same regardless of number of rows in the table as
long as
the number of rows that qualify the where restriction stays constant.
The response time is linear to the number of rows that qualify the where
restriction, but that linear behavior is also expected with MS Sql.
Andreas