/ Check-in [9abe023e]
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 | SQL 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
Context
2018-05-16
19:56
Fix an issue with rtreecheck() and auxiliary data columns. check-in: 46715136 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: 9abe023e user: drh tags: aux-data-in-rtree
18:18
Fix the OOM issue mentioned in the previous check-in. check-in: c489d8e4 user: drh tags: aux-data-in-rtree
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

    20     20   ** The data structure for a single virtual r-tree table is stored in three 
    21     21   ** native SQLite tables declared as follows. In each case, the '%' character
    22     22   ** in the table name is replaced with the user-supplied name of the r-tree
    23     23   ** table.
    24     24   **
    25     25   **   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
    26     26   **   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
    27         -**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
           27  +**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
    28     28   **
    29     29   ** The data for each node of the r-tree structure is stored in the %_node
    30     30   ** table. For each node that is not the root node of the r-tree, there is
    31     31   ** an entry in the %_parent table associating the node with its parent.
    32     32   ** And for each row of data in the table, there is an entry in the %_rowid
    33     33   ** table that maps from the entries rowid to the id of the node that it
    34         -** is stored on.
           34  +** is stored on.  If the r-tree contains auxiliary columns, those are stored
           35  +** on the end of the %_rowid table.
    35     36   **
    36     37   ** The root node of an r-tree always exists, even if the r-tree table is
    37     38   ** empty. The nodeno of the root node is always 1. All other nodes in the
    38     39   ** table must be the same size as the root node. The content of each node
    39     40   ** is formatted as follows:
    40     41   **
    41     42   **   1. If the node is the root node (node 1), then the first 2 bytes
................................................................................
  1886   1887         ** a single row.
  1887   1888         */ 
  1888   1889         pIdxInfo->estimatedCost = 30.0;
  1889   1890         pIdxInfo->estimatedRows = 1;
  1890   1891         return SQLITE_OK;
  1891   1892       }
  1892   1893   
  1893         -    if( p->usable && (p->iColumn>0 || p->op==SQLITE_INDEX_CONSTRAINT_MATCH) ){
         1894  +    if( p->usable
         1895  +    && ((p->iColumn>0 && p->iColumn<=pRtree->nDim2)
         1896  +        || p->op==SQLITE_INDEX_CONSTRAINT_MATCH)
         1897  +    ){
  1894   1898         u8 op;
  1895   1899         switch( p->op ){
  1896   1900           case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
  1897   1901           case SQLITE_INDEX_CONSTRAINT_GT: op = RTREE_GT; break;
  1898   1902           case SQLITE_INDEX_CONSTRAINT_LE: op = RTREE_LE; break;
  1899   1903           case SQLITE_INDEX_CONSTRAINT_LT: op = RTREE_LT; break;
  1900   1904           case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break;
................................................................................
  3580   3584     /* Create/Connect to the underlying relational database schema. If
  3581   3585     ** that is successful, call sqlite3_declare_vtab() to configure
  3582   3586     ** the r-tree table schema.
  3583   3587     */
  3584   3588     pSql = sqlite3_str_new(db);
  3585   3589     sqlite3_str_appendf(pSql, "CREATE TABLE x(%s", argv[3]);
  3586   3590     for(ii=4; ii<argc; ii++){
  3587         -    if( sqlite3_strlike("aux:%", argv[ii], 0)==0 ){
         3591  +    if( argv[ii][0]=='+' ){
  3588   3592         pRtree->nAux++;
  3589         -      sqlite3_str_appendf(pSql, ",%s", argv[ii]+4);
         3593  +      sqlite3_str_appendf(pSql, ",%s", argv[ii]+1);
  3590   3594       }else if( pRtree->nAux>0 ){
  3591   3595         break;
  3592   3596       }else{
  3593   3597         pRtree->nDim2++;
  3594   3598         sqlite3_str_appendf(pSql, ",%s", argv[ii]);
  3595   3599       }
  3596   3600     }
................................................................................
  3863   3867   
  3864   3868   /*
  3865   3869   ** This function is used to check that the %_parent (if bLeaf==0) or %_rowid
  3866   3870   ** (if bLeaf==1) table contains a specified entry. The schemas of the
  3867   3871   ** two tables are:
  3868   3872   **
  3869   3873   **   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
  3870         -**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
         3874  +**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER, ...)
  3871   3875   **
  3872   3876   ** In both cases, this function checks that there exists an entry with
  3873   3877   ** IPK value iKey and the second column set to iVal.
  3874   3878   **
  3875   3879   */
  3876   3880   static void rtreeCheckMapping(
  3877   3881     RtreeCheck *pCheck,             /* RtreeCheck object */
................................................................................
  3878   3882     int bLeaf,                      /* True for a leaf cell, false for interior */
  3879   3883     i64 iKey,                       /* Key for mapping */
  3880   3884     i64 iVal                        /* Expected value for mapping */
  3881   3885   ){
  3882   3886     int rc;
  3883   3887     sqlite3_stmt *pStmt;
  3884   3888     const char *azSql[2] = {
  3885         -    "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?",
  3886         -    "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?"
         3889  +    "SELECT parentnode FROM %Q.'%q_parent' WHERE nodeno=?1",
         3890  +    "SELECT nodeno FROM %Q.'%q_rowid' WHERE rowid=?1"
  3887   3891     };
  3888   3892   
  3889   3893     assert( bLeaf==0 || bLeaf==1 );
  3890   3894     if( pCheck->aCheckMapping[bLeaf]==0 ){
  3891   3895       pCheck->aCheckMapping[bLeaf] = rtreeCheckPrepare(pCheck,
  3892   3896           azSql[bLeaf], pCheck->zDb, pCheck->zTab
  3893   3897       );

Changes to ext/rtree/rtree3.test.

    77     77   } -body {
    78     78     execsql { DROP TABLE rt } 
    79     79   }
    80     80   
    81     81   do_malloc_test rtree3-3.prep {
    82     82     faultsim_delete_and_reopen
    83     83     execsql {
    84         -    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2);
           84  +    CREATE VIRTUAL TABLE rt USING rtree(ii, x1, x2, y1, y2, +a1, +a2);
    85     85       INSERT INTO rt VALUES(NULL, 3, 5, 7, 9);
    86     86     }
    87     87     faultsim_save_and_close
    88     88   } {}
    89     89   
    90     90   do_faultsim_test rtree3-3a -faults oom* -prep {
    91     91     faultsim_restore_and_reopen

Changes to ext/rtree/rtreeC.test.

   174    174   
   175    175   #--------------------------------------------------------------------
   176    176   # Test that the sqlite_stat1 data is used correctly.
   177    177   #
   178    178   reset_db
   179    179   do_execsql_test 5.1 {
   180    180     CREATE TABLE t1(x PRIMARY KEY, y);
   181         -  CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2);
          181  +  CREATE VIRTUAL TABLE rt USING rtree(id, x1, x2, +d1);
   182    182   
   183    183     INSERT INTO t1(x) VALUES(1);
   184    184     INSERT INTO t1(x) SELECT x+1 FROM t1;   --   2
   185    185     INSERT INTO t1(x) SELECT x+2 FROM t1;   --   4
   186    186     INSERT INTO t1(x) SELECT x+4 FROM t1;   --   8
   187    187     INSERT INTO t1(x) SELECT x+8 FROM t1;   --  16
   188    188     INSERT INTO t1(x) SELECT x+16 FROM t1;  --  32
   189    189     INSERT INTO t1(x) SELECT x+32 FROM t1;  --  64
   190    190     INSERT INTO t1(x) SELECT x+64 FROM t1;  -- 128
   191    191     INSERT INTO t1(x) SELECT x+128 FROM t1; -- 256
   192    192     INSERT INTO t1(x) SELECT x+256 FROM t1; -- 512
   193    193     INSERT INTO t1(x) SELECT x+512 FROM t1; --1024
   194    194   
   195         -  INSERT INTO rt SELECT x, x, x+1 FROM t1 WHERE x<=5;
          195  +  INSERT INTO rt SELECT x, x, x+1, printf('x%04xy',x) FROM t1 WHERE x<=5;
   196    196   }
   197    197   do_rtree_integrity_test 5.1.1 rt
   198    198   
   199    199   # First test a query with no ANALYZE data at all. The outer loop is
   200    200   # real table "t1".
   201    201   #
   202    202   do_eqp_test 5.2 {

Added ext/rtree/rtreeH.test.

            1  +# 2018-05-16
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# This file contains tests for the r-tree module, specifically the
           12  +# auxiliary column mechanism.
           13  +
           14  +if {![info exists testdir]} {
           15  +  set testdir [file join [file dirname [info script]] .. .. test]
           16  +} 
           17  +source [file join [file dirname [info script]] rtree_util.tcl]
           18  +source $testdir/tester.tcl
           19  +ifcapable !rtree { finish_test ; return }
           20  +
           21  +do_execsql_test rtreeH-100 {
           22  +  CREATE VIRTUAL TABLE t1 USING rtree(id,x0,x1,y0,y1,+label,+other);
           23  +  INSERT INTO t1(x0,x1,y0,y1,label) VALUES
           24  +    (0,10,0,10,'lower-left corner'),
           25  +    (0,10,90,100,'upper-left corner'),
           26  +    (90,100,0,10,'lower-right corner'),
           27  +    (90,100,90,100,'upper-right corner'),
           28  +    (40,60,40,60,'center'),
           29  +    (0,5,0,100,'left edge'),
           30  +    (95,100,0,100,'right edge'),
           31  +    (0,100,0,5,'bottom edge'),
           32  +    (0,100,95,100,'top edge'),
           33  +    (0,100,0,100,'the whole thing'),
           34  +    (0,50,0,100,'left half'),
           35  +    (51,100,0,100,'right half'),
           36  +    (0,100,0,50,'bottom half'),
           37  +    (0,100,51,100,'top half');
           38  +} {}
           39  +do_execsql_test rtreeH-101 {
           40  +  SELECT * FROM t1_rowid ORDER BY rowid
           41  +} {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} {}}
           42  +
           43  +do_execsql_test rtreeH-102 {
           44  +  SELECT * FROM t1 WHERE rowid=5;
           45  +} {5 40.0 60.0 40.0 60.0 center {}}
           46  +do_execsql_test rtreeH-103 {
           47  +  SELECT * FROM t1 WHERE label='center';
           48  +} {5 40.0 60.0 40.0 60.0 center {}}
           49  +
           50  +do_rtree_integrity_test rtreeH-110 t1
           51  +
           52  +do_execsql_test rtreeH-120 {
           53  +  SELECT label FROM t1 WHERE x1<=50 ORDER BY id
           54  +} {{lower-left corner} {upper-left corner} {left edge} {left half}}
           55  +do_execsql_test rtreeH-121 {
           56  +  SELECT label FROM t1 WHERE x1<=50 AND label NOT LIKE '%corner%' ORDER BY id
           57  +} {{left edge} {left half}}
           58  +
           59  +do_execsql_test rtreeH-200 {
           60  +  WITH RECURSIVE
           61  +    c1(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM c1 WHERE x<99),
           62  +    c2(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM c2 WHERE y<99)
           63  +  INSERT INTO t1(id, x0,x1,y0,y1,label)
           64  +    SELECT 1000+x+y*100, x, x+1, y, y+1, printf('box-%d,%d',x,y) FROM c1, c2;
           65  +} {}
           66  +
           67  +do_execsql_test rtreeH-210 {
           68  +  SELECT label FROM t1 WHERE x0>=48 AND x1<=50 AND y0>=48 AND y1<=50
           69  +     ORDER BY id;
           70  +} {box-48,48 box-49,48 box-48,49 box-49,49}
           71  +
           72  +do_execsql_test rtreeH-300 {
           73  +  UPDATE t1 SET label='x'||label
           74  +    WHERE x0>=49 AND x1<=50 AND y0>=49 AND y1<=50;
           75  +  SELECT label FROM t1 WHERE x0>=48 AND x1<=50 AND y0>=48 AND y1<=50
           76  +     ORDER BY id;
           77  +} {box-48,48 box-49,48 box-48,49 xbox-49,49}
           78  +
           79  +
           80  +finish_test