/ Check-in [32a13870]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Refactor the constraint checking logic in RTree. The new-style constraint callbacks created by sqlite3_rtree_query_callback() are now hooked up from end to end, though still untested.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-enhancements
Files: files | file ages | folders
SHA1: 32a13870175a1dd1d33af3572dde09ff607a04b6
User & Date: drh 2014-04-17 13:15:33
Context
2014-04-17
14:52
Test cases and bug fixes for the sqlite3_rtree_query_callback() mechanism. check-in: 1ccaaed6 user: drh tags: rtree-enhancements
13:15
Refactor the constraint checking logic in RTree. The new-style constraint callbacks created by sqlite3_rtree_query_callback() are now hooked up from end to end, though still untested. check-in: 32a13870 user: drh tags: rtree-enhancements
2014-04-16
21:02
Performance optimization on nodeGetCell() in R-Tree. check-in: 5d20ff9e user: drh tags: rtree-enhancements
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
...
896
897
898
899
900
901
902
903
904


905














906
907
908
909
910





911
912




913
914
915
916
917

918

919
920

921

922
923









924

925

926
927
928
929
930
931
932


933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949




950
951
952
953
954
955

956
957
958
959
960




961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983




984





985

986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007

1008
1009


1010



1011
1012
1013
1014
1015
1016
1017
1018

1019
1020
1021
1022
1023
1024
1025


1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037





1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
....
1291
1292
1293
1294
1295
1296
1297
1298


1299
1300

1301
1302
1303
1304
1305
1306
1307








1308
1309

1310
1311

1312
1313
1314


1315
1316








1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
....
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
....
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537

1538
1539
1540
1541
1542
1543
1544
....
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
    int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
    int (*xQueryFunc)(sqlite3_rtree_query_info*);
  } u;
  sqlite3_rtree_query_info *pGeom;  /* xGeom and xQueryFunc argument */
};

/* Possible values for RtreeConstraint.op */
#define RTREE_EQ    0x41
#define RTREE_LE    0x42
#define RTREE_LT    0x43
#define RTREE_GE    0x44
#define RTREE_GT    0x45
#define RTREE_MATCH 0x46  /* Old-style sqlite3_rtree_geometry_callback() */
#define RTREE_QUERY 0x47  /* New-style sqlite3_rtree_query_callback() */


/* 
** An rtree structure node.
*/
struct RtreeNode {
  RtreeNode *pParent;         /* Parent node */
................................................................................
*/
static int rtreeEof(sqlite3_vtab_cursor *cur){
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  return pCsr->atEOF;
}

/*
** The r-tree constraint passed as the second argument to this function is
** guaranteed to be a MATCH constraint.


*/














static int rtreeTestGeom(
  Rtree *pRtree,                  /* R-Tree object */
  RtreeConstraint *pConstraint,   /* MATCH constraint to test */
  RtreeCell *pCell,               /* Cell to test */
  int *pbRes                      /* OUT: Test result */





){
  int i;




  RtreeDValue aCoord[RTREE_MAX_DIMENSIONS*2];
  int nCoord = pRtree->nDim*2;

  assert( pConstraint->op==RTREE_MATCH );
  assert( pConstraint->pGeom );



  for(i=0; i<nCoord; i++){
    aCoord[i] = DCOORD(pCell->aCoord[i]);

  }

  return pConstraint->u.xGeom((sqlite3_rtree_geometry*)pConstraint->pGeom,
                              nCoord, aCoord, pbRes);









}



/* 
** Cursor pCursor currently points to a cell in a non-leaf page.
** Set *peWithin to NOT_WITHIN if the constraints in pCursor->aConstraint[]
** are guaranteed to never be satisfied by any subelement under the
** current cell.  If some subelement of the cell might satisfy all
** constraints, then set *peWithin to PARTLY_WITHIN.  If all subelements
** of the cell are guaranteed to fully satisfy all constraints, then


** set *peWithin to FULLY_WITHIN.
**
** In other words, set *peWithin to NOT_WITHIN, PARTLY_WITHIN, or
** FULLY_WITHIN if the cell is completely outside of the field-of-view,
** overlaps the field of view, or is completely contained within the
** field of view, respectively.
**
** It is not an error to set *peWithin to PARTLY_WITHIN when FULLY_WITHIN
** would be correct.  Doing so is suboptimal, but will still give the
** correct answer.  
**
** Return SQLITE_OK if successful or an SQLite error code if an error
** occurs.  Errors can only possible if there is a geometry callback.
*/
static int rtreeTestCell(
  RtreeCursor *pCursor,      /* The cursor to check */
  RtreeCell *pCell,          /* The cell to check */




  int *peWithin              /* Set true if element is out-of-bounds */
){
  int ii;
  int bOutOfBounds = 0;
  int rc = SQLITE_OK;
  Rtree *pRtree = RTREE_OF_CURSOR(pCursor);


  for(ii=0; bOutOfBounds==0 && ii<pCursor->nConstraint; ii++){
    RtreeConstraint *p = &pCursor->aConstraint[ii];
    RtreeDValue cell_min = DCOORD(pCell->aCoord[(p->iCoord>>1)*2]);
    RtreeDValue cell_max = DCOORD(pCell->aCoord[(p->iCoord>>1)*2+1]);





    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
    );

    switch( p->op ){
      case RTREE_LE: case RTREE_LT: 
        bOutOfBounds = p->u.rValue<cell_min; 
        break;

      case RTREE_GE: case RTREE_GT: 
        bOutOfBounds = p->u.rValue>cell_max; 
        break;

      case RTREE_EQ:
        bOutOfBounds = (p->u.rValue>cell_max || p->u.rValue<cell_min);
        break;

      default: {
        assert( p->op==RTREE_MATCH );
        rc = rtreeTestGeom(pRtree, p, pCell, &bOutOfBounds);
        bOutOfBounds = !bOutOfBounds;
        break;




      }





    }

  }

  *peWithin = bOutOfBounds ? NOT_WITHIN : PARTLY_WITHIN;
  return rc;
}

/* 
** pCursor points to a leaf r-tree entry which is a candidate for output.
** This routine sets *peWithin to one of NOT_WITHIN, PARTLY_WITHIN, or
** FULLY_WITHIN depending on whether or not the leaf entry is completely
** outside the region defined by pCursor->aConstraints[], or overlaps the
** region, or is completely within the region, respectively.
**
** This routine is more selective than rtreeTestCell().  rtreeTestCell()
** will return PARTLY_WITHIN or FULLY_WITHIN if the constraints are such
** that a subelement of the cell to be included in the result set.  This
** routine is is only called for leaf r-tree entries and does not need
** to concern itself with subelements.  Hence it only sets *peWithin to
** PARTLY_WITHIN or FULLY_WITHIN if the cell itself meets the requirements.
**
** Return SQLITE_OK if successful or an SQLite error code if an error
** occurs within a geometry callback.

**
** This function assumes that the cell is part of a leaf node.


*/



static int rtreeTestEntry(
  RtreeCursor *pCursor,   /* Cursor pointing to the leaf element */
  RtreeCell *pCell,       /* The cell to check */
  int *peWithin           /* OUT: NOT_WITHIN, PARTLY_WITHIN, or FULLY_WITHIN */
){
  Rtree *pRtree = RTREE_OF_CURSOR(pCursor);
  int ii;
  int res = 1;     /* Innocent until proven guilty */


  for(ii=0; res && ii<pCursor->nConstraint; ii++){
    RtreeConstraint *p = &pCursor->aConstraint[ii];
    RtreeDValue coord = DCOORD(pCell->aCoord[p->iCoord]);
    assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
        || p->op==RTREE_GT || p->op==RTREE_EQ || p->op==RTREE_MATCH
    );


    switch( p->op ){
      case RTREE_LE: res = (coord<=p->u.rValue); break;
      case RTREE_LT: res = (coord<p->u.rValue);  break;
      case RTREE_GE: res = (coord>=p->u.rValue); break;
      case RTREE_GT: res = (coord>p->u.rValue);  break;
      case RTREE_EQ: res = (coord==p->u.rValue); break;
      default: {
        int rc;
        assert( p->op==RTREE_MATCH );
        rc = rtreeTestGeom(pRtree, p, pCell, &res);
        if( rc!=SQLITE_OK ){
          return rc;





        }
        break;
      }
    }
  }

  *peWithin = res ? FULLY_WITHIN : NOT_WITHIN;
  return SQLITE_OK;
}

/*
** One of the cells in node pNode is guaranteed to have a 64-bit 
** integer value equal to iRowid. Return the index of this cell.
*/
static int nodeRowidIndex(
................................................................................
static int rtreeStepToLeaf(RtreeCursor *pCur){
  RtreeSearchPoint *p;
  Rtree *pRtree = RTREE_OF_CURSOR(pCur);
  RtreeNode *pNode;
  int eWithin;
  int rc = SQLITE_OK;
  int nCell;
  RtreeCell cell;


  RtreeSearchPoint x;


  while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
    pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
    if( rc ) return rc;
    nCell = NCELL(pNode);
    assert( nCell<200 );
    while( p->iCell<nCell ){
      nodeGetCell(pRtree, pNode, p->iCell, &cell);








      if( p->iLevel==1 ){
        rc = rtreeTestEntry(pCur, &cell, &eWithin);

      }else{
        rc = rtreeTestCell(pCur, &cell, &eWithin);

      }
      if( rc ) return rc;
      x = *p;


      p->iCell++;
      if( eWithin==NOT_WITHIN ) continue;








      if( p->iCell>=nCell ){
        RTREE_QUEUE_TRACE(pCur, "POP-S:");
        rtreeSearchPointPop(pCur);
      }
      p = rtreeSearchPointNew(pCur, /*rScore*/0.0, x.iLevel-1);
      if( p==0 ) return SQLITE_NOMEM;
      p->eWithin = eWithin;
      if( p->iLevel ){
        p->id = cell.iRowid;
        p->iCell = 0;
      }else{
        p->id = x.id;
        p->iCell = x.iCell;
      }
      RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
      break;
    }
    if( p->iCell>=nCell ){
      RTREE_QUEUE_TRACE(pCur, "POP-Se:");
      rtreeSearchPointPop(pCur);
    }
................................................................................
  memcpy(p, sqlite3_value_blob(pValue), nBlob);
  if( p->magic!=RTREE_GEOMETRY_MAGIC 
   || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(RtreeDValue))
  ){
    sqlite3_free(pGeom);
    return SQLITE_ERROR;
  }

  pGeom->pContext = p->cb.pContext;
  pGeom->nParam = p->nParam;
  pGeom->aParam = p->aParam;

  pCons->u.xGeom = p->cb.xGeom;
  pCons->pGeom = pGeom;
  return SQLITE_OK;
................................................................................
      }else{
        memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
        assert( (idxStr==0 && argc==0)
                || (idxStr && (int)strlen(idxStr)==argc*2) );
        for(ii=0; ii<argc; ii++){
          RtreeConstraint *p = &pCsr->aConstraint[ii];
          p->op = idxStr[ii*2];
          p->iCoord = idxStr[ii*2+1]-'a';
          if( p->op==RTREE_MATCH ){
            /* A MATCH operator. The right-hand-side must be a blob that
            ** can be cast into an RtreeMatchArg object. One created using
            ** an sqlite3_rtree_geometry_callback() SQL user function.
            */
            rc = deserializeGeometry(argv[ii], p);
            if( rc!=SQLITE_OK ){
              break;
            }

          }else{
#ifdef SQLITE_RTREE_INT_ONLY
            p->u.rValue = sqlite3_value_int64(argv[ii]);
#else
            p->u.rValue = sqlite3_value_double(argv[ii]);
#endif
          }
................................................................................
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
        default:
          assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
          op = RTREE_MATCH; 
          break;
      }
      zIdxStr[iIdx++] = op;
      zIdxStr[iIdx++] = p->iColumn - 1 + 'a';
      pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
      pIdxInfo->aConstraintUsage[ii].omit = 1;
    }
  }

  pIdxInfo->idxNum = 2;
  pIdxInfo->needToFreeIdxStr = 1;







|
|
|
|
|
|
|







 







|
|
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
<
|
<
<
>
>
>
>
>

<
>
>
>
>
|
<

|
<
>

>
|
<
>

>
|
|
>
>
>
>
>
>
>
>
>
|
>
|
>

<
<
<
<
<
<
>
>
|
<
<
<
<
<
<
<
<
<
<
<
<

<
<
<
>
>
>
>
|

<
<
<
<
>

<
<
<
<
>
>
>
>

|
|
<
<
|
|
<
<
<
|
<
<
<
|
<
<
<
<
<
<
<
|
>
>
>
>
|
>
>
>
>
>
|
>
|

<
<
<
<
|
<
<
<
<
<
<
|
|
|
<
<
<

<
<
>

<
>
>

>
>
>
|
|
<
<

<
<
<
>

