Opened 12 years ago

Closed 12 years ago

#1895 closed enhancement (fixed)

New node splitting algorithm for GiST

Reported by: smagen Owned by: pramsey
Priority: medium Milestone: PostGIS 2.1.0
Component: postgis Version: master
Keywords: Cc:

Description

Double sorting based node splitting algorithm allow to dramatically reduce number of index pages used for query evaluation

Attachments (2)

double_sort_split_v1.patch (25.9 KB ) - added by smagen 12 years ago.
Patch
double_sort_split_v2.patch (26.4 KB ) - added by smagen 12 years ago.
Some debugging messages were added

Download all attachments as: .zip

Change History (7)

by smagen, 12 years ago

Attachment: double_sort_split_v1.patch added

Patch

comment:2 by mcayland, 12 years ago

This looks like a well-written and well-documented patch - my only minor quibble is that it appears to drop some of the POSTGIS_DEBUGF() debugging macros which may be useful. Also out of interest, does this code alter any of the memory characteristics of the index build at all?

by smagen, 12 years ago

Attachment: double_sort_split_v2.patch added

Some debugging messages were added

in reply to:  2 comment:3 by smagen, 12 years ago

Replying to mcayland:

This looks like a well-written and well-documented patch - my only minor quibble is that it appears to drop some of the POSTGIS_DEBUGF() debugging macros which may be useful.

I've added some debug messages. However I've to also apply part of this patch http://trac.osgeo.org/postgis/attachment/ticket/1161/gidx_to_string.patch in order to see them. Got following error without it.

ERROR:  could not load library "/usr/lib/postgresql/9.1/lib/postgis-2.1.so":
/usr/lib/postgresql/9.1/lib/postgis-2.1.so: undefined symbol: gidx_to_string

Also out of interest, does this code alter any of the memory characteristics of the index build at all?

Picksplit is called against at maximum few hundred of tuples. Memory context is cleaned after each inserted tuple. So, I don't expect any noticeable change of memory characteristics.

comment:4 by pramsey, 12 years ago

Committed to trunk at r10665 with a KOROTKOV_SPLIT #define in gserialized_gist_2d.c to turn it on/off. By default it is off. Testing and sounds of joy hoped for, and then we can turn it on permanently.

comment:5 by pramsey, 12 years ago

Resolution: fixed
Status: newclosed

Set as default split at r10669

Note: See TracTickets for help on using tickets.