Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit16f8539

Browse files
committed
Support for emulating RTREE indexing in GiST. Contributed by
Oleg Bartunov and Teodor Sigaev.
1 parent3043810 commit16f8539

File tree

11 files changed

+4731
-1
lines changed

11 files changed

+4731
-1
lines changed

‎contrib/Makefile

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
# $Header: /cvsroot/pgsql/contrib/Makefile,v 1.20 2001/05/10 15:51:05 momjian Exp $
1+
# $Header: /cvsroot/pgsql/contrib/Makefile,v 1.21 2001/05/31 18:27:18 tgl Exp $
22

33
subdir = contrib
44
top_builddir = ..
@@ -27,6 +27,7 @@ WANTED_DIRS = \
2727
pgbench\
2828
pgcrypto\
2929
rserv\
30+
rtree_gist\
3031
seg\
3132
soundex\
3233
spi\

‎contrib/README

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -133,6 +133,10 @@ rserv -
133133
replication server
134134
by Vadim B. Mikheev <vadim4o@email.com>
135135

136+
rtree_gist -
137+
Support for emulating RTREE indexing in GiST
138+
by Oleg Bartunov <oleg@sai.msu.su> and Teodor Sigaev <teodor@stack.net>
139+
136140
seg -
137141
Confidence-interval datatype (GiST indexing example)
138142
by Gene Selkov, Jr. <selkovjr@mcs.anl.gov>

‎contrib/rtree_gist/Makefile

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
#
2+
# $Header: /cvsroot/pgsql/contrib/rtree_gist/Attic/Makefile,v 1.1 2001/05/31 18:27:18 tgl Exp $
3+
#
4+
5+
subdir = contrib/rtree_gist
6+
top_builddir = ../..
7+
include$(top_builddir)/src/Makefile.global
8+
9+
# override libdir to install shlib in contrib not main directory
10+
libdir :=$(libdir)/contrib
11+
12+
# shared library parameters
13+
NAME= rtree_gist
14+
SO_MAJOR_VERSION= 1
15+
SO_MINOR_VERSION= 0
16+
17+
overrideCPPFLAGS := -I$(srcdir)$(CPPFLAGS)
18+
19+
OBJS= rtree_gist.o
20+
21+
all: all-lib$(NAME).sql
22+
23+
# Shared library stuff
24+
include$(top_srcdir)/src/Makefile.shlib
25+
26+
27+
$(NAME).sql:$(NAME).sql.in
28+
sed -e's:MODULE_PATHNAME:$(libdir)/$(shlib):g'<$<>$@
29+
30+
.PHONY: submake
31+
submake:
32+
$(MAKE) -C$(top_builddir)/src/test/regress pg_regress
33+
34+
# against installed postmaster
35+
installcheck: submake
36+
$(top_builddir)/src/test/regress/pg_regress rtree_gist
37+
38+
# in-tree test doesn't work yet (no way to install my shared library)
39+
#check: all submake
40+
#$(top_builddir)/src/test/regress/pg_regress --temp-install\
41+
# --top-builddir=$(top_builddir) rtree_gist
42+
check:
43+
@echo"'make check' is not supported."
44+
@echo"Do 'make install', then 'make installcheck' instead."
45+
46+
install: all installdirs install-lib
47+
$(INSTALL_DATA)$(srcdir)/README.$(NAME)$(docdir)/contrib
48+
$(INSTALL_DATA)$(NAME).sql$(datadir)/contrib
49+
50+
installdirs:
51+
$(mkinstalldirs)$(docdir)/contrib$(datadir)/contrib$(libdir)
52+
53+
uninstall: uninstall-lib
54+
rm -f$(docdir)/contrib/README.$(NAME)$(datadir)/contrib/$(NAME).sql
55+
56+
cleandistcleanmaintainer-clean: clean-lib
57+
rm -f$(OBJS)$(NAME).sql
58+
# things created by various check targets
59+
rm -rf results tmp_check log
60+
rm -f regression.diffs regression.out regress.out run_check.out
61+
ifeq ($(PORTNAME), win)
62+
rm -f regress.def
63+
endif
64+
65+
dependdep:
66+
$(CC) -MM$(CFLAGS)*.c>depend
67+
68+
ifeq (depend,$(wildcard depend))
69+
include depend
70+
endif

‎contrib/rtree_gist/README.rtree_gist

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
This is R-Tree implementation using GiST.
2+
Code (for PG95) are taken from http://s2k-ftp.cs.berkeley.edu:8000/gist/pggist/
3+
and changed according to new version of GiST (7.1 and above)
4+
5+
All work was done by Teodor Sigaev (teodor@stack.net) and Oleg Bartunov
6+
(oleg@sai.msu.su). See http://www.sai.msu.su/~megera/postgres/gist
7+
for additional information.
8+
9+
CHANGES:
10+
Tue May 29 17:04:16 MSD 2001
11+
12+
1. Small fixes in polygon code
13+
Thanks to Dave Blasby <dblasby@refractions.net>
14+
15+
Mon May 28 19:42:14 MSD 2001
16+
17+
1. Full implementation of R-tree using GiST - gist_box_ops,gist_poly_ops
18+
2. gist_poly_ops is lossy
19+
3. NULLs support
20+
4. works with multi-key GiST
21+
22+
NOTICE:
23+
This version will works only with postgresql version 7.1 and above
24+
because of changes in interface of function calling.
25+
26+
INSTALLATION:
27+
28+
gmake
29+
gmake install
30+
-- load functions
31+
psql <database> < rtree_gist.sql
32+
33+
REGRESSION TEST:
34+
35+
gmake installcheck
36+
37+
EXAMPLE USAGE:
38+
39+
create table boxtmp (b box);
40+
-- create index
41+
create index bix on boxtmp using gist (b gist_box_ops);
42+
-- query
43+
select * from boxtmp where b && '(1000,1000,0,0)'::box;
44+
45+
46+
BENCHMARKS:
47+
48+
subdirectory bench contains benchmark suite.
49+
Prerequisities: perl, DBI, DBD:Pg, Time::HiRes
50+
51+
cd ./bench
52+
1. createdb TEST
53+
2. psql TEST < ../box.sql
54+
3. ./create_test.pl | psql TEST
55+
-- change $NUM - number of rows in test dataset
56+
4. ./bench.pl - perl script to benchmark queries.
57+
Run script without arguments to see available options.
58+
59+
a)test without GiST index, using built-in R-Tree
60+
./bench.pl -d TEST
61+
b)test R-Tree using GiST index
62+
./bench.pl -d TEST -g
63+
64+
65+
RESULTS:
66+
67+
1. One interesting thing is that insertion time for built-in R-Tree is
68+
about 8 times more than ones for GiST implementation of R-Tree !!!
69+
2. Postmaster requires much more memory for built-in R-Tree
70+
3. Search time depends on dataset. In our case we got:
71+
+------------+-----------+--------------+
72+
|Number boxes|R-tree, sec|R-tree using |
73+
| | | GiST, sec |
74+
+------------+-----------+--------------+
75+
| 10| 0.002| 0.002|
76+
+------------+-----------+--------------+
77+
| 100| 0.002| 0.002|
78+
+------------+-----------+--------------+
79+
| 1000| 0.002| 0.002|
80+
+------------+-----------+--------------+
81+
| 10000| 0.015| 0.025|
82+
+------------+-----------+--------------+
83+
| 20000| 0.029| 0.048|
84+
+------------+-----------+--------------+
85+
| 40000| 0.055| 0.092|
86+
+------------+-----------+--------------+
87+
| 80000| 0.113| 0.178|
88+
+------------+-----------+--------------+
89+
| 160000| 0.338| 0.337|
90+
+------------+-----------+--------------+
91+
| 320000| 0.674| 0.673|
92+
+------------+-----------+--------------+

