Horton

Thread

  1. Fix for GiST penalty

    Alexander Korotkov <aekorotkov@gmail.com> — 2011-05-30T22:07:24Z

    Hi!

During my work on GSoC project, I found bad perfomace of GiST for point
datatype. It appears even on uniform random data.

test=# create table test as (select point(random(), random()) from
generate_series(1, 1000000));
SELECT 1000000
test=# create index test_idx on test using gist(point);
CREATE INDEX
test=# explain (analyze, buffers) select * from test where point <@
box(point(0.5,0.5), point(0.505,0.505));
                                                       QUERY PLAN

------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=48.40..2593.73 rows=1000 width=16) (actual
time=97.479..97.551 rows=24 loops=1)
   Recheck Cond: (point <@ '(0.505,0.505),(0.5,0.5)'::box)
   Buffers: shared hit=5126
   ->  Bitmap Index Scan on test_idx  (cost=0.00..48.15 rows=1000 width=0)
(actual time=97.462..97.462 rows=24 loops=1)
         Index Cond: (point <@ '(0.505,0.505),(0.5,0.5)'::box)
         Buffers: shared hit=5102
 Total runtime: 97.644 ms
(7 rows)

Search for the cause takes relatively long time from me, but finally I did.
In gist_box_penalty function floating point error in line
  *result = (float) (size_box(ud) - size_box(origentry->key));
sometimes makes *result a very small negative number.
I beleive that best place to fix it is gistpenalty function. The attached
patch makes this function treating negative number from user's penalty as
zero. I didn't find mention of negative penalty value in documentation. So,
AFAICS such behaviour shouldn't break anything.
After the patch index performance is ok.

test=# explain (analyze, buffers) select * from test where point <@
box(point(0.5,0.5), point(0.505,0.505));
                                                      QUERY PLAN

----------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=44.35..2589.68 rows=1000 width=16) (actual
time=0.988..1.116 rows=24 loops=1)
   Recheck Cond: (point <@ '(0.505,0.505),(0.5,0.5)'::box)
   Buffers: shared hit=44
   ->  Bitmap Index Scan on test_idx  (cost=0.00..44.10 rows=1000 width=0)
(actual time=0.966..0.966 rows=24 loops=1)
         Index Cond: (point <@ '(0.505,0.505),(0.5,0.5)'::box)
         Buffers: shared hit=20
 Total runtime: 1.313 ms
(7 rows)

------
With best regards,
Alexander Korotkov.

  2. Re: Fix for GiST penalty

    Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> — 2011-05-31T08:06:57Z

    On 31.05.2011 01:07, Alexander Korotkov wrote:
> In gist_box_penalty function floating point error in line
>    *result = (float) (size_box(ud) - size_box(origentry->key));
> sometimes makes *result a very small negative number.
> I beleive that best place to fix it is gistpenalty function. The attached
> patch makes this function treating negative number from user's penalty as
> zero. I didn't find mention of negative penalty value in documentation. So,
> AFAICS such behaviour shouldn't break anything.
> After the patch index performance is ok.

Yeah, there seems to be a hidden assumption that the return value of the 
penalty function is always >= 0. The logic in gistchoose() in particular 
seems to assume that, by using < 0 to mean uninitialized slots in the 
which_grow array.

The documentation should be fixed too.

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com

  3. Re: Fix for GiST penalty

    Alexander Korotkov <aekorotkov@gmail.com> — 2011-05-31T10:03:06Z

    On Tue, May 31, 2011 at 12:06 PM, Heikki Linnakangas <
heikki.linnakangas@enterprisedb.com> wrote:

> The documentation should be fixed too.
>
Patch with documentation fix is attached.

I tried to reproduce this problem on another computer with Windows, but
problem doesn't occurs. So, seems that it can be OS, compiler, optimization
level or CPU specific.
I provide some information about my laptop where I've encountered with
problem. I hope this helps to reproduce this problem if needed.

$ uname -a
Linux smagen-notebook 2.6.38-8-generic-pae #42-Ubuntu SMP Mon Apr 11
05:17:09 UTC 2011 i686 i686 i386 GNU/Linux

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=11.04
DISTRIB_CODENAME=natty
DISTRIB_DESCRIPTION="Ubuntu 11.04"

$ gcc --version
gcc (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2

$ cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Duo CPU     T7300  @ 2.00GHz
stepping : 10
cpu MHz : 800.000
cache size : 4096 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
apicid : 0
initial apicid : 0
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat
pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc
arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3
cx16 xtpr pdcm lahf_lm ida dts tpr_shadow vnmi flexpriority
bogomips : 3990.66
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:

processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Duo CPU     T7300  @ 2.00GHz
stepping : 10
cpu MHz : 800.000
cache size : 4096 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
apicid : 1
initial apicid : 1
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat
pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc
arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3
cx16 xtpr pdcm lahf_lm ida dts tpr_shadow vnmi flexpriority
bogomips : 3989.97
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:

------
With best regards,
Alexander Korotkov.

  4. Re: Fix for GiST penalty

    Tom Lane <tgl@sss.pgh.pa.us> — 2011-05-31T21:55:49Z

    Alexander Korotkov <aekorotkov@gmail.com> writes:
> On Tue, May 31, 2011 at 12:06 PM, Heikki Linnakangas <
> heikki.linnakangas@enterprisedb.com> wrote:
>> The documentation should be fixed too.

> Patch with documentation fix is attached.

Applied, thanks.  I threw in an isnan() test too, just to be really sure
funny penalty results wouldn't break anything.

			regards, tom lane