Update sqlite3 to 3.8.6. A list of changes are available here:

http://sqlite.org/releaselog/3_8_6.html.

Tested in a bulk and ok landry@

7 files changed, 1141 insertions, 775 deletions

diff --git a/lib/libsqlite3/ext/rtree/rtree.c b/lib/libsqlite3/ext/rtree/rtree.c
index 577e19d4c61..8150538d452 100644
--- a/lib/libsqlite3/ext/rtree/rtree.c
+++ b/lib/libsqlite3/ext/rtree/rtree.c
@@ -54,48 +54,6 @@
 
 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)
 
-/*
-** This file contains an implementation of a couple of different variants
-** of the r-tree algorithm. See the README file for further details. The 
-** same data-structure is used for all, but the algorithms for insert and
-** delete operations vary. The variants used are selected at compile time 
-** by defining the following symbols:
-*/
-
-/* Either, both or none of the following may be set to activate 
-** r*tree variant algorithms.
-*/
-#define VARIANT_RSTARTREE_CHOOSESUBTREE 0
-#define VARIANT_RSTARTREE_REINSERT      1
-
-/* 
-** Exactly one of the following must be set to 1.
-*/
-#define VARIANT_GUTTMAN_QUADRATIC_SPLIT 0
-#define VARIANT_GUTTMAN_LINEAR_SPLIT    0
-#define VARIANT_RSTARTREE_SPLIT         1
-
-#define VARIANT_GUTTMAN_SPLIT \
-        (VARIANT_GUTTMAN_LINEAR_SPLIT||VARIANT_GUTTMAN_QUADRATIC_SPLIT)
-
-#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
-  #define PickNext QuadraticPickNext
-  #define PickSeeds QuadraticPickSeeds
-  #define AssignCells splitNodeGuttman
-#endif
-#if VARIANT_GUTTMAN_LINEAR_SPLIT
-  #define PickNext LinearPickNext
-  #define PickSeeds LinearPickSeeds
-  #define AssignCells splitNodeGuttman
-#endif
-#if VARIANT_RSTARTREE_SPLIT
-  #define AssignCells splitNodeStartree
-#endif
-
-#if !defined(NDEBUG) && !defined(SQLITE_DEBUG) 
-# define NDEBUG 1
-#endif
-
 #ifndef SQLITE_CORE
   #include "sqlite3ext.h"
   SQLITE_EXTENSION_INIT1
@@ -105,11 +63,13 @@
 
 #include <string.h>
 #include <assert.h>
+#include <stdio.h>
 
 #ifndef SQLITE_AMALGAMATION
 #include "sqlite3rtree.h"
 typedef sqlite3_int64 i64;
 typedef unsigned char u8;
+typedef unsigned short u16;
 typedef unsigned int u32;
 #endif
 
@@ -127,6 +87,7 @@ typedef struct RtreeConstraint RtreeConstraint;
 typedef struct RtreeMatchArg RtreeMatchArg;
 typedef struct RtreeGeomCallback RtreeGeomCallback;
 typedef union RtreeCoord RtreeCoord;
+typedef struct RtreeSearchPoint RtreeSearchPoint;
 
 /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */
 #define RTREE_MAX_DIMENSIONS 5
@@ -135,7 +96,7 @@ typedef union RtreeCoord RtreeCoord;
 ** ever contain very many entries, so a fixed number of buckets is 
 ** used.
 */
-#define HASHSIZE 128
+#define HASHSIZE 97
 
 /* The xBestIndex method of this virtual table requires an estimate of
 ** the number of rows in the virtual table to calculate the costs of
@@ -151,15 +112,15 @@ typedef union RtreeCoord RtreeCoord;
 ** An rtree virtual-table object.
 */
 struct Rtree {
-  sqlite3_vtab base;
+  sqlite3_vtab base;          /* Base class.  Must be first */
   sqlite3 *db;                /* Host database connection */
   int iNodeSize;              /* Size in bytes of each node in the node table */
-  int nDim;                   /* Number of dimensions */
-  int nBytesPerCell;          /* Bytes consumed per cell */
+  u8 nDim;                    /* Number of dimensions */
+  u8 eCoordType;              /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */
+  u8 nBytesPerCell;           /* Bytes consumed per cell */
   int iDepth;                 /* Current depth of the r-tree structure */
   char *zDb;                  /* Name of database containing r-tree table */
   char *zName;                /* Name of r-tree table */ 
-  RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
   int nBusy;                  /* Current number of users of this structure */
   i64 nRowEst;                /* Estimated number of rows in this table */
 
@@ -186,10 +147,10 @@ struct Rtree {
   sqlite3_stmt *pWriteParent;
   sqlite3_stmt *pDeleteParent;
 
-  int eCoordType;
+  RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ 
 };
 
-/* Possible values for eCoordType: */
+/* Possible values for Rtree.eCoordType: */
 #define RTREE_COORD_REAL32 0
 #define RTREE_COORD_INT32  1
 
@@ -201,12 +162,31 @@ struct Rtree {
 #ifdef SQLITE_RTREE_INT_ONLY
   typedef sqlite3_int64 RtreeDValue;       /* High accuracy coordinate */
   typedef int RtreeValue;                  /* Low accuracy coordinate */
+# define RTREE_ZERO 0
 #else
   typedef double RtreeDValue;              /* High accuracy coordinate */
   typedef float RtreeValue;                /* Low accuracy coordinate */
+# define RTREE_ZERO 0.0
 #endif
 
 /*
+** When doing a search of an r-tree, instances of the following structure
+** record intermediate results from the tree walk.
+**
+** The id is always a node-id.  For iLevel>=1 the id is the node-id of
+** the node that the RtreeSearchPoint represents.  When iLevel==0, however,
+** the id is of the parent node and the cell that RtreeSearchPoint
+** represents is the iCell-th entry in the parent node.
+*/
+struct RtreeSearchPoint {
+  RtreeDValue rScore;    /* The score for this node.  Smallest goes first. */
+  sqlite3_int64 id;      /* Node ID */
+  u8 iLevel;             /* 0=entries.  1=leaf node.  2+ for higher */
+  u8 eWithin;            /* PARTLY_WITHIN or FULLY_WITHIN */
+  u8 iCell;              /* Cell index within the node */
+};
+
+/*
 ** The minimum number of cells allowed for a node is a third of the 
 ** maximum. In Gutman's notation:
 **
@@ -228,21 +208,44 @@ struct Rtree {
 */
 #define RTREE_MAX_DEPTH 40
 
+
+/*
+** Number of entries in the cursor RtreeNode cache.  The first entry is
+** used to cache the RtreeNode for RtreeCursor.sPoint.  The remaining
+** entries cache the RtreeNode for the first elements of the priority queue.
+*/
+#define RTREE_CACHE_SZ  5
+
 /* 
 ** An rtree cursor object.
 */
 struct RtreeCursor {
-  sqlite3_vtab_cursor base;
-  RtreeNode *pNode;                 /* Node cursor is currently pointing at */
-  int iCell;                        /* Index of current cell in pNode */
+  sqlite3_vtab_cursor base;         /* Base class.  Must be first */
+  u8 atEOF;                         /* True if at end of search */
+  u8 bPoint;                        /* True if sPoint is valid */
   int iStrategy;                    /* Copy of idxNum search parameter */
   int nConstraint;                  /* Number of entries in aConstraint */
   RtreeConstraint *aConstraint;     /* Search constraints. */
+  int nPointAlloc;                  /* Number of slots allocated for aPoint[] */
+  int nPoint;                       /* Number of slots used in aPoint[] */
+  int mxLevel;                      /* iLevel value for root of the tree */
+  RtreeSearchPoint *aPoint;         /* Priority queue for search points */
+  RtreeSearchPoint sPoint;          /* Cached next search point */
+  RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */
+  u32 anQueue[RTREE_MAX_DEPTH+1];   /* Number of queued entries by iLevel */
 };
 
+/* Return the Rtree of a RtreeCursor */
+#define RTREE_OF_CURSOR(X)   ((Rtree*)((X)->base.pVtab))
+
+/*
+** A coordinate can be either a floating point number or a integer.  All
+** coordinates within a single R-Tree are always of the same time.
+*/
 union RtreeCoord {
-  RtreeValue f;
-  int i;
+  RtreeValue f;      /* Floating point value */
+  int i;             /* Integer value */
+  u32 u;             /* Unsigned for byte-order conversions */
 };
 
 /*
@@ -267,38 +270,67 @@ union RtreeCoord {
 struct RtreeConstraint {
   int iCoord;                     /* Index of constrained coordinate */
   int op;                         /* Constraining operation */
-  RtreeDValue rValue;             /* Constraint value. */
-  int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
-  sqlite3_rtree_geometry *pGeom;  /* Constraint callback argument for a MATCH */
+  union {
+    RtreeDValue rValue;             /* Constraint value. */
+    int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*);
+    int (*xQueryFunc)(sqlite3_rtree_query_info*);
+  } u;
+  sqlite3_rtree_query_info *pInfo;  /* 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
+#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 */
-  i64 iNode;
-  int nRef;
-  int isDirty;
-  u8 *zData;
-  RtreeNode *pNext;                 /* Next node in this hash chain */
+  RtreeNode *pParent;         /* Parent node */
+  i64 iNode;                  /* The node number */
+  int nRef;                   /* Number of references to this node */
+  int isDirty;                /* True if the node needs to be written to disk */
+  u8 *zData;                  /* Content of the node, as should be on disk */
+  RtreeNode *pNext;           /* Next node in this hash collision chain */
 };
+
+/* Return the number of cells in a node  */
 #define NCELL(pNode) readInt16(&(pNode)->zData[2])
 
 /* 
-** Structure to store a deserialized rtree record.
+** A single cell from a node, deserialized
 */
 struct RtreeCell {
-  i64 iRowid;
-  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];
+  i64 iRowid;                                 /* Node or entry ID */
+  RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2];  /* Bounding box coordinates */
+};
+
+
+/*
+** This object becomes the sqlite3_user_data() for the SQL functions
+** that are created by sqlite3_rtree_geometry_callback() and
+** sqlite3_rtree_query_callback() and which appear on the right of MATCH
+** operators in order to constrain a search.
+**
+** xGeom and xQueryFunc are the callback functions.  Exactly one of 
+** xGeom and xQueryFunc fields is non-NULL, depending on whether the
+** SQL function was created using sqlite3_rtree_geometry_callback() or
+** sqlite3_rtree_query_callback().
+** 
+** This object is deleted automatically by the destructor mechanism in
+** sqlite3_create_function_v2().
+*/
+struct RtreeGeomCallback {
+  int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
+  int (*xQueryFunc)(sqlite3_rtree_query_info*);
+  void (*xDestructor)(void*);
+  void *pContext;
 };
 
 
@@ -310,29 +342,16 @@ struct RtreeCell {
 #define RTREE_GEOMETRY_MAGIC 0x891245AB
 
 /*
-** An instance of this structure must be supplied as a blob argument to
-** the right-hand-side of an SQL MATCH operator used to constrain an
-** r-tree query.
+** An instance of this structure (in the form of a BLOB) is returned by
+** the SQL functions that sqlite3_rtree_geometry_callback() and
+** sqlite3_rtree_query_callback() create, and is read as the right-hand
+** operand to the MATCH operator of an R-Tree.
 */
 struct RtreeMatchArg {
-  u32 magic;                      /* Always RTREE_GEOMETRY_MAGIC */
-  int (*xGeom)(sqlite3_rtree_geometry *, int, RtreeDValue*, int *);
-  void *pContext;
-  int nParam;
-  RtreeDValue aParam[1];
-};
-
-/*
-** When a geometry callback is created (see sqlite3_rtree_geometry_callback),
-** a single instance of the following structure is allocated. It is used
-** as the context for the user-function created by by s_r_g_c(). The object
-** is eventually deleted by the destructor mechanism provided by
-** sqlite3_create_function_v2() (which is called by s_r_g_c() to create
-** the geometry callback function).
-*/
-struct RtreeGeomCallback {
-  int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*);
-  void *pContext;
+  u32 magic;                  /* Always RTREE_GEOMETRY_MAGIC */
+  RtreeGeomCallback cb;       /* Info about the callback functions */
+  int nParam;                 /* Number of parameters to the SQL function */
+  RtreeDValue aParam[1];      /* Values for parameters to the SQL function */
 };
 
 #ifndef MAX
@@ -426,10 +445,7 @@ static void nodeZero(Rtree *pRtree, RtreeNode *p){
 ** in the Rtree.aHash table.
 */
 static int nodeHash(i64 iNode){
-  return (
-    (iNode>>56) ^ (iNode>>48) ^ (iNode>>40) ^ (iNode>>32) ^ 
-    (iNode>>24) ^ (iNode>>16) ^ (iNode>> 8) ^ (iNode>> 0)
-  ) % HASHSIZE;
+  return iNode % HASHSIZE;
 }
 
 /*
@@ -489,8 +505,7 @@ static RtreeNode *nodeNew(Rtree *pRtree, RtreeNode *pParent){
 /*
 ** Obtain a reference to an r-tree node.
 */
-static int
-nodeAcquire(
+static int nodeAcquire(
   Rtree *pRtree,             /* R-tree structure */
   i64 iNode,                 /* Node number to load */
   RtreeNode *pParent,        /* Either the parent node or NULL */
@@ -579,10 +594,10 @@ nodeAcquire(
 ** Overwrite cell iCell of node pNode with the contents of pCell.
 */
 static void nodeOverwriteCell(
-  Rtree *pRtree, 
-  RtreeNode *pNode,  
-  RtreeCell *pCell, 
-  int iCell
+  Rtree *pRtree,             /* The overall R-Tree */
+  RtreeNode *pNode,          /* The node into which the cell is to be written */
+  RtreeCell *pCell,          /* The cell to write */
+  int iCell                  /* Index into pNode into which pCell is written */
 ){
   int ii;
   u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
@@ -594,7 +609,7 @@ static void nodeOverwriteCell(
 }
 
 /*
-** Remove cell the cell with index iCell from node pNode.
+** Remove the cell with index iCell from node pNode.
 */
 static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
   u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell];
@@ -611,11 +626,10 @@ static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){
 **
 ** If there is not enough free space in pNode, return SQLITE_FULL.
 */
-static int
-nodeInsertCell(
-  Rtree *pRtree, 
-  RtreeNode *pNode, 
-  RtreeCell *pCell 
+static int nodeInsertCell(
+  Rtree *pRtree,                /* The overall R-Tree */
+  RtreeNode *pNode,             /* Write new cell into this node */
+  RtreeCell *pCell              /* The cell to be inserted */
 ){
   int nCell;                    /* Current number of cells in pNode */
   int nMaxCell;                 /* Maximum number of cells for pNode */
@@ -636,8 +650,7 @@ nodeInsertCell(
 /*
 ** If the node is dirty, write it out to the database.
 */
-static int
-nodeWrite(Rtree *pRtree, RtreeNode *pNode){
+static int nodeWrite(Rtree *pRtree, RtreeNode *pNode){
   int rc = SQLITE_OK;
   if( pNode->isDirty ){
     sqlite3_stmt *p = pRtree->pWriteNode;
@@ -662,8 +675,7 @@ nodeWrite(Rtree *pRtree, RtreeNode *pNode){
 ** Release a reference to a node. If the node is dirty and the reference
 ** count drops to zero, the node data is written to the database.
 */
-static int
-nodeRelease(Rtree *pRtree, RtreeNode *pNode){
+static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){
   int rc = SQLITE_OK;
   if( pNode ){
     assert( pNode->nRef>0 );
@@ -691,9 +703,9 @@ nodeRelease(Rtree *pRtree, RtreeNode *pNode){
 ** an internal node, then the 64-bit integer is a child page number.
 */
 static i64 nodeGetRowid(
-  Rtree *pRtree, 
-  RtreeNode *pNode, 
-  int iCell
+  Rtree *pRtree,       /* The overall R-Tree */
+  RtreeNode *pNode,    /* The node from which to extract the ID */
+  int iCell            /* The cell index from which to extract the ID */
 ){
   assert( iCell<NCELL(pNode) );
   return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]);
@@ -703,11 +715,11 @@ static i64 nodeGetRowid(
 ** Return coordinate iCoord from cell iCell in node pNode.
 */
 static void nodeGetCoord(
-  Rtree *pRtree, 
-  RtreeNode *pNode, 
-  int iCell,
-  int iCoord,
-  RtreeCoord *pCoord           /* Space to write result to */
+  Rtree *pRtree,               /* The overall R-Tree */
+  RtreeNode *pNode,            /* The node from which to extract a coordinate */
+  int iCell,                   /* The index of the cell within the node */
+  int iCoord,                  /* Which coordinate to extract */
+  RtreeCoord *pCoord           /* OUT: Space to write result to */
 ){
   readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord);
 }
@@ -717,15 +729,20 @@ static void nodeGetCoord(
 ** to by pCell with the results.
 */
 static void nodeGetCell(
-  Rtree *pRtree, 
-  RtreeNode *pNode, 
-  int iCell,
-  RtreeCell *pCell
+  Rtree *pRtree,               /* The overall R-Tree */
+  RtreeNode *pNode,            /* The node containing the cell to be read */
+  int iCell,                   /* Index of the cell within the node */
+  RtreeCell *pCell             /* OUT: Write the cell contents here */
 ){
-  int ii;
+  u8 *pData;
+  u8 *pEnd;
+  RtreeCoord *pCoord;
   pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell);
-  for(ii=0; ii<pRtree->nDim*2; ii++){
-    nodeGetCoord(pRtree, pNode, iCell, ii, &pCell->aCoord[ii]);
+  pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell);
+  pEnd = pData + pRtree->nDim*8;
+  pCoord = pCell->aCoord;
+  for(; pData<pEnd; pData+=4, pCoord++){
+    readCoord(pData, pCoord);
   }
 }
 
@@ -851,10 +868,10 @@ static void freeCursorConstraints(RtreeCursor *pCsr){
   if( pCsr->aConstraint ){
     int i;                        /* Used to iterate through constraint array */
     for(i=0; i<pCsr->nConstraint; i++){
-      sqlite3_rtree_geometry *pGeom = pCsr->aConstraint[i].pGeom;
-      if( pGeom ){
-        if( pGeom->xDelUser ) pGeom->xDelUser(pGeom->pUser);
-        sqlite3_free(pGeom);
+      sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo;
+      if( pInfo ){
+        if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser);
+        sqlite3_free(pInfo);
       }
     }
     sqlite3_free(pCsr->aConstraint);
@@ -867,12 +884,13 @@ static void freeCursorConstraints(RtreeCursor *pCsr){
 */
 static int rtreeClose(sqlite3_vtab_cursor *cur){
   Rtree *pRtree = (Rtree *)(cur->pVtab);
-  int rc;
+  int ii;
   RtreeCursor *pCsr = (RtreeCursor *)cur;
   freeCursorConstraints(pCsr);
-  rc = nodeRelease(pRtree, pCsr->pNode);
+  sqlite3_free(pCsr->aPoint);
+  for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]);
   sqlite3_free(pCsr);
-  return rc;
+  return SQLITE_OK;
 }
 
 /*
@@ -883,194 +901,164 @@ static int rtreeClose(sqlite3_vtab_cursor *cur){
 */
 static int rtreeEof(sqlite3_vtab_cursor *cur){
   RtreeCursor *pCsr = (RtreeCursor *)cur;
-  return (pCsr->pNode==0);
+  return pCsr->atEOF;
 }
 
 /*
-** The r-tree constraint passed as the second argument to this function is
-** guaranteed to be a MATCH constraint.
-*/
-static int testRtreeGeom(
-  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->xGeom(pConstraint->pGeom, nCoord, aCoord, pbRes);
+** Convert raw bits from the on-disk RTree record into a coordinate value.
+** The on-disk format is big-endian and needs to be converted for little-
+** endian platforms.  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".
+**
+** There are three versions of this macro, one each for little-endian and
+** big-endian processors and a third generic implementation.  The endian-
+** specific implementations are much faster and are preferred if the
+** processor endianness is known at compile-time.  The SQLITE_BYTEORDER
+** macro is part of sqliteInt.h and hence the endian-specific
+** implementation will only be used if this module is compiled as part
+** of the amalgamation.
+*/
+#if defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==1234
+#define RTREE_DECODE_COORD(eInt, a, r) {                        \
+    RtreeCoord c;    /* Coordinate decoded */                   \
+    memcpy(&c.u,a,4);                                           \
+    c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)|                   \
+          ((c.u&0xff)<<24)|((c.u&0xff00)<<8);                   \
+    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
+}
+#elif defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==4321
+#define RTREE_DECODE_COORD(eInt, a, r) {                        \
+    RtreeCoord c;    /* Coordinate decoded */                   \
+    memcpy(&c.u,a,4);                                           \
+    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
+}
+#else
+#define RTREE_DECODE_COORD(eInt, a, r) {                        \
+    RtreeCoord c;    /* Coordinate decoded */                   \
+    c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16)                     \
+           +((u32)a[2]<<8) + a[3];                              \
+    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
 }
+#endif
 
-/* 
-** Cursor pCursor currently points to a cell in a non-leaf page.
-** Set *pbEof to true if the sub-tree headed by the cell is filtered
-** (excluded) by the constraints in the pCursor->aConstraint[] 
-** array, or false otherwise.
-**
-** Return SQLITE_OK if successful or an SQLite error code if an error
-** occurs within a geometry callback.
+/*
+** Check the RTree node or entry given by pCellData and p against the MATCH
+** constraint pConstraint.  
 */
-static int testRtreeCell(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
-  RtreeCell cell;
-  int ii;
-  int bRes = 0;
-  int rc = SQLITE_OK;
-
-  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
-  for(ii=0; bRes==0 && ii<pCursor->nConstraint; ii++){
-    RtreeConstraint *p = &pCursor->aConstraint[ii];
-    RtreeDValue cell_min = DCOORD(cell.aCoord[(p->iCoord>>1)*2]);
-    RtreeDValue cell_max = DCOORD(cell.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: 
-        bRes = p->rValue<cell_min; 
-        break;
-
-      case RTREE_GE: case RTREE_GT: 
-        bRes = p->rValue>cell_max; 
-        break;
-
-      case RTREE_EQ:
-        bRes = (p->rValue>cell_max || p->rValue<cell_min);
-        break;
-
-      default: {
-        assert( p->op==RTREE_MATCH );
-        rc = testRtreeGeom(pRtree, p, &cell, &bRes);
-        bRes = !bRes;
-        break;
-      }
+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 *pInfo = pConstraint->pInfo; /* Callback info */
+  int nCoord = pInfo->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 );
+
+  if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){
+    pInfo->iRowid = readInt64(pCellData);
+  }
+  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*)pInfo,
+                              nCoord, aCoord, &i);
+    if( i==0 ) *peWithin = NOT_WITHIN;
+    *prScore = RTREE_ZERO;
+  }else{
+    pInfo->aCoord = aCoord;
+    pInfo->iLevel = pSearch->iLevel - 1;
+    pInfo->rScore = pInfo->rParentScore = pSearch->rScore;
+    pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin;
+    rc = pConstraint->u.xQueryFunc(pInfo);
+    if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin;
+    if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){
+      *prScore = pInfo->rScore;
     }
   }
-
-  *pbEof = bRes;
   return rc;
 }
 
 /* 
-** Test if the cell that cursor pCursor currently points to
-** would be filtered (excluded) by the constraints in the 
-** pCursor->aConstraint[] array. If so, set *pbEof to true before
-** returning. If the cell is not filtered (excluded) by the constraints,
-** set pbEof to zero.
-**
-** 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 testRtreeEntry(Rtree *pRtree, RtreeCursor *pCursor, int *pbEof){
-  RtreeCell cell;
-  int ii;
-  *pbEof = 0;
-
-  nodeGetCell(pRtree, pCursor->pNode, pCursor->iCell, &cell);
-  for(ii=0; ii<pCursor->nConstraint; ii++){
-    RtreeConstraint *p = &pCursor->aConstraint[ii];
-    RtreeDValue coord = DCOORD(cell.aCoord[p->iCoord]);
-    int res;
-    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->rValue); break;
-      case RTREE_LT: res = (coord<p->rValue);  break;
-      case RTREE_GE: res = (coord>=p->rValue); break;
-      case RTREE_GT: res = (coord>p->rValue);  break;
-      case RTREE_EQ: res = (coord==p->rValue); break;
-      default: {
-        int rc;
-        assert( p->op==RTREE_MATCH );
-        rc = testRtreeGeom(pRtree, p, &cell, &res);
-        if( rc!=SQLITE_OK ){
-          return rc;
-        }
-        break;
-      }
-    }
-
-    if( !res ){
-      *pbEof = 1;
-      return SQLITE_OK;
-    }
-  }
-
-  return SQLITE_OK;
-}
-
-/*
-** Cursor pCursor currently points at a node that heads a sub-tree of
-** height iHeight (if iHeight==0, then the node is a leaf). Descend
-** to point to the left-most cell of the sub-tree that matches the 
-** configured constraints.
-*/
-static int descendToCell(
-  Rtree *pRtree, 
-  RtreeCursor *pCursor, 
-  int iHeight,
-  int *pEof                 /* OUT: Set to true if cannot descend */
+** 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 */
 ){
-  int isEof;
-  int rc;
-  int ii;
-  RtreeNode *pChild;
-  sqlite3_int64 iRowid;
+  sqlite3_rtree_dbl val;     /* Coordinate value convert to a double */
 
-  RtreeNode *pSavedNode = pCursor->pNode;
-  int iSavedCell = pCursor->iCell;
+  /* 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( iHeight>=0 );
+  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 */
 
-  if( iHeight==0 ){
-    rc = testRtreeEntry(pRtree, pCursor, &isEof);
-  }else{
-    rc = testRtreeCell(pRtree, pCursor, &isEof);
-  }
-  if( rc!=SQLITE_OK || isEof || iHeight==0 ){
-    goto descend_to_cell_out;
-  }
-
-  iRowid = nodeGetRowid(pRtree, pCursor->pNode, pCursor->iCell);
-  rc = nodeAcquire(pRtree, iRowid, pCursor->pNode, &pChild);
-  if( rc!=SQLITE_OK ){
-    goto descend_to_cell_out;
+    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;
+}
 
-  nodeRelease(pRtree, pCursor->pNode);
-  pCursor->pNode = pChild;
-  isEof = 1;
-  for(ii=0; isEof && ii<NCELL(pChild); ii++){
-    pCursor->iCell = ii;
-    rc = descendToCell(pRtree, pCursor, iHeight-1, &isEof);
-    if( rc!=SQLITE_OK ){
-      goto descend_to_cell_out;
-    }
-  }
+/*
+** 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 */
 
-  if( isEof ){
-    assert( pCursor->pNode==pChild );
-    nodeReference(pSavedNode);
-    nodeRelease(pRtree, pChild);
-    pCursor->pNode = pSavedNode;
-    pCursor->iCell = iSavedCell;
+  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;
   }
-
-descend_to_cell_out:
-  *pEof = isEof;
-  return rc;
+  *peWithin = NOT_WITHIN;
 }
 
 /*
@@ -1085,6 +1073,7 @@ static int nodeRowidIndex(
 ){
   int ii;
   int nCell = NCELL(pNode);
+  assert( nCell<200 );
   for(ii=0; ii<nCell; ii++){
     if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){
       *piIndex = ii;
@@ -1107,48 +1096,302 @@ static int nodeParentIndex(Rtree *pRtree, RtreeNode *pNode, int *piIndex){
   return SQLITE_OK;
 }
 
-/* 
-** Rtree virtual table module xNext method.
+/*
+** Compare two search points.  Return negative, zero, or positive if the first
+** is less than, equal to, or greater than the second.
+**
+** The rScore is the primary key.  Smaller rScore values come first.
+** If the rScore is a tie, then use iLevel as the tie breaker with smaller
+** iLevel values coming first.  In this way, if rScore is the same for all
+** SearchPoints, then iLevel becomes the deciding factor and the result
+** is a depth-first search, which is the desired default behavior.
+*/
+static int rtreeSearchPointCompare(
+  const RtreeSearchPoint *pA,
+  const RtreeSearchPoint *pB
+){
+  if( pA->rScore<pB->rScore ) return -1;
+  if( pA->rScore>pB->rScore ) return +1;
+  if( pA->iLevel<pB->iLevel ) return -1;
+  if( pA->iLevel>pB->iLevel ) return +1;
+  return 0;
+}
+
+/*
+** Interchange to search points in a cursor.
+*/
+static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
+  RtreeSearchPoint t = p->aPoint[i];
+  assert( i<j );
+  p->aPoint[i] = p->aPoint[j];
+  p->aPoint[j] = t;
+  i++; j++;
+  if( i<RTREE_CACHE_SZ ){
+    if( j>=RTREE_CACHE_SZ ){
+      nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
+      p->aNode[i] = 0;
+    }else{
+      RtreeNode *pTemp = p->aNode[i];
+      p->aNode[i] = p->aNode[j];
+      p->aNode[j] = pTemp;
+    }
+  }
+}
+
+/*
+** Return the search point with the lowest current score.
 */
-static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
-  Rtree *pRtree = (Rtree *)(pVtabCursor->pVtab);
-  RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
-  int rc = SQLITE_OK;
+static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){
+  return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0;
+}
 
-  /* RtreeCursor.pNode must not be NULL. If is is NULL, then this cursor is
-  ** already at EOF. It is against the rules to call the xNext() method of
-  ** a cursor that has already reached EOF.
-  */
-  assert( pCsr->pNode );
+/*
+** Get the RtreeNode for the search point with the lowest score.
+*/
+static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){
+  sqlite3_int64 id;
+  int ii = 1 - pCur->bPoint;
+  assert( ii==0 || ii==1 );
+  assert( pCur->bPoint || pCur->nPoint );
+  if( pCur->aNode[ii]==0 ){
+    assert( pRC!=0 );
+    id = ii ? pCur->aPoint[0].id : pCur->sPoint.id;
+    *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]);
+  }
+  return pCur->aNode[ii];
+}
+
+/*
+** Push a new element onto the priority queue
+*/
+static RtreeSearchPoint *rtreeEnqueue(
+  RtreeCursor *pCur,    /* The cursor */
+  RtreeDValue rScore,   /* Score for the new search point */
+  u8 iLevel             /* Level for the new search point */
+){
+  int i, j;
+  RtreeSearchPoint *pNew;
+  if( pCur->nPoint>=pCur->nPointAlloc ){
+    int nNew = pCur->nPointAlloc*2 + 8;
+    pNew = sqlite3_realloc(pCur->aPoint, nNew*sizeof(pCur->aPoint[0]));
+    if( pNew==0 ) return 0;
+    pCur->aPoint = pNew;
+    pCur->nPointAlloc = nNew;
+  }
+  i = pCur->nPoint++;
+  pNew = pCur->aPoint + i;
+  pNew->rScore = rScore;
+  pNew->iLevel = iLevel;
+  assert( iLevel>=0 && iLevel<=RTREE_MAX_DEPTH );
+  while( i>0 ){
+    RtreeSearchPoint *pParent;
+    j = (i-1)/2;
+    pParent = pCur->aPoint + j;
+    if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break;
+    rtreeSearchPointSwap(pCur, j, i);
+    i = j;
+    pNew = pParent;
+  }
+  return pNew;
+}
+
+/*
+** Allocate a new RtreeSearchPoint and return a pointer to it.  Return
+** NULL if malloc fails.
+*/
+static RtreeSearchPoint *rtreeSearchPointNew(
+  RtreeCursor *pCur,    /* The cursor */
+  RtreeDValue rScore,   /* Score for the new search point */
+  u8 iLevel             /* Level for the new search point */
+){
+  RtreeSearchPoint *pNew, *pFirst;
+  pFirst = rtreeSearchPointFirst(pCur);
+  pCur->anQueue[iLevel]++;
+  if( pFirst==0
+   || pFirst->rScore>rScore 
+   || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
+  ){
+    if( pCur->bPoint ){
+      int ii;
+      pNew = rtreeEnqueue(pCur, rScore, iLevel);
+      if( pNew==0 ) return 0;
+      ii = (int)(pNew - pCur->aPoint) + 1;
+      if( ii<RTREE_CACHE_SZ ){
+        assert( pCur->aNode[ii]==0 );
+        pCur->aNode[ii] = pCur->aNode[0];
+       }else{
+        nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]);
+      }
+      pCur->aNode[0] = 0;
+      *pNew = pCur->sPoint;
+    }
+    pCur->sPoint.rScore = rScore;
+    pCur->sPoint.iLevel = iLevel;
+    pCur->bPoint = 1;
+    return &pCur->sPoint;
+  }else{
+    return rtreeEnqueue(pCur, rScore, iLevel);
+  }
+}
 
-  if( pCsr->iStrategy==1 ){
-    /* This "scan" is a direct lookup by rowid. There is no next entry. */
-    nodeRelease(pRtree, pCsr->pNode);
-    pCsr->pNode = 0;
+#if 0
+/* Tracing routines for the RtreeSearchPoint queue */
+static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){
+  if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); }
+  printf(" %d.%05lld.%02d %g %d",
+    p->iLevel, p->id, p->iCell, p->rScore, p->eWithin
+  );
+  idx++;
+  if( idx<RTREE_CACHE_SZ ){
+    printf(" %p\n", pCur->aNode[idx]);
   }else{
-    /* Move to the next entry that matches the configured constraints. */
-    int iHeight = 0;
-    while( pCsr->pNode ){
-      RtreeNode *pNode = pCsr->pNode;
-      int nCell = NCELL(pNode);
-      for(pCsr->iCell++; pCsr->iCell<nCell; pCsr->iCell++){
-        int isEof;
-        rc = descendToCell(pRtree, pCsr, iHeight, &isEof);
-        if( rc!=SQLITE_OK || !isEof ){
-          return rc;
+    printf("\n");
+  }
+}
+static void traceQueue(RtreeCursor *pCur, const char *zPrefix){
+  int ii;
+  printf("=== %9s ", zPrefix);
+  if( pCur->bPoint ){
+    tracePoint(&pCur->sPoint, -1, pCur);
+  }
+  for(ii=0; ii<pCur->nPoint; ii++){
+    if( ii>0 || pCur->bPoint ) printf("              ");
+    tracePoint(&pCur->aPoint[ii], ii, pCur);
+  }
+}
+# define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B)
+#else
+# define RTREE_QUEUE_TRACE(A,B)   /* no-op */
+#endif
+
+/* Remove the search point with the lowest current score.
+*/
+static void rtreeSearchPointPop(RtreeCursor *p){
+  int i, j, k, n;
+  i = 1 - p->bPoint;
+  assert( i==0 || i==1 );
+  if( p->aNode[i] ){
+    nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
+    p->aNode[i] = 0;
+  }
+  if( p->bPoint ){
+    p->anQueue[p->sPoint.iLevel]--;
+    p->bPoint = 0;
+  }else if( p->nPoint ){
+    p->anQueue[p->aPoint[0].iLevel]--;
+    n = --p->nPoint;
+    p->aPoint[0] = p->aPoint[n];
+    if( n<RTREE_CACHE_SZ-1 ){
+      p->aNode[1] = p->aNode[n+1];
+      p->aNode[n+1] = 0;
+    }
+    i = 0;
+    while( (j = i*2+1)<n ){
+      k = j+1;
+      if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
+        if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
+          rtreeSearchPointSwap(p, i, k);
+          i = k;
+        }else{
+          break;
+        }
+      }else{
+        if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){
+          rtreeSearchPointSwap(p, i, j);
+          i = j;
+        }else{
+          break;
         }
       }
-      pCsr->pNode = pNode->pParent;
-      rc = nodeParentIndex(pRtree, pNode, &pCsr->iCell);
-      if( rc!=SQLITE_OK ){
-        return rc;
+    }
+  }
+}
+
+
+/*
+** Continue the search on cursor pCur until the front of the queue
+** contains an entry suitable for returning as a result-set row,
+** or until the RtreeSearchPoint queue is empty, indicating that the
+** query has completed.
+*/
+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)-1;
+      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);
       }
-      nodeReference(pCsr->pNode);
-      nodeRelease(pRtree, pNode);
-      iHeight++;
+      if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO;
+      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);
     }
   }
+  pCur->atEOF = p==0;
+  return SQLITE_OK;
+}
 
+/* 
+** Rtree virtual table module xNext method.
+*/
+static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
+  RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
+  int rc = SQLITE_OK;
+
+  /* Move to the next entry that matches the configured constraints. */
+  RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
+  rtreeSearchPointPop(pCsr);
+  rc = rtreeStepToLeaf(pCsr);
   return rc;
 }
 
@@ -1156,13 +1399,14 @@ static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
 ** Rtree virtual table module xRowid method.
 */
 static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
-  Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
-
-  assert(pCsr->pNode);
-  *pRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
-
-  return SQLITE_OK;
+  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
+  int rc = SQLITE_OK;
+  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
+  if( rc==SQLITE_OK && p ){
+    *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell);
+  }
+  return rc;
 }
 
 /* 
@@ -1171,13 +1415,18 @@ static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
 static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
   Rtree *pRtree = (Rtree *)cur->pVtab;
   RtreeCursor *pCsr = (RtreeCursor *)cur;
+  RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr);
+  RtreeCoord c;
+  int rc = SQLITE_OK;
+  RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc);
 
+  if( rc ) return rc;
+  if( p==0 ) return SQLITE_OK;
   if( i==0 ){
-    i64 iRowid = nodeGetRowid(pRtree, pCsr->pNode, pCsr->iCell);
-    sqlite3_result_int64(ctx, iRowid);
+    sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell));
   }else{
-    RtreeCoord c;
-    nodeGetCoord(pRtree, pCsr->pNode, pCsr->iCell, i-1, &c);
+    if( rc ) return rc;
+    nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c);
 #ifndef SQLITE_RTREE_INT_ONLY
     if( pRtree->eCoordType==RTREE_COORD_REAL32 ){
       sqlite3_result_double(ctx, c.f);
@@ -1188,7 +1437,6 @@ static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
       sqlite3_result_int(ctx, c.i);
     }
   }
-
   return SQLITE_OK;
 }
 
@@ -1199,12 +1447,18 @@ static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
 ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf
 ** to zero and return an SQLite error code.
 */
-static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
+static int findLeafNode(
+  Rtree *pRtree,              /* RTree to search */
+  i64 iRowid,                 /* The rowid searching for */
+  RtreeNode **ppLeaf,         /* Write the node here */
+  sqlite3_int64 *piNode       /* Write the node-id here */
+){
   int rc;
   *ppLeaf = 0;
   sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid);
   if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){
     i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0);
+    if( piNode ) *piNode = iNode;
     rc = nodeAcquire(pRtree, iNode, 0, ppLeaf);
     sqlite3_reset(pRtree->pReadRowid);
   }else{
@@ -1220,9 +1474,10 @@ static int findLeafNode(Rtree *pRtree, i64 iRowid, RtreeNode **ppLeaf){
 ** operator.
 */
 static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
-  RtreeMatchArg *p;
-  sqlite3_rtree_geometry *pGeom;
-  int nBlob;
+  RtreeMatchArg *pBlob;              /* BLOB returned by geometry function */
+  sqlite3_rtree_query_info *pInfo;   /* Callback information */
+  int nBlob;                         /* Size of the geometry function blob */
+  int nExpected;                     /* Expected size of the BLOB */
 
   /* Check that value is actually a blob. */
   if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR;
@@ -1235,27 +1490,29 @@ static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){
     return SQLITE_ERROR;
   }
 
-  pGeom = (sqlite3_rtree_geometry *)sqlite3_malloc(
-      sizeof(sqlite3_rtree_geometry) + nBlob
-  );
-  if( !pGeom ) return SQLITE_NOMEM;
-  memset(pGeom, 0, sizeof(sqlite3_rtree_geometry));
-  p = (RtreeMatchArg *)&pGeom[1];
+  pInfo = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pInfo)+nBlob );
+  if( !pInfo ) return SQLITE_NOMEM;
+  memset(pInfo, 0, sizeof(*pInfo));
+  pBlob = (RtreeMatchArg*)&pInfo[1];
 
-  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);
+  memcpy(pBlob, sqlite3_value_blob(pValue), nBlob);
+  nExpected = (int)(sizeof(RtreeMatchArg) +
+                    (pBlob->nParam-1)*sizeof(RtreeDValue));
+  if( pBlob->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=nExpected ){
+    sqlite3_free(pInfo);
     return SQLITE_ERROR;
   }
+  pInfo->pContext = pBlob->cb.pContext;
+  pInfo->nParam = pBlob->nParam;
+  pInfo->aParam = pBlob->aParam;
 
-  pGeom->pContext = p->pContext;
-  pGeom->nParam = p->nParam;
-  pGeom->aParam = p->aParam;
-
-  pCons->xGeom = p->xGeom;
-  pCons->pGeom = pGeom;
+  if( pBlob->cb.xGeom ){
+    pCons->u.xGeom = pBlob->cb.xGeom;
+  }else{
+    pCons->op = RTREE_QUERY;
+    pCons->u.xQueryFunc = pBlob->cb.xQueryFunc;
+  }
+  pCons->pInfo = pInfo;
   return SQLITE_OK;
 }
 
@@ -1269,44 +1526,59 @@ static int rtreeFilter(
 ){
   Rtree *pRtree = (Rtree *)pVtabCursor->pVtab;
   RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
-
   RtreeNode *pRoot = 0;
   int ii;
   int rc = SQLITE_OK;
+  int iCell = 0;
 
   rtreeReference(pRtree);
 
+  /* Reset the cursor to the same state as rtreeOpen() leaves it in. */
   freeCursorConstraints(pCsr);
-  pCsr->iStrategy = idxNum;
+  sqlite3_free(pCsr->aPoint);
+  memset(pCsr, 0, sizeof(RtreeCursor));
+  pCsr->base.pVtab = (sqlite3_vtab*)pRtree;
 
+  pCsr->iStrategy = idxNum;
   if( idxNum==1 ){
     /* Special case - lookup by rowid. */
     RtreeNode *pLeaf;        /* Leaf on which the required cell resides */
+    RtreeSearchPoint *p;     /* Search point for the the leaf */
     i64 iRowid = sqlite3_value_int64(argv[0]);
-    rc = findLeafNode(pRtree, iRowid, &pLeaf);
-    pCsr->pNode = pLeaf; 
-    if( pLeaf ){
-      assert( rc==SQLITE_OK );
-      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &pCsr->iCell);
+    i64 iNode = 0;
+    rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode);
+    if( rc==SQLITE_OK && pLeaf!=0 ){
+      p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0);
+      assert( p!=0 );  /* Always returns pCsr->sPoint */
+      pCsr->aNode[0] = pLeaf;
+      p->id = iNode;
+      p->eWithin = PARTLY_WITHIN;
+      rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
+      p->iCell = iCell;
+      RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
+    }else{
+      pCsr->atEOF = 1;
     }
   }else{
     /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
     ** with the configured constraints. 
     */
-    if( argc>0 ){
+    rc = nodeAcquire(pRtree, 1, 0, &pRoot);
+    if( rc==SQLITE_OK && argc>0 ){
       pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
       pCsr->nConstraint = argc;
       if( !pCsr->aConstraint ){
         rc = SQLITE_NOMEM;
       }else{
         memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc);
+        memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1));
         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 ){
+          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.
@@ -1315,41 +1587,35 @@ static int rtreeFilter(
             if( rc!=SQLITE_OK ){
               break;
             }
+            p->pInfo->nCoord = pRtree->nDim*2;
+            p->pInfo->anQueue = pCsr->anQueue;
+            p->pInfo->mxLevel = pRtree->iDepth + 1;
           }else{
 #ifdef SQLITE_RTREE_INT_ONLY
-            p->rValue = sqlite3_value_int64(argv[ii]);
+            p->u.rValue = sqlite3_value_int64(argv[ii]);
 #else
-            p->rValue = sqlite3_value_double(argv[ii]);
+            p->u.rValue = sqlite3_value_double(argv[ii]);
 #endif
           }
         }
       }
     }
-  
-    if( rc==SQLITE_OK ){
-      pCsr->pNode = 0;
-      rc = nodeAcquire(pRtree, 1, 0, &pRoot);
-    }
     if( rc==SQLITE_OK ){
-      int isEof = 1;
-      int nCell = NCELL(pRoot);
-      pCsr->pNode = pRoot;
-      for(pCsr->iCell=0; rc==SQLITE_OK && pCsr->iCell<nCell; pCsr->iCell++){
-        assert( pCsr->pNode==pRoot );
-        rc = descendToCell(pRtree, pCsr, pRtree->iDepth, &isEof);
-        if( !isEof ){
-          break;
-        }
-      }
-      if( rc==SQLITE_OK && isEof ){
-        assert( pCsr->pNode==pRoot );
-        nodeRelease(pRtree, pRoot);
-        pCsr->pNode = 0;
-      }
-      assert( rc!=SQLITE_OK || !pCsr->pNode || pCsr->iCell<NCELL(pCsr->pNode) );
+      RtreeSearchPoint *pNew;
+      pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, pRtree->iDepth+1);
+      if( pNew==0 ) return SQLITE_NOMEM;
+      pNew->id = 1;
+      pNew->iCell = 0;
+      pNew->eWithin = PARTLY_WITHIN;
+      assert( pCsr->bPoint==1 );
+      pCsr->aNode[0] = pRoot;
+      pRoot = 0;
+      RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
+      rc = rtreeStepToLeaf(pCsr);
     }
   }
 
+  nodeRelease(pRtree, pRoot);
   rtreeRelease(pRtree);
   return rc;
 }
@@ -1451,7 +1717,7 @@ static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
           break;
       }
       zIdxStr[iIdx++] = op;
-      zIdxStr[iIdx++] = p->iColumn - 1 + 'a';
+      zIdxStr[iIdx++] = p->iColumn - 1 + '0';
       pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2);
       pIdxInfo->aConstraintUsage[ii].omit = 1;
     }
@@ -1544,62 +1810,32 @@ static RtreeDValue cellGrowth(Rtree *pRtree, RtreeCell *p, RtreeCell *pCell){
   return (cellArea(pRtree, &cell)-area);
 }
 
-#if VARIANT_RSTARTREE_CHOOSESUBTREE || VARIANT_RSTARTREE_SPLIT
 static RtreeDValue cellOverlap(
   Rtree *pRtree, 
   RtreeCell *p, 
   RtreeCell *aCell, 
-  int nCell, 
-  int iExclude
+  int nCell
 ){
   int ii;
-  RtreeDValue overlap = 0.0;
+  RtreeDValue overlap = RTREE_ZERO;
   for(ii=0; ii<nCell; ii++){
-#if VARIANT_RSTARTREE_CHOOSESUBTREE
-    if( ii!=iExclude )
-#else
-    assert( iExclude==-1 );
-    UNUSED_PARAMETER(iExclude);
-#endif
-    {
-      int jj;
-      RtreeDValue o = (RtreeDValue)1;
-      for(jj=0; jj<(pRtree->nDim*2); jj+=2){
-        RtreeDValue x1, x2;
-
-        x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
-        x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
-
-        if( x2<x1 ){
-          o = 0.0;
-          break;
-        }else{
-          o = o * (x2-x1);
-        }
+    int jj;
+    RtreeDValue o = (RtreeDValue)1;
+    for(jj=0; jj<(pRtree->nDim*2); jj+=2){
+      RtreeDValue x1, x2;
+      x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj]));
+      x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1]));
+      if( x2<x1 ){
+        o = (RtreeDValue)0;
+        break;
+      }else{
+        o = o * (x2-x1);
       }
-      overlap += o;
     }
+    overlap += o;
   }
   return overlap;
 }
-#endif
-
-#if VARIANT_RSTARTREE_CHOOSESUBTREE
-static RtreeDValue cellOverlapEnlargement(
-  Rtree *pRtree, 
-  RtreeCell *p, 
-  RtreeCell *pInsert, 
-  RtreeCell *aCell, 
-  int nCell, 
-  int iExclude
-){
-  RtreeDValue before, after;
-  before = cellOverlap(pRtree, p, aCell, nCell, iExclude);
-  cellUnion(pRtree, p, pInsert);
-  after = cellOverlap(pRtree, p, aCell, nCell, iExclude);
-  return (after-before);
-}
-#endif
 
 
 /*
@@ -1621,12 +1857,8 @@ static int ChooseLeaf(
     int iCell;
     sqlite3_int64 iBest = 0;
 
-    RtreeDValue fMinGrowth = 0.0;
-    RtreeDValue fMinArea = 0.0;
-#if VARIANT_RSTARTREE_CHOOSESUBTREE
-    RtreeDValue fMinOverlap = 0.0;
-    RtreeDValue overlap;
-#endif
+    RtreeDValue fMinGrowth = RTREE_ZERO;
+    RtreeDValue fMinArea = RTREE_ZERO;
 
     int nCell = NCELL(pNode);
     RtreeCell cell;
@@ -1634,22 +1866,6 @@ static int ChooseLeaf(
 
     RtreeCell *aCell = 0;
 
-#if VARIANT_RSTARTREE_CHOOSESUBTREE
-    if( ii==(pRtree->iDepth-1) ){
-      int jj;
-      aCell = sqlite3_malloc(sizeof(RtreeCell)*nCell);
-      if( !aCell ){
-        rc = SQLITE_NOMEM;
-        nodeRelease(pRtree, pNode);
-        pNode = 0;
-        continue;
-      }
-      for(jj=0; jj<nCell; jj++){
-        nodeGetCell(pRtree, pNode, jj, &aCell[jj]);
-      }
-    }
-#endif
-
     /* Select the child node which will be enlarged the least if pCell
     ** is inserted into it. Resolve ties by choosing the entry with
     ** the smallest area.
@@ -1661,26 +1877,9 @@ static int ChooseLeaf(
       nodeGetCell(pRtree, pNode, iCell, &cell);
       growth = cellGrowth(pRtree, &cell, pCell);
       area = cellArea(pRtree, &cell);
-
-#if VARIANT_RSTARTREE_CHOOSESUBTREE
-      if( ii==(pRtree->iDepth-1) ){
-        overlap = cellOverlapEnlargement(pRtree,&cell,pCell,aCell,nCell,iCell);
-      }else{
-        overlap = 0.0;
-      }
-      if( (iCell==0) 
-       || (overlap<fMinOverlap) 
-       || (overlap==fMinOverlap && growth<fMinGrowth)
-       || (overlap==fMinOverlap && growth==fMinGrowth && area<fMinArea)
-      ){
-        bBest = 1;
-        fMinOverlap = overlap;
-      }
-#else
       if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){
         bBest = 1;
       }
-#endif
       if( bBest ){
         fMinGrowth = growth;
         fMinArea = area;
@@ -1751,155 +1950,6 @@ static int parentWrite(Rtree *pRtree, sqlite3_int64 iNode, sqlite3_int64 iPar){
 
 static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int);
 
-#if VARIANT_GUTTMAN_LINEAR_SPLIT
-/*
-** Implementation of the linear variant of the PickNext() function from
-** Guttman[84].
-*/
-static RtreeCell *LinearPickNext(
-  Rtree *pRtree,
-  RtreeCell *aCell, 
-  int nCell, 
-  RtreeCell *pLeftBox, 
-  RtreeCell *pRightBox,
-  int *aiUsed
-){
-  int ii;
-  for(ii=0; aiUsed[ii]; ii++);
-  aiUsed[ii] = 1;
-  return &aCell[ii];
-}
-
-/*
-** Implementation of the linear variant of the PickSeeds() function from
-** Guttman[84].
-*/
-static void LinearPickSeeds(
-  Rtree *pRtree,
-  RtreeCell *aCell, 
-  int nCell, 
-  int *piLeftSeed, 
-  int *piRightSeed
-){
-  int i;
-  int iLeftSeed = 0;
-  int iRightSeed = 1;
-  RtreeDValue maxNormalInnerWidth = (RtreeDValue)0;
-
-  /* Pick two "seed" cells from the array of cells. The algorithm used
-  ** here is the LinearPickSeeds algorithm from Gutman[1984]. The 
-  ** indices of the two seed cells in the array are stored in local
-  ** variables iLeftSeek and iRightSeed.
-  */
-  for(i=0; i<pRtree->nDim; i++){
-    RtreeDValue x1 = DCOORD(aCell[0].aCoord[i*2]);
-    RtreeDValue x2 = DCOORD(aCell[0].aCoord[i*2+1]);
-    RtreeDValue x3 = x1;
-    RtreeDValue x4 = x2;
-    int jj;
-
-    int iCellLeft = 0;
-    int iCellRight = 0;
-
-    for(jj=1; jj<nCell; jj++){
-      RtreeDValue left = DCOORD(aCell[jj].aCoord[i*2]);
-      RtreeDValue right = DCOORD(aCell[jj].aCoord[i*2+1]);
-
-      if( left<x1 ) x1 = left;
-      if( right>x4 ) x4 = right;
-      if( left>x3 ){
-        x3 = left;
-        iCellRight = jj;
-      }
-      if( right<x2 ){
-        x2 = right;
-        iCellLeft = jj;
-      }
-    }
-
-    if( x4!=x1 ){
-      RtreeDValue normalwidth = (x3 - x2) / (x4 - x1);
-      if( normalwidth>maxNormalInnerWidth ){
-        iLeftSeed = iCellLeft;
-        iRightSeed = iCellRight;
-      }
-    }
-  }
-
-  *piLeftSeed = iLeftSeed;
-  *piRightSeed = iRightSeed;
-}
-#endif /* VARIANT_GUTTMAN_LINEAR_SPLIT */
-
-#if VARIANT_GUTTMAN_QUADRATIC_SPLIT
-/*
-** Implementation of the quadratic variant of the PickNext() function from
-** Guttman[84].
-*/
-static RtreeCell *QuadraticPickNext(
-  Rtree *pRtree,
-  RtreeCell *aCell, 
-  int nCell, 
-  RtreeCell *pLeftBox, 
-  RtreeCell *pRightBox,
-  int *aiUsed
-){
-  #define FABS(a) ((a)<0.0?-1.0*(a):(a))
-
-  int iSelect = -1;
-  RtreeDValue fDiff;
-  int ii;
-  for(ii=0; ii<nCell; ii++){
-    if( aiUsed[ii]==0 ){
-      RtreeDValue left = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
-      RtreeDValue right = cellGrowth(pRtree, pLeftBox, &aCell[ii]);
-      RtreeDValue diff = FABS(right-left);
-      if( iSelect<0 || diff>fDiff ){
-        fDiff = diff;
-        iSelect = ii;
-      }
-    }
-  }
-  aiUsed[iSelect] = 1;
-  return &aCell[iSelect];
-}
-
-/*
-** Implementation of the quadratic variant of the PickSeeds() function from
-** Guttman[84].
-*/
-static void QuadraticPickSeeds(
-  Rtree *pRtree,
-  RtreeCell *aCell, 
-  int nCell, 
-  int *piLeftSeed, 
-  int *piRightSeed
-){
-  int ii;
-  int jj;
-
-  int iLeftSeed = 0;
-  int iRightSeed = 1;
-  RtreeDValue fWaste = 0.0;
-
-  for(ii=0; ii<nCell; ii++){
-    for(jj=ii+1; jj<nCell; jj++){
-      RtreeDValue right = cellArea(pRtree, &aCell[jj]);
-      RtreeDValue growth = cellGrowth(pRtree, &aCell[ii], &aCell[jj]);
-      RtreeDValue waste = growth - right;
-
-      if( waste>fWaste ){
-        iLeftSeed = ii;
-        iRightSeed = jj;
-        fWaste = waste;
-      }
-    }
-  }
-
-  *piLeftSeed = iLeftSeed;
-  *piRightSeed = iRightSeed;
-}
-#endif /* VARIANT_GUTTMAN_QUADRATIC_SPLIT */
 
 /*
 ** Arguments aIdx, aDistance and aSpare all point to arrays of size
@@ -2040,7 +2090,6 @@ static void SortByDimension(
   }
 }
 
-#if VARIANT_RSTARTREE_SPLIT
 /*
 ** Implementation of the R*-tree variant of SplitNode from Beckman[1990].
 */
@@ -2059,7 +2108,7 @@ static int splitNodeStartree(
 
   int iBestDim = 0;
   int iBestSplit = 0;
-  RtreeDValue fBestMargin = 0.0;
+  RtreeDValue fBestMargin = RTREE_ZERO;
 
   int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int));
 
@@ -2080,9 +2129,9 @@ static int splitNodeStartree(
   }
 
   for(ii=0; ii<pRtree->nDim; ii++){
-    RtreeDValue margin = 0.0;
-    RtreeDValue fBestOverlap = 0.0;
-    RtreeDValue fBestArea = 0.0;
+    RtreeDValue margin = RTREE_ZERO;
+    RtreeDValue fBestOverlap = RTREE_ZERO;
+    RtreeDValue fBestArea = RTREE_ZERO;
     int iBestLeft = 0;
     int nLeft;
 
@@ -2108,7 +2157,7 @@ static int splitNodeStartree(
       }
       margin += cellMargin(pRtree, &left);
       margin += cellMargin(pRtree, &right);
-      overlap = cellOverlap(pRtree, &left, &right, 1, -1);
+      overlap = cellOverlap(pRtree, &left, &right, 1);
       area = cellArea(pRtree, &left) + cellArea(pRtree, &right);
       if( (nLeft==RTREE_MINCELLS(pRtree))
        || (overlap<fBestOverlap)
@@ -2140,63 +2189,7 @@ static int splitNodeStartree(
   sqlite3_free(aaSorted);
   return SQLITE_OK;
 }
-#endif
 
-#if VARIANT_GUTTMAN_SPLIT
-/*
-** Implementation of the regular R-tree SplitNode from Guttman[1984].
-*/
-static int splitNodeGuttman(
-  Rtree *pRtree,
-  RtreeCell *aCell,
-  int nCell,
-  RtreeNode *pLeft,
-  RtreeNode *pRight,
-  RtreeCell *pBboxLeft,
-  RtreeCell *pBboxRight
-){
-  int iLeftSeed = 0;
-  int iRightSeed = 1;
-  int *aiUsed;
-  int i;
-
-  aiUsed = sqlite3_malloc(sizeof(int)*nCell);
-  if( !aiUsed ){
-    return SQLITE_NOMEM;
-  }
-  memset(aiUsed, 0, sizeof(int)*nCell);
-
-  PickSeeds(pRtree, aCell, nCell, &iLeftSeed, &iRightSeed);
-
-  memcpy(pBboxLeft, &aCell[iLeftSeed], sizeof(RtreeCell));
-  memcpy(pBboxRight, &aCell[iRightSeed], sizeof(RtreeCell));
-  nodeInsertCell(pRtree, pLeft, &aCell[iLeftSeed]);
-  nodeInsertCell(pRtree, pRight, &aCell[iRightSeed]);
-  aiUsed[iLeftSeed] = 1;
-  aiUsed[iRightSeed] = 1;
-
-  for(i=nCell-2; i>0; i--){
-    RtreeCell *pNext;
-    pNext = PickNext(pRtree, aCell, nCell, pBboxLeft, pBboxRight, aiUsed);
-    RtreeDValue diff =  
-      cellGrowth(pRtree, pBboxLeft, pNext) - 
-      cellGrowth(pRtree, pBboxRight, pNext)
-    ;
-    if( (RTREE_MINCELLS(pRtree)-NCELL(pRight)==i)
-     || (diff>0.0 && (RTREE_MINCELLS(pRtree)-NCELL(pLeft)!=i))
-    ){
-      nodeInsertCell(pRtree, pRight, pNext);
-      cellUnion(pRtree, pBboxRight, pNext);
-    }else{
-      nodeInsertCell(pRtree, pLeft, pNext);
-      cellUnion(pRtree, pBboxLeft, pNext);
-    }
-  }
-
-  sqlite3_free(aiUsed);
-  return SQLITE_OK;
-}
-#endif
 
 static int updateMapping(
   Rtree *pRtree, 
@@ -2274,7 +2267,8 @@ static int SplitNode(
   memset(pLeft->zData, 0, pRtree->iNodeSize);
   memset(pRight->zData, 0, pRtree->iNodeSize);
 
-  rc = AssignCells(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox);
+  rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
+                         &leftbbox, &rightbbox);
   if( rc!=SQLITE_OK ){
     goto splitnode_out;
   }
@@ -2557,7 +2551,7 @@ static int Reinsert(
   }
 
   for(ii=0; ii<nCell; ii++){
-    aDistance[ii] = 0.0;
+    aDistance[ii] = RTREE_ZERO;
     for(iDim=0; iDim<pRtree->nDim; iDim++){
       RtreeDValue coord = (DCOORD(aCell[ii].aCoord[iDim*2+1]) - 
                                DCOORD(aCell[ii].aCoord[iDim*2]));
@@ -2623,16 +2617,12 @@ static int rtreeInsertCell(
     }
   }
   if( nodeInsertCell(pRtree, pNode, pCell) ){
-#if VARIANT_RSTARTREE_REINSERT
     if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){
       rc = SplitNode(pRtree, pNode, pCell, iHeight);
     }else{
       pRtree->iReinsertHeight = iHeight;
       rc = Reinsert(pRtree, pNode, pCell, iHeight);
     }
-#else
-    rc = SplitNode(pRtree, pNode, pCell, iHeight);
-#endif
   }else{
     rc = AdjustTree(pRtree, pNode, pCell);
     if( rc==SQLITE_OK ){
@@ -2702,7 +2692,7 @@ static int rtreeDeleteRowid(Rtree *pRtree, sqlite3_int64 iDelete){
   ** about to be deleted. 
   */
   if( rc==SQLITE_OK ){
-    rc = findLeafNode(pRtree, iDelete, &pLeaf);
+    rc = findLeafNode(pRtree, iDelete, &pLeaf, 0);
   }
 
   /* Delete the cell in question from the leaf node. */
@@ -2947,26 +2937,32 @@ static int rtreeRename(sqlite3_vtab *pVtab, const char *zNewName){
 ** on sqlite_stat1 data. Otherwise, use RTREE_DEFAULT_ROWEST.
 */
 static int rtreeQueryStat1(sqlite3 *db, Rtree *pRtree){
-  const char *zSql = "SELECT stat FROM sqlite_stat1 WHERE tbl= ? || '_rowid'";
+  const char *zFmt = "SELECT stat FROM %Q.sqlite_stat1 WHERE tbl = '%q_rowid'";
+  char *zSql;
   sqlite3_stmt *p;
   int rc;
   i64 nRow = 0;
 
-  rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0);
-  if( rc==SQLITE_OK ){
-    sqlite3_bind_text(p, 1, pRtree->zName, -1, SQLITE_STATIC);
-    if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0);
-    rc = sqlite3_finalize(p);
-  }else if( rc!=SQLITE_NOMEM ){
-    rc = SQLITE_OK;
-  }
+  zSql = sqlite3_mprintf(zFmt, pRtree->zDb, pRtree->zName);
+  if( zSql==0 ){
+    rc = SQLITE_NOMEM;
+  }else{
+    rc = sqlite3_prepare_v2(db, zSql, -1, &p, 0);
+    if( rc==SQLITE_OK ){
+      if( sqlite3_step(p)==SQLITE_ROW ) nRow = sqlite3_column_int64(p, 0);
+      rc = sqlite3_finalize(p);
+    }else if( rc!=SQLITE_NOMEM ){
+      rc = SQLITE_OK;
+    }
 
-  if( rc==SQLITE_OK ){
-    if( nRow==0 ){
-      pRtree->nRowEst = RTREE_DEFAULT_ROWEST;
-    }else{
-      pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST);
+    if( rc==SQLITE_OK ){
+      if( nRow==0 ){
+        pRtree->nRowEst = RTREE_DEFAULT_ROWEST;
+      }else{
+        pRtree->nRowEst = MAX(nRow, RTREE_MIN_ROWEST);
+      }
     }
+    sqlite3_free(zSql);
   }
 
   return rc;
@@ -3033,7 +3029,8 @@ static int rtreeSqlInit(
     char *zCreate = sqlite3_mprintf(
 "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
 "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
-"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"
+"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,"
+                                  " parentnode INTEGER);"
 "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
       zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
     );
@@ -3235,6 +3232,8 @@ static int rtreeInit(
   if( rc==SQLITE_OK ){
     *ppVtab = (sqlite3_vtab *)pRtree;
   }else{
+    assert( *ppVtab==0 );
+    assert( pRtree->nBusy==1 );
     rtreeRelease(pRtree);
   }
   return rc;
@@ -3245,10 +3244,10 @@ static int rtreeInit(
 ** Implementation of a scalar function that decodes r-tree nodes to
 ** human readable strings. This can be used for debugging and analysis.
 **
-** The scalar function takes two arguments, a blob of data containing
-** an r-tree node, and the number of dimensions the r-tree indexes.
-** For a two-dimensional r-tree structure called "rt", to deserialize
-** all nodes, a statement like:
+** The scalar function takes two arguments: (1) the number of dimensions
+** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing
+** an r-tree node.  For a two-dimensional r-tree structure called "rt", to
+** deserialize all nodes, a statement like:
 **
 **   SELECT rtreenode(2, data) FROM rt_node;
 **
@@ -3281,7 +3280,7 @@ static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
     nCell = (int)strlen(zCell);
     for(jj=0; jj<tree.nDim*2; jj++){
 #ifndef SQLITE_RTREE_INT_ONLY
-      sqlite3_snprintf(512-nCell,&zCell[nCell], " %f",
+      sqlite3_snprintf(512-nCell,&zCell[nCell], " %g",
                        (double)cell.aCoord[jj].f);
 #else
       sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
@@ -3302,6 +3301,15 @@ static void rtreenode(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
   sqlite3_result_text(ctx, zText, -1, sqlite3_free);
 }
 
+/* This routine implements an SQL function that returns the "depth" parameter
+** from the front of a blob that is an r-tree node.  For example:
+**
+**     SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1;
+**
+** The depth value is 0 for all nodes other than the root node, and the root
+** node always has nodeno=1, so the example above is the primary use for this
+** routine.  This routine is intended for testing and analysis only.
+*/
 static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){
   UNUSED_PARAMETER(nArg);
   if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB 
@@ -3344,22 +3352,31 @@ int sqlite3RtreeInit(sqlite3 *db){
 }
 
 /*
-** A version of sqlite3_free() that can be used as a callback. This is used
-** in two places - as the destructor for the blob value returned by the
-** invocation of a geometry function, and as the destructor for the geometry
-** functions themselves.
+** This routine deletes the RtreeGeomCallback object that was attached
+** one of the SQL functions create by sqlite3_rtree_geometry_callback()
+** or sqlite3_rtree_query_callback().  In other words, this routine is the
+** destructor for an RtreeGeomCallback objecct.  This routine is called when
+** the corresponding SQL function is deleted.
 */
-static void doSqlite3Free(void *p){
+static void rtreeFreeCallback(void *p){
+  RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p;
+  if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext);
   sqlite3_free(p);
 }
 
 /*
-** Each call to sqlite3_rtree_geometry_callback() creates an ordinary SQLite
-** scalar user function. This C function is the callback used for all such
-** registered SQL functions.
+** Each call to sqlite3_rtree_geometry_callback() or
+** sqlite3_rtree_query_callback() creates an ordinary SQLite
+** scalar function that is implemented by this routine.
 **
-** The scalar user functions return a blob that is interpreted by r-tree
-** table MATCH operators.
+** All this function does is construct an RtreeMatchArg object that
+** contains the geometry-checking callback routines and a list of
+** parameters to this function, then return that RtreeMatchArg object
+** as a BLOB.
+**
+** The R-Tree MATCH operator will read the returned BLOB, deserialize
+** the RtreeMatchArg object, and use the RtreeMatchArg object to figure
+** out which elements of the R-Tree should be returned by the query.
 */
 static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
   RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx);
@@ -3373,8 +3390,7 @@ static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
   }else{
     int i;
     pBlob->magic = RTREE_GEOMETRY_MAGIC;
-    pBlob->xGeom = pGeomCtx->xGeom;
-    pBlob->pContext = pGeomCtx->pContext;
+    pBlob->cb = pGeomCtx[0];
     pBlob->nParam = nArg;
     for(i=0; i<nArg; i++){
 #ifdef SQLITE_RTREE_INT_ONLY
@@ -3383,7 +3399,7 @@ static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
       pBlob->aParam[i] = sqlite3_value_double(aArg[i]);
 #endif
     }
-    sqlite3_result_blob(ctx, pBlob, nBlob, doSqlite3Free);
+    sqlite3_result_blob(ctx, pBlob, nBlob, sqlite3_free);
   }
 }
 
@@ -3391,10 +3407,10 @@ static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){
 ** Register a new geometry function for use with the r-tree MATCH operator.
 */
 int sqlite3_rtree_geometry_callback(
-  sqlite3 *db,
-  const char *zGeom,
-  int (*xGeom)(sqlite3_rtree_geometry *, int, RtreeDValue *, int *),
-  void *pContext
+  sqlite3 *db,                  /* Register SQL function on this connection */
+  const char *zGeom,            /* Name of the new SQL function */
+  int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */
+  void *pContext                /* Extra data associated with the callback */
 ){
   RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */
 
@@ -3402,12 +3418,36 @@ int sqlite3_rtree_geometry_callback(
   pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
   if( !pGeomCtx ) return SQLITE_NOMEM;
   pGeomCtx->xGeom = xGeom;
+  pGeomCtx->xQueryFunc = 0;
+  pGeomCtx->xDestructor = 0;
   pGeomCtx->pContext = pContext;
-
-  /* Create the new user-function. Register a destructor function to delete
-  ** the context object when it is no longer required.  */
   return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, 
-      (void *)pGeomCtx, geomCallback, 0, 0, doSqlite3Free
+      (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
+  );
+}
+
+/*
+** Register a new 2nd-generation geometry function for use with the
+** r-tree MATCH operator.
+*/
+int sqlite3_rtree_query_callback(
+  sqlite3 *db,                 /* Register SQL function on this connection */
+  const char *zQueryFunc,      /* Name of new SQL function */
+  int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */
+  void *pContext,              /* Extra data passed into the callback */
+  void (*xDestructor)(void*)   /* Destructor for the extra data */
+){
+  RtreeGeomCallback *pGeomCtx;      /* Context object for new user-function */
+
+  /* Allocate and populate the context object. */
+  pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback));
+  if( !pGeomCtx ) return SQLITE_NOMEM;
+  pGeomCtx->xGeom = 0;
+  pGeomCtx->xQueryFunc = xQueryFunc;
+  pGeomCtx->xDestructor = xDestructor;
+  pGeomCtx->pContext = pContext;
+  return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, 
+      (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback
   );
 }
 
diff --git a/lib/libsqlite3/ext/rtree/rtree1.test b/lib/libsqlite3/ext/rtree/rtree1.test
index 275b13264f7..0beb16cc949 100644
--- a/lib/libsqlite3/ext/rtree/rtree1.test
+++ b/lib/libsqlite3/ext/rtree/rtree1.test
@@ -33,6 +33,7 @@ set testprefix rtree1
 #   rtree-8.*: Test constrained scans of r-tree data.
 #
 #   rtree-12.*: Test that on-conflict clauses are supported.
+#   rtree-13.*: Test that bug [d2889096e7bdeac6d] has been fixed.
 #
 
 ifcapable !rtree {
@@ -120,12 +121,13 @@ proc execsql_intout {sql} {
 # Test that it is possible to open an existing database that contains
 # r-tree tables.
 #
-do_test rtree-1.4.1 {
-  execsql {
-    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
-    INSERT INTO t1 VALUES(1, 5.0, 10.0);
-    INSERT INTO t1 VALUES(2, 15.0, 20.0);
-  }
+do_execsql_test rtree-1.4.1a {
+  CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
+  INSERT INTO t1 VALUES(1, 5.0, 10.0);
+  SELECT substr(hex(data),1,40) FROM t1_node;
+} {00000001000000000000000140A0000041200000}
+do_execsql_test rtree-1.4.1b {
+  INSERT INTO t1 VALUES(2, 15.0, 20.0);
 } {}
 do_test rtree-1.4.2 {
   db close
@@ -435,16 +437,18 @@ do_test rtree-11.2 {
 # Test on-conflict clause handling.
 #
 db_delete_and_reopen
-do_execsql_test 12.0 {
+do_execsql_test 12.0.1 {
   CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2);
   INSERT INTO t1 VALUES(1,   1, 2, 3, 4);
+  SELECT substr(hex(data),1,56) FROM t1_node;
+} {00000001000000000000000100000001000000020000000300000004}
+do_execsql_test 12.0.2 {
   INSERT INTO t1 VALUES(2,   2, 3, 4, 5);
   INSERT INTO t1 VALUES(3,   3, 4, 5, 6);
 
   CREATE TABLE source(idx, x1, x2, y1, y2);
   INSERT INTO source VALUES(5, 8, 8, 8, 8);
   INSERT INTO source VALUES(2, 7, 7, 7, 7);
-  
 }
 db_save_and_close
 foreach {tn sql_template testdata} {
@@ -510,4 +514,25 @@ foreach {tn sql_template testdata} {
     db close
   }
 }
+
+#-------------------------------------------------------------------------
+# Test that bug [d2889096e7bdeac6d] has been fixed.
+#
+reset_db
+do_execsql_test 13.1 {
+  CREATE VIRTUAL TABLE t9 USING rtree(id, xmin, xmax);
+  INSERT INTO t9 VALUES(1,0,0);            
+  INSERT INTO t9 VALUES(2,0,0);
+  SELECT * FROM t9 WHERE id IN (1, 2);
+} {1 0.0 0.0 2 0.0 0.0}
+
+do_execsql_test 13.2 {
+  WITH r(x) AS (
+    SELECT 1 UNION ALL
+    SELECT 2 UNION ALL
+    SELECT 3
+  )
+  SELECT * FROM r CROSS JOIN t9 WHERE id=x;
+} {1 1 0.0 0.0 2 2 0.0 0.0}
+
 finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtree6.test b/lib/libsqlite3/ext/rtree/rtree6.test
index bdc9bb41461..cec3a8da410 100644
--- a/lib/libsqlite3/ext/rtree/rtree6.test
+++ b/lib/libsqlite3/ext/rtree/rtree6.test
@@ -57,31 +57,31 @@ do_test rtree6-1.1 {
 
 do_test rtree6-1.2 {
   rtree_strategy {SELECT * FROM t1 WHERE x1>10}
-} {Ea}
+} {E0}
 
 do_test rtree6-1.3 {
   rtree_strategy {SELECT * FROM t1 WHERE x1<10}
-} {Ca}
+} {C0}
 
 do_test rtree6-1.4 {
   rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
-} {Ca}
+} {C0}
 
 do_test rtree6-1.5 {
   rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
-} {Ca}
+} {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:Ca} 
+  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:Ca} 
+  0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 
   0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
 }
 
@@ -92,10 +92,16 @@ do_eqp_test rtree6.2.3 {
   0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)}
 }
 
-do_eqp_test rtree6.2.4 {
+do_eqp_test rtree6.2.4.1 {
+  SELECT * FROM t1,t2 WHERE v=+ii 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.4.2 {
   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 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 
   0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)}
 }
 
@@ -126,7 +132,7 @@ do_test rtree6.3.2 {
       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}
+} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}
 do_test rtree6.3.3 {
   rtree_strategy {
     SELECT * FROM t3 WHERE 
@@ -137,7 +143,7 @@ do_test rtree6.3.3 {
       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}
+} {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0}
 
 do_execsql_test rtree6-3.4 {
   SELECT * FROM t3 WHERE x1>0.5 AND x1>0.8 AND x1>1.1
diff --git a/lib/libsqlite3/ext/rtree/rtreeB.test b/lib/libsqlite3/ext/rtree/rtreeB.test
index 7cb445cc4fa..aeb308eca7e 100644
--- a/lib/libsqlite3/ext/rtree/rtreeB.test
+++ b/lib/libsqlite3/ext/rtree/rtreeB.test
@@ -41,7 +41,7 @@ ifcapable rtree_int_only {
       INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400);
       SELECT rtreenode(2, data) FROM t1_node;
     }
-  } {{{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}}}
+  } {{{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}}}
 }
 
 finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtreeC.test b/lib/libsqlite3/ext/rtree/rtreeC.test
index 2e5bedec965..94db05a4d1b 100644
--- a/lib/libsqlite3/ext/rtree/rtreeC.test
+++ b/lib/libsqlite3/ext/rtree/rtreeC.test
@@ -29,7 +29,7 @@ do_eqp_test 1.1 {
   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}
+  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
 }
 
 do_eqp_test 1.2 {
@@ -37,7 +37,7 @@ do_eqp_test 1.2 {
   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}
+  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
 }
 
 do_eqp_test 1.3 {
@@ -45,7 +45,7 @@ do_eqp_test 1.3 {
   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}
+  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
 }
 
 do_eqp_test 1.5 {
@@ -82,7 +82,7 @@ do_eqp_test 2.1 {
   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}
+  0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
 }
 
 do_eqp_test 2.2 {
@@ -90,7 +90,7 @@ do_eqp_test 2.2 {
   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}
+  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
 }
 
 do_eqp_test 2.3 {
@@ -98,7 +98,7 @@ do_eqp_test 2.3 {
   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}
+  0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0}
 }
 
 do_eqp_test 2.5 {
@@ -158,5 +158,116 @@ do_execsql_test 4.3 {
   SELECT b, a FROM t2 LEFT JOIN t1 ON (+a = +b);
 } {1 1 3 {}}
 
-finish_test
+#--------------------------------------------------------------------
+# Test that the sqlite_stat1 data is used correctly.
+#
+reset_db
+do_execsql_test 5.1 {
+  CREATE TABLE t1(x PRIMARY KEY, y);
+  CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2);
+
+  INSERT INTO t1(x) VALUES(1);
+  INSERT INTO t1(x) SELECT x+1 FROM t1;   --   2
+  INSERT INTO t1(x) SELECT x+2 FROM t1;   --   4
+  INSERT INTO t1(x) SELECT x+4 FROM t1;   --   8
+  INSERT INTO t1(x) SELECT x+8 FROM t1;   --  16
+  INSERT INTO t1(x) SELECT x+16 FROM t1;  --  32
+  INSERT INTO t1(x) SELECT x+32 FROM t1;  --  64
+  INSERT INTO t1(x) SELECT x+64 FROM t1;  -- 128
+  INSERT INTO t1(x) SELECT x+128 FROM t1; -- 256
+  INSERT INTO t1(x) SELECT x+256 FROM t1; -- 512
+  INSERT INTO t1(x) SELECT x+512 FROM t1; --1024
+
+  INSERT INTO rt SELECT x, x, x+1 FROM t1 WHERE x<=5;
+}
+
+# First test a query with no ANALYZE data at all. The outer loop is
+# real table "t1".
+#
+do_eqp_test 5.2 {
+  SELECT * FROM t1, rt WHERE x==id;
+} {
+  0 0 0 {SCAN TABLE t1} 
+  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 1:}
+}
+
+# Now create enough ANALYZE data to tell SQLite that virtual table "rt"
+# contains very few rows. This causes it to move "rt" to the outer loop.
+#
+do_execsql_test 5.3 {
+  ANALYZE;
+  DELETE FROM sqlite_stat1 WHERE tbl='t1';
+}
+db close
+sqlite3 db test.db
+do_eqp_test 5.4 {
+  SELECT * FROM t1, rt WHERE x==id;
+} {
+  0 0 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 2:} 
+  0 1 0 {SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (x=?)}
+}
+
+# Delete the ANALYZE data. "t1" should be the outer loop again.
+#
+do_execsql_test 5.5 { DROP TABLE sqlite_stat1; }
+db close
+sqlite3 db test.db
+do_eqp_test 5.6 {
+  SELECT * FROM t1, rt WHERE x==id;
+} {
+  0 0 0 {SCAN TABLE t1} 
+  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 1:}
+}
 
+# This time create and attach a database that contains ANALYZE data for
+# tables of the same names as those used internally by virtual table
+# "rt". Check that the rtree module is not fooled into using this data.
+# Table "t1" should remain the outer loop.
+#
+do_test 5.7 {
+  db backup test.db2
+  sqlite3 db2 test.db2
+  db2 eval {
+    ANALYZE;
+    DELETE FROM sqlite_stat1 WHERE tbl='t1';
+  }
+  db2 close
+  db close
+  sqlite3 db test.db
+  execsql { ATTACH 'test.db2' AS aux; }
+} {}
+do_eqp_test 5.8 {
+  SELECT * FROM t1, rt WHERE x==id;
+} {
+  0 0 0 {SCAN TABLE t1} 
+  0 1 1 {SCAN TABLE rt VIRTUAL TABLE INDEX 1:}
+}
+
+#--------------------------------------------------------------------
+# Test that having a second connection drop the sqlite_stat1 table
+# before it is required by rtreeConnect() does not cause problems.
+#
+ifcapable rtree {
+  reset_db
+  do_execsql_test 6.1 {
+    CREATE TABLE t1(x);
+    CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2);
+    INSERT INTO t1 VALUES(1);
+    INSERT INTO rt VALUES(1,2,3);
+    ANALYZE;
+  }
+  db close
+  sqlite3 db test.db
+  do_execsql_test 6.2 { SELECT * FROM t1 } {1}
+  
+  do_test 6.3 {
+    sqlite3 db2 test.db
+    db2 eval { DROP TABLE sqlite_stat1 }
+    db2 close
+    execsql { SELECT * FROM rt }
+  } {1 2.0 3.0}
+  db close
+}
+
+
+finish_test
diff --git a/lib/libsqlite3/ext/rtree/rtreeE.test b/lib/libsqlite3/ext/rtree/rtreeE.test
new file mode 100644
index 00000000000..c450623790e
--- /dev/null
+++ b/lib/libsqlite3/ext/rtree/rtreeE.test
@@ -0,0 +1,129 @@
+# 2010 August 28
+#
+# The author disclaims copyright to this source code.  In place of
+# a legal notice, here is a blessing:
+#
+#    May you do good and not evil.
+#    May you find forgiveness for yourself and forgive others.
+#    May you share freely, never taking more than you give.
+#
+#***********************************************************************
+# This file contains tests for the r-tree module. Specifically, it tests
+# that new-style custom r-tree queries (geometry callbacks) work.
+# 
+
+if {![info exists testdir]} {
+  set testdir [file join [file dirname [info script]] .. .. test]
+} 
+source $testdir/tester.tcl
+ifcapable !rtree { finish_test ; return }
+ifcapable rtree_int_only { finish_test; return }
+
+
+#-------------------------------------------------------------------------
+# Test the example 2d "circle" geometry callback.
+#
+register_circle_geom db
+
+do_execsql_test rtreeE-1.1 {
+  PRAGMA page_size=512;
+  CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1);
+  
+  /* A tight pattern of small boxes near 0,0 */
+  WITH RECURSIVE
+    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
+    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
+  INSERT INTO rt1 SELECT x+5*y, x, x+2, y, y+2 FROM x, y;
+
+  /* A looser pattern of small boxes near 100, 0 */
+  WITH RECURSIVE
+    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
+    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
+  INSERT INTO rt1 SELECT 100+x+5*y, x*3+100, x*3+102, y*3, y*3+2 FROM x, y;
+
+  /* A looser pattern of larger boxes near 0, 200 */
+  WITH RECURSIVE
+    x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4),
+    y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4)
+  INSERT INTO rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y;
+} {}
+
+# Queries against each of the three clusters */
+do_execsql_test rtreeE-1.1 {
+  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id;
+} {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}
+do_execsql_test rtreeE-1.2 {
+  SELECT id FROM rt1 WHERE id MATCH Qcircle(100.0, 0.0, 50.0, 3) ORDER BY id;
+} {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}
+do_execsql_test rtreeE-1.3 {
+  SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 200.0, 50.0, 3) ORDER BY id;
+} {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}
+
+# The Qcircle geometry function gives a lower score to larger leaf-nodes.
+# This causes the 200s to sort before the 100s and the 0s to sort before
+# last.
+#
+do_execsql_test rtreeE-1.4 {
+  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,3) AND id%100==0
+} {200 100 0}
+
+# Exclude odd rowids on a depth-first search
+do_execsql_test rtreeE-1.5 {
+  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,4) ORDER BY +id
+} {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224}
+
+# Exclude odd rowids on a breadth-first search.
+do_execsql_test rtreeE-1.6 {
+  SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,5) ORDER BY +id
+} {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224}
+
+# Construct a large 2-D RTree with thousands of random entries.
+#
+do_test rtreeE-2.1 {
+  db eval {
+    CREATE TABLE t2(id,x0,x1,y0,y1);
+    CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1);
+    BEGIN;
+  }
+  expr srand(0)
+  for {set i 1} {$i<=10000} {incr i} {
+    set dx [expr {int(rand()*40)+1}]
+    set dy [expr {int(rand()*40)+1}]
+    set x0 [expr {int(rand()*(10000 - $dx))}]
+    set x1 [expr {$x0+$dx}]
+    set y0 [expr {int(rand()*(10000 - $dy))}]
+    set y1 [expr {$y0+$dy}]
+    set id [expr {$i+10000}]
+    db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)}
+  }
+  db eval {
+    INSERT INTO rt2 SELECT * FROM t2;
+    COMMIT;
+  }
+} {}
+
+for {set i 1} {$i<=200} {incr i} {
+  set dx [expr {int(rand()*100)}]
+  set dy [expr {int(rand()*100)}]
+  set x0 [expr {int(rand()*(10000 - $dx))}]
+  set x1 [expr {$x0+$dx}]
+  set y0 [expr {int(rand()*(10000 - $dy))}]
+  set y1 [expr {$y0+$dy}]
+  set ans [db eval {SELECT id FROM t2 WHERE x1>=$x0 AND x0<=$x1 AND y1>=$y0 AND y0<=$y1 ORDER BY id}]
+  do_execsql_test rtreeE-2.2.$i {
+    SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ORDER BY id
+  } $ans
+}
+
+# Run query that have very deep priority queues
+#
+set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=5000 AND y1>=0 AND y0<=5000 ORDER BY id}]
+do_execsql_test rtreeE-2.3 {
+  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,5000,0,5000) ORDER BY id
+} $ans
+set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=10000 AND y1>=0 AND y0<=10000 ORDER BY id}]
+do_execsql_test rtreeE-2.4 {
+  SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,10000,0,10000) ORDER BY id
+} $ans
+
+finish_test
diff --git a/lib/libsqlite3/ext/rtree/sqlite3rtree.h b/lib/libsqlite3/ext/rtree/sqlite3rtree.h
index c849091f29a..5de0508d002 100644
--- a/lib/libsqlite3/ext/rtree/sqlite3rtree.h
+++ b/lib/libsqlite3/ext/rtree/sqlite3rtree.h
@@ -21,6 +21,16 @@ extern "C" {
 #endif
 
 typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
+typedef struct sqlite3_rtree_query_info sqlite3_rtree_query_info;
+
+/* The double-precision datatype used by RTree depends on the
+** SQLITE_RTREE_INT_ONLY compile-time option.
+*/
+#ifdef SQLITE_RTREE_INT_ONLY
+  typedef sqlite3_int64 sqlite3_rtree_dbl;
+#else
+  typedef double sqlite3_rtree_dbl;
+#endif
 
 /*
 ** Register a geometry callback named zGeom that can be used as part of an
@@ -31,11 +41,7 @@ typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry;
 int sqlite3_rtree_geometry_callback(
   sqlite3 *db,
   const char *zGeom,
-#ifdef SQLITE_RTREE_INT_ONLY
-  int (*xGeom)(sqlite3_rtree_geometry*, int n, sqlite3_int64 *a, int *pRes),
-#else
-  int (*xGeom)(sqlite3_rtree_geometry*, int n, double *a, int *pRes),
-#endif
+  int (*xGeom)(sqlite3_rtree_geometry*, int, sqlite3_rtree_dbl*,int*),
   void *pContext
 );
 
@@ -47,11 +53,60 @@ int sqlite3_rtree_geometry_callback(
 struct sqlite3_rtree_geometry {
   void *pContext;                 /* Copy of pContext passed to s_r_g_c() */
   int nParam;                     /* Size of array aParam[] */
-  double *aParam;                 /* Parameters passed to SQL geom function */
+  sqlite3_rtree_dbl *aParam;      /* Parameters passed to SQL geom function */
   void *pUser;                    /* Callback implementation user data */
   void (*xDelUser)(void *);       /* Called by SQLite to clean up pUser */
 };
 
+/*
+** Register a 2nd-generation geometry callback named zScore that can be 
+** used as part of an R-Tree geometry query as follows:
+**
+**   SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zQueryFunc(... params ...)
+*/
+int sqlite3_rtree_query_callback(
+  sqlite3 *db,
+  const char *zQueryFunc,
+  int (*xQueryFunc)(sqlite3_rtree_query_info*),
+  void *pContext,
+  void (*xDestructor)(void*)
+);
+
+
+/*
+** A pointer to a structure of the following type is passed as the 
+** argument to scored geometry callback registered using
+** sqlite3_rtree_query_callback().
+**
+** Note that the first 5 fields of this structure are identical to
+** sqlite3_rtree_geometry.  This structure is a subclass of
+** sqlite3_rtree_geometry.
+*/
+struct sqlite3_rtree_query_info {
+  void *pContext;                   /* pContext from when function registered */
+  int nParam;                       /* Number of function parameters */
+  sqlite3_rtree_dbl *aParam;        /* value of function parameters */
+  void *pUser;                      /* callback can use this, if desired */
+  void (*xDelUser)(void*);          /* function to free pUser */
+  sqlite3_rtree_dbl *aCoord;        /* Coordinates of node or entry to check */
+  unsigned int *anQueue;            /* Number of pending entries in the queue */
+  int nCoord;                       /* Number of coordinates */
+  int iLevel;                       /* Level of current node or entry */
+  int mxLevel;                      /* The largest iLevel value in the tree */
+  sqlite3_int64 iRowid;             /* Rowid for current entry */
+  sqlite3_rtree_dbl rParentScore;   /* Score of parent node */
+  int eParentWithin;                /* Visibility of parent node */
+  int eWithin;                      /* OUT: Visiblity */
+  sqlite3_rtree_dbl rScore;         /* OUT: Write the score here */
+};
+
+/*
+** Allowed values for sqlite3_rtree_query.eWithin and .eParentWithin.
+*/
+#define NOT_WITHIN       0   /* Object completely outside of query region */
+#define PARTLY_WITHIN    1   /* Object partially overlaps query region */
+#define FULLY_WITHIN     2   /* Object fully contained within query region */
+
 
 #ifdef __cplusplus
 }  /* end of the 'extern "C"' block */