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?

--
--Josh

Josh Berkus
Aglio Database Solutions
San Francisco

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddressHere" to majordomo@postgresql.org)

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

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

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

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly