Re: knngist - 0.8

On Sun, Dec 26, 2010 at 2:41 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Hitoshi Harada <umi(dot)tanuki(at)gmail(dot)com> writes:
>> Catching up tonight, I wonder I could propose to add ordering
>> operators in btree, not in gist, for basic types.
>
> I thought about that for a bit while working on the knngist patch, but
> couldn't really see any useful application.  In particular, I don't see
> a way to shoehorn + and - in there as ordering operators.  They don't
> match the structure.  The RANGE problem wants to add operators that are
> somehow related to a btree's operators, but they're not related in the
> way that knngist uses.

It's superficially syntactically similar (value op constant) but as
you say it's really a different problem. The KNNGIST case could occur
in combination with this case, too: ORDER BY (point-column +
zero-vector-constant) distance-from point-constant. What's really
going on here is that there's a class of operations which can be
applied to an ORDER-BY column without actually changing the ordering -
adding or subtracting a constant, multiplying by a positive value,
concatenating with the empty string, etc. In theory, we could try to
recognize such cases and avoid a sort, but it seems like a lot of work
in proportion to the likely benefit.

A far more valuable case to optimize would be the one where you have
ORDER BY a, b and can obtain input pre-sorted by a but not by a, b.
It'd be extremely useful to be able to take the data sorted by just a
and sort each group on b.

As far as window functions go, we clearly need some kind of type
interface feature, but I am unclear whether we should sandwhich it
into the btree opclass machinery or whether it might be better to
create a whole separate concept just for this purpose. Range types
might also like to have some of the same information (addition and
subtraction operators for a type, and perhaps also the identity and
unit if those exist).

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company