SQLite

Check-in [9abe023e1a]
Login

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

Overview
Comment:Do not allow auxiliary columns in the rtree to interfere with query planning. Begin adding test cases.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | aux-data-in-rtree
Files: files | file ages | folders
SHA3-256: 9abe023e1afa7dc1a7eba7fbb3128401de129873d86b7c71c221decca26a821c
User & Date: drh 2018-05-16 19:07:07.322
Context
2018-05-16
19:56
Fix an issue with rtreecheck() and auxiliary data columns. (check-in: 4671513607 user: drh tags: aux-data-in-rtree)
19:07
Do not allow auxiliary columns in the rtree to interfere with query planning. Begin adding test cases. (check-in: 9abe023e1a user: drh tags: aux-data-in-rtree)
18:18
Fix the OOM issue mentioned in the previous check-in. (check-in: c489d8e44e user: drh tags: aux-data-in-rtree)
Changes
Unified Diff Show Whitespace Changes Patch
Changes to ext/rtree/rtree.c.
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

35
36
37
38
39
40
41
** The data structure for a single virtual r-tree table is stored in three 
** native SQLite tables declared as follows. In each case, the '%' character
** in the table name is replaced with the user-supplied name of the r-tree
** table.
**
**   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
**
** The data for each node of the r-tree structure is stored in the %_node
** table. For each node that is not the root node of the r-tree, there is
** an entry in the %_parent table associating the node with its parent.
** And for each row of data in the table, there is an entry in the %_rowid
** table that maps from the entries rowid to the id of the node that it
** is stored on.

**
** The root node of an r-tree always exists, even if the r-tree table is
** empty. The nodeno of the root node is always 1. All other nodes in the
** table must be the same size as the root node. The content of each node
** is formatted as follows:
**
**   1. If the node is the root node (node 1), then the first 2 bytes







|






|
>







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
** The data structure for a single virtual r-tree table is stored in three 
** native SQLite tables declared as follows. In each case, the '%' character
** in the table name is replaced with the user-supplied name of the r-tree
** table.
**
**   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
**
** The data for each node of the r-tree structure is stored in the %_node
** table. For each node that is not the root node of the r-tree, there is
** an entry in the %_parent table associating the node with its parent.
** And for each row of data in the table, there is an entry in the %_rowid
** table that maps from the entries rowid to the id of the node that it
** is stored on.  If the r-tree contains auxiliary columns, those are stored
** on the end of the %_rowid table.
**
** The root node of an r-tree always exists, even if the r-tree table is
** empty. The nodeno of the root node is always 1. All other nodes in the
** table must be the same size as the root node. The content of each node
** is formatted as follows:
**
**   1. If the node is the root node (node 1), then the first 2 bytes
1886
1887
1888
1889
1890
1891
1892


1893

1894
1895
1896
1897
1898
1899
1900
      ** a single row.
      */ 
      pIdxInfo->estimatedCost = 30.0;
      pIdxInfo->estimatedRows = 1;
      return SQLITE_OK;
    }



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

      u8 op;
      switch( p->op ){
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;







>
>
|
>







1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
      ** a single row.
      */ 
      pIdxInfo->estimatedCost = 30.0;
      pIdxInfo->estimatedRows = 1;
      return SQLITE_OK;
    }

    if( p->usable
    && ((p->iColumn>0 && p->iColumn<=pRtree->nDim2)
        || p->op==SQLITE_INDEX_CONSTRAINT_MATCH)
    ){
      u8 op;
      switch( p->op ){
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
        case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
        case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
        case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
        case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
  /* Create/Connect to the underlying relational database schema. If
  ** that is successful, call sqlite3_declare_vtab() to configure
  ** the r-tree table schema.
  */
  pSql = sqlite3_str_new(db);
  sqlite3_str_appendf(pSql, "CREATE TABLE x(%s", argv[3]);
  for(ii=4; ii<argc; ii++){
    if( sqlite3_strlike("aux:%", argv[ii], 0)==0 ){
      pRtree->nAux++;
      sqlite3_str_appendf(pSql, ",%s", argv[ii]+4);
    }else if( pRtree->nAux>0 ){
      break;
    }else{
      pRtree->nDim2++;
      sqlite3_str_appendf(pSql, ",%s", argv[ii]);
    }
  }







|

|







3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
  /* Create/Connect to the underlying relational database schema. If
  ** that is successful, call sqlite3_declare_vtab() to configure
  ** the r-tree table schema.
  */
  pSql = sqlite3_str_new(db);
  sqlite3_str_appendf(pSql, "CREATE TABLE x(%s", argv[3]);
  for(ii=4; ii<argc; ii++){
    if( argv[ii][0]=='+' ){
      pRtree->nAux++;
      sqlite3_str_appendf(pSql, ",%s", argv[ii]+1);
    }else if( pRtree->nAux>0 ){
      break;
    }else{
      pRtree->nDim2++;
      sqlite3_str_appendf(pSql, ",%s", argv[ii]);
    }
  }
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893

/*
** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
** (if bLeaf==1) table contains a specified entry. The schemas of the
** two tables are:
**
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
**
** In both cases, this function checks that there exists an entry with
** IPK value iKey and the second column set to iVal.
**
*/
static void rtreeCheckMapping(
  RtreeCheck *pCheck,             /* RtreeCheck object */
  int bLeaf,                      /* True for a leaf cell, false for interior */
  i64 iKey,                       /* Key for mapping */
  i64 iVal                        /* Expected value for mapping */
){
  int rc;
  sqlite3_stmt *pStmt;
  const char *azSql[2] = {
    "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?",
    "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?"
  };

  assert( bLeaf==0 || bLeaf==1 );
  if( pCheck->aCheckMapping[bLeaf]==0 ){
    pCheck->aCheckMapping[bLeaf] = rtreeCheckPrepare(pCheck,
        azSql[bLeaf], pCheck->zDb, pCheck->zTab
    );







|














|
|







3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897

/*
** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
** (if bLeaf==1) table contains a specified entry. The schemas of the
** two tables are:
**
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
**
** In both cases, this function checks that there exists an entry with
** IPK value iKey and the second column set to iVal.
**
*/
static void rtreeCheckMapping(
  RtreeCheck *pCheck,             /* RtreeCheck object */
  int bLeaf,                      /* True for a leaf cell, false for interior */
  i64 iKey,                       /* Key for mapping */
  i64 iVal                        /* Expected value for mapping */
){
  int rc;
  sqlite3_stmt *pStmt;
  const char *azSql[2] = {
    "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?1",
    "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?1"
  };

  assert( bLeaf==0 || bLeaf==1 );
  if( pCheck->aCheckMapping[bLeaf]==0 ){
    pCheck->aCheckMapping[bLeaf] = rtreeCheckPrepare(pCheck,
        azSql[bLeaf], pCheck->zDb, pCheck->zTab
    );
Changes to ext/rtree/rtree3.test.
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
} -body {
  execsql { DROP TABLE rt } 
}

do_malloc_test rtree3-3.prep {
  faultsim_delete_and_reopen
  execsql {
    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
  }
  faultsim_save_and_close
} {}

do_faultsim_test rtree3-3a -faults oom* -prep {
  faultsim_restore_and_reopen







|







77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
} -body {
  execsql { DROP TABLE rt } 
}

do_malloc_test rtree3-3.prep {
  faultsim_delete_and_reopen
  execsql {
    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2, +a1, +a2);
    INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
  }
  faultsim_save_and_close
} {}

do_faultsim_test rtree3-3a -faults oom* -prep {
  faultsim_restore_and_reopen
Changes to ext/rtree/rtreeC.test.
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

#--------------------------------------------------------------------
# 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;
}
do_rtree_integrity_test 5.1.1 rt

# First test a query with no ANALYZE data at all. The outer loop is
# real table "t1".
#
do_eqp_test 5.2 {







|













|







174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

#--------------------------------------------------------------------
# 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, +d1);

  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, printf('x%04xy',x) FROM t1 WHERE x<=5;
}
do_rtree_integrity_test 5.1.1 rt

# First test a query with no ANALYZE data at all. The outer loop is
# real table "t1".
#
do_eqp_test 5.2 {
Added ext/rtree/rtreeH.test.
































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
# 2018-05-16
#
# 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 the
# auxiliary column mechanism.

if {![info exists testdir]} {
  set testdir [file join [file dirname [info script]] .. .. test]
} 
source [file join [file dirname [info script]] rtree_util.tcl]
source $testdir/tester.tcl
ifcapable !rtree { finish_test ; return }

do_execsql_test rtreeH-100 {
  CREATE VIRTUAL TABLE t1 USING rtree(id,x0,x1,y0,y1,+label,+other);
  INSERT INTO t1(x0,x1,y0,y1,label) VALUES
    (0,10,0,10,'lower-left corner'),
    (0,10,90,100,'upper-left corner'),
    (90,100,0,10,'lower-right corner'),
    (90,100,90,100,'upper-right corner'),
    (40,60,40,60,'center'),
    (0,5,0,100,'left edge'),
    (95,100,0,100,'right edge'),
    (0,100,0,5,'bottom edge'),
    (0,100,95,100,'top edge'),
    (0,100,0,100,'the whole thing'),
    (0,50,0,100,'left half'),
    (51,100,0,100,'right half'),
    (0,100,0,50,'bottom half'),
    (0,100,51,100,'top half');
} {}
do_execsql_test rtreeH-101 {
  SELECT * FROM t1_rowid ORDER BY rowid
} {1 1 {lower-left corner} {} 2 1 {upper-left corner} {} 3 1 {lower-right corner} {} 4 1 {upper-right corner} {} 5 1 center {} 6 1 {left edge} {} 7 1 {right edge} {} 8 1 {bottom edge} {} 9 1 {top edge} {} 10 1 {the whole thing} {} 11 1 {left half} {} 12 1 {right half} {} 13 1 {bottom half} {} 14 1 {top half} {}}

do_execsql_test rtreeH-102 {
  SELECT * FROM t1 WHERE rowid=5;
} {5 40.0 60.0 40.0 60.0 center {}}
do_execsql_test rtreeH-103 {
  SELECT * FROM t1 WHERE label='center';
} {5 40.0 60.0 40.0 60.0 center {}}

do_rtree_integrity_test rtreeH-110 t1

do_execsql_test rtreeH-120 {
  SELECT label FROM t1 WHERE x1<=50 ORDER BY id
} {{lower-left corner} {upper-left corner} {left edge} {left half}}
do_execsql_test rtreeH-121 {
  SELECT label FROM t1 WHERE x1<=50 AND label NOT LIKE '%corner%' ORDER BY id
} {{left edge} {left half}}

do_execsql_test rtreeH-200 {
  WITH RECURSIVE
    c1(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c1 WHERE x<99),
    c2(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM c2 WHERE y<99)
  INSERT INTO t1(id, x0,x1,y0,y1,label)
    SELECT 1000+x+y*100, x, x+1, y, y+1, printf('box-%d,%d',x,y) FROM c1, c2;
} {}

do_execsql_test rtreeH-210 {
  SELECT label FROM t1 WHERE x0>=48 AND x1<=50 AND y0>=48 AND y1<=50
     ORDER BY id;
} {box-48,48 box-49,48 box-48,49 box-49,49}

do_execsql_test rtreeH-300 {
  UPDATE t1 SET label='x'||label
    WHERE x0>=49 AND x1<=50 AND y0>=49 AND y1<=50;
  SELECT label FROM t1 WHERE x0>=48 AND x1<=50 AND y0>=48 AND y1<=50
     ORDER BY id;
} {box-48,48 box-49,48 box-48,49 xbox-49,49}


finish_test