/ Check-in [71692aa9]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:More test cases with very long priority queues.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-enhancements
Files: files | file ages | folders
SHA1: 71692aa97c78676f0ba80eaeec0ad9ac225f4427
User & Date: drh 2014-04-17 15:34:58
Context
2014-04-17
23:23
Performance optimization on byte-swapping in R-Tree. check-in: 444084fd user: drh tags: rtree-enhancements
15:34
More test cases with very long priority queues. check-in: 71692aa9 user: drh tags: rtree-enhancements
14:52
Test cases and bug fixes for the sqlite3_rtree_query_callback() mechanism. check-in: 1ccaaed6 user: drh tags: rtree-enhancements
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtreeE.test.

    23     23   #-------------------------------------------------------------------------
    24     24   # Test the example 2d "circle" geometry callback.
    25     25   #
    26     26   register_circle_geom db
    27     27   
    28     28   do_execsql_test rtreeE-1.1 {
    29     29     PRAGMA page_size=512;
    30         -  CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1);
           30  +  CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1);
    31     31     
    32     32     /* A tight pattern of small boxes near 0,0 */
    33     33     WITH RECURSIVE
    34     34       x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    35     35       y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
    36         -  INSERT INTO rt2 SELECT x+5*y, x, x+2, y, y+2 FROM x, y;
           36  +  INSERT INTO rt1 SELECT x+5*y, x, x+2, y, y+2 FROM x, y;
    37     37   
    38     38     /* A looser pattern of small boxes near 100, 0 */
    39     39     WITH RECURSIVE
    40     40       x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    41     41       y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
    42         -  INSERT INTO rt2 SELECT 100+x+5*y, x*3+100, x*3+102, y*3, y*3+2 FROM x, y;
           42  +  INSERT INTO rt1 SELECT 100+x+5*y, x*3+100, x*3+102, y*3, y*3+2 FROM x, y;
    43     43   
    44     44     /* A looser pattern of larger boxes near 0, 200 */
    45     45     WITH RECURSIVE
    46     46       x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
    47     47       y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
    48         -  INSERT INTO rt2 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
           48  +  INSERT INTO rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
    49     49   } {}
    50     50   
    51         -if 0 {
    52     51   # Queries against each of the three clusters */
    53     52   do_execsql_test rtreeE-1.1 {
    54         -  SELECT id FROM rt2 WHERE id MATCH Qcircle(0.0, 0.0, 50.0) ORDER BY id;
           53  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id;
    55     54   } {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24}
    56     55   do_execsql_test rtreeE-1.2 {
    57         -  SELECT id FROM rt2 WHERE id MATCH Qcircle(100.0, 0.0, 50.0) ORDER BY id;
           56  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(100.0, 0.0, 50.0, 3) ORDER BY id;
    58     57   } {100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124}
    59     58   do_execsql_test rtreeE-1.3 {
    60         -  SELECT id FROM rt2 WHERE id MATCH Qcircle(0.0, 200.0, 50.0) ORDER BY id;
           59  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 200.0, 50.0, 3) ORDER BY id;
    61     60   } {200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224}
    62         -}
    63     61   
    64     62   # The Qcircle geometry function gives a lower score to larger leaf-nodes.
    65     63   # This causes the 200s to sort before the 100s and the 0s to sort before
    66     64   # last.
    67     65   #
    68     66   do_execsql_test rtreeE-1.4 {
    69         -  SELECT id FROM rt2 WHERE id MATCH Qcircle(0,0,1000) AND id%100==0
           67  +  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,3) AND id%100==0
    70     68   } {200 100 0}
           69  +
           70  +# Construct a large 2-D RTree with thousands of random entries.
           71  +#
           72  +do_test rtreeE-2.1 {
           73  +  db eval {
           74  +    CREATE TABLE t2(id,x0,x1,y0,y1);
           75  +    CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1);
           76  +    BEGIN;
           77  +  }
           78  +  expr srand(0)
           79  +  for {set i 1} {$i<=10000} {incr i} {
           80  +    set dx [expr {int(rand()*40)+1}]
           81  +    set dy [expr {int(rand()*40)+1}]
           82  +    set x0 [expr {int(rand()*(10000 - $dx))}]
           83  +    set x1 [expr {$x0+$dx}]
           84  +    set y0 [expr {int(rand()*(10000 - $dy))}]
           85  +    set y1 [expr {$y0+$dy}]
           86  +    set id [expr {$i+10000}]
           87  +    db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)}
           88  +  }
           89  +  db eval {
           90  +    INSERT INTO rt2 SELECT * FROM t2;
           91  +    COMMIT;
           92  +  }
           93  +} {}
           94  +
           95  +for {set i 1} {$i<=200} {incr i} {
           96  +  set dx [expr {int(rand()*100)}]
           97  +  set dy [expr {int(rand()*100)}]
           98  +  set x0 [expr {int(rand()*(10000 - $dx))}]
           99  +  set x1 [expr {$x0+$dx}]
          100  +  set y0 [expr {int(rand()*(10000 - $dy))}]
          101  +  set y1 [expr {$y0+$dy}]
          102  +  set ans [db eval {SELECT id FROM t2 WHERE x1>=$x0 AND x0<=$x1 AND y1>=$y0 AND y0<=$y1 ORDER BY id}]
          103  +  do_execsql_test rtreeE-2.2.$i {
          104  +    SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ORDER BY id
          105  +  } $ans
          106  +}
          107  +
          108  +# Run query that have very deep priority queues
          109  +#
          110  +set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=5000 AND y1>=0 AND y0<=5000 ORDER BY id}]
          111  +do_execsql_test rtreeE-2.3 {
          112  +  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,5000,0,5000) ORDER BY id
          113  +} $ans
          114  +set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=10000 AND y1>=0 AND y0<=10000 ORDER BY id}]
          115  +do_execsql_test rtreeE-2.4 {
          116  +  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,10000,0,10000) ORDER BY id
          117  +} $ans
    71    118   
    72    119   finish_test

