/ Check-in [1f717385]
Login

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:1f717385340f295064a7649cfc36ad048573cbacb6faa20f5c6067328c40c745
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
Hide Diffs Unified Diffs Ignore Whitespace Patch

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,