/ Check-in [6f3e94f4]
Login

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

Overview
Comment:Further improvements to the RTREE_DECODE_COORD() method, to take advantage of known processor byte orders when available. This makes the code 3% faster, according to valgrind. Also add test cases to make sure the on-disk representation is correct.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-enhancements
Files: files | file ages | folders
SHA1: 6f3e94f4b1b403cd7bfc5e8e0ffbd61b5174d3a4
User & Date: drh 2014-04-18 01:37:08
Context
2014-04-21
15:21
Fix an off-by-one error in setting the "iLevel" field of the sqlite3_rtree_query_info structure passed into the RTree query callback. check-in: d708f159 user: drh tags: rtree-enhancements
2014-04-18
01:37
Further improvements to the RTREE_DECODE_COORD() method, to take advantage of known processor byte orders when available. This makes the code 3% faster, according to valgrind. Also add test cases to make sure the on-disk representation is correct. check-in: 6f3e94f4 user: drh tags: rtree-enhancements
01:14
Merge the latest changes from sessions. check-in: d9eef5b0 user: drh tags: rtree-enhancements
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

900
901
902
903
904
905
906
907
908
909
910

911
912
913
914





915
916

917
918
919
920
921
922
923






924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
....
2238
2239
2240
2241
2242
2243
2244
2245

2246
2247
2248
2249
2250
2251
2252
....
2999
3000
3001
3002
3003
3004
3005
3006

3007
3008
3009
3010
3011
3012
3013
static int rtreeEof(sqlite3_vtab_cursor *cur){
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  return pCsr->atEOF;
}

/*
** Convert raw bits from the on-disk RTree record into a coordinate value.
** The on-disk format is big-endian and needs to be converted for little-endian
** platforms.  The on-disk record stores integer coordinates if eInt is true
** and it stores 32-bit floating point records if eInt is false.  a[] is the four
** bytes of the on-disk record to be decoded.  Store the results in "r".

**
** The first version of this macro is fast on x86, x86_64 and ARM, all of which
** are little-endian.  The second version of this macro is cross-platform but
** takes twice as long, according to valgrind on linux x64.





*/
#if defined(__x86) || defined(__x86_64) || defined(__arm__) || defined(_MSC_VER)

#define RTREE_DECODE_COORD(eInt, a, r) {                        \
    RtreeCoord c;    /* Coordinate decoded */                   \
    memcpy(&c.u,a,4);                                           \
    c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)|                   \
          ((c.u&0xff)<<24)|((c.u&0xff00)<<8);                   \
    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}






#else
#define RTREE_DECODE_COORD(eInt, a, r) {                        \
    RtreeCoord c;    /* Coordinate decoded */                   \
    c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16)                     \
           +((u32)a[2]<<8) + a[3];                              \
    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#endif
   

/*
** Check the RTree node or entry given by pCellData and p against the MATCH
** constraint pConstraint.  
*/
static int rtreeCallbackConstraint(
  RtreeConstraint *pConstraint,  /* The constraint to test */
................................................................................
    rc = SQLITE_NOMEM;
    goto splitnode_out;
  }

  memset(pLeft->zData, 0, pRtree->iNodeSize);
  memset(pRight->zData, 0, pRtree->iNodeSize);

  rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,&leftbbox,&rightbbox);

  if( rc!=SQLITE_OK ){
    goto splitnode_out;
  }

  /* Ensure both child nodes have node numbers assigned to them by calling
  ** nodeWrite(). Node pRight always needs a node number, as it was created
  ** by nodeNew() above. But node pLeft sometimes already has a node number.
................................................................................

  pRtree->db = db;

  if( isCreate ){
    char *zCreate = sqlite3_mprintf(
"CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY, parentnode INTEGER);"

"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
      zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
    );
    if( !zCreate ){
      return SQLITE_NOMEM;
    }
    rc = sqlite3_exec(db, zCreate, 0, 0, 0);







|
|
|
|
>

<
|
|
>
>
>
>
>

<
>







>
>
>
>
>
>








<







 







|
>







 







|
>







900
901
902
903
904
905
906
907
908
909
910
911
912

913
914
915
916
917
918
919
920

921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942

943
944
945
946
947
948
949
....
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
....
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
static int rtreeEof(sqlite3_vtab_cursor *cur){
  RtreeCursor *pCsr = (RtreeCursor *)cur;
  return pCsr->atEOF;
}

/*
** Convert raw bits from the on-disk RTree record into a coordinate value.
** The on-disk format is big-endian and needs to be converted for little-
** endian platforms.  The on-disk record stores integer coordinates if
** eInt is true and it stores 32-bit floating point records if eInt is
** false.  a[] is the four bytes of the on-disk record to be decoded.
** Store the results in "r".
**

** There are three versions of this macro, one each for little-endian and
** big-endian processors and a third generic implementation.  The endian-
** specific implementations are much faster and are preferred if the
** processor endianness is known at compile-time.  The SQLITE_BYTEORDER
** macro is part of sqliteInt.h and hence the endian-specific
** implementation will only be used if this module is compiled as part
** of the amalgamation.
*/

#if defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==1234
#define RTREE_DECODE_COORD(eInt, a, r) {                        \
    RtreeCoord c;    /* Coordinate decoded */                   \
    memcpy(&c.u,a,4);                                           \
    c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)|                   \
          ((c.u&0xff)<<24)|((c.u&0xff00)<<8);                   \
    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#elif defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==4321