‎contrib/rtree_gist/bench/bench.pl

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
#!/usr/bin/perl -w
2+
3+
use strict;
4+
# make sure we are in a sane environment.
5+
use DBI();
6+
use DBD::Pg();
7+
use Time::HiResqw( usleep ualarm gettimeofday tv_interval);
8+
use Getopt::Std;
9+
my%opt;
10+
getopts('d:b:gv', \%opt);
11+
12+
if ( !(scalar%opt ) ) {
13+
print<<EOT;
14+
Usage:
15+
$0 -d DATABASE -b N [-v] [-g]
16+
-d DATABASE - DATABASE name
17+
-b N -number of cycles
18+
-v - print sql
19+
-g -use GiST index( default built-in R-tree )
20+
21+
EOT
22+
exit;
23+
}
24+
25+
$opt{d} ||='TEST';
26+
my$dbi=DBI->connect('DBI:Pg:dbname='.$opt{d}) ||die"Couldn't connect DB:$opt{d} !\n";
27+
28+
my$sql;
29+
my$notice;
30+
my$sss ='(3000,3000,2990,2990)';
31+
if ($opt{g} ) {
32+
$notice ="Testing GiST implementation of R-Tree";
33+
$sql ="select count(*) from boxtmp where b && '$sss'::box;";
34+
}else {
35+
$notice ="Testing built-in implementation of R-Tree";
36+
$sql ="select count(*) from boxtmp2 where b && '$sss'::box;";
37+
}
38+
39+
my$t0 = [gettimeofday];
40+
my$count=0;
41+
my$b=$opt{b};
42+
43+
$b ||=1;
44+
foreach ( 1..$b ) {
45+
my@a=exec_sql($dbi,$sql);
46+
$count=$#a;
47+
}
48+
my$elapsed = tv_interval ($t0, [gettimeofday]);
49+
print"$notice:\n";
50+
print"$sql\n"if ($opt{v} );
51+
print"Done\n";
52+
printsprintf("total: %.02f sec; number:%d; for one: %.03f sec; found%d docs\n",$elapsed,$b,$elapsed/$b,$count+1 );
53+
$dbi-> disconnect;
54+
55+
subexec_sql {
56+
my ($dbi,$sql,@keys) =@_;
57+
my$sth=$dbi->prepare($sql) ||die;
58+
$sth->execute(@keys ) ||die;
59+
my$r;
60+
my@row;
61+
while (defined ($r=$sth->fetchrow_hashref ) ) {
62+
push@row,$r;
63+
}
64+
$sth->finish;
65+
return@row;
66+
}
67+
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
#!/usr/bin/perl
2+
use strict;
3+
4+
my$NUM = 20000;
5+
print"drop table boxtmp;\n";
6+
print"drop table boxtmp2;\n";
7+
8+
print"create table boxtmp (b box);\n";
9+
print"create table boxtmp2 (b box);\n";
10+
11+
srand(1);
12+
open(DAT,">bbb.dat") ||die;
13+
foreach ( 1..$NUM ) {
14+
#print DAT '(',int( 500+500*rand() ),',',int( 500+500*rand() ),',',int( 500*rand() ),',',int( 500*rand() ),")\n";
15+
my ($x1,$y1,$x2,$y2 ) = (
16+
10000*rand(),
17+
10000*rand(),
18+
10000*rand(),
19+
10000*rand()
20+
);
21+
print DAT'(',
22+
max($x1,$x2),',',
23+
max($y1,$y2),',',
24+
min($x1,$x2),',',
25+
min($y1,$y2),")\n";
26+
}
27+
close DAT;
28+
29+
print"copy boxtmp from stdin;\n";
30+
open(DAT,"bbb.dat") ||die;
31+
while(<DAT>) {print; }
32+
close DAT;
33+
print"\\.\n";
34+
35+
print"copy boxtmp2 from stdin;\n";
36+
open(DAT,"bbb.dat") ||die;
37+
while(<DAT>) {print; }
38+
close DAT;
39+
print"\\.\n";
40+
41+
print"create index bix on boxtmp using gist (b gist_box_ops);\n";
42+
print"create index bix2 on boxtmp2 using rtree (b box_ops);\n";
43+
44+
45+
submin {
46+
return ($_[0] <$_[1] ) ?$_[0] :$_[1];
47+
}
48+
submax {
49+
return ($_[0] >$_[1] ) ?$_[0] :$_[1];
50+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp