
> > 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

Fri, 2 Nov 2001 09:33:57 +0100
"Zeugswetter Andreas SB SD" <ZeugswetterA@spardat.at>
Re: Serious performance problem