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