/ Changes On Branch rtree-queue
Login

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

Changes In Branch rtree-queue Excluding Merge-Ins

This is equivalent to a diff from ade5b986e8 to f864baccd3

2014-04-16
17:23
Convert the RTree module query mechanism over to using a priority queue for walking the RTree. (check-in: f26936f71a user: drh tags: rtree-enhancements)
17:15
TCL tests now all pass. (Closed-Leaf check-in: f864baccd3 user: drh tags: rtree-queue)
14:45
Fix a bug in rowid=? query handling. More problems remain. (check-in: 5b0e6ba4a5 user: drh tags: rtree-queue)
2014-04-15
21:06
Initial attempt at getting R-Tree queries to work using a priority queue. This check-in compiles, but R-Trees do not work well. And there are debugging printf()s left in the code. This is an incremental check-in. (check-in: 53688a25c2 user: drh tags: rtree-queue)
2014-04-14
14:43
Fix comments on the rtreenode() and rtreedepth() test function in the R-Tree module. (check-in: ade5b986e8 user: drh tags: rtree-enhancements)
12:18
Remove over 300 lines of unused code, code that implemented the older Guttman insertion algorithms that are no longer used. (check-in: 3ba5f295c7 user: drh tags: rtree-enhancements)

Changes to ext/rtree/rtree.c.

    59     59     SQLITE_EXTENSION_INIT1
    60     60   #else
    61     61     #include "sqlite3.h"
    62     62   #endif
    63     63   
    64     64   #include <string.h>
    65     65   #include <assert.h>
           66  +#include <stdio.h>
    66     67   
    67     68   #ifndef SQLITE_AMALGAMATION
    68     69   #include "sqlite3rtree.h"
    69     70   typedef sqlite3_int64 i64;
    70     71   typedef unsigned char u8;
    71     72   typedef unsigned short u16;
    72     73   typedef unsigned int u32;
................................................................................
    82     83   typedef struct RtreeCursor RtreeCursor;
    83     84   typedef struct RtreeNode RtreeNode;
    84     85   typedef struct RtreeCell RtreeCell;
    85     86   typedef struct RtreeConstraint RtreeConstraint;
    86     87   typedef struct RtreeMatchArg RtreeMatchArg;
    87     88   typedef struct RtreeGeomCallback RtreeGeomCallback;
    88     89   typedef union RtreeCoord RtreeCoord;
           90  +typedef struct RtreeSearchPoint RtreeSearchPoint;
    89     91   
    90     92   /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
    91     93   #define RTREE_MAX_DIMENSIONS 5
    92     94   
    93     95   /* Size of hash table Rtree.aHash. This hash table is not expected to
    94     96   ** ever contain very many entries, so a fixed number of buckets is 
    95     97   ** used.
................................................................................
   161    163     typedef sqlite3_int64 RtreeDValue;       /* High accuracy coordinate */
   162    164     typedef int RtreeValue;                  /* Low accuracy coordinate */
   163    165   #else
   164    166     typedef double RtreeDValue;              /* High accuracy coordinate */
   165    167     typedef float RtreeValue;                /* Low accuracy coordinate */
   166    168   #endif
   167    169   
          170  +/*
          171  +** When doing a search of an r-tree, instances of the following structure
          172  +** record intermediate results from the tree walk.
          173  +**
          174  +** The id is always a node-id.  For iLevel>=1 the id is the node-id of
          175  +** the node that the RtreeSearchPoint represents.  When iLevel==0, however,
          176  +** the id is of the parent node and the cell that RtreeSearchPoint
          177  +** represents is the iCell-th entry in the parent node.
          178  +*/
          179  +struct RtreeSearchPoint {
          180  +  RtreeDValue rScore;    /* The score for this node.  Smallest goes first. */
          181  +  sqlite3_int64 id;      /* Node ID */
          182  +  u8 iLevel;             /* 0=entries.  1=leaf node.  2+ for higher */
          183  +  u8 eWithin;            /* PARTLY_WITHIN or FULLY_WITHIN */
          184  +  u8 iCell;              /* Cell index within the node */
          185  +};
          186  +
   168    187   /*
   169    188   ** The minimum number of cells allowed for a node is a third of the 
   170    189   ** maximum. In Gutman's notation:
   171    190   **
   172    191   **     m = M/3
   173    192   **
   174    193   ** If an R*-tree "Reinsert" operation is required, the same number of
................................................................................
   183    202   ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates).
   184    203   ** Therefore all non-root nodes must contain at least 3 entries. Since 
   185    204   ** 2^40 is greater than 2^64, an r-tree structure always has a depth of
   186    205   ** 40 or less.
   187    206   */
   188    207   #define RTREE_MAX_DEPTH 40
   189    208   
          209  +
          210  +/*
          211  +** Number of entries in the cursor RtreeNode cache.  The first entry is
          212  +** used to cache the RtreeNode for RtreeCursor.sPoint.  The remaining
          213  +** entries cache the RtreeNode for the first elements of the priority queue.
          214  +*/
          215  +#define RTREE_CACHE_SZ  5
          216  +
   190    217   /* 
   191    218   ** An rtree cursor object.
   192    219   */
   193    220   struct RtreeCursor {
   194    221     sqlite3_vtab_cursor base;         /* Base class.  Must be first */
   195         -  RtreeNode *pNode;                 /* Node cursor is currently pointing at */
   196         -  int iCell;                        /* Index of current cell in pNode */
          222  +  u8 atEOF;                         /* True if at end of search */
          223  +  u8 bPoint;                        /* True if sPoint is valid */
   197    224     int iStrategy;                    /* Copy of idxNum search parameter */
   198    225     int nConstraint;                  /* Number of entries in aConstraint */
   199    226     RtreeConstraint *aConstraint;     /* Search constraints. */
          227  +  int nPointAlloc;                  /* Number of slots allocated for aPoint[] */
          228  +  int nPoint;                       /* Number of slots used in aPoint[] */
          229  +  RtreeSearchPoint *aPoint;         /* Priority queue for search points */
          230  +  RtreeSearchPoint sPoint;          /* Cached next search point */
          231  +  RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
   200    232   };
   201    233   
          234  +/* Return the Rtree of a RtreeCursor */
          235  +#define RTREE_OF_CURSOR(X)   ((Rtree*)((X)->base.pVtab))
          236  +
   202    237   /*
   203    238   ** A coordinate can be either a floating point number or a integer.  All
   204    239   ** coordinates within a single R-Tree are always of the same time.
   205    240   */
   206    241   union RtreeCoord {
   207    242     RtreeValue f;      /* Floating point value */
   208    243     int i;             /* Integer value */
................................................................................
   242    277   #define RTREE_EQ    0x41
   243    278   #define RTREE_LE    0x42
   244    279   #define RTREE_LT    0x43
   245    280   #define RTREE_GE    0x44
   246    281   #define RTREE_GT    0x45
   247    282   #define RTREE_MATCH 0x46  /* Old-style sqlite3_rtree_geometry_callback() */
   248    283   #define RTREE_QUERY 0x47  /* New-style sqlite3_rtree_query_callback() */
          284  +
   249    285   
   250    286   /* 
   251    287   ** An rtree structure node.
   252    288   */
   253    289   struct RtreeNode {
   254    290     RtreeNode *pParent;         /* Parent node */
   255    291     i64 iNode;                  /* The node number */
................................................................................
   834    870   }
   835    871   
   836    872   /* 
   837    873   ** Rtree virtual table module xClose method.
   838    874   */
   839    875   static int rtreeClose(sqlite3_vtab_cursor *cur){
   840    876     Rtree *pRtree = (Rtree *)(cur->pVtab);
   841         -  int rc;
          877  +  int ii;
   842    878     RtreeCursor *pCsr = (RtreeCursor *)cur;
   843    879     freeCursorConstraints(pCsr);
   844         -  rc = nodeRelease(pRtree, pCsr->pNode);
          880  +  sqlite3_free(pCsr->aPoint);
          881  +  for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
   845    882     sqlite3_free(pCsr);
   846         -  return rc;
          883  +  return SQLITE_OK;
   847    884   }
   848    885   
   849    886   /*
   850    887   ** Rtree virtual table module xEof method.
   851    888   **
   852    889   ** Return non-zero if the cursor does not currently point to a valid 
   853    890   ** record (i.e if the scan has finished), or zero otherwise.
   854    891   */
   855    892   static int rtreeEof(sqlite3_vtab_cursor *cur){
   856    893     RtreeCursor *pCsr = (RtreeCursor *)cur;
   857         -  return (pCsr->pNode==0);
          894  +  return pCsr->atEOF;
   858    895   }
   859    896   
   860    897   /*
   861    898   ** The r-tree constraint passed as the second argument to this function is
   862    899   ** guaranteed to be a MATCH constraint.
   863    900   */
   864         -static int testRtreeGeom(
          901  +static int rtreeTestGeom(
   865    902     Rtree *pRtree,                  /* R-Tree object */
   866    903     RtreeConstraint *pConstraint,   /* MATCH constraint to test */
   867    904     RtreeCell *pCell,               /* Cell to test */
   868    905     int *pbRes                      /* OUT: Test result */
   869    906   ){
   870    907     int i;
   871    908     RtreeDValue aCoord[RTREE_MAX_DIMENSIONS*2];
................................................................................
   879    916     }
   880    917     return pConstraint->u.xGeom((sqlite3_rtree_geometry*)pConstraint->pGeom,
   881    918                                 nCoord, aCoord, pbRes);
   882    919   }
   883    920   
   884    921   /* 
   885    922   ** Cursor pCursor currently points to a cell in a non-leaf page.
   886         -** Set *pbEof to true if the sub-tree headed by the cell is filtered
   887         -** (excluded) by the constraints in the pCursor->aConstraint[] 
   888         -** array, or false otherwise.
          923  +** Set *peWithin to NOT_WITHIN if the constraints in pCursor->aConstraint[]
          924  +** are guaranteed to never be satisfied by any subelement under the
          925  +** current cell.  If some subelement of the cell might satisfy all
          926  +** constraints, then set *peWithin to PARTLY_WITHIN.  If all subelements
          927  +** of the cell are guaranteed to fully satisfy all constraints, then
          928  +** set *peWithin to FULLY_WITHIN.
          929  +**
          930  +** In other words, set *peWithin to NOT_WITHIN, PARTLY_WITHIN, or
          931  +** FULLY_WITHIN if the cell is completely outside of the field-of-view,
          932  +** overlaps the field of view, or is completely contained within the
          933  +** field of view, respectively.
          934  +**
          935  +** It is not an error to set *peWithin to PARTLY_WITHIN when FULLY_WITHIN
          936  +** would be correct.  Doing so is suboptimal, but will still give the
          937  +** correct answer.  
   889    938   **
   890    939   ** Return SQLITE_OK if successful or an SQLite error code if an error
   891         -** occurs within a geometry callback.
          940  +** occurs.  Errors can only possible if there is a geometry callback.
   892    941   */
   893         -static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   894         -  RtreeCell cell;
          942  +static int rtreeTestCell(
          943  +  RtreeCursor *pCursor,      /* The cursor to check */
          944  +  RtreeCell *pCell,          /* The cell to check */
          945  +  int *peWithin              /* Set true if element is out-of-bounds */
          946  +){
   895    947     int ii;
   896         -  int bRes = 0;
          948  +  int bOutOfBounds = 0;
   897    949     int rc = SQLITE_OK;
          950  +  Rtree *pRtree = RTREE_OF_CURSOR(pCursor);
   898    951   
   899         -  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   900         -  for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
          952  +  for(ii=0; bOutOfBounds==0 && ii<pCursor->nConstraint; ii++){
   901    953       RtreeConstraint *p = &pCursor->aConstraint[ii];
   902         -    RtreeDValue cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
   903         -    RtreeDValue cell_max = DCOORD(cell.aCoord[(p->iCoord>>1)*2+1]);
          954  +    RtreeDValue cell_min = DCOORD(pCell->aCoord[(p->iCoord>>1)*2]);
          955  +    RtreeDValue cell_max = DCOORD(pCell->aCoord[(p->iCoord>>1)*2+1]);
   904    956   
   905    957       assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   906    958           || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   907    959       );
   908    960   
   909    961       switch( p->op ){
   910    962         case RTREE_LE: case RTREE_LT: 
   911         -        bRes = p->u.rValue<cell_min; 
          963  +        bOutOfBounds = p->u.rValue<cell_min; 
   912    964           break;
   913    965   
   914    966         case RTREE_GE: case RTREE_GT: 
   915         -        bRes = p->u.rValue>cell_max; 
          967  +        bOutOfBounds = p->u.rValue>cell_max; 
   916    968           break;
   917    969   
   918    970         case RTREE_EQ:
   919         -        bRes = (p->u.rValue>cell_max || p->u.rValue<cell_min);
          971  +        bOutOfBounds = (p->u.rValue>cell_max || p->u.rValue<cell_min);
   920    972           break;
   921    973   
   922    974         default: {
   923    975           assert( p->op==RTREE_MATCH );
   924         -        rc = testRtreeGeom(pRtree, p, &cell, &bRes);
   925         -        bRes = !bRes;
          976  +        rc = rtreeTestGeom(pRtree, p, pCell, &bOutOfBounds);
          977  +        bOutOfBounds = !bOutOfBounds;
   926    978           break;
   927    979         }
   928    980       }
   929    981     }
   930    982   
   931         -  *pbEof = bRes;
          983  +  *peWithin = bOutOfBounds ? NOT_WITHIN : PARTLY_WITHIN;
   932    984     return rc;
   933    985   }
   934    986   
   935    987   /* 
   936         -** Test if the cell that cursor pCursor currently points to
   937         -** would be filtered (excluded) by the constraints in the 
   938         -** pCursor->aConstraint[] array. If so, set *pbEof to true before
   939         -** returning. If the cell is not filtered (excluded) by the constraints,
   940         -** set pbEof to zero.
          988  +** pCursor points to a leaf r-tree entry which is a candidate for output.
          989  +** This routine sets *peWithin to one of NOT_WITHIN, PARTLY_WITHIN, or
          990  +** FULLY_WITHIN depending on whether or not the leaf entry is completely
          991  +** outside the region defined by pCursor->aConstraints[], or overlaps the
          992  +** region, or is completely within the region, respectively.
          993  +**
          994  +** This routine is more selective than rtreeTestCell().  rtreeTestCell()
          995  +** will return PARTLY_WITHIN or FULLY_WITHIN if the constraints are such
          996  +** that a subelement of the cell to be included in the result set.  This
          997  +** routine is is only called for leaf r-tree entries and does not need
          998  +** to concern itself with subelements.  Hence it only sets *peWithin to
          999  +** PARTLY_WITHIN or FULLY_WITHIN if the cell itself meets the requirements.
   941   1000   **
   942   1001   ** Return SQLITE_OK if successful or an SQLite error code if an error
   943   1002   ** occurs within a geometry callback.
   944   1003   **
   945   1004   ** This function assumes that the cell is part of a leaf node.
   946   1005   */
   947         -static int testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
   948         -  RtreeCell cell;
         1006  +static int rtreeTestEntry(
         1007  +  RtreeCursor *pCursor,   /* Cursor pointing to the leaf element */
         1008  +  RtreeCell *pCell,       /* The cell to check */
         1009  +  int *peWithin           /* OUT: NOT_WITHIN, PARTLY_WITHIN, or FULLY_WITHIN */
         1010  +){
         1011  +  Rtree *pRtree = RTREE_OF_CURSOR(pCursor);
   949   1012     int ii;
   950         -  *pbEof = 0;
         1013  +  int res = 1;     /* Innocent until proven guilty */
   951   1014   
   952         -  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
   953         -  for(ii=0; ii<pCursor->nConstraint; ii++){
         1015  +  for(ii=0; res && ii<pCursor->nConstraint; ii++){
   954   1016       RtreeConstraint *p = &pCursor->aConstraint[ii];
   955         -    RtreeDValue coord = DCOORD(cell.aCoord[p->iCoord]);
   956         -    int res;
         1017  +    RtreeDValue coord = DCOORD(pCell->aCoord[p->iCoord]);
   957   1018       assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
   958   1019           || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
   959   1020       );
   960   1021       switch( p->op ){
   961   1022         case RTREE_LE: res = (coord<=p->u.rValue); break;
   962   1023         case RTREE_LT: res = (coord<p->u.rValue);  break;
   963   1024         case RTREE_GE: res = (coord>=p->u.rValue); break;
   964   1025         case RTREE_GT: res = (coord>p->u.rValue);  break;
   965   1026         case RTREE_EQ: res = (coord==p->u.rValue); break;
   966   1027         default: {
   967   1028           int rc;
   968   1029           assert( p->op==RTREE_MATCH );
   969         -        rc = testRtreeGeom(pRtree, p, &cell, &res);
         1030  +        rc = rtreeTestGeom(pRtree, p, pCell, &res);
   970   1031           if( rc!=SQLITE_OK ){
   971   1032             return rc;
   972   1033           }
   973   1034           break;
   974   1035         }
   975   1036       }
   976         -
   977         -    if( !res ){
   978         -      *pbEof = 1;
   979         -      return SQLITE_OK;
   980         -    }
   981   1037     }
   982   1038   
         1039  +  *peWithin = res ? FULLY_WITHIN : NOT_WITHIN;
   983   1040     return SQLITE_OK;
   984   1041   }
   985   1042   
   986         -/*
   987         -** Cursor pCursor currently points at a node that heads a sub-tree of
   988         -** height iHeight (if iHeight==0, then the node is a leaf). Descend
   989         -** to point to the left-most cell of the sub-tree that matches the 
   990         -** configured constraints.
   991         -*/
   992         -static int descendToCell(
   993         -  Rtree *pRtree, 
   994         -  RtreeCursor *pCursor, 
   995         -  int iHeight,
   996         -  int *pEof                 /* OUT: Set to true if cannot descend */
   997         -){
   998         -  int isEof;
   999         -  int rc;
  1000         -  int ii;
  1001         -  RtreeNode *pChild;
  1002         -  sqlite3_int64 iRowid;
  1003         -
  1004         -  RtreeNode *pSavedNode = pCursor->pNode;
  1005         -  int iSavedCell = pCursor->iCell;
  1006         -
  1007         -  assert( iHeight>=0 );
  1008         -
  1009         -  if( iHeight==0 ){
  1010         -    rc = testRtreeEntry(pRtree, pCursor, &isEof);
  1011         -  }else{
  1012         -    rc = testRtreeCell(pRtree, pCursor, &isEof);
  1013         -  }
  1014         -  if( rc!=SQLITE_OK || isEof || iHeight==0 ){
  1015         -    goto descend_to_cell_out;
  1016         -  }
  1017         -
  1018         -  iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
  1019         -  rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
  1020         -  if( rc!=SQLITE_OK ){
  1021         -    goto descend_to_cell_out;
  1022         -  }
  1023         -
  1024         -  nodeRelease(pRtree, pCursor->pNode);
  1025         -  pCursor->pNode = pChild;
  1026         -  isEof = 1;
  1027         -  for(ii=0; isEof && ii<NCELL(pChild); ii++){
  1028         -    pCursor->iCell = ii;
  1029         -    rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
  1030         -    if( rc!=SQLITE_OK ){
  1031         -      goto descend_to_cell_out;
  1032         -    }
  1033         -  }
  1034         -
  1035         -  if( isEof ){
  1036         -    assert( pCursor->pNode==pChild );
  1037         -    nodeReference(pSavedNode);
  1038         -    nodeRelease(pRtree, pChild);
  1039         -    pCursor->pNode = pSavedNode;
  1040         -    pCursor->iCell = iSavedCell;
  1041         -  }
  1042         -
  1043         -descend_to_cell_out:
  1044         -  *pEof = isEof;
  1045         -  return rc;
  1046         -}
  1047         -
  1048   1043   /*
  1049   1044   ** One of the cells in node pNode is guaranteed to have a 64-bit 
  1050   1045   ** integer value equal to iRowid. Return the index of this cell.
  1051   1046   */
  1052   1047   static int nodeRowidIndex(
  1053   1048     Rtree *pRtree, 
  1054   1049     RtreeNode *pNode, 
  1055   1050     i64 iRowid,
  1056   1051     int *piIndex
  1057   1052   ){
  1058   1053     int ii;
  1059   1054     int nCell = NCELL(pNode);
         1055  +  assert( nCell<200 );
  1060   1056     for(ii=0; ii<nCell; ii++){
  1061   1057       if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
  1062   1058         *piIndex = ii;
  1063   1059         return SQLITE_OK;
  1064   1060       }
  1065   1061     }
  1066   1062     return SQLITE_CORRUPT_VTAB;
................................................................................
  1074   1070     RtreeNode *pParent = pNode->pParent;
  1075   1071     if( pParent ){
  1076   1072       return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex);
  1077   1073     }
  1078   1074     *piIndex = -1;
  1079   1075     return SQLITE_OK;
  1080   1076   }
         1077  +
         1078  +/*
         1079  +** Compare two search points.  Return negative, zero, or positive if the first
         1080  +** is less than, equal to, or greater than the second.
         1081  +*/
         1082  +static int rtreeSearchPointCompare(
         1083  +  const RtreeSearchPoint *pA,
         1084  +  const RtreeSearchPoint *pB
         1085  +){
         1086  +  if( pA->rScore<pB->rScore ) return -1;
         1087  +  if( pA->rScore>pB->rScore ) return +1;
         1088  +  if( pA->iLevel<pB->iLevel ) return -1;
         1089  +  if( pA->iLevel>pB->iLevel ) return +1;
         1090  +  return 0;
         1091  +}
         1092  +
         1093  +/*
         1094  +** Interchange to search points in a cursor.
         1095  +*/
         1096  +static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
         1097  +  RtreeSearchPoint t = p->aPoint[i];
         1098  +  assert( i<j );
         1099  +  p->aPoint[i] = p->aPoint[j];
         1100  +  p->aPoint[j] = t;
         1101  +  i++; j++;
         1102  +  if( i<RTREE_CACHE_SZ ){
         1103  +    if( j>=RTREE_CACHE_SZ ){
         1104  +      nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
         1105  +      p->aNode[i] = 0;
         1106  +    }else{
         1107  +      RtreeNode *pTemp = p->aNode[i];
         1108  +      p->aNode[i] = p->aNode[j];
         1109  +      p->aNode[j] = pTemp;
         1110  +    }
         1111  +  }
         1112  +}
         1113  +
         1114  +/*
         1115  +** Return the search point with the lowest current score.
         1116  +*/
         1117  +static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
         1118  +  return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
         1119  +}
         1120  +
         1121  +/*
         1122  +** Get the RtreeNode for the search point with the lowest score.
         1123  +*/
         1124  +static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){
         1125  +  sqlite3_int64 id;
         1126  +  int ii = 1 - pCur->bPoint;
         1127  +  assert( ii==0 || ii==1 );
         1128  +  assert( pCur->bPoint || pCur->nPoint );
         1129  +  if( pCur->aNode[ii]==0 ){
         1130  +    assert( pRC!=0 );
         1131  +    id = ii ? pCur->aPoint[0].id : pCur->sPoint.id;
         1132  +    *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]);
         1133  +  }
         1134  +  return pCur->aNode[ii];
         1135  +}
         1136  +
         1137  +/*
         1138  +** Push a new element onto the priority queue
         1139  +*/
         1140  +static RtreeSearchPoint *rtreeEnqueue(
         1141  +  RtreeCursor *pCur,    /* The cursor */
         1142  +  RtreeDValue rScore,   /* Score for the new search point */
         1143  +  u8 iLevel             /* Level for the new search point */
         1144  +){
         1145  +  int i, j;
         1146  +  RtreeSearchPoint *pNew;
         1147  +  if( pCur->nPoint>=pCur->nPointAlloc ){
         1148  +    int nNew = pCur->nPointAlloc*2 + 8;
         1149  +    pNew = sqlite3_realloc(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
         1150  +    if( pNew==0 ) return 0;
         1151  +    pCur->aPoint = pNew;
         1152  +    pCur->nPointAlloc = nNew;
         1153  +  }
         1154  +  i = pCur->nPoint++;
         1155  +  pNew = pCur->aPoint + i;
         1156  +  pNew->rScore = rScore;
         1157  +  pNew->iLevel = iLevel;  
         1158  +  while( i>0 ){
         1159  +    RtreeSearchPoint *pParent;
         1160  +    j = (i-1)/2;
         1161  +    pParent = pCur->aPoint + j;
         1162  +    if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
         1163  +    rtreeSearchPointSwap(pCur, j, i);
         1164  +    i = j;
         1165  +    pNew = pParent;
         1166  +  }
         1167  +  return pNew;
         1168  +}
         1169  +
         1170  +/*
         1171  +** Allocate a new RtreeSearchPoint and return a pointer to it.  Return
         1172  +** NULL if malloc fails.
         1173  +*/
         1174  +static RtreeSearchPoint *rtreeSearchPointNew(
         1175  +  RtreeCursor *pCur,    /* The cursor */
         1176  +  RtreeDValue rScore,   /* Score for the new search point */
         1177  +  u8 iLevel             /* Level for the new search point */
         1178  +){
         1179  +  RtreeSearchPoint *pNew, *pFirst;
         1180  +  pFirst = rtreeSearchPointFirst(pCur);
         1181  +  if( pFirst==0
         1182  +   || pFirst->rScore>rScore 
         1183  +   || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
         1184  +  ){
         1185  +    if( pCur->bPoint ){
         1186  +      int ii;
         1187  +      pNew = rtreeEnqueue(pCur, rScore, iLevel);
         1188  +      if( pNew==0 ) return 0;
         1189  +      ii = (int)(pNew - pCur->aPoint) + 1;
         1190  +      if( ii<RTREE_CACHE_SZ ){
         1191  +        assert( pCur->aNode[ii]==0 );
         1192  +        pCur->aNode[ii] = pCur->aNode[0];
         1193  +       }else{
         1194  +        nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]);
         1195  +      }
         1196  +      pCur->aNode[0] = 0;
         1197  +      *pNew = pCur->sPoint;
         1198  +    }
         1199  +    pCur->sPoint.rScore = rScore;
         1200  +    pCur->sPoint.iLevel = iLevel;
         1201  +    pCur->bPoint = 1;
         1202  +    return &pCur->sPoint;
         1203  +  }else{
         1204  +    return rtreeEnqueue(pCur, rScore, iLevel);
         1205  +  }
         1206  +}
         1207  +
         1208  +#if 0
         1209  +/* Tracing routines for the RtreeSearchPoint queue */
         1210  +static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){
         1211  +  if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); }
         1212  +  printf(" %d.%05lld.%02d %g %d",
         1213  +    p->iLevel, p->id, p->iCell, p->rScore, p->eWithin
         1214  +  );
         1215  +  idx++;
         1216  +  if( idx<RTREE_CACHE_SZ ){
         1217  +    printf(" %p\n", pCur->aNode[idx]);
         1218  +  }else{
         1219  +    printf("\n");
         1220  +  }
         1221  +}
         1222  +static void traceQueue(RtreeCursor *pCur, const char *zPrefix){
         1223  +  int ii;
         1224  +  printf("=== %9s ", zPrefix);
         1225  +  if( pCur->bPoint ){
         1226  +    tracePoint(&pCur->sPoint, -1, pCur);
         1227  +  }
         1228  +  for(ii=0; ii<pCur->nPoint; ii++){
         1229  +    if( ii>0 || pCur->bPoint ) printf("              ");
         1230  +    tracePoint(&pCur->aPoint[ii], ii, pCur);
         1231  +  }
         1232  +}
         1233  +# define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
         1234  +#else
         1235  +# define RTREE_QUEUE_TRACE(A,B)   /* no-op */
         1236  +#endif
         1237  +
         1238  +/* Remove the search point with the lowest current score.
         1239  +*/
         1240  +static void rtreeSearchPointPop(RtreeCursor *p){
         1241  +  int i, j, k, n;
         1242  +  i = 1 - p->bPoint;
         1243  +  assert( i==0 || i==1 );
         1244  +  if( p->aNode[i] ){
         1245  +    nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
         1246  +    p->aNode[i] = 0;
         1247  +  }
         1248  +  if( p->bPoint ){
         1249  +    p->bPoint = 0;
         1250  +  }else if( p->nPoint ){
         1251  +    n = --p->nPoint;
         1252  +    p->aPoint[0] = p->aPoint[n];
         1253  +    if( n<RTREE_CACHE_SZ-1 ){
         1254  +      p->aNode[1] = p->aNode[n+1];
         1255  +      p->aNode[n+1] = 0;
         1256  +    }
         1257  +    i = 0;
         1258  +    while( (j = i*2+1)<n ){
         1259  +      k = j+1;
         1260  +      if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
         1261  +        if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
         1262  +          rtreeSearchPointSwap(p, i, k);
         1263  +          i = k;
         1264  +        }else{
         1265  +          break;
         1266  +        }
         1267  +      }else{
         1268  +        if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){
         1269  +          rtreeSearchPointSwap(p, i, j);
         1270  +          i = j;
         1271  +        }else{
         1272  +          break;
         1273  +        }
         1274  +      }
         1275  +    }
         1276  +  }
         1277  +}
         1278  +
         1279  +
         1280  +/*
         1281  +** Continue the search on cursor pCur until the front of the queue
         1282  +** contains an entry suitable for returning as a result-set row,
         1283  +** or until the RtreeSearchPoint queue is empty, indicating that the
         1284  +** query has completed.
         1285  +*/
         1286  +static int rtreeStepToLeaf(RtreeCursor *pCur){
         1287  +  RtreeSearchPoint *p;
         1288  +  Rtree *pRtree = RTREE_OF_CURSOR(pCur);
         1289  +  RtreeNode *pNode;
         1290  +  int eWithin;
         1291  +  int rc = SQLITE_OK;
         1292  +  int nCell;
         1293  +  RtreeCell cell;
         1294  +  RtreeSearchPoint x;
         1295  +
         1296  +  while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
         1297  +    pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
         1298  +    if( rc ) return rc;
         1299  +    nCell = NCELL(pNode);
         1300  +    assert( nCell<200 );
         1301  +    while( p->iCell<nCell ){
         1302  +      nodeGetCell(pRtree, pNode, p->iCell, &cell);
         1303  +      if( p->iLevel==1 ){
         1304  +        rc = rtreeTestEntry(pCur, &cell, &eWithin);
         1305  +      }else{
         1306  +        rc = rtreeTestCell(pCur, &cell, &eWithin);
         1307  +      }
         1308  +      if( rc ) return rc;
         1309  +      x = *p;
         1310  +      p->iCell++;
         1311  +      if( eWithin==NOT_WITHIN ) continue;
         1312  +      if( p->iCell>=nCell ){
         1313  +        RTREE_QUEUE_TRACE(pCur, "POP-S:");
         1314  +        rtreeSearchPointPop(pCur);
         1315  +      }
         1316  +      p = rtreeSearchPointNew(pCur, /*rScore*/0.0, x.iLevel-1);
         1317  +      if( p==0 ) return SQLITE_NOMEM;
         1318  +      p->eWithin = eWithin;
         1319  +      if( p->iLevel ){
         1320  +        p->id = cell.iRowid;
         1321  +        p->iCell = 0;
         1322  +      }else{
         1323  +        p->id = x.id;
         1324  +        p->iCell = x.iCell;
         1325  +      }
         1326  +      RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
         1327  +      break;
         1328  +    }
         1329  +    if( p->iCell>=nCell ){
         1330  +      RTREE_QUEUE_TRACE(pCur, "POP-Se:");
         1331  +      rtreeSearchPointPop(pCur);
         1332  +    }
         1333  +  }
         1334  +  pCur->atEOF = p==0;
         1335  +  return SQLITE_OK;
         1336  +}
  1081   1337   
  1082   1338   /* 
  1083   1339   ** Rtree virtual table module xNext method.
  1084   1340   */
  1085   1341   static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
  1086         -  Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
  1087   1342     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1088   1343     int rc = SQLITE_OK;
  1089   1344   
  1090         -  /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
  1091         -  ** already at EOF. It is against the rules to call the xNext() method of
  1092         -  ** a cursor that has already reached EOF.
  1093         -  */
  1094         -  assert( pCsr->pNode );
  1095         -
  1096         -  if( pCsr->iStrategy==1 ){
  1097         -    /* This "scan" is a direct lookup by rowid. There is no next entry. */
  1098         -    nodeRelease(pRtree, pCsr->pNode);
  1099         -    pCsr->pNode = 0;
  1100         -  }else{
  1101         -    /* Move to the next entry that matches the configured constraints. */
  1102         -    int iHeight = 0;
  1103         -    while( pCsr->pNode ){
  1104         -      RtreeNode *pNode = pCsr->pNode;
  1105         -      int nCell = NCELL(pNode);
  1106         -      for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
  1107         -        int isEof;
  1108         -        rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
  1109         -        if( rc!=SQLITE_OK || !isEof ){
  1110         -          return rc;
  1111         -        }
  1112         -      }
  1113         -      pCsr->pNode = pNode->pParent;
  1114         -      rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
  1115         -      if( rc!=SQLITE_OK ){
  1116         -        return rc;
  1117         -      }
  1118         -      nodeReference(pCsr->pNode);
  1119         -      nodeRelease(pRtree, pNode);
  1120         -      iHeight++;
  1121         -    }
  1122         -  }
  1123         -
         1345  +  /* Move to the next entry that matches the configured constraints. */
         1346  +  RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
         1347  +  rtreeSearchPointPop(pCsr);
         1348  +  rc = rtreeStepToLeaf(pCsr);
  1124   1349     return rc;
  1125   1350   }
  1126   1351   
  1127   1352   /* 
  1128   1353   ** Rtree virtual table module xRowid method.
  1129   1354   */
  1130   1355   static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
  1131         -  Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
  1132   1356     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1133         -
  1134         -  assert(pCsr->pNode);
  1135         -  *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
  1136         -
  1137         -  return SQLITE_OK;
         1357  +  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
         1358  +  int rc = SQLITE_OK;
         1359  +  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
         1360  +  if( rc==SQLITE_OK && p ){
         1361  +    *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell);
         1362  +  }
         1363  +  return rc;
  1138   1364   }
  1139   1365   
  1140   1366   /* 
  1141   1367   ** Rtree virtual table module xColumn method.
  1142   1368   */
  1143   1369   static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
  1144   1370     Rtree *pRtree = (Rtree *)cur->pVtab;
  1145   1371     RtreeCursor *pCsr = (RtreeCursor *)cur;
         1372  +  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
         1373  +  RtreeCoord c;
         1374  +  int rc = SQLITE_OK;
         1375  +  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
  1146   1376   
         1377  +  if( rc ) return rc;
         1378  +  if( p==0 ) return SQLITE_OK;
  1147   1379     if( i==0 ){
  1148         -    i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
  1149         -    sqlite3_result_int64(ctx, iRowid);
         1380  +    sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
  1150   1381     }else{
  1151         -    RtreeCoord c;
  1152         -    nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
         1382  +    if( rc ) return rc;
         1383  +    nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c);
  1153   1384   #ifndef SQLITE_RTREE_INT_ONLY
  1154   1385       if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
  1155   1386         sqlite3_result_double(ctx, c.f);
  1156   1387       }else
  1157   1388   #endif
  1158   1389       {
  1159   1390         assert( pRtree->eCoordType==RTREE_COORD_INT32 );
  1160   1391         sqlite3_result_int(ctx, c.i);
  1161   1392       }
  1162   1393     }
  1163         -
  1164   1394     return SQLITE_OK;
  1165   1395   }
  1166   1396   
  1167   1397   /* 
  1168   1398   ** Use nodeAcquire() to obtain the leaf node containing the record with 
  1169   1399   ** rowid iRowid. If successful, set *ppLeaf to point to the node and
  1170   1400   ** return SQLITE_OK. If there is no such record in the table, set
  1171   1401   ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
  1172   1402   ** to zero and return an SQLite error code.
  1173   1403   */
  1174         -static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
         1404  +static int findLeafNode(
         1405  +  Rtree *pRtree,              /* RTree to search */
         1406  +  i64 iRowid,                 /* The rowid searching for */
         1407  +  RtreeNode **ppLeaf,         /* Write the node here */
         1408  +  sqlite3_int64 *piNode       /* Write the node-id here */
         1409  +){
  1175   1410     int rc;
  1176   1411     *ppLeaf = 0;
  1177   1412     sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
  1178   1413     if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
  1179   1414       i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
         1415  +    if( piNode ) *piNode = iNode;
  1180   1416       rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
  1181   1417       sqlite3_reset(pRtree->pReadRowid);
  1182   1418     }else{
  1183   1419       rc = sqlite3_reset(pRtree->pReadRowid);
  1184   1420     }
  1185   1421     return rc;
  1186   1422   }
................................................................................
  1235   1471   static int rtreeFilter(
  1236   1472     sqlite3_vtab_cursor *pVtabCursor, 
  1237   1473     int idxNum, const char *idxStr,
  1238   1474     int argc, sqlite3_value **argv
  1239   1475   ){
  1240   1476     Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
  1241   1477     RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  1242         -
  1243   1478     RtreeNode *pRoot = 0;
  1244   1479     int ii;
  1245   1480     int rc = SQLITE_OK;
         1481  +  int iCell = 0;
  1246   1482   
  1247   1483     rtreeReference(pRtree);
  1248   1484   
  1249   1485     freeCursorConstraints(pCsr);
  1250   1486     pCsr->iStrategy = idxNum;
  1251   1487   
  1252   1488     if( idxNum==1 ){
  1253   1489       /* Special case - lookup by rowid. */
  1254   1490       RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
         1491  +    RtreeSearchPoint *p;     /* Search point for the the leaf */
  1255   1492       i64 iRowid = sqlite3_value_int64(argv[0]);
  1256         -    rc = findLeafNode(pRtree, iRowid, &pLeaf);
  1257         -    pCsr->pNode = pLeaf; 
  1258         -    if( pLeaf ){
  1259         -      assert( rc==SQLITE_OK );
  1260         -      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
         1493  +    i64 iNode = 0;
         1494  +    rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
         1495  +    if( rc==SQLITE_OK && pLeaf!=0 ){
         1496  +      p = rtreeSearchPointNew(pCsr, 0.0, 0);
         1497  +      assert( p!=0 );  /* Always returns pCsr->sPoint */
         1498  +      pCsr->aNode[0] = pLeaf;
         1499  +      p->id = iNode;
         1500  +      p->eWithin = PARTLY_WITHIN;
         1501  +      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
         1502  +      p->iCell = iCell;
         1503  +      RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
         1504  +    }else{
         1505  +      pCsr->atEOF = 1;
  1261   1506       }
  1262   1507     }else{
  1263   1508       /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
  1264   1509       ** with the configured constraints. 
  1265   1510       */
  1266   1511       if( argc>0 ){
  1267   1512         pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
................................................................................
  1293   1538   #endif
  1294   1539             }
  1295   1540           }
  1296   1541         }
  1297   1542       }
  1298   1543     
  1299   1544       if( rc==SQLITE_OK ){
  1300         -      pCsr->pNode = 0;
  1301   1545         rc = nodeAcquire(pRtree, 1, 0, &pRoot);
  1302   1546       }
  1303   1547       if( rc==SQLITE_OK ){
  1304         -      int isEof = 1;
  1305         -      int nCell = NCELL(pRoot);
  1306         -      pCsr->pNode = pRoot;
  1307         -      for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
  1308         -        assert( pCsr->pNode==pRoot );
  1309         -        rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
  1310         -        if( !isEof ){
  1311         -          break;
  1312         -        }
  1313         -      }
  1314         -      if( rc==SQLITE_OK && isEof ){
  1315         -        assert( pCsr->pNode==pRoot );
  1316         -        nodeRelease(pRtree, pRoot);
  1317         -        pCsr->pNode = 0;
  1318         -      }
  1319         -      assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
         1548  +      RtreeSearchPoint *pNew = rtreeSearchPointNew(pCsr, 0.0, pRtree->iDepth+1);
         1549  +      if( pNew==0 ) return SQLITE_NOMEM;
         1550  +      pNew->id = 1;
         1551  +      pNew->iCell = 0;
         1552  +      pNew->eWithin = PARTLY_WITHIN;
         1553  +      assert( pCsr->bPoint==1 );
         1554  +      pCsr->aNode[0] = pRoot;
         1555  +      RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
         1556  +      rc = rtreeStepToLeaf(pCsr);
  1320   1557       }
  1321   1558     }
  1322   1559   
  1323   1560     rtreeRelease(pRtree);
  1324   1561     return rc;
  1325   1562   }
  1326   1563   
................................................................................
  2391   2628     /* Obtain a reference to the root node to initialize Rtree.iDepth */
  2392   2629     rc = nodeAcquire(pRtree, 1, 0, &pRoot);
  2393   2630   
  2394   2631     /* Obtain a reference to the leaf node that contains the entry 
  2395   2632     ** about to be deleted. 
  2396   2633     */
  2397   2634     if( rc==SQLITE_OK ){
  2398         -    rc = findLeafNode(pRtree, iDelete, &pLeaf);
         2635  +    rc = findLeafNode(pRtree, iDelete, &pLeaf, 0);
  2399   2636     }
  2400   2637   
  2401   2638     /* Delete the cell in question from the leaf node. */
  2402   2639     if( rc==SQLITE_OK ){
  2403   2640       int rc2;
  2404   2641       rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell);
  2405   2642       if( rc==SQLITE_OK ){
................................................................................
  2978   3215       int jj;
  2979   3216   
  2980   3217       nodeGetCell(&tree, &node, ii, &cell);
  2981   3218       sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
  2982   3219       nCell = (int)strlen(zCell);
  2983   3220       for(jj=0; jj<tree.nDim*2; jj++){
  2984   3221   #ifndef SQLITE_RTREE_INT_ONLY
  2985         -      sqlite3_snprintf(512-nCell,&zCell[nCell], " %f",
         3222  +      sqlite3_snprintf(512-nCell,&zCell[nCell], " %g",
  2986   3223                          (double)cell.aCoord[jj].f);
  2987   3224   #else
  2988   3225         sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
  2989   3226                          cell.aCoord[jj].i);
  2990   3227   #endif
  2991   3228         nCell = (int)strlen(zCell);
  2992   3229       }

Changes to ext/rtree/rtreeB.test.

    37     37         INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0);
    38     38         INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0);
    39     39         INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0);
    40     40         INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0);
    41     41         INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
    42     42         SELECT rtreenode(2, data) FROM t1_node;
    43     43       }
    44         -  } {{{1073741824 0.000000 0.000000 100.000000 100.000000} {2147483646 0.000000 0.000000 200.000000 200.000000} {4294967296 0.000000 0.000000 300.000000 300.000000} {8589934592 20.000000 20.000000 150.000000 150.000000} {9223372036854775807 150.000000 150.000000 400.000000 400.000000}}}
           44  +  } {{{1073741824 0 0 100 100} {2147483646 0 0 200 200} {4294967296 0 0 300 300} {8589934592 20 20 150 150} {9223372036854775807 150 150 400 400}}}
    45     45   }
    46     46   
    47     47   finish_test