Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add the new interfaces to rtree, though they do not yet work. Add the "show_speedtest1_rtree.tcl" script for showing the test data used for the R-Tree tests of speedtest1. Change speedtest1 to generate better R-Tree test data. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | rtree-enhancements |
Files: | files | file ages | folders |
SHA1: |
0b70275972c7a6a533566c1e50bffbf3 |
User & Date: | drh 2014-04-11 23:14:48.914 |
Context
2014-04-12
| ||
17:44 | Continuing clean-up of the R-Tree module in preparation for cutting in the new generalized query mechanism. (check-in: 66c858f205 user: drh tags: rtree-enhancements) | |
2014-04-11
| ||
23:14 | Add the new interfaces to rtree, though they do not yet work. Add the "show_speedtest1_rtree.tcl" script for showing the test data used for the R-Tree tests of speedtest1. Change speedtest1 to generate better R-Tree test data. (check-in: 0b70275972 user: drh tags: rtree-enhancements) | |
17:41 | Add the --verify option to speedtest1. Add verification test cases to the "rtree" testset and a case that uses a custom geometry callback. (check-in: 9d485c4207 user: drh tags: rtree-enhancements) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
320 321 322 323 324 325 326 327 328 329 330 331 332 | ** An instance of this structure must be supplied as a blob argument to ** the right-hand-side of an SQL MATCH operator used to constrain an ** r-tree query. */ struct RtreeMatchArg { u32 magic; /* Always RTREE_GEOMETRY_MAGIC */ int (*xGeom)(sqlite3_rtree_geometry *, int, RtreeDValue*, int *); void *pContext; int nParam; RtreeDValue aParam[1]; }; /* | > | > | | | < > > | 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 | ** An instance of this structure must be supplied as a blob argument to ** the right-hand-side of an SQL MATCH operator used to constrain an ** r-tree query. */ struct RtreeMatchArg { u32 magic; /* Always RTREE_GEOMETRY_MAGIC */ int (*xGeom)(sqlite3_rtree_geometry *, int, RtreeDValue*, int *); int (*xQueryFunc)(sqlite3_rtree_query_info*); void *pContext; int nParam; RtreeDValue aParam[1]; }; /* ** When a geometry callback is created using either ** sqlite3_rtree_geometry_callback() or sqlite3_rtree_query_callback(), ** a single instance of the following structure is allocated. It is used ** as the context for the user-function created by sqlite3_rtree_*_callback(). ** The object is eventually deleted by the destructor mechanism provided by ** sqlite3_create_function_v2(). */ struct RtreeGeomCallback { int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*); int (*xQueryFunc)(sqlite3_rtree_query_info*); void (*xDestructor)(void*); void *pContext; }; #ifndef MAX # define MAX(x,y) ((x) < (y) ? (y) : (x)) #endif #ifndef MIN |
︙ | ︙ | |||
3348 3349 3350 3351 3352 3353 3354 | rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); } return rc; } /* | < < | | > | > > | > | < | | | 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 | rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); } return rc; } /* ** This routine is called when a custom geometry function or custom query ** function is cancelled. The pointer is to a RtreeGeomCallback object ** that needs to be freed. */ static void rtreeFreeCallback(void *p){ RtreeGeomCallback *pGeom = (RtreeGeomCallback*)p; if( pGeom->xDestructor ) pGeom->xDestructor(pGeom->pContext); sqlite3_free(p); } /* ** Each call to sqlite3_rtree_geometry_callback() or ** sqlite3_rtree_query_callback() creates an ordinary SQLite ** scalar user function that is implemented by this routine. ** ** This function returns a blob that is interpreted by r-tree ** table MATCH operator. */ static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){ RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx); RtreeMatchArg *pBlob; int nBlob; nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue); |
︙ | ︙ | |||
3387 3388 3389 3390 3391 3392 3393 | for(i=0; i<nArg; i++){ #ifdef SQLITE_RTREE_INT_ONLY pBlob->aParam[i] = sqlite3_value_int64(aArg[i]); #else pBlob->aParam[i] = sqlite3_value_double(aArg[i]); #endif } | | > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 | for(i=0; i<nArg; i++){ #ifdef SQLITE_RTREE_INT_ONLY pBlob->aParam[i] = sqlite3_value_int64(aArg[i]); #else pBlob->aParam[i] = sqlite3_value_double(aArg[i]); #endif } sqlite3_result_blob(ctx, pBlob, nBlob, sqlite3_free); } } /* ** Register a new geometry function for use with the r-tree MATCH operator. */ int sqlite3_rtree_geometry_callback( sqlite3 *db, const char *zGeom, int (*xGeom)(sqlite3_rtree_geometry *, int, RtreeDValue *, int *), void *pContext ){ RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ /* Allocate and populate the context object. */ pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); if( !pGeomCtx ) return SQLITE_NOMEM; pGeomCtx->xGeom = xGeom; pGeomCtx->xQueryFunc = 0; pGeomCtx->xDestructor = 0; pGeomCtx->pContext = pContext; /* Create the new user-function. Register a destructor function to delete ** the context object when it is no longer required. */ return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback ); } /* ** Register a new 2nd-generation geometry function for use with the ** r-tree MATCH operator. */ int sqlite3_rtree_query_callback( sqlite3 *db, const char *zQueryFunc, int (*xQueryFunc)(sqlite3_rtree_query_info*), void *pContext, void (*xDestructor)(void*) ){ RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ /* Allocate and populate the context object. */ pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); if( !pGeomCtx ) return SQLITE_NOMEM; pGeomCtx->xGeom = 0; pGeomCtx->xQueryFunc = xQueryFunc; pGeomCtx->xDestructor = xDestructor; pGeomCtx->pContext = pContext; /* Create the new user-function. Register a destructor function to delete ** the context object when it is no longer required. */ return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback ); } #if !SQLITE_CORE #ifdef _WIN32 __declspec(dllexport) #endif |
︙ | ︙ |
Changes to ext/rtree/sqlite3rtree.h.
︙ | ︙ | |||
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <sqlite3.h> #ifdef __cplusplus extern "C" { #endif typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry; /* ** Register a geometry callback named zGeom that can be used as part of an ** R-Tree geometry query as follows: ** ** SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...) */ int sqlite3_rtree_geometry_callback( sqlite3 *db, const char *zGeom, | > > > > > > > > > > < < < | < | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | #include <sqlite3.h> #ifdef __cplusplus extern "C" { #endif typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry; typedef struct sqlite3_rtree_query_info sqlite3_rtree_query_info; /* The double-precision datatype used by RTree depends on the ** SQLITE_RTREE_INT_ONLY compile-time option. */ #ifdef SQLITE_RTREE_INT_ONLY typedef sqlite3_int64 sqlite3_rtree_dbl; #else typedef double sqlite3_rtree_dbl; #endif /* ** Register a geometry callback named zGeom that can be used as part of an ** R-Tree geometry query as follows: ** ** SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...) */ int sqlite3_rtree_geometry_callback( sqlite3 *db, const char *zGeom, int (*xGeom)(sqlite3_rtree_geometry*, int, sqlite3_rtree_dbl*,int*), void *pContext ); /* ** A pointer to a structure of the following type is passed as the first ** argument to callbacks registered using rtree_geometry_callback(). */ struct sqlite3_rtree_geometry { void *pContext; /* Copy of pContext passed to s_r_g_c() */ int nParam; /* Size of array aParam[] */ sqlite3_rtree_dbl *aParam; /* Parameters passed to SQL geom function */ void *pUser; /* Callback implementation user data */ void (*xDelUser)(void *); /* Called by SQLite to clean up pUser */ }; /* ** Register a 2nd-generation geometry callback named zScore that can be ** used as part of an R-Tree geometry query as follows: ** ** SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zQueryFunc(... params ...) */ int sqlite3_rtree_query_callback( sqlite3 *db, const char *zQueryFunc, int (*xQueryFunc)(sqlite3_rtree_query_info*), void *pContext, void (*xDestructor)(void*) ); /* ** A pointer to a structure of the following type is passed as the ** argument to scored geometry callback registered using ** sqlite3_rtree_query_callback(). */ struct sqlite3_rtree_query_info { void *pContext; /* pContext from when function registered */ int nParam; /* Number of function parameters */ sqlite3_rtree_dbl *aParam; /* value of function parameters */ void *pUser; /* callback can use this, if desired */ void (*xDelUser)(void*); /* function to free pUser */ sqlite3_rtree_dbl *aCoord; /* Coordinates of node or entry to check */ int nCoord; /* Number of coordinates */ int iLevel; /* Level of current node or entry */ sqlite3_int64 iRowid; /* Rowid for current entry */ sqlite3_rtree_dbl rParentScore; /* Score of parent node */ int eParentWithin; /* Visibility of parent node */ int eWithin; /* OUT: Visiblity */ sqlite3_rtree_dbl rScore; /* OUT: Write the score here */ }; /* ** Allowed values for sqlite3_rtree_query.eWithin and .eParentWithin. */ #define NOT_WITHIN 0 /* Object completely outside of query region */ #define PARTLY_WITHIN 1 /* Object partially overlaps query region */ #define FULLY_WITHIN 2 /* Object fully contained within query region */ #ifdef __cplusplus } /* end of the 'extern "C"' block */ #endif #endif /* ifndef _SQLITE3RTREE_H_ */ |
Changes to main.mk.
︙ | ︙ | |||
479 480 481 482 483 484 485 | parse.c: $(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk cp $(TOP)/src/parse.y . rm -f parse.h ./lemon $(OPTS) parse.y mv parse.h parse.h.temp $(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h | | | 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 | parse.c: $(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk cp $(TOP)/src/parse.y . rm -f parse.h ./lemon $(OPTS) parse.y mv parse.h parse.h.temp $(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h sqlite3.h: $(TOP)/src/sqlite.h.in $(TOP)/manifest.uuid $(TOP)/VERSION $(TOP)/ext/rtree/sqlite3rtree.h tclsh $(TOP)/tool/mksqlite3h.tcl $(TOP) >sqlite3.h keywordhash.h: $(TOP)/tool/mkkeywordhash.c $(BCC) -o mkkeywordhash $(OPTS) $(TOP)/tool/mkkeywordhash.c ./mkkeywordhash >keywordhash.h |
︙ | ︙ |
Added test/show_speedtest1_rtree.tcl.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | #!/usr/bin/tclsh # # This script displays the field of rectangles used by --testset rtree # of speedtest1. Run this script as follows: # # rm test.db # ./speedtest1 --testset rtree --size 25 test.db # sqlite3 --separator ' ' test.db 'SELECT * FROM rt1' >data.txt # wish show_speedtest1_rtree.tcl # # The filename "data.txt" is hard coded into this script and so that name # must be used on lines 3 and 4 above. Elsewhere, different filenames can # be used. The --size N parameter can be adjusted as desired. # package require Tk set f [open data.txt rb] set data [read $f] close $f canvas .c frame .b button .b.b1 -text X-Y -command refill-xy button .b.b2 -text X-Z -command refill-xz button .b.b3 -text Y-Z -command refill-yz pack .b.b1 .b.b2 .b.b3 -side left pack .c -side top -fill both -expand 1 pack .b -side top proc resize_canvas_to_fit {} { foreach {x0 y0 x1 y1} [.c bbox all] break set w [expr {$x1-$x0}] set h [expr {$y1-$y0}] .c config -width $w -height $h } proc refill-xy {} { .c delete all foreach {id x0 x1 y0 y1 z0 z1} $::data { .c create rectangle $x0 $y0 $x1 $y1 } .c scale all 0 0 0.05 0.05 resize_canvas_to_fit } proc refill-xz {} { .c delete all foreach {id x0 x1 y0 y1 z0 z1} $::data { .c create rectangle $x0 $z0 $x1 $z1 } .c scale all 0 0 0.05 0.05 resize_canvas_to_fit } proc refill-yz {} { .c delete all foreach {id x0 x1 y0 y1 z0 z1} $::data { .c create rectangle $y0 $z0 $y1 $z1 } .c scale all 0 0 0.05 0.05 resize_canvas_to_fit } refill-xy |
Changes to test/speedtest1.c.
︙ | ︙ | |||
934 935 936 937 938 939 940 941 942 943 944 945 946 | } /* Generate two numbers between 1 and mx. The first number is less than ** the second. Usually the numbers are near each other but can sometimes ** be far apart. */ static void twoCoords( unsigned mx, /* Range of 1..mx */ unsigned *pX0, unsigned *pX1 /* OUT: write results here */ ){ unsigned d, x0, x1, span; span = mx/100 + 1; | > | | | 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 | } /* Generate two numbers between 1 and mx. The first number is less than ** the second. Usually the numbers are near each other but can sometimes ** be far apart. */ static void twoCoords( int p1, int p2, /* Parameters adjusting sizes */ unsigned mx, /* Range of 1..mx */ unsigned *pX0, unsigned *pX1 /* OUT: write results here */ ){ unsigned d, x0, x1, span; span = mx/100 + 1; if( speedtest1_random()%3==0 ) span *= p1; if( speedtest1_random()%p2==0 ) span = mx/2; d = speedtest1_random()%span + 1; x0 = speedtest1_random()%(mx-d) + 1; x1 = x0 + d; *pX0 = x0; *pX1 = x1; } |
︙ | ︙ | |||
972 973 974 975 976 977 978 | *pRes = aCoord[3]>=p->aParam[0] && aCoord[2]<=p->aParam[1]; return SQLITE_OK; } /* ** A testset for the R-Tree virtual table */ | | | | | | | 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 | *pRes = aCoord[3]>=p->aParam[0] && aCoord[2]<=p->aParam[1]; return SQLITE_OK; } /* ** A testset for the R-Tree virtual table */ void testset_rtree(int p1, int p2){ unsigned i, n; unsigned mxCoord; unsigned x0, x1, y0, y1, z0, z1; unsigned iStep; int *aCheck = sqlite3_malloc( sizeof(int)*g.szTest*100 ); mxCoord = 15000; n = g.szTest*100; speedtest1_begin_test(100, "%d INSERTs into an r-tree", n); speedtest1_exec("BEGIN"); speedtest1_exec("CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1,z0,z1)"); speedtest1_prepare("INSERT INTO rt1(id,x0,x1,y0,y1,z0,z1)" "VALUES(?1,?2,?3,?4,?5,?6,?7)"); for(i=1; i<=n; i++){ twoCoords(p1, p2, mxCoord, &x0, &x1); twoCoords(p1, p2, mxCoord, &y0, &y1); twoCoords(p1, p2, mxCoord, &z0, &z1); sqlite3_bind_int(g.pStmt, 1, i); sqlite3_bind_int(g.pStmt, 2, x0); sqlite3_bind_int(g.pStmt, 3, x1); sqlite3_bind_int(g.pStmt, 4, y0); sqlite3_bind_int(g.pStmt, 5, y1); sqlite3_bind_int(g.pStmt, 6, z0); sqlite3_bind_int(g.pStmt, 7, z1); |
︙ | ︙ | |||
1318 1319 1320 1321 1322 1323 1324 | if( strcmp(zTSet,"main")==0 ){ testset_main(); }else if( strcmp(zTSet,"debug1")==0 ){ testset_debug1(); }else if( strcmp(zTSet,"cte")==0 ){ testset_cte(); }else if( strcmp(zTSet,"rtree")==0 ){ | | | 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 | if( strcmp(zTSet,"main")==0 ){ testset_main(); }else if( strcmp(zTSet,"debug1")==0 ){ testset_debug1(); }else if( strcmp(zTSet,"cte")==0 ){ testset_cte(); }else if( strcmp(zTSet,"rtree")==0 ){ testset_rtree(6, 147); }else{ fatal_error("unknown testset: \"%s\"\nChoices: main debug1 cte rtree\n", zTSet); } speedtest1_final(); /* Database connection statistics printed after both prepared statements |
︙ | ︙ |