Subject: Rtree problems (Bug ?)

From: "Schenkelaars.V.F" <[email-masked]>
Date: Tue, 14 Apr 92 15:52:28 MET DST

Dear Postgres group,

I have a problem using the R-tree with my own defined 3D box type "BOX3".
Whenever I define an index on an attribute of this type the
backend crashes. I think it crashes at the moment the first split occurs. At
the end of this mail is all the relevant code. The
C function are all working fine, I have tested them with BOX3. Please
help me with this problem.

Makefile -----8<--------8<--------8<--------8<--------8<--------8<----

CC=cc
CFLAGS=-c -I/usr/postgres/src/lib/H

all: create geo-ext3.o

geo-ext3.o:       geo-ext3.c geo-ext3.h
		$(CC) $(CFLAGS) geo-ext3.c

create:         create.o
		$(CC) -o create create.o -lpq -lm

create.o:       create.c
		$(CC) $(CFLAGS) create.c
----8<--------8<--------8<--------8<--------8<--------8<--------8<----
/*
 * create.c 
 * 	Fill the "test" relation in the database "test3d".
 */
#include <stdio.h>
#include "tmp/libpq.h"
#define NAMELENGTH 256
#define max_val 2147483647L

void
main ()
{
    char query[NAMELENGTH];
    int i, n=500;
    float max=1000.0, maxlen=10.0, x1, y1, z1, x2, y2, z2;

    PQsetdb ("test3d");
    printf ("Current database:  %s\n", PQdb () );
    printf("BEGIN\n"); 
    PQexec("create test (region = BOX3)");
    PQexec("define index test_rtree on test using rtree (region Box3_ops)");
    for (i=0; i<n; i++) {
       x1 = ((max-maxlen)*(float)random())/((float)max_val);
       y1 = ((max-maxlen)*(float)random())/((float)max_val);
       z1 = ((max-maxlen)*(float)random())/((float)max_val);
       x2 = x1 + (maxlen*(float)random())/((float)max_val);
       y2 = y1 + (maxlen*(float)random())/((float)max_val);
       z2 = z1 + (maxlen*(float)random())/((float)max_val);
       sprintf (query,"append test(region=\"(%f,%f,%f,%f,%f,%f)\"::BOX3)",
          x1, y1,z1, x2, y2, z2);
       if (i%10 == 0 ) printf ("%d: QUERY: %s\n", i, query);
       PQexec (query); 
    }

    /* finish execution. */
    PQfinish ();
    printf("END\n");
}

/* geo-ext3.c
 * 3D Geometric extentions to Postgres developed by TNO, The Netherlands.
 * In analogy with the 2D geometric data types developed by the
 * Postgres Research group, Berkeley.
 */

#include <stdio.h>
#include "utils/log.h"
#include "utils/geo-decls.h"
#include "geo-ext3.h"

#define LDELIM          '('
#define RDELIM          ')'
#define DELIM           ','
#define BOX3NARGS        6

BOX3 *
Box3_in(str)
   char    *str;
{
   char    *coord[BOX3NARGS], *p;
   int     i;
   BOX3   *result;
   extern  double   atof();
   float   tmp;

   if (str == NULL) {
      elog(WARN, "Empty string BOX3");
      return(NULL);
   }
   for (i = 0, p = str; *p && i < BOX3NARGS && *p != RDELIM; p++)
      if (*p == DELIM || (*p == LDELIM && !i))
         coord[i++] = p + 1;
   if (i < BOX3NARGS - 1) {
      elog(WARN, "Ill formatted BOX3: %s", str);
      return(NULL);
   }
   result = PALLOCTYPE(BOX3);
   result->xh = (float) atof(coord[0]);
   result->yh = (float) atof(coord[1]);
   result->zh = (float) atof(coord[2]);
   result->xl = (float) atof(coord[3]);
   result->yl = (float) atof(coord[4]);
   result->zl = (float) atof(coord[5]);

   if (result->xh < result->xl) {
      tmp = result->xh; result->xh = result->xl; result->xl = tmp;
   }
   if (result->yh < result->yl) {
      tmp = result->yh; result->yh = result->yl; result->yl = tmp;
   }
   if (result->zh < result->zl) {
      tmp = result->zh; result->zh = result->zl; result->zl = tmp;
   }

   return(result);
}
 
char *
Box3_out(box)
   BOX3    *box;
{
   char     *result; 
 
   if (box == NULL) {
      elog(WARN, "NULL pointer for BOX3");
      return(NULL);
   }
   result = (char *) palloc(80);
   (void) sprintf(result, "(%g,%g,%g,%g,%g,%g)",
      box->xl, box->yl, box->zl, box->xh, box->yh, box->zh);
   return(result);
}

/* Box3 functions*/
/*===============*/

int
Size3Box(box)
   BOX3     *box;
{
   return ((int) 
           ((box->xh-box->xl)*(box->yh-box->yl)*(box->zh-box->zl)));
}