<
<
<
|
|
<
>
>
|
<
<
<
<
<
<
<
<
<
<
<
>
>
>
>
>
|
<
<
<
<
<
|
<







 







|
>
>


>






|
>
>
>
>
>
>
>
>
|
<
>
|
<
>
|
<
<
>
>


>
>
>
>
>
>
>
>




|


<
<
<
<
|
|
<







 







<







 







|









>







 







|







270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
...
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922

923


924
925
926
927
928
929

930
931
932
933
934

935
936

937
938
939
940

941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959






960
961
962












963



964
965
966
967
968
969




970
971




972
973
974
975
976
977
978


979
980



981



982







983
984
985
986
987
988
989
990
991
992
993
994
995
996
997




998






999
1000
1001



1002


1003
1004

1005
1006
1007
1008
1009
1010
1011
1012


1013



1014
1015



1016
1017

1018
1019
1020











1021
1022
1023
1024
1025
1026





1027

1028
1029
1030
1031
1032
1033
1034
....
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301

1302
1303

1304
1305


1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324




1325
1326

1327
1328
1329
1330
1331
1332
1333
....
1452
1453
1454
1455
1456
1457
1458

1459
1460
1461
1462
1463
1464
1465
....
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
....
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
    int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
    int (*xQueryFunc)(sqlite3_rtree_query_info*);
  } u;
  sqlite3_rtree_query_info *pGeom;  /* xGeom and xQueryFunc argument */
};

/* Possible values for RtreeConstraint.op */
#define RTREE_EQ    0x41  /* A */
#define RTREE_LE    0x42  /* B */
#define RTREE_LT    0x43  /* C */
#define RTREE_GE    0x44  /* D */
#define RTREE_GT    0x45  /* E */
#define RTREE_MATCH 0x46  /* F: Old-style sqlite3_rtree_geometry_callback() */
#define RTREE_QUERY 0x47  /* G: New-style sqlite3_rtree_query_callback() */


/* 
** An rtree structure node.
*/
struct RtreeNode {
  RtreeNode *pParent;         /* Parent node */
................................................................................
*/
static int rtreeEof(sqlite3_vtab_cursor *cur){
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  return pCsr->atEOF;
}

/*
** Convert raw bits from the on-disk RTree record into a coordinate value
** The on-disk record stores integer coordinates if eInt is true and it
** stores 32-bit floating point records if eInt is false.  a[] is the four
** bytes of the on-disk record to be decoded.  Store the results in "r".
*/
#define RTREE_DECODE_COORD(eInt, a, r) {                        \
    u32 x;           /* Raw bits of the coordinate value */     \
    RtreeCoord c;    /* Coordinate decoded */                   \
    x = ((u32)a[0]<<24) + ((u32)a[1]<<16)                       \
           +((u32)a[2]<<8) + a[3];                              \
    c.i = *(int*)&x;                                            \
    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
   

/*
** Check the RTree node or entry given by pCellData and p against the MATCH
** constraint pConstraint.  
*/
static int rtreeCallbackConstraint(

  RtreeConstraint *pConstraint,  /* The constraint to test */


  int eInt,                      /* True if RTree holding integer coordinates */
  u8 *pCellData,                 /* Raw cell content */
  RtreeSearchPoint *pSearch,     /* Container of this cell */
  sqlite3_rtree_dbl *prScore,    /* OUT: score for the cell */
  int *peWithin                  /* OUT: visibility of the cell */
){

  int i;                                                /* Loop counter */
  sqlite3_rtree_query_info *pGeom = pConstraint->pGeom; /* Callback info */
  int nCoord = pGeom->nCoord;                           /* No. of coordinates */
  int rc;                                             /* Callback return code */
  sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2];   /* Decoded coordinates */


  assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY );

  assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 );

  pCellData += 8;
  for(i=0; i<nCoord; i++, pCellData += 4){

    RTREE_DECODE_COORD(eInt, pCellData, aCoord[i]);
  }
  if( pConstraint->op==RTREE_MATCH ){
    rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pGeom,
                              nCoord, aCoord, &i);
    if( i==0 ) *peWithin = NOT_WITHIN;
  }else{
    pGeom->aCoord = aCoord;
    pGeom->iLevel = pSearch->iLevel;
    pGeom->rScore = pGeom->rParentScore = pSearch->rScore;
    pGeom->eWithin = pGeom->eParentWithin = pSearch->eWithin;
    rc = pConstraint->u.xQueryFunc(pGeom);
    if( pGeom->eWithin<*peWithin ) *peWithin = pGeom->eWithin;
    if( pGeom->rScore<*prScore ) *prScore = pGeom->rScore;
  }
  return rc;
}

/* 






** Check the internal RTree node given by pCellData against constraint p.
** If this constraint cannot be satisfied by any child within the node,
** set *peWithin to NOT_WITHIN.












*/



static void rtreeNonleafConstraint(
  RtreeConstraint *p,        /* The constraint to test */
  int eInt,                  /* True if RTree holds integer coordinates */
  u8 *pCellData,             /* Raw cell content as appears on disk */
  int *peWithin              /* Adjust downward, as appropriate */
){




  sqlite3_rtree_dbl val;     /* Coordinate value convert to a double */





  /* p->iCoord might point to either a lower or upper bound coordinate
  ** in a coordinate pair.  But make pCellData point to the lower bound.
  */
  pCellData += 8 + 4*(p->iCoord&0xfe);

  assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
      || p->op==RTREE_GT || p->op==RTREE_EQ );


  switch( p->op ){
    case RTREE_LE:



    case RTREE_LT:



    case RTREE_EQ:







      RTREE_DECODE_COORD(eInt, pCellData, val);
      /* val now holds the lower bound of the coordinate pair */
      if( p->u.rValue>=val ) return;
      if( p->op!=RTREE_EQ ) break;  /* RTREE_LE and RTREE_LT end here */
      /* Fall through for the RTREE_EQ case */

    default: /* RTREE_GT or RTREE_GE,  or fallthrough of RTREE_EQ */
      pCellData += 4;
      RTREE_DECODE_COORD(eInt, pCellData, val);
      /* val now holds the upper bound of the coordinate pair */
      if( p->u.rValue<=val ) return;
  }
  *peWithin = NOT_WITHIN;
}





/*






** Check the leaf RTree cell given by pCellData against constraint p.
** If this constraint is not satisfied, set *peWithin to NOT_WITHIN.
** If the constraint is satisfied, leave *peWithin unchanged.



**


** The constraint is of the form:  xN op $val
**

** The op is given by p->op.  The xN is p->iCoord-th coordinate in
** pCellData.  $val is given by p->u.rValue.
*/
static void rtreeLeafConstraint(
  RtreeConstraint *p,        /* The constraint to test */
  int eInt,                  /* True if RTree holds integer coordinates */
  u8 *pCellData,             /* Raw cell content as appears on disk */
  int *peWithin              /* Adjust downward, as appropriate */


){



  RtreeDValue xN;      /* Coordinate value converted to a double */




  assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE 
      || p->op==RTREE_GT || p->op==RTREE_EQ );

  pCellData += 8 + p->iCoord*4;
  RTREE_DECODE_COORD(eInt, pCellData, xN);
  switch( p->op ){











    case RTREE_LE: if( xN <= p->u.rValue ) return;  break;
    case RTREE_LT: if( xN <  p->u.rValue ) return;  break;
    case RTREE_GE: if( xN >= p->u.rValue ) return;  break;
    case RTREE_GT: if( xN >  p->u.rValue ) return;  break;
    default:       if( xN == p->u.rValue ) return;  break;
  }





  *peWithin = NOT_WITHIN;

}

