SQLite

Check-in [b9fb95194d]
Login

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

Overview
Comment:Have r-tree prefer to use the constraint "col MATCH ?" over "rowid = ?".
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b9fb95194d4f7c535f1d175fd2e18d69d76e8fc4
User & Date: dan 2015-05-22 16:08:42.447
Context
2015-05-22
17:29
The SRT_Table type for the SelectDest object is now just an SRT_EphemTab for which the ephemeral table has already been allocated. (check-in: b9727e6bbf user: drh tags: trunk)
16:08
Have r-tree prefer to use the constraint "col MATCH ?" over "rowid = ?". (check-in: b9fb95194d user: dan tags: trunk)
13:09
Fix two faulty assert statements discovered by fuzzing. (check-in: 799817bfb2 user: drh tags: trunk)
2015-05-21
20:26
Have r-tree prefer to use the constraint "col MATCH ?" over "rowid = ?". drh added later: All changes on this branch have been cherrypicked to trunk and will be merged into sessions from trunk. So this branch can close. (Closed-Leaf check-in: b9e45596d8 user: dan tags: sessions-value-dup)
Changes
Unified Diff Ignore Whitespace Patch
Changes to ext/rtree/rtree.c.
1665
1666
1667
1668
1669
1670
1671

1672
1673
1674
1675
1676










1677
1678
1679
1680
1681

1682

1683
1684
1685
1686
1687
1688
1689
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  Rtree *pRtree = (Rtree*)tab;
  int rc = SQLITE_OK;
  int ii;

  i64 nRow;                       /* Estimated rows returned by this scan */

  int iIdx = 0;
  char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
  memset(zIdxStr, 0, sizeof(zIdxStr));











  assert( pIdxInfo->idxStr==0 );
  for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
    struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];


    if( p->usable && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){

      /* We have an equality constraint on the rowid. Use strategy 1. */
      int jj;
      for(jj=0; jj<ii; jj++){
        pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
        pIdxInfo->aConstraintUsage[jj].omit = 0;
      }
      pIdxInfo->idxNum = 1;







>





>
>
>
>
>
>
>
>
>
>





>
|
>







1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
** to which the constraint applies. The leftmost coordinate column
** is 'a', the second from the left 'b' etc.
*/
static int rtreeBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  Rtree *pRtree = (Rtree*)tab;
  int rc = SQLITE_OK;
  int ii;
  int bMatch = 0;                 /* True if there exists a MATCH constraint */
  i64 nRow;                       /* Estimated rows returned by this scan */

  int iIdx = 0;
  char zIdxStr[RTREE_MAX_DIMENSIONS*8+1];
  memset(zIdxStr, 0, sizeof(zIdxStr));

  /* Check if there exists a MATCH constraint - even an unusable one. If there
  ** is, do not consider the lookup-by-rowid plan as using such a plan would
  ** require the VDBE to evaluate the MATCH constraint, which is not currently
  ** possible. */
  for(ii=0; ii<pIdxInfo->nConstraint; ii++){
    if( pIdxInfo->aConstraint[ii].op==SQLITE_INDEX_CONSTRAINT_MATCH ){
      bMatch = 1;
    }
  }

  assert( pIdxInfo->idxStr==0 );
  for(ii=0; ii<pIdxInfo->nConstraint && iIdx<(int)(sizeof(zIdxStr)-1); ii++){
    struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii];

    if( bMatch==0 && p->usable 
     && p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ 
    ){
      /* We have an equality constraint on the rowid. Use strategy 1. */
      int jj;
      for(jj=0; jj<ii; jj++){
        pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
        pIdxInfo->aConstraintUsage[jj].omit = 0;
      }
      pIdxInfo->idxNum = 1;
Changes to ext/rtree/rtreeE.test.
72
73
74
75
76
77
78







79
80
81
82
83
84
85
  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);







>
>
>
>
>
>
>







72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
  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}

# Test that rtree prefers MATCH to lookup-by-rowid.
#
do_execsql_test rtreeE-1.7 {
  SELECT id FROM rt1 WHERE id=18 AND id MATCH Qcircle(0,0,1000,5)
} {18}


# 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);
121
122
123
124
125
126
127
128

129
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








>

128
129
130
131
132
133
134
135
136
137
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