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 |
| Timelines: | family | ancestors | descendants | both | rtree-geopoly |
| Files: | files | file ages | folders |
| SHA3-256: |
1f717385340f295064a7649cfc36ad04 |
| User & Date: | drh 2018-08-25 23:03:27.261 |
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: 5a0e154103 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: 1f71738534 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: 6eb5d09b7f user: drh tags: rtree-geopoly) | |
Changes
Changes to ext/rtree/geopoly.c.
| ︙ | ︙ | |||
1105 1106 1107 1108 1109 1110 1111 | ** 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] | | > > | 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 |
** 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 */
){
|
| ︙ | ︙ | |||
1155 1156 1157 1158 1159 1160 1161 |
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);
| | > > | | | | | | | | | | | | | | | > > > > > > > > > > > > > > > > > > | 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 |
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;
|
| ︙ | ︙ | |||
1214 1215 1216 1217 1218 1219 1220 | /* ** 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 ** ------------------------------------------------ | | | | > > > | > > > | | | 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 |
/*
** 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;
}
|
| ︙ | ︙ | |||
1457 1458 1459 1460 1461 1462 1463 |
*pxFunc = geopolyOverlapFunc;
*ppArg = 0;
return SQLITE_INDEX_CONSTRAINT_FUNCTION;
}
if( nArg==2 && sqlite3_stricmp(zName, "geopoly_within")==0 ){
*pxFunc = geopolyWithinFunc;
*ppArg = 0;
| | | 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 |
*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 405 406 407 408 409 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)
)
FROM geo1, querypoly
WHERE geopoly_within(_shape, 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)
)
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 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 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)
)
FROM geo1, querypoly
WHERE geopoly_within(_shape, 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)
)
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,
|
| ︙ | ︙ |