BOX3 *
Intersect3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   BOX3     *result;
   int      Overlap3BoxBox();

   if (! Overlap3BoxBox(box1,box2)) {
/*      elog(WARN, "No intersection BOX3 BOX3"); */
      return(NULL);
   }
   result = PALLOCTYPE(BOX3);
   result->xh = MIN(box1->xh, box2->xh);
   result->xl = MAX(box1->xl, box2->xl);
   result->yh = MIN(box1->yh, box2->yh);
   result->yl = MAX(box1->yl, box2->yl);
   result->zh = MIN(box1->zh, box2->zh);
   result->zl = MAX(box1->zl, box2->zl);

   return(result);
}

BOX3 *
Union3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   BOX3     *result;

   result = PALLOCTYPE(BOX3);
   result->xh = MAX(box1->xh, box2->xh);
   result->xl = MIN(box1->xl, box2->xl);
   result->yh = MAX(box1->yh, box2->yh);
   result->yl = MIN(box1->yl, box2->yl);
   result->zh = MAX(box1->zh, box2->zh);
   result->zl = MIN(box1->zl, box2->zl);

   return(result);
}

int 
Equal3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return(FPeq((double)box1->xh, (double)box2->xh) &&
          FPeq((double)box1->xl, (double)box2->xl) &&
          FPeq((double)box1->yh, (double)box2->yh) &&
          FPeq((double)box1->yl, (double)box2->yl) &&
          FPeq((double)box1->zh, (double)box2->zh) &&
          FPeq((double)box1->zl, (double)box2->zl));
}

int
Overlap3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return(((box1->xh >= box2->xh && box1->xl <= box2->xh) ||
                (box2->xh >= box1->xh && box2->xl <= box1->xh)) &&
               ((box1->yh >= box2->yh && box1->yl <= box2->yh) ||
                (box2->yh >= box1->yh && box2->yl <= box1->yh)) &&
               ((box1->zh >= box2->zh && box1->zl <= box2->zh) ||
                (box2->zh >= box1->zh && box2->zl <= box1->zh)) );
}

int
Overleft3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return(box1->xh <= box2->xh);
}

int
Left3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return(box1->xh < box2->xh);
}

int
Overright3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return(box1->xh >= box2->xh);
}

int
Right3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return(box1->xh > box2->xh);
}

int
Contain3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return((box1->xh >= box2->xh && box1->xl <= box2->xl &&
           box1->yh >= box2->yh && box1->yl <= box2->yl &&
           box1->zh >= box2->zh && box1->zl <= box2->zl));
}

int
Contained3BoxBox(box1, box2)
   BOX3     *box1, *box2;
{
   return((box1->xh <= box2->xh && box1->xl >= box2->xl &&
           box1->yh <= box2->yh && box1->yl >= box2->yl &&
           box1->zh <= box2->zh && box1->zl >= box2->zl));
}
----8<--------8<--------8<--------8<--------8<--------8<--------8<----
/* geo-ext3.h
 *
 * Include file for geo-ext3.c (3D geometric extensions to Postgres)
 * used in combination with the standard Postgres "utils/geo-decls.h"
 */

typedef struct
 {
   float  xh, yh, zh, xl, yl, zl;
 }
BOX3;

BOX3      *Box3_in();
char      *Box3_out();
loadgeo-ext3 -----8<--------8<--------8<--------8<--------8<--------8<----
#! /bin/sh

# Change for own path setting 
DB=${1:-test3d}
TESTHOME=${2:-/fusr/vfsj3/postgres}

monitor $DB << EOF

/*=============================================================*/
/* geo-ext3.pq                                                 */
/*                                                             */
/* Defining the 3D new types with the input and output         */
/* functions, geometric functions, and operators.              */
/*=============================================================*/

define function Box3_in ( language = "c", returntype = BOX3)
   arg is (char16)
   as "$TESTHOME/geo-ext3.o"
\g
define function Box3_out ( language = "c", returntype = char16)
   arg is (BOX3)
   as "$TESTHOME/geo-ext3.o"
\g
define type BOX3 (internallength = 24,
   input = Box3_in, output = Box3_out)
\g

/* BOX FUNCTIONS */
/*===============*/