#define RTREE_DECODE_COORD(eInt, a, r) {                        \
    RtreeCoord c;    /* Coordinate decoded */                   \
    memcpy(&c.u,a,4);                                           \
    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#else
#define RTREE_DECODE_COORD(eInt, a, r) {                        \
    RtreeCoord c;    /* Coordinate decoded */                   \
    c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16)                     \
           +((u32)a[2]<<8) + a[3];                              \
    r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \
}
#endif


/*
** Check the RTree node or entry given by pCellData and p against the MATCH
** constraint pConstraint.  
*/
static int rtreeCallbackConstraint(
  RtreeConstraint *pConstraint,  /* The constraint to test */
................................................................................
    rc = SQLITE_NOMEM;
    goto splitnode_out;
  }

  memset(pLeft->zData, 0, pRtree->iNodeSize);
  memset(pRight->zData, 0, pRtree->iNodeSize);

  rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight,
                         &leftbbox, &rightbbox);
  if( rc!=SQLITE_OK ){
    goto splitnode_out;
  }

  /* Ensure both child nodes have node numbers assigned to them by calling
  ** nodeWrite(). Node pRight always needs a node number, as it was created
  ** by nodeNew() above. But node pLeft sometimes already has a node number.
................................................................................

  pRtree->db = db;

  if( isCreate ){
    char *zCreate = sqlite3_mprintf(
"CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);"
"CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);"
"CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY,"
                                  " parentnode INTEGER);"
"INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))",
      zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize
    );
    if( !zCreate ){
      return SQLITE_NOMEM;
    }
    rc = sqlite3_exec(db, zCreate, 0, 0, 0);

Changes to ext/rtree/rtree1.test.

116
117
118
119
120
121
122
123
124
125
126



127
128
129
130
131
132
133
134
135
...
431
432
433
434
435
436
437
438
439
440



441
442
443
444
445
446
447
448
449
450
451
452
453
454
  }
  return $out
}

# Test that it is possible to open an existing database that contains
# r-tree tables.
#
do_test rtree-1.4.1 {
  execsql {
    CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
    INSERT INTO t1 VALUES(1, 5.0, 10.0);



    INSERT INTO t1 VALUES(2, 15.0, 20.0);
  }
} {}
do_test rtree-1.4.2 {
  db close
  sqlite3 db test.db
  execsql_intout { SELECT * FROM t1 ORDER BY ii }
} {1 5 10 2 15 20}
do_test rtree-1.4.3 {
................................................................................
  }
} {2}

#-------------------------------------------------------------------------
# Test on-conflict clause handling.
#
db_delete_and_reopen
do_execsql_test 12.0 {
  CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2);
  INSERT INTO t1 VALUES(1,   1, 2, 3, 4);



  INSERT INTO t1 VALUES(2,   2, 3, 4, 5);
  INSERT INTO t1 VALUES(3,   3, 4, 5, 6);

  CREATE TABLE source(idx, x1, x2, y1, y2);
  INSERT INTO source VALUES(5, 8, 8, 8, 8);
  INSERT INTO source VALUES(2, 7, 7, 7, 7);
  
}
db_save_and_close
foreach {tn sql_template testdata} {
  1    "INSERT %CONF% INTO t1 VALUES(2, 7, 7, 7, 7)" {
    ROLLBACK 0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
    ABORT    0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
    IGNORE   0 0 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}







|
<
|
|
>
>
>
|
<







 







|


>
>
>






<







116
117
118
119
120
121
122
123

124
125
126
127
128
129

130
131
132
133
134
135
136
...
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450

451
452
453
454
455
456
457
  }
  return $out
}

# Test that it is possible to open an existing database that contains
# r-tree tables.
#
do_execsql_test rtree-1.4.1a {

  CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2);
  INSERT INTO t1 VALUES(1, 5.0, 10.0);
  SELECT substr(hex(data),1,40) FROM t1_node;
} {00000001000000000000000140A0000041200000}
do_execsql_test rtree-1.4.1b {
  INSERT INTO t1 VALUES(2, 15.0, 20.0);

} {}
do_test rtree-1.4.2 {
  db close
  sqlite3 db test.db
  execsql_intout { SELECT * FROM t1 ORDER BY ii }
} {1 5 10 2 15 20}
do_test rtree-1.4.3 {
................................................................................
  }
} {2}

#-------------------------------------------------------------------------
# Test on-conflict clause handling.
#
db_delete_and_reopen
do_execsql_test 12.0.1 {
  CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2);
  INSERT INTO t1 VALUES(1,   1, 2, 3, 4);
  SELECT substr(hex(data),1,56) FROM t1_node;
} {00000001000000000000000100000001000000020000000300000004}
do_execsql_test 12.0.2 {
  INSERT INTO t1 VALUES(2,   2, 3, 4, 5);
  INSERT INTO t1 VALUES(3,   3, 4, 5, 6);

  CREATE TABLE source(idx, x1, x2, y1, y2);
  INSERT INTO source VALUES(5, 8, 8, 8, 8);
  INSERT INTO source VALUES(2, 7, 7, 7, 7);

}
db_save_and_close
foreach {tn sql_template testdata} {
  1    "INSERT %CONF% INTO t1 VALUES(2, 7, 7, 7, 7)" {
    ROLLBACK 0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6}
    ABORT    0 1 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}
    IGNORE   0 0 {1 1 2 3 4   2 2 3 4 5   3 3 4 5 6   4 4 5 6 7}