Need theory/comprehension help on Multi-Column indexes

Folks,

I've been poking around the indexing code, and I really don't

understand

the
page structure and splittng/branching for multi-column BTree indexes.
I've
looked in a couple DB textbooks to get a theoretically underpinning of

the

structure of multi-column indexes, but none of the ones I've seen

cover

them.
Can someone help me out?

Heh. You haven't done much programming in COBOL. The basic idea is to
combine the multiple fields in a sequence of bytes (reversible into the
original fields) and do a straight strcmp()
int c(6) n(2)
So you have key k on t(f1, f2, f3)
And do an insert to t(1, 'abc', 44)
The datum
******* **
"00000001 abc44" gets applied to the index. The values below the stars
are the lowest values supported by that particular type. The
requirement being that for a type to be indexible it must have able to
be mutated into a fixed length string.

At least, that is the simple way to do it. It is also possible to
create an index using discreet fields and the type's built in Boolean
comparison. This is more complicated, for example to find out if
t(a,b,c) > t(a1,b1,c1)
You have to check
a >= a1 and
(a > a1 or b >= b1) and
(a > a1 or b > b1 or c > c1)
or the Boolean reverse of the above:
a > a1 or
(a >= a1 and b > b1) or
(a >= a1 or b >= b1 or c > c1)

The above expression would have to be applied to generate a comparison
between an input value and a stored key value.
Merlin

Josh Berkus <josh@agliodbs.com> writes:

I've been poking around the indexing code, and I really don't understand the
page structure and splittng/branching for multi-column BTree indexes.

It's not fundamentally different from single-column indexes. The only
aspect of a btree index that requires any knowledge about the content of
index entries is the "compare two index entries for lesser, equal, or
greater" operation. For that, we just compare the first columns, then
compare the second columns if the first are equal, etc. Plain
lexicographic sort semantics.

Everything else in the btree code just considers an index entry to be an
undifferentiated tuple.

regards, tom lane

Tom, Merlin,

It's not fundamentally different from single-column indexes. The only
aspect of a btree index that requires any knowledge about the content of
index entries is the "compare two index entries for lesser, equal, or
greater" operation. For that, we just compare the first columns, then
compare the second columns if the first are equal, etc. Plain
lexicographic sort semantics.

So the different columns of the index don't have seperate data pages? It's
just a partitioned index node?

Wow, no wonder I couldn't figure it out, I was looking for something more
complicated ...

BTW, while we're on the optimizer, what is random_page_cost supposed to
represent, exactly? I used to think it was the ratio of index page
retreivals to direct page retrievals, but I see that that's already being
calculated for. I'm wondering if it might be possible to calculate RPC and
eliminate it as a GUC.

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco