/ Check-in [483932c4]
Login

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

Overview
Comment:Have the rtree module set the estimatedCost output variable. Ticket #3312. (CVS 5649)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:483932c4e08901a11b7ab671073fd0a048b10d66
User & Date: danielk1977 2008-09-01 12:47:00
Context
2008-09-01
15:52
Defer deleting Table objects associated with flattened subqueries until all code has been generated, in case some expression node still references the Table object. Ticket #3346. (CVS 5650) check-in: d04d7033 user: drh tags: trunk
12:47
Have the rtree module set the estimatedCost output variable. Ticket #3312. (CVS 5649) check-in: 483932c4 user: danielk1977 tags: trunk
2008-08-31
00:29
Changed to used sqlite3_snprintf instead of snprintf (test code only). (CVS 5648) check-in: d68791e3 user: shane tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1112
1113
1114
1115
1116
1117
1118







1119
1120
1121
1122
1123
1124
1125
....
1165
1166
1167
1168
1169
1170
1171


1172
1173
1174
1175
1176
1177
1178
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
**
** $Id: rtree.c,v 1.7 2008/07/16 14:43:35 drh Exp $
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
................................................................................
      for(jj=0; jj<ii; jj++){
        pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
        pIdxInfo->aConstraintUsage[jj].omit = 0;
      }
      pIdxInfo->idxNum = 1;
      pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
      pIdxInfo->aConstraintUsage[jj].omit = 1;







      return SQLITE_OK;
    }

    if( p->usable && p->iColumn>0 ){
      u8 op = 0;
      switch( p->op ){
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
................................................................................
  }

  pIdxInfo->idxNum = 2;
  pIdxInfo->needToFreeIdxStr = 1;
  if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
    return SQLITE_NOMEM;
  }


  return rc;
}

/*
** Return the N-dimensional volumn of the cell stored in *p.
*/
static float cellArea(Rtree *pRtree, RtreeCell *p){







|







 







>
>
>
>
>
>
>







 







>
>







8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
....
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
....
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains code for implementations of the r-tree and r*-tree
** algorithms packaged as an SQLite virtual table module.
**
** $Id: rtree.c,v 1.8 2008/09/01 12:47:00 danielk1977 Exp $
*/

#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE)

/*
** This file contains an implementation of a couple of different variants
** of the r-tree algorithm. See the README file for further details. The 
................................................................................
      for(jj=0; jj<ii; jj++){
        pIdxInfo->aConstraintUsage[jj].argvIndex = 0;
        pIdxInfo->aConstraintUsage[jj].omit = 0;
      }
      pIdxInfo->idxNum = 1;
      pIdxInfo->aConstraintUsage[ii].argvIndex = 1;
      pIdxInfo->aConstraintUsage[jj].omit = 1;

      /* This strategy involves a two rowid lookups on an B-Tree structures
      ** and then a linear search of an R-Tree node. This should be 
      ** considered almost as quick as a direct rowid lookup (for which 
      ** sqlite uses an internal cost of 0.0).
      */ 
      pIdxInfo->estimatedCost = 10.0;
      return SQLITE_OK;
    }

    if( p->usable && p->iColumn>0 ){
      u8 op = 0;
      switch( p->op ){
        case SQLITE_INDEX_CONSTRAINT_EQ: op = RTREE_EQ; break;
................................................................................
  }

  pIdxInfo->idxNum = 2;
  pIdxInfo->needToFreeIdxStr = 1;
  if( iIdx>0 && 0==(pIdxInfo->idxStr = sqlite3_mprintf("%s", zIdxStr)) ){
    return SQLITE_NOMEM;
  }
  assert( iIdx>=0 );
  pIdxInfo->estimatedCost = (2000000.0 / (double)(iIdx + 1));
  return rc;
}

/*
** Return the N-dimensional volumn of the cell stored in *p.
*/
static float cellArea(Rtree *pRtree, RtreeCell *p){

Added ext/rtree/rtree6.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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
# 2008 Sep 1
#
# 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.
#
#***********************************************************************
#
# $Id: rtree6.test,v 1.1 2008/09/01 12:47:00 danielk1977 Exp $
#

if {![info exists testdir]} {
  set testdir [file join [file dirname $argv0] .. .. test]
} 
source $testdir/tester.tcl

ifcapable !rtree {
  finish_test
  return
}

#   Operator    Byte Value
#   ----------------------
#      =        0x41 ('A')
#     <=        0x42 ('B')
#      <        0x43 ('C')
#     >=        0x44 ('D')
#      >        0x45 ('E')
#   ----------------------

proc rtree_strategy {sql} {
  set ret [list]
  db eval "explain $sql" a {
    if {$a(opcode) eq "VFilter"} {
      lappend ret $a(p4)
    }
  }
  set ret
}

proc query_plan {sql} {
  set ret [list]
  db eval "explain query plan $sql" a {
    lappend ret $a(detail)
  }
  set ret
}

do_test rtree6-1.1 {
  execsql {
    CREATE TABLE t2(k INTEGER PRIMARY KEY, v);
    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2);
  }
} {}

do_test rtree6-1.2 {
  rtree_strategy {SELECT * FROM t1 WHERE x1>10}
} {Ea}

do_test rtree6-1.3 {
  rtree_strategy {SELECT * FROM t1 WHERE x1<10}
} {Ca}

do_test rtree6-1.4 {
  rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
} {Ca}

do_test rtree6-1.5 {
  rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
} {Ca}

do_test rtree6.2.1 {
  query_plan {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10}
} [list \
  {TABLE t1 VIRTUAL TABLE INDEX 2:Ca} \
  {TABLE t2 USING PRIMARY KEY}        \
]

do_test rtree6.2.2 {
  query_plan {SELECT * FROM t1,t2 WHERE k=ii AND x1<10}
} [list \
  {TABLE t1 VIRTUAL TABLE INDEX 2:Ca} \
  {TABLE t2 USING PRIMARY KEY}        \
]

do_test rtree6.2.3 {
  query_plan {SELECT * FROM t1,t2 WHERE k=ii}
} [list \
  {TABLE t2}                          \
  {TABLE t1 VIRTUAL TABLE INDEX 1:}   \
]

do_test rtree6.2.4 {
  query_plan {SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10}
} [list \
  {TABLE t2}                              \
  {TABLE t1 VIRTUAL TABLE INDEX 2:CaEb}   \
]

do_test rtree6.2.5 {
  query_plan {SELECT * FROM t1,t2 WHERE k=ii AND x1<v}
} [list \
  {TABLE t2}                              \
  {TABLE t1 VIRTUAL TABLE INDEX 1:}   \
]

finish_test