Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Enhance the geopoly virtual table so that it does a better job of optimizing geopoly_within() queries. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | rtree-geopoly |
| Files: | files | file ages | folders |
| SHA3-256: |
1f717385340f295064a7649cfc36ad04 |
| User & Date: | drh 2018-08-25 23:03:27 |
Context
|
2018-08-27
| ||
| 15:55 | Split the three-argument version of geopoly_within() off into a separate function named geopoly_contains_point(). check-in: 5a0e1541 user: drh tags: rtree-geopoly | |
|
2018-08-25
| ||
| 23:03 | Enhance the geopoly virtual table so that it does a better job of optimizing geopoly_within() queries. check-in: 1f717385 user: drh tags: rtree-geopoly | |
| 19:51 | Provide the two-argument geopoly_within(P1,P2) routine that determines if polygon P2 is contained within polygon P1. Make this function available to the query planner for optimized rtree lookups. Update the visual01.txt script to verify that the new functionality actually works. check-in: 6eb5d09b user: drh tags: rtree-geopoly | |
Changes
Changes to ext/rtree/geopoly.c.
1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 .... 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 .... 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 .... 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 .... 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 .... 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 |
** GEOPOLY virtual table module xFilter method. ** ** Query plans: ** ** 1 rowid lookup ** 2 search for objects overlapping the same bounding box ** that contains polygon argv[0] ** 3 full table scan */ static int geopolyFilter( sqlite3_vtab_cursor *pVtabCursor, /* The cursor to initialize */ int idxNum, /* Query plan */ const char *idxStr, /* Not Used */ int argc, sqlite3_value **argv /* Parameters to the query plan */ ){ ................................................................................ pCsr->atEOF = 1; } }else{ /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array ** with the configured constraints. */ rc = nodeAcquire(pRtree, 1, 0, &pRoot); if( rc==SQLITE_OK && idxNum==2 ){ RtreeCoord bbox[4]; RtreeConstraint *p; assert( argc==1 ); geopolyBBox(0, argv[0], bbox, &rc); if( rc ){ return rc; } ................................................................................ pCsr->aConstraint = p = sqlite3_malloc(sizeof(RtreeConstraint)*4); pCsr->nConstraint = 4; if( p==0 ){ rc = SQLITE_NOMEM; }else{ memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*4); memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1)); p->op = 'B'; p->iCoord = 0; p->u.rValue = bbox[1].f; p++; p->op = 'D'; p->iCoord = 1; p->u.rValue = bbox[0].f; p++; p->op = 'B'; p->iCoord = 2; p->u.rValue = bbox[3].f; p++; p->op = 'D'; p->iCoord = 3; p->u.rValue = bbox[2].f; } } if( rc==SQLITE_OK ){ RtreeSearchPoint *pNew; pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1)); if( pNew==0 ) return SQLITE_NOMEM; pNew->id = 1; ................................................................................ /* ** Rtree virtual table module xBestIndex method. There are three ** table scan strategies to choose from (in order from most to ** least desirable): ** ** idxNum idxStr Strategy ** ------------------------------------------------ ** 1 Unused Direct lookup by rowid. ** 2 Unused R-tree query ** 3 Unused full-table scan. ** ------------------------------------------------ */ static int geopolyBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ int ii; int iRowidTerm = -1; int iFuncTerm = -1; for(ii=0; ii<pIdxInfo->nConstraint; ii++){ struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii]; if( !p->usable ) continue; if( p->iColumn<0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){ iRowidTerm = ii; break; } if( p->iColumn==0 && p->op==SQLITE_INDEX_CONSTRAINT_FUNCTION ){ iFuncTerm = ii; } } if( iRowidTerm>=0 ){ pIdxInfo->idxNum = 1; pIdxInfo->idxStr = "rowid"; pIdxInfo->aConstraintUsage[iRowidTerm].argvIndex = 1; ................................................................................ pIdxInfo->aConstraintUsage[iRowidTerm].omit = 1; pIdxInfo->estimatedCost = 30.0; pIdxInfo->estimatedRows = 1; pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE; return SQLITE_OK; } if( iFuncTerm>=0 ){ pIdxInfo->idxNum = 2; pIdxInfo->idxStr = "rtree"; pIdxInfo->aConstraintUsage[iFuncTerm].argvIndex = 1; pIdxInfo->aConstraintUsage[iFuncTerm].omit = 0; pIdxInfo->estimatedCost = 300.0; pIdxInfo->estimatedRows = 10; return SQLITE_OK; } pIdxInfo->idxNum = 3; pIdxInfo->idxStr = "fullscan"; pIdxInfo->estimatedCost = 3000000.0; pIdxInfo->estimatedRows = 100000; return SQLITE_OK; } ................................................................................ *pxFunc = geopolyOverlapFunc; *ppArg = 0; return SQLITE_INDEX_CONSTRAINT_FUNCTION; } if( nArg==2 && sqlite3_stricmp(zName, "geopoly_within")==0 ){ *pxFunc = geopolyWithinFunc; *ppArg = 0; return SQLITE_INDEX_CONSTRAINT_FUNCTION; } return 0; } static sqlite3_module geopolyModule = { 2, /* iVersion */ |
> > | | > > | | | | | | | | | | | | | | | > > > > > > > > > > > > > > > > > > | | | > > > | > > > | | | |
1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 .... 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 .... 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 .... 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 .... 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 .... 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 |
** GEOPOLY virtual table module xFilter method. ** ** Query plans: ** ** 1 rowid lookup ** 2 search for objects overlapping the same bounding box ** that contains polygon argv[0] ** 3 search for objects overlapping the same bounding box ** that contains polygon argv[0] ** 4 full table scan */ static int geopolyFilter( sqlite3_vtab_cursor *pVtabCursor, /* The cursor to initialize */ int idxNum, /* Query plan */ const char *idxStr, /* Not Used */ int argc, sqlite3_value **argv /* Parameters to the query plan */ ){ ................................................................................ pCsr->atEOF = 1; } }else{ /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array ** with the configured constraints. */ rc = nodeAcquire(pRtree, 1, 0, &pRoot); if( rc==SQLITE_OK && idxNum<=3 ){ RtreeCoord bbox[4]; RtreeConstraint *p; assert( argc==1 ); geopolyBBox(0, argv[0], bbox, &rc); if( rc ){ return rc; } ................................................................................ pCsr->aConstraint = p = sqlite3_malloc(sizeof(RtreeConstraint)*4); pCsr->nConstraint = 4; if( p==0 ){ rc = SQLITE_NOMEM; }else{ memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*4); memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1)); if( idxNum==2 ){ /* Overlap query */ p->op = 'B'; p->iCoord = 0; p->u.rValue = bbox[1].f; p++; p->op = 'D'; p->iCoord = 1; p->u.rValue = bbox[0].f; p++; p->op = 'B'; p->iCoord = 2; p->u.rValue = bbox[3].f; p++; p->op = 'D'; p->iCoord = 3; p->u.rValue = bbox[2].f; }else{ /* Within query */ p->op = 'D'; p->iCoord = 0; p->u.rValue = bbox[0].f; p++; p->op = 'B'; p->iCoord = 1; p->u.rValue = bbox[1].f; p++; p->op = 'D'; p->iCoord = 2; p->u.rValue = bbox[2].f; p++; p->op = 'B'; p->iCoord = 3; p->u.rValue = bbox[3].f; } } } if( rc==SQLITE_OK ){ RtreeSearchPoint *pNew; pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, (u8)(pRtree->iDepth+1)); if( pNew==0 ) return SQLITE_NOMEM; pNew->id = 1; ................................................................................ /* ** Rtree virtual table module xBestIndex method. There are three ** table scan strategies to choose from (in order from most to ** least desirable): ** ** idxNum idxStr Strategy ** ------------------------------------------------ ** 1 "rowid" Direct lookup by rowid. ** 2 "rtree" R-tree overlap query using geopoly_overlap() ** 3 "rtree" R-tree within query using geopoly_within() ** 4 "fullscan" full-table scan. ** ------------------------------------------------ */ static int geopolyBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ int ii; int iRowidTerm = -1; int iFuncTerm = -1; int idxNum = 0; for(ii=0; ii<pIdxInfo->nConstraint; ii++){ struct sqlite3_index_constraint *p = &pIdxInfo->aConstraint[ii]; if( !p->usable ) continue; if( p->iColumn<0 && p->op==SQLITE_INDEX_CONSTRAINT_EQ ){ iRowidTerm = ii; break; } if( p->iColumn==0 && p->op>=SQLITE_INDEX_CONSTRAINT_FUNCTION ){ /* p->op==SQLITE_INDEX_CONSTRAINT_FUNCTION for geopoly_overlap() ** p->op==(SQLITE_INDEX_CONTRAINT_FUNCTION+1) for geopoly_within(). ** See geopolyFindFunction() */ iFuncTerm = ii; idxNum = p->op - SQLITE_INDEX_CONSTRAINT_FUNCTION + 2; } } if( iRowidTerm>=0 ){ pIdxInfo->idxNum = 1; pIdxInfo->idxStr = "rowid"; pIdxInfo->aConstraintUsage[iRowidTerm].argvIndex = 1; ................................................................................ pIdxInfo->aConstraintUsage[iRowidTerm].omit = 1; pIdxInfo->estimatedCost = 30.0; pIdxInfo->estimatedRows = 1; pIdxInfo->idxFlags = SQLITE_INDEX_SCAN_UNIQUE; return SQLITE_OK; } if( iFuncTerm>=0 ){ pIdxInfo->idxNum = idxNum; pIdxInfo->idxStr = "rtree"; pIdxInfo->aConstraintUsage[iFuncTerm].argvIndex = 1; pIdxInfo->aConstraintUsage[iFuncTerm].omit = 0; pIdxInfo->estimatedCost = 300.0; pIdxInfo->estimatedRows = 10; return SQLITE_OK; } pIdxInfo->idxNum = 4; pIdxInfo->idxStr = "fullscan"; pIdxInfo->estimatedCost = 3000000.0; pIdxInfo->estimatedRows = 100000; return SQLITE_OK; } ................................................................................ *pxFunc = geopolyOverlapFunc; *ppArg = 0; return SQLITE_INDEX_CONSTRAINT_FUNCTION; } if( nArg==2 && sqlite3_stricmp(zName, "geopoly_within")==0 ){ *pxFunc = geopolyWithinFunc; *ppArg = 0; return SQLITE_INDEX_CONSTRAINT_FUNCTION+1; } return 0; } static sqlite3_module geopolyModule = { 2, /* iVersion */ |
Changes to ext/rtree/visual01.txt.
391
392
393
394
395
396
397
398
399
400
401
402
403
404
...
410
411
412
413
414
415
416
417
418
419
420
421
422
423
|
FROM geo1, querypoly
WHERE geopoly_overlap(_shape, poly);
SELECT geopoly_svg(poly,
printf('style="fill:%s;fill-opacity:0.5;"',clr)
)
FROM querypoly;
.print '</svg>'
.print '<h1>Within Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
)
................................................................................
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
)
FROM geo1, querypoly
WHERE geopoly_within(_shape, poly);
SELECT geopoly_svg(poly,
printf('style="fill:%s;fill-opacity:0.5;"',clr)
)
FROM querypoly;
.print '</svg>'
.print '<h1>Not Overlap Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
...
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
|
FROM geo1, querypoly
WHERE geopoly_overlap(_shape, poly);
SELECT geopoly_svg(poly,
printf('style="fill:%s;fill-opacity:0.5;"',clr)
)
FROM querypoly;
.print '</svg>'
.print '<h1>Bounding-Box Overlap Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
)
FROM geo1, querypoly
WHERE geopoly_overlap(geopoly_bbox(_shape), geopoly_bbox(poly));
.print '</pre>'
.print '<svg width="1000" height="800" style="border:1px solid black">'
SELECT geopoly_svg(_shape,
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
),
geopoly_svg(geopoly_bbox(_shape),
'style="fill:none;stroke:black;stroke-width:1"'
)
FROM geo1, querypoly
WHERE geopoly_overlap(geopoly_bbox(_shape), geopoly_bbox(poly));
SELECT geopoly_svg(poly,
printf('style="fill:%s;fill-opacity:0.5;"',clr)
)
FROM querypoly;
SELECT geopoly_svg(geopoly_bbox(poly),
'style="fill:none;stroke:black;stroke-width:3"'
)
FROM querypoly;
.print '</svg>'
.print '<h1>Within Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
)
................................................................................
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
)
FROM geo1, querypoly
WHERE geopoly_within(_shape, poly);
SELECT geopoly_svg(poly,
printf('style="fill:%s;fill-opacity:0.5;"',clr)
)
FROM querypoly;
.print '</svg>'
.print '<h1>Bounding-Box WITHIN Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
)
FROM geo1, querypoly
WHERE geopoly_within(geopoly_bbox(_shape), geopoly_bbox(poly));
.print '</pre>'
.print '<svg width="1000" height="800" style="border:1px solid black">'
SELECT geopoly_svg(_shape,
printf('style="fill:none;stroke:%s;stroke-width:1"',geo1.clr)
),
geopoly_svg(geopoly_bbox(_shape),
'style="fill:none;stroke:black;stroke-width:1"'
)
FROM geo1, querypoly
WHERE geopoly_within(geopoly_bbox(_shape), geopoly_bbox(poly));
SELECT geopoly_svg(poly,
printf('style="fill:%s;fill-opacity:0.5;"',clr)
)
FROM querypoly;
SELECT geopoly_svg(geopoly_bbox(poly),
'style="fill:none;stroke:black;stroke-width:3"'
)
FROM querypoly;
.print '</svg>'
.print '<h1>Not Overlap Query</h1>'
.print '<pre>'
EXPLAIN QUERY PLAN
SELECT geopoly_svg(_shape,
|