Message-ID: <419723A7.5040505@samurai.com>
Date: Sun, 14 Nov 2004 20:21:43 +1100
From: Neil Conway <neilc@samurai.com>
User-Agent: Mozilla Thunderbird 0.9 (Macintosh/20041103)
MIME-Version: 1.0
To: PostgreSQL-development <pgsql-hackers@postgresql.org>
Cc: Oleg Bartunov <oleg@sai.msu.su>, Teodor Sigaev <teodor@stack.net>
Subject: [HACKERS] GiST: PickSplit and multi-attr indexes
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org
Lines: 33
Xref: stark.xeocode.com list.pgsql-hackers:31466

Oleg & Teodor,

If I understand the code correctly, GiST will only pass the first 
attribute of each index tuple to the user-defined PickSplit method when 
it wants to split a node. (see circa line 1269 of gist.c)

Is this a wise design decision? Granted, in many situations the first 
attribute in the index is sufficient to make a reasonable decision about 
how to divide the node into two halves, but I don't think that is 
universally true. For example, consider a two column index whose first 
attribute has a small number of distinct values. It could well be that 
all the first attribute values in a node-to-be-split would be the same. 
Only passing the first attribute to PickSplit would result in an 
essentially random distribution of tuples among the split nodes, rather 
than allowing the GiST extension to make use of the second attribution 
to partition the nodes. That's an extreme example, but it is easy to 
construct more realistic scenarios (basically, any situation in which 
the cardinality of the first index attribute is low -- a reasonably 
common occurrence with a multi-column index, I believe).

I'm not sure whether this would be a problem in practice. Speculation: 
repeated invocations of PickSplit are one of the main factors in 
deriving the ultimate shape of the GiST tree. Poor distribution of keys 
resulting from PickSplit would eventually result in unnecessarily loose 
bounding predicates in internal nodes, which would hurt performance.

Comments welcome,

Neil

---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings