Re: Yet another fast GiST build

On Fri, Aug 30, 2019 at 2:44 PM Andrey Borodin <x4mmm(at)yandex-team(dot)ru> wrote:
>
> 30 авг. 2019 г., в 3:47, Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> написал(а):
>
> 1) Binary search in non-leaf pages instead of probing each key is much faster.
>
>
> That's a neat idea, but key union breaks ordering, even for z-order.
> for two sets of tuples X and Y
> if for any i,o from N, Xi < Yo
> does not guaranty union(X) < union (Y)
>
> For example consider this z-ordered keyspace (picture attached)
>
> union(5, 9) is z-order-smaller than union(4,4)
>
> I'm not even sure we can use sorted search for choosing subtree for insertion.

Sorry, I didn't explain my proposal in enough details. I didn't mean
B-tree separator keys would be the same as union key (MBR). I mean
B-tree on Z-values, which maintains union key in addition to separator
keys. So, you select downlink to insert using separator Z-values and
then also extend union key (if needed). It's probably still not
enough detail yet. I'll try to spend more time for more detailed
description later.

>
> How do you think, should I supply GiST-build patch with docs and tests and add it to CF? Or do we need more design discussion before?

+1 for adding to CF.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company