/*
** One of the cells in node pNode is guaranteed to have a 64-bit 
** integer value equal to iRowid. Return the index of this cell.
*/
static int nodeRowidIndex(
................................................................................
static int rtreeStepToLeaf(RtreeCursor *pCur){
  RtreeSearchPoint *p;
  Rtree *pRtree = RTREE_OF_CURSOR(pCur);
  RtreeNode *pNode;
  int eWithin;
  int rc = SQLITE_OK;
  int nCell;
  int nConstraint = pCur->nConstraint;
  int ii;
  int eInt;
  RtreeSearchPoint x;

  eInt = pRtree->eCoordType==RTREE_COORD_INT32;
  while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){
    pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc);
    if( rc ) return rc;
    nCell = NCELL(pNode);
    assert( nCell<200 );
    while( p->iCell<nCell ){
      sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)0;
      u8 *pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell);
      eWithin = FULLY_WITHIN;
      for(ii=0; ii<nConstraint; ii++){
        RtreeConstraint *pConstraint = pCur->aConstraint + ii;
        if( pConstraint->op>=RTREE_MATCH ){
          rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p,
                                       &rScore, &eWithin);
          if( rc ) return rc;
        }else if( p->iLevel==1 ){

          rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin);
        }else{

          rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin);
        }


        if( eWithin==NOT_WITHIN ) break;
      }
      p->iCell++;
      if( eWithin==NOT_WITHIN ) continue;
      x.iLevel = p->iLevel - 1;
      if( x.iLevel ){
        x.id = readInt64(pCellData);
        x.iCell = 0;
      }else{
        x.id = p->id;
        x.iCell = p->iCell - 1;
      }
      if( p->iCell>=nCell ){
        RTREE_QUEUE_TRACE(pCur, "POP-S:");
        rtreeSearchPointPop(pCur);
      }
      p = rtreeSearchPointNew(pCur, rScore, x.iLevel);
      if( p==0 ) return SQLITE_NOMEM;
      p->eWithin = eWithin;




      p->id = x.id;
      p->iCell = x.iCell;

      RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
      break;
    }
    if( p->iCell>=nCell ){
      RTREE_QUEUE_TRACE(pCur, "POP-Se:");
      rtreeSearchPointPop(pCur);
    }
................................................................................
  memcpy(p, sqlite3_value_blob(pValue), nBlob);
  if( p->magic!=RTREE_GEOMETRY_MAGIC 
   || nBlob!=(int)(sizeof(RtreeMatchArg) + (p->nParam-1)*sizeof(RtreeDValue))
  ){
    sqlite3_free(pGeom);
    return SQLITE_ERROR;
  }

  pGeom->pContext = p->cb.pContext;
  pGeom->nParam = p->nParam;
  pGeom->aParam = p->aParam;

  pCons->u.xGeom = p->cb.xGeom;
  pCons->pGeom = pGeom;
  return SQLITE_OK;
................................................................................
      }else{
        memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
        assert( (idxStr==0 && argc==0)
                || (idxStr && (int)strlen(idxStr)==argc*2) );
        for(ii=0; ii<argc; ii++){
          RtreeConstraint *p = &pCsr->aConstraint[ii];
          p->op = idxStr[ii*2];
          p->iCoord = idxStr[ii*2+1]-'0';
          if( p->op==RTREE_MATCH ){
            /* A MATCH operator. The right-hand-side must be a blob that
            ** can be cast into an RtreeMatchArg object. One created using
            ** an sqlite3_rtree_geometry_callback() SQL user function.
            */
            rc = deserializeGeometry(argv[ii], p);
            if( rc!=SQLITE_OK ){
              break;
            }
            p->pGeom->nCoord = pRtree->nDim*2;
          }else{
#ifdef SQLITE_RTREE_INT_ONLY
            p->u.rValue = sqlite3_value_int64(argv[ii]);
#else
            p->u.rValue = sqlite3_value_double(argv[ii]);
#endif
          }
................................................................................
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
        default:
          assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH );
          op = RTREE_MATCH; 
          break;
      }
      zIdxStr[iIdx++] = op;
      zIdxStr[iIdx++] = p->iColumn - 1 + '0';
      pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
      pIdxInfo->aConstraintUsage[ii].omit = 1;
    }
  }

  pIdxInfo->idxNum = 2;
  pIdxInfo->needToFreeIdxStr = 1;

Changes to ext/rtree/rtree6.test.

53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
...
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
    CREATE TABLE t2(k INTEGER PRIMARY KEY, v);
    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2);
  }
} {}

do_test rtree6-1.2 {
  rtree_strategy {SELECT * FROM t1 WHERE x1>10}
} {Ea}

do_test rtree6-1.3 {
  rtree_strategy {SELECT * FROM t1 WHERE x1<10}
} {Ca}

do_test rtree6-1.4 {
  rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
} {Ca}

do_test rtree6-1.5 {
  rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
} {Ca}

do_eqp_test rtree6.2.1 {
  SELECT * FROM t1,t2 WHERE k=+ii AND x1<10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:Ca} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

do_eqp_test rtree6.2.2 {
  SELECT * FROM t1,t2 WHERE k=ii AND x1<10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:Ca} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

do_eqp_test rtree6.2.3 {
  SELECT * FROM t1,t2 WHERE k=ii
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

do_eqp_test rtree6.2.4 {
  SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:CaEb} 
  0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
}

do_eqp_test rtree6.2.5 {
  SELECT * FROM t1,t2 WHERE k=ii AND x1<v
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
................................................................................
  rtree_strategy {
    SELECT * FROM t3 WHERE 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 
  }
} {EaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEa}
do_test rtree6.3.3 {
  rtree_strategy {
    SELECT * FROM t3 WHERE 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5
  }
} {EaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEaEa}

do_execsql_test rtree6-3.4 {
  SELECT * FROM t3 WHERE x1>0.5 AND x1>0.8 AND x1>1.1
} {}
do_execsql_test rtree6-3.5 {
  SELECT * FROM t3 WHERE 
    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 







|



|



|



|




|






|













|







 







|










|







53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
...
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
    CREATE TABLE t2(k INTEGER PRIMARY KEY, v);
    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2);
  }
} {}

do_test rtree6-1.2 {
  rtree_strategy {SELECT * FROM t1 WHERE x1>10}
} {E0}

do_test rtree6-1.3 {
  rtree_strategy {SELECT * FROM t1 WHERE x1<10}
} {C0}

do_test rtree6-1.4 {
  rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
} {C0}

do_test rtree6-1.5 {
  rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
} {C0}

do_eqp_test rtree6.2.1 {
  SELECT * FROM t1,t2 WHERE k=+ii AND x1<10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

do_eqp_test rtree6.2.2 {
  SELECT * FROM t1,t2 WHERE k=ii AND x1<10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

do_eqp_test rtree6.2.3 {
  SELECT * FROM t1,t2 WHERE k=ii
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
  0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
}

do_eqp_test rtree6.2.4 {
  SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
  0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
}

do_eqp_test rtree6.2.5 {
  SELECT * FROM t1,t2 WHERE k=ii AND x1<v
} {
  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 
................................................................................
  rtree_strategy {
    SELECT * FROM t3 WHERE 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 
  }
} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}
do_test rtree6.3.3 {
  rtree_strategy {
    SELECT * FROM t3 WHERE 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 
      x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5
  }
} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}

do_execsql_test rtree6-3.4 {
  SELECT * FROM t3 WHERE x1>0.5 AND x1>0.8 AND x1>1.1
} {}
do_execsql_test rtree6-3.5 {
  SELECT * FROM t3 WHERE 
    x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND 

Changes to ext/rtree/rtreeC.test.

25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
..
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
...
267
268
269
270
271
272
273
274
}

do_eqp_test 1.1 {
  SELECT * FROM r_tree, t 
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 1 {SCAN TABLE t}
  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
}

do_eqp_test 1.2 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
}

do_eqp_test 1.3 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
}

do_eqp_test 1.5 {
  SELECT * FROM t, r_tree
} {
  0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
  0 1 0 {SCAN TABLE t} 
................................................................................
sqlite3 db test.db

do_eqp_test 2.1 {
  SELECT * FROM r_tree, t 
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 1 {SCAN TABLE t}
  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
}

do_eqp_test 2.2 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
}

do_eqp_test 2.3 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:DdBcDbBa}
}

do_eqp_test 2.5 {
  SELECT * FROM t, r_tree
} {
  0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
  0 1 0 {SCAN TABLE t} 
................................................................................
    execsql { SELECT * FROM rt }
  } {1 2.0 3.0}
  db close
}


finish_test








|







|







|







 







|







|







|







 







<
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
..
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
...
267
268
269
270
271
272
273

}

do_eqp_test 1.1 {
  SELECT * FROM r_tree, t 
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 1 {SCAN TABLE t}
  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
}

do_eqp_test 1.2 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
}

do_eqp_test 1.3 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
}

do_eqp_test 1.5 {
  SELECT * FROM t, r_tree
} {
  0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
  0 1 0 {SCAN TABLE t} 
................................................................................
sqlite3 db test.db

do_eqp_test 2.1 {
  SELECT * FROM r_tree, t 
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 1 {SCAN TABLE t}
  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
}

do_eqp_test 2.2 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
}

do_eqp_test 2.3 {
  SELECT * FROM t, r_tree
  WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y
} {
  0 0 0 {SCAN TABLE t}
  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
}

do_eqp_test 2.5 {
  SELECT * FROM t, r_tree
} {
  0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:}
  0 1 0 {SCAN TABLE t} 
................................................................................
    execsql { SELECT * FROM rt }
  } {1 2.0 3.0}
  db close
}


finish_test