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: | 9abe023e1afa7dc1a7eba7fbb3128401 |
| 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
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