Changes to src/test_rtree.c.

    32     32       double ymin;
    33     33       double ymax;
    34     34     } aBox[2];
    35     35     double centerx;
    36     36     double centery;
    37     37     double radius;
    38     38     double mxArea;
           39  +  int eScoreType;
    39     40   };
    40     41   
    41     42   /*
    42     43   ** Destructor function for Circle objects allocated by circle_geom().
    43     44   */
    44     45   static void circle_del(void *p){
    45     46     sqlite3_free(p);
................................................................................
   171    172       /* If pUser is still 0, then the parameter values have not been tested
   172    173       ** for correctness or stored into a Circle structure yet. Do this now. */
   173    174   
   174    175       /* This geometry callback is for use with a 2-dimensional r-tree table.
   175    176       ** Return an error if the table does not have exactly 2 dimensions. */
   176    177       if( p->nCoord!=4 ) return SQLITE_ERROR;
   177    178   
   178         -    /* Test that the correct number of parameters (3) have been supplied,
          179  +    /* Test that the correct number of parameters (4) have been supplied,
   179    180       ** and that the parameters are in range (that the radius of the circle 
   180    181       ** radius is greater than zero). */
   181         -    if( p->nParam!=3 || p->aParam[2]<0.0 ) return SQLITE_ERROR;
          182  +    if( p->nParam!=4 || p->aParam[2]<0.0 ) return SQLITE_ERROR;
   182    183   
   183    184       /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM
   184    185       ** if the allocation fails. */
   185    186       pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle)));
   186    187       if( !pCircle ) return SQLITE_NOMEM;
   187    188       p->xDelUser = circle_del;
   188    189   
