Re: Further open item (Was: Status of 7.2) - Mailing list pgsql-hackers

From Hannu Krosing
Subject Re: Further open item (Was: Status of 7.2)
Date
Msg-id 3BF90A88.4070101@tm.ee
Whole thread Raw
In response to Re: Further open item (Was: Status of 7.2)  ("Tille, Andreas" <TilleA@rki.de>)
List pgsql-hackers

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




pgsql-hackers by date:

Previous
From: mlw
Date:
Subject: Re: postgresql.conf
Next
From: Hannu Krosing
Date:
Subject: Re: Further open item (Was: Status of 7.2)