SQLite

**    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){

# 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