................................................................................
   189    190       /* Record the center and radius of the circular region. One way that
   190    191       ** tested bounding boxes that intersect the circular region are detected
   191    192       ** is by testing if each corner of the bounding box lies within radius
   192    193       ** units of the center of the circle. */
   193    194       pCircle->centerx = p->aParam[0];
   194    195       pCircle->centery = p->aParam[1];
   195    196       pCircle->radius = p->aParam[2];
          197  +    pCircle->eScoreType = (int)p->aParam[3];
   196    198   
   197    199       /* Define two bounding box regions. The first, aBox[0], extends to
   198    200       ** infinity in the X dimension. It covers the same range of the Y dimension
   199    201       ** as the circular region. The second, aBox[1], extends to infinity in
   200    202       ** the Y dimension and is constrained to the range of the circle in the
   201    203       ** X dimension.
   202    204       **
................................................................................
   243    245         ){
   244    246           nWithin = 1;
   245    247           break;
   246    248         }
   247    249       }
   248    250     }
   249    251   
   250         -  if( p->iLevel==2 ){
   251         -    p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;
   252         -    if( p->rScore<0.01 ) p->rScore = 0.01;
          252  +  if( pCircle->eScoreType==1 ){
          253  +    /* Depth first search */
          254  +    p->rScore = p->iLevel;
          255  +  }else if( pCircle->eScoreType==2 ){
          256  +    /* Breadth first search */
          257  +    p->rScore = 100 - p->iLevel;
   253    258     }else{
   254         -    p->rScore = 0.0;
          259  +    /* Depth-first search, except sort the leaf nodes by area with
          260  +    ** the largest area first */
          261  +    if( p->iLevel==2 ){
          262  +      p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea;
          263  +      if( p->rScore<0.01 ) p->rScore = 0.01;
          264  +    }else{
          265  +      p->rScore = 0.0;
          266  +    }
   255    267     }
   256    268     if( nWithin==0 ){
   257    269       p->eWithin = NOT_WITHIN;
   258    270     }else if( nWithin>=4 ){
   259    271       p->eWithin = FULLY_WITHIN;
   260    272     }else{
   261    273       p->eWithin = PARTLY_WITHIN;
   262    274     }
   263    275     return SQLITE_OK;
   264    276   }
          277  +/*
          278  +** Implementation of "breadthfirstsearch" r-tree geometry callback using the 
          279  +** 2nd-generation interface that allows scoring.
          280  +**
          281  +**     ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ...
          282  +**
          283  +** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1.
          284  +*/
          285  +static int bfs_query_func(sqlite3_rtree_query_info *p){
          286  +  double x0,x1,y0,y1;        /* Dimensions of box being tested */
          287  +  double bx0,bx1,by0,by1;    /* Boundary of the query function */
          288  +
          289  +  if( p->nParam!=4 ) return SQLITE_ERROR;
          290  +  x0 = p->aCoord[0];
          291  +  x1 = p->aCoord[1];
          292  +  y0 = p->aCoord[2];
          293  +  y1 = p->aCoord[3];
          294  +  bx0 = p->aParam[0];
          295  +  bx1 = p->aParam[1];
          296  +  by0 = p->aParam[2];
          297  +  by1 = p->aParam[3];
          298  +  p->rScore = 100 - p->iLevel;
          299  +  if( p->eParentWithin==FULLY_WITHIN ){
          300  +    p->eWithin = FULLY_WITHIN;
          301  +  }else if( x0>=bx0 && x1<=bx1 && y0>=by0 && y1<=by1 ){
          302  +    p->eWithin = FULLY_WITHIN;
          303  +  }else if( x1>=bx0 && x0<=bx1 && y1>=by0 && y0<=by1 ){
          304  +    p->eWithin = PARTLY_WITHIN;
          305  +  }else{
          306  +    p->eWithin = NOT_WITHIN;
          307  +  }
          308  +  return SQLITE_OK;
          309  +}
   265    310   
   266    311   /* END of implementation of "circle" geometry callback.
   267    312   **************************************************************************
   268    313   *************************************************************************/
   269    314   
   270    315   #include <assert.h>
   271    316   #include "tcl.h"
................................................................................
   398    443     }
   399    444     if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
   400    445     rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0);
   401    446     if( rc==SQLITE_OK ){
   402    447       rc = sqlite3_rtree_query_callback(db, "Qcircle",
   403    448                                         circle_query_func, 0, 0);
   404    449     }
          450  +  if( rc==SQLITE_OK ){
          451  +    rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch",
          452  +                                      bfs_query_func, 0, 0);
          453  +  }
   405    454     Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC);
   406    455   #endif
   407    456     return TCL_OK;
   408    457   }
   409    458   
   410    459   int Sqlitetestrtree_Init(Tcl_Interp *interp){
   411    460     Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0);
   412    461     Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0);
   413    462     return TCL_OK;
   414    463   }