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: |
9abe023e1afa7dc1a7eba7fbb3128401 |
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
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
20 21 22 23 24 25 26 | ** 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) | | | > | 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 | ** a single row. */ pIdxInfo->estimatedCost = 30.0; pIdxInfo->estimatedRows = 1; return SQLITE_OK; } | > > | > | 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 | /* 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++){ | | | | 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 | /* ** 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) | | | | | 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 | } -body { execsql { DROP TABLE rt } } do_malloc_test rtree3-3.prep { faultsim_delete_and_reopen execsql { | | | 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 | #-------------------------------------------------------------------- # Test that the sqlite_stat1 data is used correctly. # reset_db do_execsql_test 5.1 { CREATE TABLE t1(x PRIMARY KEY, y); | | | | 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 |