With help of Oleg I found, that line "*left = *right = FirstOffsetNumber;"
was needed only for 7.X compatibility, and it isn't needed any more.
Also, I've replaced "i - 1" by "i - FirstOffsetNumber" in array filling.
I believe it's more correct way, because it'll work correctly in the case
when FirstOffsetNumber alters.
----
With best regards,
Alexander Korotkov.
*** a/contrib/seg/seg.c
--- b/contrib/seg/seg.c
***************
*** 292,329 **** gseg_penalty(GISTENTRY *origentry, GISTENTRY *newentry, float *result)
return (result);
}
/*
** The GiST PickSplit method for segments
! ** We use Guttman's poly time split algorithm
*/
GIST_SPLITVEC *
gseg_picksplit(GistEntryVector *entryvec,
GIST_SPLITVEC *v)
{
! OffsetNumber i,
! j;
! SEG *datum_alpha,
! *datum_beta;
SEG *datum_l,
*datum_r;
! SEG *union_d,
! *union_dl,
! *union_dr;
! SEG *inter_d;
! bool firsttime;
! float size_alpha,
! size_beta,
! size_union,
! size_inter;
! float size_waste,
! waste;
! float size_l,
! size_r;
int nbytes;
! OffsetNumber seed_1 = 1,
! seed_2 = 2;
OffsetNumber *left,
*right;
OffsetNumber maxoff;
--- 292,333 ----
return (result);
}
+ /*
+ * Auxiliary structure for picksplit method.
+ */
+ typedef struct
+ {
+ int index;
+ SEG *data;
+ } PickSplitSortItem;
+ /*
+ * Compare function for PickSplitSortItem based on seg_cmp.
+ */
+ static int
+ sort_item_cmp(const void *a, const void *b)
+ {
+ PickSplitSortItem *i1 = (PickSplitSortItem *)a;
+ PickSplitSortItem *i2 = (PickSplitSortItem *)b;
+ return seg_cmp(i1->data, i2->data);
+ }
/*
** The GiST PickSplit method for segments
! ** Algorithm based on sorting. Incoming array of segs is sorting using seg_cmp
! ** function. After that first half of segs goes to the left datum, and the
! ** second half of segs goes to the right datum.
*/
GIST_SPLITVEC *
gseg_picksplit(GistEntryVector *entryvec,
GIST_SPLITVEC *v)
{
! OffsetNumber i;
SEG *datum_l,
*datum_r;
! PickSplitSortItem *sortItems;
int nbytes;
! OffsetNumber seed_2;
OffsetNumber *left,
*right;
OffsetNumber maxoff;
***************
*** 332,443 **** gseg_picksplit(GistEntryVector *entryvec,
fprintf(stderr, "picksplit\n");
#endif
! maxoff = entryvec->n - 2;
! nbytes = (maxoff + 2) * sizeof(OffsetNumber);
v->spl_left = (OffsetNumber *) palloc(nbytes);
v->spl_right = (OffsetNumber *) palloc(nbytes);
! firsttime = true;
! waste = 0.0;
!
! for (i = FirstOffsetNumber; i < maxoff; i = OffsetNumberNext(i))
{
! datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
! for (j = OffsetNumberNext(i); j <= maxoff; j = OffsetNumberNext(j))
! {
! datum_beta = (SEG *) DatumGetPointer(entryvec->vector[j].key);
!
! /* compute the wasted space by unioning these guys */
! /* size_waste = size_union - size_inter; */
! union_d = seg_union(datum_alpha, datum_beta);
! rt_seg_size(union_d, &size_union);
! inter_d = seg_inter(datum_alpha, datum_beta);
! rt_seg_size(inter_d, &size_inter);
! size_waste = size_union - size_inter;
!
! /*
! * are these a more promising split that what we've already seen?
! */
! if (size_waste > waste || firsttime)
! {
! waste = size_waste;
! seed_1 = i;
! seed_2 = j;
! firsttime = false;
! }
! }
}
left = v->spl_left;
v->spl_nleft = 0;
right = v->spl_right;
v->spl_nright = 0;
! datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[seed_1].key);
! datum_l = seg_union(datum_alpha, datum_alpha);
! rt_seg_size(datum_l, &size_l);
! datum_beta = (SEG *) DatumGetPointer(entryvec->vector[seed_2].key);
! datum_r = seg_union(datum_beta, datum_beta);
! rt_seg_size(datum_r, &size_r);
!
! /*
! * Now split up the regions between the two seeds. An important property
! * of this split algorithm is that the split vector v has the indices of
! * items to be split in order in its left and right vectors. We exploit
! * this property by doing a merge in the code that actually splits the
! * page.
! *
! * For efficiency, we also place the new index tuple in this loop. This is
! * handled at the very end, when we have placed all the existing tuples
! * and i == maxoff + 1.
! */
!
! maxoff = OffsetNumberNext(maxoff);
! for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
! /*
! * If we've already decided where to place this item, just put it on
! * the right list. Otherwise, we need to figure out which page needs
! * the least enlargement in order to store the item.
! */
!
! if (i == seed_1)
! {
! *left++ = i;
! v->spl_nleft++;
! continue;
! }
! else if (i == seed_2)
! {
! *right++ = i;
! v->spl_nright++;
! continue;
! }
!
! /* okay, which page needs least enlargement? */
! datum_alpha = (SEG *) DatumGetPointer(entryvec->vector[i].key);
! union_dl = seg_union(datum_l, datum_alpha);
! union_dr = seg_union(datum_r, datum_alpha);
! rt_seg_size(union_dl, &size_alpha);
! rt_seg_size(union_dr, &size_beta);
!
! /* pick which page to add it to */
! if (size_alpha - size_l < size_beta - size_r)
{
! datum_l = union_dl;
! size_l = size_alpha;
! *left++ = i;
v->spl_nleft++;
}
else
{
! datum_r = union_dr;
! size_r = size_alpha;
! *right++ = i;
v->spl_nright++;
}
}
- *left = *right = FirstOffsetNumber; /* sentinel value, see dosplit() */
v->spl_ldatum = PointerGetDatum(datum_l);
v->spl_rdatum = PointerGetDatum(datum_r);
--- 336,386 ----
fprintf(stderr, "picksplit\n");
#endif
! maxoff = entryvec->n - 1;
! nbytes = (maxoff + 1) * sizeof(OffsetNumber);
! sortItems = (PickSplitSortItem *)palloc(maxoff * sizeof(PickSplitSortItem));
v->spl_left = (OffsetNumber *) palloc(nbytes);
v->spl_right = (OffsetNumber *) palloc(nbytes);
! /*
! * Preparing auxiliary array and sorting.
! */
! for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
{
! sortItems[i - FirstOffsetNumber].index = i;
! sortItems[i - FirstOffsetNumber].data = (SEG *) DatumGetPointer(entryvec->vector[i].key);
}
+ qsort(sortItems, maxoff, sizeof(PickSplitSortItem), sort_item_cmp);
+ seed_2 = maxoff / 2;
left = v->spl_left;
v->spl_nleft = 0;
right = v->spl_right;
v->spl_nright = 0;
! for (i = 0; i < maxoff; i++)
{
! /* First half of segs goes to the left datum. */
! if (i < seed_2)
{
! datum_l = seg_union(sortItems[i].data,
! (i == 0
! ? sortItems[i].data /* union with self at start */
! : datum_l) /* union with existing value */ );
! *left++ = sortItems[i].index;
v->spl_nleft++;
}
+ /* The other half of segs goes to the right datum. */
else
{
! datum_r = seg_union(sortItems[i].data,
! (i == seed_2
! ? sortItems[i].data /* union with self at start */
! : datum_r) /* union with existing value */ );
! *right++ = sortItems[i].index;
v->spl_nright++;
}
}
v->spl_ldatum = PointerGetDatum(datum_l);
v->spl_rdatum = PointerGetDatum(datum_r);
--
Sent via pgsql-hackers mailing list ([email protected])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