define function Size3Box ( language = "c", returntype = int4)
   arg is (BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Intersect3BoxBox ( language = "c", returntype = BOX3)
   arg is (BOX3,BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Union3BoxBox ( language = "c", returntype = BOX3)
   arg is (BOX3,BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Equal3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Overlap3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Overleft3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Left3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Overright3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Right3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Contain3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

define function Contained3BoxBox ( language = "c", returntype = bool)
   arg is (BOX3, BOX3)
   as "$TESTHOME/geo-ext3.o"
\g

/* Geometric operators */
/*=====================*/

define operator <<  (arg1 = BOX3, arg2 = BOX3,
                     procedure = Left3BoxBox,
 	 	     negator = !<<,
                     restrict = intltsel, join = intltjoinsel) \g

define operator &<  (arg1 = BOX3, arg2 = BOX3,
                     procedure = Overleft3BoxBox,
 	 	     negator = !&<,
                     restrict = intltsel, join = intltjoinsel) \g

define operator &&  (arg1 = BOX3, arg2 = BOX3,
                     procedure = Overlap3BoxBox,
 	 	     commutator = &&, negator = !&&,
                     restrict = intltsel, join = intltjoinsel) \g

define operator &>  (arg1 = BOX3, arg2 = BOX3,
                     procedure = Overright3BoxBox ,
 	 	     commutator = &<, negator = !&>,
                     restrict = intltsel, join = intltjoinsel) \g

define operator >>  (arg1 = BOX3, arg2 = BOX3,
                     procedure = Right3BoxBox,
 	 	     commutator = <<, negator = !>>,
                     restrict = intltsel, join = intltjoinsel) \g

define operator ~=  (arg1 = BOX3, arg2 = BOX3,
                     procedure = Equal3BoxBox,
 	 	     commutator = ~=, negator = !~=,
                     restrict = intltsel, join = intltjoinsel) \g

define operator ~   (arg1 = BOX3, arg2 = BOX3,
                     procedure = Contain3BoxBox,
 	 	     negator = !~,
                     restrict = intltsel, join = intltjoinsel) \g

define operator @   (arg1 = BOX3, arg2 = BOX3,
                     procedure = Contained3BoxBox,
 	 	     commutator = ~, negator = !@,
                     restrict = intltsel, join = intltjoinsel) \g

append pg_opclass (opcname = "Box3_ops")\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "1"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
                where opr.oprname = "<<" and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "2"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
		where opr.oprname = "&<" and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "3"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
		where opr.oprname = "&&" and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "4"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
		where opr.oprname = "&>" and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "5"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
		where opr.oprname = ">>" and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "6"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
		where opr.oprname = "~="  and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "7"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
		where opr.oprname = "~" and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amop( amopid = "402"::oid,
		amopclaid = opc.oid,
		amopopr = opr.oid,
		amopstrategy = "8"::int2,
		amopselect = "rtsel"::regproc,
		amopnpages = "rtnpage"::regproc)
		from opc in pg_opclass,
		     opr in pg_operator,
                     opt in pg_type
		where opr.oprname = "@" and 
		      opt.typname = "BOX3" and
                      opt.oid = opr.oprright and
                      opt.oid = opr.oprleft and
		      opc.opcname = "Box3_ops"
		\g

append pg_amproc( amid = "402"::oid,
		amopclaid = opc.oid,
		amproc = proc.oid,
		amprocnum = "1"::int2)
		from opc in pg_opclass,
		     proc in pg_proc
                where proc.proname = "Union3BoxBox" and 
		      opc.opcname = "Box3_ops"
		\g

append pg_amproc( amid = "402"::oid,
		amopclaid = opc.oid,
		amproc = proc.oid,
		amprocnum = "2"::int2)
		from opc in pg_opclass,
		     proc in pg_proc
                where proc.proname = "Intersect3BoxBox" and 
		      opc.opcname = "Box3_ops"
		\g

append pg_amproc( amid = "402"::oid,
		amopclaid = opc.oid,
		amproc = proc.oid,
		amprocnum = "3"::int2)
		from opc in pg_opclass,
		     proc in pg_proc
                where proc.proname = "Size3Box" and 
		      opc.opcname = "Box3_ops"
		\g

vacuum \g

EOF
setup -------8<--------8<--------8<--------8<--------8<--------8<----
#! /bin/sh

destroydb test3d
createdb test3d	
loadgeo-ext3 test3d /fusr/vfsj3/postgres

create

---

From: postarch (Postgres Mailing Archive)
Date: Tue, 26 May 92 21:09:54 PDT

first, a warning to people using the dynamic loader:  you should use
names of fifteen characters or less for the routines that you dynamically
load.  the reason for this is that the released code assumes in several
places that routine names are null-terminated, and this isn't true for
sixteen-character names.  vincent, in particular, you need to change all
occurrences of

    Overright3BoxBox
    Intersect3BoxBox
    Contained3BoxBox

to something shorter.

now, to deal with another bug, specific to the rtree extensions vincent
is doing:

> backend crashes. I think it crashes at the moment the first split occurs.

you're correct, the bug is in the node split code.  your geo-ext3.c
file contains the routine

    int
    Size3Box(box)
       BOX3     *box;
    {
       return ((int) 

you should change this to

    int
    Size3Box(box)
       BOX3     *box;
    {
       if (box == (BOX3 *) NULL)
	   return(0);
       else
	   return((int) 
		  ((box->xh-box->xl)*(box->yh-box->yl)*(box->zh-box->zl)));
    }

what happens is that your intersection routine returns NULL if two boxes
don't intersect.  the quadratic-cost split algorithm from guttman's paper,
as i implemented it for postgres, computes the sizes of the union and
intersection of the n-dimensional boxes in order to choose an optimal
node split.  Size3Box() got passed the null pointer from the intersect
routine.

i'll fix the split code to check for this condition before calling
the intersect procedure.  for the time being, the change described above
will solve your problem.  i successfully ran your test program on my
system this afternoon, with these modifications.

incidentally, i'm pleased to see you folks are extending the access method
classes like this.  your code was clean, and you uncovered a genuine bug.
let me know if you have further problems -- response times should get
shorter, now that summer is here.
					mike olson
					project sequoia 2000
					uc berkeley
					[email-masked]