Fix for seg picksplit function

Hello Alexander,

Here follows a review of your patch.

Hackers,

Seg contrib module contains the same bug in picksplit function as
cube contrib module.

Good catch! :-)

Also, Guttman's split algorithm is not needed in unidimensional case,
because sorting based algorithm is good in this case.

I had some doubts whether this is true in the general case, instead of
the given example. I increased the interval width in your example to
0.25*b instead of 0.00005*b, with the purpose to increase overlaps
between intervals. Though the performance gain was less, it was still
faster than Guttmans algorithm. To make things worse I also tested with
an interval with of 1*b, resulting in a lot of overlaps and compared
several overlap queries. The sorting algorithm was 25% to 40% faster on
searches. Index creation time with the sorting algorithm is also a
fraction of the original creation time.

Since this testing could be part of a review, I looked at the code as
well and listed myself as reviewer on the commitfest.

Comparing with gbt_num_picksplit reveals some differences with sort
array intialization and size, the former's sort array starts at index 1
(FirstOffsetNumber), your implementation starts at 0 for sorting and
hence the size of the sorting array can be one element less. I prefer
your way of sort array initialization; gbt_num_pickplits's use of
FirstOffsetNumber of the qsort array seems to mix a define from the
gist/btree namespace for no reason and might even lead to confusion.

The remaining part of the new picksplit function puts the segs into left
or right, I think the code is easier to understand if there was only one
for loop from i=1 to 1 < maxoff, for the current code I had to verify
that all sort array entries were really used with the two seperate loops
that also skipped the first value. I edited the code a bit, and also
used seg_union to initialize/palloc the datum values. Finally, waste and
firsttime variables were initialized but not used anymore, so removed.

Attached is a revised patch.

regards,
Yeb Havinga

PS: when comparing with gbt_num_picksplit, I noticed that that one does
not update v->spl_ldatum and spl_rdatum to the union datums, but
initializes these to 0 at the beginning and never seems to update them.
Not sure if this is a problem since the num_picksplit stuff seems to
work well.

Hello Yeb,

Thank you for review and code refactoring.

PS: when comparing with gbt_num_picksplit, I noticed that that one does not

update v->spl_ldatum and spl_rdatum to the union datums, but initializes
these to 0 at the beginning and never seems to update them. Not sure if this
is a problem since the num_picksplit stuff seems to work well.

Actually gbt_num_picksplit updates v->spl_ldatum and spl_rdatum
inside gbt_num_bin_union function.

----
With best regards,
Alexander Korotkov.

Do you think now patch is ready for committer or it require further review
by you or somebody else?

----
With best regards,
Alexander Korotkov.

Alexander Korotkov wrote:

Do you think now patch is ready for committer or it require further
review by you or somebody else?

It's probably ready for committer, however the code now doesn't mention
any reference or bit of information that it is faster than the original
one. I was wondering how you discovered this, or is there any reverence
to e.g. a gist paper/other work where this is researched? If the info is
available, some comments in the code might help future gist developers
for picking a right algorithm for other datatypes.

I don't think further review is required, but very much welcome further
exploration of which picksplit algorithms match which datatype in which
distribution best.

regards,
Yeb Havinga

Hmm, the second for loop in gseg_picksplit uses "i < maxoff" whereas the
other one uses <=. The first is probably correct; if the second is also
correct it merits a comment on the discrepancy (To be honest, I'd get
rid of the "-1" in computing maxoff and use < in both places, given that
offsets are 1-indexed). Also, the second one is using i++ to increment;
probably should be OffsetNumberNext just to stay consistent with the
rest of the code.

The assignment to *left and *right at the end of the routine seem pretty
useless (not to mention the comment talking about a routine that doesn't
exist anywhere).

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

Hmm, the second for loop in gseg_picksplit uses "i < maxoff" whereas the
other one uses <=. The first is probably correct; if the second is also
correct it merits a comment on the discrepancy (To be honest, I'd get
rid of the "-1" in computing maxoff and use < in both places, given that
offsets are 1-indexed). Also, the second one is using i++ to increment;
probably should be OffsetNumberNext just to stay consistent with the
rest of the code.

Actually I can't understand the purpose of FirstOffsetNumber
and OffsetNumberNext macros. When I wrote the patch I though about sortItems
as about "clean from all these strange things" array, that's why I didn't
use OffsetNumberNext there. :)
I see only way to save logic of these macros is to use array starting from
FirstOffsetNumber index like in gbt_num_picksplit.

The assignment to *left and *right at the end of the routine seem pretty

useless (not to mention the comment talking about a routine that doesn't
exist anywhere).

I found, that gtrgm_picksplit in pg_trgm and gtsvector_picksplit in core
still use this assignment, while gist_box_picksplit and gbt_num_picksplit
not. If this assignment is overall useless, than I think we should remove it
from gtrgm_picksplit and gtsvector_picksplit in order to not mislead
developers of gist implementations.

----
With best regards,
Alexander Korotkov.

On Wed, Nov 10, 2010 at 4:53 PM, Alexander Korotkov <aekorotkov@gmail.com>wrote:

Hmm, the second for loop in gseg_picksplit uses "i < maxoff" whereas the

other one uses <=. The first is probably correct; if the second is also
correct it merits a comment on the discrepancy (To be honest, I'd get
rid of the "-1" in computing maxoff and use < in both places, given that
offsets are 1-indexed). Also, the second one is using i++ to increment;
probably should be OffsetNumberNext just to stay consistent with the
rest of the code.

Actually I can't understand the purpose of FirstOffsetNumber
and OffsetNumberNext macros. When I wrote the patch I though about sortItems
as about "clean from all these strange things" array, that's why I didn't
use OffsetNumberNext there. :)
I see only way to save logic of these macros is to use array starting from
FirstOffsetNumber index like in gbt_num_picksplit.

For example, if we assume, that OffsetNumberNext can do something other that
just increment, that we shouldn't use it in loop on sortItems, but should do
following things:
1) Do additional loop first to calculate actual items count. (Because we
don't know how OffsetNumberNext increases the index. Probably it can
increase it by various value.)
2) Fill sortItems using separate index.

----
With best regards,
Alexander Korotkov.

On 2010-11-10 14:27, Alvaro Herrera wrote:

Hmm, the second for loop in gseg_picksplit uses "i< maxoff" whereas the
other one uses<=. The first is probably correct; if the second is also
correct it merits a comment on the discrepancy (To be honest, I'd get
rid of the "-1" in computing maxoff and use< in both places, given that
offsets are 1-indexed).

Good point. The second loop walks over the sorted array, which is
0-indexed. Do you favor making the sort array 1-indexed, like done in
e.g. gbt_num_picksplit? The downside is that the sort array is
initialized with length maxoff + 1: puzzling on its own, even more since
maxoff itself is initialized as entryvec->n -1. Note also that the qsort
call for the 1-indexed variant is more complex since it must skip the
first element.

probably should be OffsetNumberNext just to stay consistent with the
rest of the code.

Yes.

The assignment to *left and *right at the end of the routine seem pretty
useless (not to mention the comment talking about a routine that doesn't
exist anywhere).

They are necessary and it is code untouched by this patch, and the same
line occurs in other picksplit functions as well. The gbt_num_picksplit
function shows that it can be avoided, by rewriting in the second loop

*left++ = sortItems[i].index;
into
v->spl_left[v->spl_nleft] = sortItems[i].index

Even though this is longer code, I prefer this variant over the shorter one.

regards,
Yeb Havinga

On Wed, Nov 10, 2010 at 5:37 PM, Yeb Havinga <yebhavinga@gmail.com> wrote:

They are necessary and it is code untouched by this patch, and the same
line occurs in other picksplit functions as well. The gbt_num_picksplit
function shows that it can be avoided, by rewriting in the second loop

*left++ = sortItems[i].index;
into
v->spl_left[v->spl_nleft] = sortItems[i].index

Even though this is longer code, I prefer this variant over the shorter
one.

I can't understand this point. How the way of spl_left and spl_right arrays
filling is related with additional FirstOffsetNumber value at the end of
array, which is added by "*left = *right = FirstOffsetNumber;" line?

----
With best regards,
Alexander Korotkov.

On 2010-11-10 15:46, Alexander Korotkov wrote:

On Wed, Nov 10, 2010 at 5:37 PM, Yeb Havinga <yebhavinga@gmail.com
<mailto:yebhavinga@gmail.com>> wrote:

They are necessary and it is code untouched by this patch, and the
same line occurs in other picksplit functions as well. The
gbt_num_picksplit function shows that it can be avoided, by
rewriting in the second loop

*left++ = sortItems[i].index;
into
v->spl_left[v->spl_nleft] = sortItems[i].index

Even though this is longer code, I prefer this variant over the
shorter one.

I can't understand this point. How the way of spl_left
and spl_right arrays filling is related with
additional FirstOffsetNumber value at the end of array, which is
added by "*left = *right = FirstOffsetNumber;" line?

You're right, they are not related. I'm no longer sure it is necessary,
looking at gistUserPicksplit.

regards,
Yeb Havinga

On Wed, Nov 10, 2010 at 6:05 PM, Yeb Havinga <yebhavinga@gmail.com> wrote:

On 2010-11-10 15:46, Alexander Korotkov wrote:

On Wed, Nov 10, 2010 at 5:37 PM, Yeb Havinga <yebhavinga@gmail.com> wrote:

They are necessary and it is code untouched by this patch, and the same
line occurs in other picksplit functions as well. The gbt_num_picksplit
function shows that it can be avoided, by rewriting in the second loop

*left++ = sortItems[i].index;
into
v->spl_left[v->spl_nleft] = sortItems[i].index

Even though this is longer code, I prefer this variant over the shorter
one.

I can't understand this point. How the way of spl_left and spl_right arrays
filling is related with additional FirstOffsetNumber value at the end of
array, which is added by "*left = *right = FirstOffsetNumber;" line?

You're right, they are not related. I'm no longer sure it is necessary,
looking at gistUserPicksplit.

Teodor, Oleg, probably, you can help us. Is "*left = *right =
FirstOffsetNumber;" line necessary in picksplit function or doing something
useful?

----
With best regards,
Alexander Korotkov.

Alexander Korotkov <aekorotkov@gmail.com> writes:

On Wed, Nov 10, 2010 at 4:53 PM, Alexander Korotkov <aekorotkov@gmail.com>wrote:

Actually I can't understand the purpose of FirstOffsetNumber
and OffsetNumberNext macros.

For example, if we assume, that OffsetNumberNext can do something other that
just increment, that we shouldn't use it in loop on sortItems,

Right. Good style is to use FirstOffsetNumber/OffsetNumberNext if you
are walking through the items on a page. They should *not* be used when
you are just iterating over a local array. I'd go with "for (i = 0;
i < nitems; i++)" for the latter.

regards, tom lane

On 2010-11-10 14:53, Alexander Korotkov wrote:

Actually I can't understand the purpose of FirstOffsetNumber
and OffsetNumberNext macros. When I wrote the patch I though about
sortItems as about "clean from all these strange things" array, that's
why I didn't use OffsetNumberNext there. :)
I see only way to save logic of these macros is to use array starting
from FirstOffsetNumber index like in gbt_num_picksplit.

Another reason for not using is FirstOffsetNumber and it's related
macro's on the qsort array, is that InvalidOffsetNumber (0) is not
invalid for the array.
However all other sorts in picksplit functions already seem to do it
this way. I'm not sure it's wise to introduce a different approach.

The assignment to *left and *right at the end of the routine seem
pretty
useless (not to mention the comment talking about a routine that
doesn't
exist anywhere).

I found, that gtrgm_picksplit in pg_trgm and gtsvector_picksplit in
core still use this assignment, while gist_box_picksplit
and gbt_num_picksplit not. If this assignment is overall useless, than
I think we should remove it from gtrgm_picksplit
and gtsvector_picksplit in order to not mislead developers of gist
implementations.

+1

regards,
Yeb Havinga

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.

On Mon, Nov 15, 2010 at 4:06 AM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:

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.

The loop that begins here:

for (i = 0; i < maxoff; i++)
{
/* First half of segs goes to the left datum. */
if (i < seed_2)

...looks like it should perhaps be broken into two separate loops.
That might also help tweak the logic in a way that eliminates this:

seg.c: In function ‘gseg_picksplit’:
seg.c:327: warning: ‘datum_r’ may be used uninitialized in this function
seg.c:326: warning: ‘datum_l’ may be used uninitialized in this function

But on a broader note, I'm not very certain the sorting algorithm is
sensible. For example, suppose you have 10 segments that are exactly
'0' and 20 segments that are exactly '1'. Maybe I'm misunderstanding,
but it seems like this will result in a 15/15 split when we almost
certainly want a 10/20 split. I think there will be problems in more
complex cases as well. The documentation says about the less-than and
greater-than operators that "These operators do not make a lot of
sense for any practical purpose but sorting."

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

On Tue, Nov 16, 2010 at 3:07 AM, Robert Haas <robertmhaas@gmail.com> wrote:

The loop that begins here:

for (i = 0; i < maxoff; i++)
{
/* First half of segs goes to the left datum. */
if (i < seed_2)

...looks like it should perhaps be broken into two separate loops.
That might also help tweak the logic in a way that eliminates this:

seg.c: In function ‘gseg_picksplit’:
seg.c:327: warning: ‘datum_r’ may be used uninitialized in this function
seg.c:326: warning: ‘datum_l’ may be used uninitialized in this function

I restored original version of that loop.

But on a broader note, I'm not very certain the sorting algorithm is
sensible. For example, suppose you have 10 segments that are exactly
'0' and 20 segments that are exactly '1'. Maybe I'm misunderstanding,
but it seems like this will result in a 15/15 split when we almost
certainly want a 10/20 split. I think there will be problems in more
complex cases as well. The documentation says about the less-than and
greater-than operators that "These operators do not make a lot of
sense for any practical purpose but sorting."

I think almost any split algorithm has corner cases when it's results don't
look very good. I think the way to understand significance of these corner
cases for real life is to perform sufficient testing on datasets which is
close to real life. I'm not feeling power to propose enough of test datasets
and estimate their significance for real life cases, and I need help in this
field.

----
With best regards,
Alexander Korotkov.

On Tue, Nov 16, 2010 at 3:07 AM, Robert Haas <robertmhaas@gmail.com> wrote:

But on a broader note, I'm not very certain the sorting algorithm is
sensible. For example, suppose you have 10 segments that are exactly
'0' and 20 segments that are exactly '1'. Maybe I'm misunderstanding,
but it seems like this will result in a 15/15 split when we almost
certainly want a 10/20 split. I think there will be problems in more
complex cases as well. The documentation says about the less-than and
greater-than operators that "These operators do not make a lot of
sense for any practical purpose but sorting."

In order to illustrate a real problem we should think about
gist behavior with great enough amount of data. For example, I tried to
extrapolate this case to 100000 of segs where 40% are (0,1) segs and 60% are
(1,2) segs. And this case doesn't seem a problem for me.
Here are the details.

test=# insert into seg_test (select case when random()<0.4 then '0..1'::seg
else '1..2'::seg end from generate_series(1,100000));
INSERT 0 100000
Time: 7543,941 ms

test=# create index seg_test_idx on seg_test using gist(a);
CREATE INDEX
Time: 17839,450 ms

test=# explain (analyze, buffers) select count(*) from seg_test where a @>
'1.5'::seg;
QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=344.84..344.85 rows=1 width=0) (actual
time=186.192..186.193 rows=1 loops=1)
Buffers: shared hit=887
-> Bitmap Heap Scan on seg_test (cost=5.05..344.59 rows=100 width=0)
(actual time=16.066..102.586 rows=60206 l
oops=1)
Recheck Cond: (a @> '1.5'::seg)
Buffers: shared hit=887
-> Bitmap Index Scan on seg_test_idx (cost=0.00..5.03 rows=100
width=0) (actual time=15.948..15.948 rows
=60206 loops=1)
Index Cond: (a @> '1.5'::seg)
Buffers: shared hit=396
Total runtime: 186.306 ms
(9 rows)

test=# explain (analyze, buffers) select count(*) from seg_test where a @>
'0.5'::seg;
QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=344.84..344.85 rows=1 width=0) (actual
time=144.293..144.295 rows=1 loops=1)
Buffers: shared hit=754
-> Bitmap Heap Scan on seg_test (cost=5.05..344.59 rows=100 width=0)
(actual time=28.926..87.625 rows=39794 lo
ops=1)
Recheck Cond: (a @> '0.5'::seg)
Buffers: shared hit=754
-> Bitmap Index Scan on seg_test_idx (cost=0.00..5.03 rows=100
width=0) (actual time=26.969..26.969 rows
=39794 loops=1)
Index Cond: (a @> '0.5'::seg)
Buffers: shared hit=263
Total runtime: 144.374 ms
(9 rows)

test=# select pg_relpages('seg_test_idx');
pg_relpages
-------------
656
(1 row)

Total number of pages in index is 656 and number of pages used in scans
is 263+396=659. Only 3 pages overhead.
We can see the distribution of segs in index using gevel.

test=# select a, count(1) from gist_print('seg_test_idx') as t(level int,
valid bool, a seg) group by a;
a | count
--------+-------
0 .. 1 | 40054
0 .. 2 | 2
1 .. 2 | 60599
(3 rows)

test=# select level, a, count(1) from gist_print('seg_test_idx') as t(level
int, valid bool, a seg) group by level,a order by level, a;
level | a | count
-------+--------+-------
1 | 0 .. 1 | 1
1 | 0 .. 2 | 1
1 | 1 .. 2 | 1
2 | 0 .. 1 | 259
2 | 0 .. 2 | 1
2 | 1 .. 2 | 392
3 | 0 .. 1 | 39794
3 | 1 .. 2 | 60206
(8 rows)

We have only 2 segs '0..2' (one on the first level and one on the second)
and all other segs are '0..1' and '1..2'. I think there will be more
problems when we'll have many of distinct values where each have count value
about half of index page.

----
With best regards,
Alexander Korotkov.

On Tue, Nov 16, 2010 at 6:07 AM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:

On Tue, Nov 16, 2010 at 3:07 AM, Robert Haas <robertmhaas@gmail.com> wrote:

But on a broader note, I'm not very certain the sorting algorithm is
sensible.  For example, suppose you have 10 segments that are exactly
'0' and 20 segments that are exactly '1'.  Maybe I'm misunderstanding,
but it seems like this will result in a 15/15 split when we almost
certainly want a 10/20 split.  I think there will be problems in more
complex cases as well.  The documentation says about the less-than and
greater-than operators that "These operators do not make a lot of
sense for any practical purpose but sorting."

In order to illustrate a real problem we should think about
gist behavior with great enough amount of data. For example, I tried to
extrapolate this case to 100000 of segs where 40% are (0,1) segs and 60% are
(1,2) segs. And this case doesn't seem a problem for me.

Well, the problem with just comparing on < is that it takes very
little account of the upper bounds. I think the cases where a simple
split would hurt you the most are those where examining the upper
bound is necessary to to get a good split.

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

On 2010-11-20 04:46, Robert Haas wrote:

On Tue, Nov 16, 2010 at 6:07 AM, Alexander Korotkov
<aekorotkov@gmail.com> wrote:

On Tue, Nov 16, 2010 at 3:07 AM, Robert Haas<robertmhaas@gmail.com> wrote:

But on a broader note, I'm not very certain the sorting algorithm is
sensible. For example, suppose you have 10 segments that are exactly
'0' and 20 segments that are exactly '1'. Maybe I'm misunderstanding,
but it seems like this will result in a 15/15 split when we almost
certainly want a 10/20 split. I think there will be problems in more
complex cases as well. The documentation says about the less-than and
greater-than operators that "These operators do not make a lot of
sense for any practical purpose but sorting."

In order to illustrate a real problem we should think about
gist behavior with great enough amount of data. For example, I tried to
extrapolate this case to 100000 of segs where 40% are (0,1) segs and 60% are
(1,2) segs. And this case doesn't seem a problem for me.

Well, the problem with just comparing on< is that it takes very
little account of the upper bounds. I think the cases where a simple
split would hurt you the most are those where examining the upper
bound is necessary to to get a good split.

With the current 8K default blocksize, I put my money on the sorting
algorithm for any seg case. The r-tree algorithm's performance is
probably more influenced by large buckets->low tree depth->generic keys
on non leaf nodes.

regards,
Yeb Havinga