Re: WIP: SP-GiST, Space-Partitioned GiST

Teodor Sigaev <teodor(at)sigaev(dot)ru> writes:
>> However, I now have another question: what is the point of the
>> allTheSame mechanism? It seems to add quite a great deal of complexity,

> I thought about two options: separate code path in core to support
> a-lot-of-the-same-values with minimal support in support functions and move all
> logic about this case to support functions. Second option is demonstrated in
> k-d-tree implementation, where split axis is contained by each half-plane.
> May be it is a simpler solution although it moves responsibility to opclass
> developers.

I eventually realized that you have to have it to ensure that you can
split a leaf-tuple list across pages even when the opclass picksplit
function thinks the values are all the same. What made no sense to me
was (a) having the property forcibly inherit to child inner tuples,
and (b) suppressing node labels in allTheSame tuples. That could make
it impossible for the opclass to reconstruct values. In my local copy
I've changed this behavior a bit and improved the documentation about
what opclasses have to do with the flag.

>> one thing, it's giving me fits while attempting to fix the limitation
>> on storing long indexed values. There's no reason why a suffix tree
>> representation shouldn't work for long strings, but you have to be
>> willing to cap the length of any given inner tuple's prefix to something

> I don't see clear interface for now: let we have an empty index and we
> need to insert a long string (more than even several page). So, it's
> needed to have support function to split input value to several
> ones. I supposed that sp-gist is already complex enough for first step
> to add support for this non very useful case.

Well, I have it working well enough to satisfy me locally. The
picksplit function can handle the prefixing perfectly well, as long as
it's not surprised by getting called on a single oversized leaf tuple.
(I changed the format of leaf tuples to let the size field be 30 bits,
so we can have an oversized leaf tuple in memory even if we can't store
it. This doesn't cost anything space-wise because of alignment rules.)

> Of course, for future we have a plans to add support of long values,
> NULLs/IS NULL, knn-search at least.

I think if we're going to do nulls we can't wait; that will necessarily
change the on-disk representation, which is going to be a hard sell once
9.2 is out the door. Neither leaf nor inner tuples have any good way to
deal with nulls at present. Maybe if you invent a completely separate
representation for nulls it could be added on after the fact, but that
seems like an ugly answer.

> I missed that planner will not create qual-free scan, because I thought it's
> still possible with NOT NULL columns. If not, this code could be
> removed/commented/ifdefed.

Well, it won't do so because pg_am.amoptionalkey is not set. But we
can't set that if we don't store NULLs.

Right at the moment, my local copy has completely broken handling of
WAL, because I've been focusing on the opclass interface and didn't
worry about WAL while I was whacking the picksplit code around.
I'll try to clean that up today and then post a new version of the
patch.

regards, tom lane