 
> > There is not much point in arguing a specific query case,
> It is no specific query case.  It is the speed of an index scan which
> goes like N if you do it with PostgreSQL and it goes like log N if
> you do not have to look back into the table like MS SQL server does.

I cannot see why you keep saying that. It is simply not true.
MS SQL shows a behavior of O(N), it is simply, that PostgreSQL
because of well described methodology takes longer per affected row.
The speed difference is linear, no matter how many rows
are affected.

Andreas 

Mon, 19 Nov 2001 13:55:10 +0100
"Zeugswetter Andreas SB SD" <ZeugswetterA@spardat.at>
Re: Further open item (Was: Status of 7.2)
On Mon, 19 Nov 2001, Zeugswetter Andreas SB SD wrote:

> > It is no specific query case.  It is the speed of an index scan which
> > goes like N if you do it with PostgreSQL and it goes like log N if
> > you do not have to look back into the table like MS SQL server does.
>
> I cannot see why you keep saying that. It is simply not true.
> MS SQL shows a behavior of O(N), it is simply, that PostgreSQL
> because of well described methodology takes longer per affected row.
> The speed difference is linear, no matter how many rows
> are affected.
Iï¿½m basing my assumption on the statement of my colleague.  He
told me that consequent index usage results in O(log N) behaviour.
Iï¿½m really no expert in database theory but if you like I can foreward
your question.

Kind regards

         Andreas.

Mon, 19 Nov 2001 14:27:58 +0100 (CET)
"Tille, Andreas" <TilleA@rki.de>
Re: Further open item (Was: Status of 7.2)


Tille, Andreas wrote:

>On Mon, 19 Nov 2001, Zeugswetter Andreas SB SD wrote:
>
>>>It is no specific query case.  It is the speed of an index scan which
>>>goes like N if you do it with PostgreSQL and it goes like log N if
>>>you do not have to look back into the table like MS SQL server does.
>>>
>>I cannot see why you keep saying that. It is simply not true.
>>MS SQL shows a behavior of O(N), it is simply, that PostgreSQL
>>because of well described methodology takes longer per affected row.
>>The speed difference is linear, no matter how many rows
>>are affected.
>>
>Iï¿½m basing my assumption on the statement of my colleague.  He
>told me that consequent index usage results in O(log N) behaviour.
>
Searching through index only vs. searching through index + looking up 
each tuple in main
table can be better than linear, if the tuples are scattered throughout 
main table.

Searching through index only is probably faster by roughly a factor of  
2 * (size_of_heap_tuple/size_of_index_entry) in your case where you want 
to count
about half of the rows in table.



----------------
Hannu



Mon, 19 Nov 2001 18:35:04 +0500
Hannu Krosing <hannu@tm.ee>
Re: Further open item (Was: Status of 7.2)