Index Scan cost expression

From: Amit Gupta <amit(dot)pc(dot)gupta(at)gmail(dot)com>
To: pgsql-hackers(at)postgresql(dot)org
Subject: Index Scan cost expression
Date: 2009-01-27 13:39:56
Message-ID: 8d79a95c0901270539h307f4650ge2b2716fb8c7841@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

While trying to figure out an appropriate cost expression function for
Thick indexes, i learned that we are using Mackert and Lohman formula
(described in their paper "Index Scans Using a Finite LRU Buffer: A
Validated I/O Model", ACM Transactions on Database Systems).
The paper's result is as follows:
# Heap Pages fetched from disk for x index probes =
min(2TDx/(2T+Dx), T) when T <= b
2TDx/(2T+Dx) when T > b and Dx <= 2Tb/(2T-b)
b + (Dx - 2Tb/(2T-b))*(T-b)/T when T > b and Dx > 2Tb/(2T-b)

where,
T = # pages in table
N = # tuples in table
D = avg. number of an index value is repeated in the table.
(duplication factor), and
b buffer/cache size

Please note that the above result only computes _heap_ page reads.

The above expression is used by index_pages_fetched() function to
compute index scan cost. The function however doesn't account for cost
of index page scans. On average an index probe will require (h-1) page
reads from disk, where h is the height of the B-tree (when # index
probes << # index key values). I can post the details of the
derivation of this result, if required.
I am planning to use a similar expression for Thick indexes cost expressions.

Upon taking a cursory look at the cost functions of other operators, I
realized that available memory (effective_cache_size) is not
considered for estimating the costs of hash/sort/NLjoin/etc. Why is
that the case?

Regards,
Amit
Persistent Systems

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Timo Savola 2009-01-27 13:41:15 log_duration_sample config option patch
Previous Message Magnus Hagander 2009-01-27 13:15:11 Re: mingw check hung