Re: Index optimization ?

Bo Lorentsen wrote:
> So if the random function was stable, you either get all or none, as et
> gets executed only ones ?
>
>> An indexscan is a legal optimization only if the function(s) in the
>> WHERE clause are all STABLE or better. This is because the index access
>> code will only evaluate the righthand side of the "indexcol = something"
>> clause once, and then will use that value to descend the btree and
>> select matching index entries. We must be certain that this gives the
>> same result we would get from a seqscan.
>>
>>
> Now this sounds like a blink of the problem that I don't understand :-)
> When you say it evaluate "right side" ones, what kind of information are
> you (the executer) then getting, and how is the index match then
> performed. Is all the where clause expression marked as volatile at this
> level, just to be sure ?
Lets say, you have an query "select * from table where field =
function()". Now, according to the sql-spec, you would have to
scan each row in "table", call the function "functio()", and compare the
result. If the result of the call to "function()" matches the value in
"field", the you return the row, otherwise you don't return it.

An index is a tree, where each node has two subnodes/children. Each node
representents a row of your table (or, rather, references a row - it
contails only the value of the field you indexed). Additionally,
the value of the field of the "left" child (and the value of the field
of its children, and so on) is always guaranteed to be smaller-or-equal
to the value of field of the node itself, and the value
of the field of the "right" child is always guaranteed to be
greater-or-equal to the value of the field of the node.
So, if you have three records in the table "table", like this:
f1
--
1
2
3

Then your index looks the following:
2
/ \
1 3

Now, when doing an index lookup, you have to know which value to look
for (lets say you look for 3). Then you look at the top node, and
compare the value you are looking for to the value of the node. In our
case, the node has a smaller value then the one we are looking for.
Because we know that the left child of the toplevel node will have an
even smaller value, we don't need to look at the left child at all. We
just check the right child, and there we find our record with "field"=3.

_BUT_ this only works, because we knew for which value to look before we
started searching. If we the value we look for is constantly changing,
our index lookup would return bogus results. So, if the value is unknown
_at_the_beginning_ of the search, you can't use the index, because the
power of an index search comes from the idea to skip a whole subtree (in
our case the left one), because we _know_ it can't contain the value we
are looking for.

Functions marked "immutable" or "stable" is _guaranteed_ to never change
their value during a select statement, or at least not in an
unpredictable way. Thats why you can use return values of "immutable" or
"stable" functions for an index search.

> Well maybe the real question is how does the executer match an index, or
> am I off track ?
Lets say, you are doing the following query
"select * from table where field1 = currval('seq')" and field2 =
nextval('seq')

Now, the value of "currval('seq')" changes with every row visited. In
your example, the value of "currval" is actually stable - but postgres
has no way to know this. To use an index scan for your query, postgres
would need to know, that only a call to nextval can change the value of
currval - but this, of course, is a quite difficult dependency for a
database to track.

greetings, Florian Pflug