Sender: gsstark@MIT.EDU
To: Greg Stark <gsstark@mit.edu>
Cc: pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] GiST: PickSplit and multi-attr indexes
References: <419723A7.5040505@samurai.com> <27866.1100476459@sss.pgh.pa.us>
	<1100492090.23420.28.camel@localhost.localdomain>
	<7879.1100531985@sss.pgh.pa.us>
	<1100578365.23420.71.camel@localhost.localdomain>
	<17937.1100616003@sss.pgh.pa.us> <87wtwl7bqe.fsf@stark.xeocode.com>
In-Reply-To: <87wtwl7bqe.fsf@stark.xeocode.com>
From: Greg Stark <gsstark@MIT.EDU>
Organization: The Emacs Conspiracy; member since 1992
Date: 16 Nov 2004 16:12:57 -0500
Message-ID: <87r7mt7b1i.fsf@stark.xeocode.com>
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Lines: 30
Xref: stark.xeocode.com misc:37449

Greg Stark <gsstark@MIT.EDU> writes:

> I'm not sure that GiST indexes behave the same way as btree indexes for the
> multi-column case. 
> 
> In a btree index the second column is entirely subordinate to the first
> column. In a GiST index the data is multi-dimensional, and all dimensions are
> equally important.

In fact on further consideration I do have a proposal.

If you look at the GiST implementations for various index types you'll see
that many (all?) take the same approach for PickSplit. In fact they pretty
much all have the same code copy/pasted to handle it.

The approach they take is to have a function which calculates an abstract
"distance" between any two entries. There's an algorithm that they use to pick
the split based on this distance function.

If you abandoned "PickSplit" and instead exposed this distance function as the
external API then the behaviour for multi-column indexes is clear. You
calculate the distance along all the axes and calculate the diagonal distance.

I think abandoning PickSplit for the distance function might also mean you
don't need a separate function for Penalty either, but I'm not sure on that.

-- 
greg