/ Check-in [a439ddd6]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Bug fixes to the priority-queue implementation for R-Trees. Improved tracing capability. Some queries work now, but still many problems.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | rtree-queue
Files: files | file ages | folders
SHA1: a439ddd629c6bb5ea2e7e274673fee4f5c207acf
User & Date: drh 2014-04-16 13:00:08
Context
2014-04-16
14:45
Fix a bug in rowid=? query handling. More problems remain. check-in: 5b0e6ba4 user: drh tags: rtree-queue
13:00
Bug fixes to the priority-queue implementation for R-Trees. Improved tracing capability. Some queries work now, but still many problems. check-in: a439ddd6 user: drh tags: rtree-queue
2014-04-15
21:06
Initial attempt at getting R-Tree queries to work using a priority queue. This check-in compiles, but R-Trees do not work well. And there are debugging printf()s left in the code. This is an incremental check-in. check-in: 53688a25 user: drh tags: rtree-queue
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/rtree/rtree.c.

1094
1095
1096
1097
1098
1099
1100

1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
....
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
....
1217
1218
1219
1220
1221
1222
1223




1224
1225
1226
1227
1228
1229
1230
....
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
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
....
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
....
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
....
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
** Interchange to search points in a cursor.
*/
static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
  RtreeSearchPoint t = p->aPoint[i];
  assert( i<j );
  p->aPoint[i] = p->aPoint[j];
  p->aPoint[j] = t;

  if( i<RTREE_CACHE_SZ-1 ){
    if( j>=RTREE_CACHE_SZ-1 ){
      nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i+1]);
      p->aNode[i+1] = 0;
    }else{
      RtreeNode *pTemp = p->aNode[i+i];
      p->aNode[i+1] = p->aNode[j+1];
      p->aNode[j+1] = pTemp;
    }
  }
}

/*
** Return the search point with the lowest current score.
*/
................................................................................
  RtreeSearchPoint *pNew, *pFirst;
  pFirst = rtreeSearchPointFirst(pCur);
  if( pFirst==0
   || pFirst->rScore>rScore 
   || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
  ){
    if( pCur->bPoint ){

      pNew = rtreeEnqueue(pCur, rScore, iLevel);
      if( pNew==0 ) return 0;


      assert( pCur->aNode[1]==0 );
      pCur->aNode[1] = pCur->aNode[0];



      pCur->aNode[0] = 0;
      *pNew = pCur->sPoint;
    }
    pCur->sPoint.rScore = rScore;
    pCur->sPoint.iLevel = iLevel;
    pCur->bPoint = 1;
    return &pCur->sPoint;
  }else{
    return rtreeEnqueue(pCur, rScore, iLevel);
  }
}















static void traceTop(RtreeCursor *pCur, const char *zPrefix){
  RtreeSearchPoint *p = rtreeSearchPointFirst(pCur);


  if( p ){
    printf("=== %6s id=%lld lvl=%d iCell=%d rScore=%g eWithin=%d\n",
       zPrefix, p->id, p->iLevel, p->iCell, p->rScore, p->eWithin);

  }



}





/* Remove the search point with the lowest current score.
*/
static void rtreeSearchPointPop(RtreeCursor *p){
  int i, j, k, n;
  i = p->bPoint;
  assert( i==0 || i==1 );
................................................................................
    p->aNode[i] = 0;
  }
  if( p->bPoint ){
    p->bPoint = 0;
  }else if( p->nPoint ){
    n = --p->nPoint;
    p->aPoint[0] = p->aPoint[n];




    i = 0;
    while( (j = i*2+1)<n ){
      k = j+1;
      if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
        if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
          rtreeSearchPointSwap(p, i, k);
          i = k;
................................................................................
        rc = rtreeTestEntry(pCur, &cell, &eWithin);
      }else{
        rc = rtreeTestCell(pCur, &cell, &eWithin);
      }
      if( rc ) return rc;
      x = *p;
      p->iCell++;

      if( p->iCell>=nCell ){
traceTop(pCur, "POP:");
        rtreeSearchPointPop(pCur);
      }
      if( eWithin==NOT_WITHIN ) continue;
      pNew = rtreeSearchPointNew(pCur, /*rScore*/0.0, x.iLevel-1);
      if( pNew==0 ) return SQLITE_NOMEM;
      pNew->eWithin = eWithin;
      if( pNew->iLevel ){
        pNew->id = cell.iRowid;
        pNew->iCell = 0;
      }else{
        pNew->id = x.id;
        pNew->iCell = x.iCell;
      }

traceTop(pCur, "PUSH:");
      break;
    }




  }
  pCur->atEOF = p==0;
  return SQLITE_OK;
}

/* 
** Rtree virtual table module xNext method.
*/
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
  RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  int rc = SQLITE_OK;

  /* Move to the next entry that matches the configured constraints. */
traceTop(pCsr, "POP:");
  rtreeSearchPointPop(pCsr);
  rtreeStepToLeaf(pCsr);
  return rc;
}

/* 
** Rtree virtual table module xRowid method.
................................................................................
    p = rtreeSearchPointNew(pCsr, 0.0, 0);
    if( p==0 ) return SQLITE_NOMEM;
    rc = findLeafNode(pRtree, iRowid, &pLeaf, &p->id);
    pCsr->aNode[0] = pLeaf;
    p->eWithin = PARTLY_WITHIN;
    if( rc ) rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
    p->iCell = iCell;
traceTop(pCsr, "PUSH:");
  }else{
    /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
    ** with the configured constraints. 
    */
    if( argc>0 ){
      pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
      pCsr->nConstraint = argc;
................................................................................
      RtreeSearchPoint *pNew = rtreeSearchPointNew(pCsr, 0.0, pRtree->iDepth+1);
      if( pNew==0 ) return SQLITE_NOMEM;
      pNew->id = 1;
      pNew->iCell = 0;
      pNew->eWithin = PARTLY_WITHIN;
      assert( pCsr->bPoint==1 );
      pCsr->aNode[0] = pRoot;
traceTop(pCsr, "PUSH:");
      rc = rtreeStepToLeaf(pCsr);
    }
  }

  rtreeRelease(pRtree);
  return rc;
}
................................................................................
    int jj;

    nodeGetCell(&tree, &node, ii, &cell);
    sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
    nCell = (int)strlen(zCell);
    for(jj=0; jj<tree.nDim*2; jj++){
#ifndef SQLITE_RTREE_INT_ONLY
      sqlite3_snprintf(512-nCell,&zCell[nCell], " %f",
                       (double)cell.aCoord[jj].f);
#else
      sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
                       cell.aCoord[jj].i);
#endif
      nCell = (int)strlen(zCell);
    }







>
|
|
|
|

|
|
|







 







>


>
>
|
|
>
>
>












>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
<
>
>
|
<
<
>

>
>
>
|
>
>
>
>







 







>
>
>
>







 







>

|


<










>
|


>
>
>
>













|







 







|







 







|







 







|







1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
....
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
1221
1222

1223
1224
1225


1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
....
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
....
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315

1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
....
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
....
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
....
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
** Interchange to search points in a cursor.
*/
static void rtreeSearchPointSwap(RtreeCursor *p, int i, int j){
  RtreeSearchPoint t = p->aPoint[i];
  assert( i<j );
  p->aPoint[i] = p->aPoint[j];
  p->aPoint[j] = t;
  i++; j++;
  if( i<RTREE_CACHE_SZ ){
    if( j>=RTREE_CACHE_SZ ){
      nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]);
      p->aNode[i] = 0;
    }else{
      RtreeNode *pTemp = p->aNode[i];
      p->aNode[i] = p->aNode[j];
      p->aNode[j] = pTemp;
    }
  }
}

/*
** Return the search point with the lowest current score.
*/
................................................................................
  RtreeSearchPoint *pNew, *pFirst;
  pFirst = rtreeSearchPointFirst(pCur);
  if( pFirst==0
   || pFirst->rScore>rScore 
   || (pFirst->rScore==rScore && pFirst->iLevel>iLevel)
  ){
    if( pCur->bPoint ){
      int ii;
      pNew = rtreeEnqueue(pCur, rScore, iLevel);
      if( pNew==0 ) return 0;
      ii = (int)(pNew - pCur->aPoint) + 1;
      if( ii<RTREE_CACHE_SZ ){
        assert( pCur->aNode[ii]==0 );
        pCur->aNode[ii] = pCur->aNode[0];
       }else{
        nodeRelease(RTREE_OF_CURSOR(pCur), pCur->aNode[0]);
      }
      pCur->aNode[0] = 0;
      *pNew = pCur->sPoint;
    }
    pCur->sPoint.rScore = rScore;
    pCur->sPoint.iLevel = iLevel;
    pCur->bPoint = 1;
    return &pCur->sPoint;
  }else{
    return rtreeEnqueue(pCur, rScore, iLevel);
  }
}

#if 0
/* Tracing routines for the RtreeSearchPoint queue */
static void tracePoint(RtreeSearchPoint *p, int idx, RtreeCursor *pCur){
  if( idx<0 ){ printf(" s"); }else{ printf("%2d", idx); }
  printf(" %d.%05lld.%02d %g %d",
    p->iLevel, p->id, p->iCell, p->rScore, p->eWithin
  );
  idx++;
  if( idx<RTREE_CACHE_SZ ){
    printf(" %p\n", pCur->aNode[idx]);
  }else{
    printf("\n");
  }
}
static void traceQueue(RtreeCursor *pCur, const char *zPrefix){

  int ii;
  printf("=== %9s ", zPrefix);
  if( pCur->bPoint ){


    tracePoint(&pCur->sPoint, -1, pCur);
  }
  for(ii=0; ii<pCur->nPoint; ii++){
    if( ii>0 || pCur->bPoint ) printf("              ");
    tracePoint(&pCur->aPoint[ii], ii, pCur);
  }
}
#else
# define RTREE_QUEUE_TRACE(A,B)   /* no-op */
#endif

/* Remove the search point with the lowest current score.
*/
static void rtreeSearchPointPop(RtreeCursor *p){
  int i, j, k, n;
  i = p->bPoint;
  assert( i==0 || i==1 );
................................................................................
    p->aNode[i] = 0;
  }
  if( p->bPoint ){
    p->bPoint = 0;
  }else if( p->nPoint ){
    n = --p->nPoint;
    p->aPoint[0] = p->aPoint[n];
    if( n<RTREE_CACHE_SZ-1 ){
      p->aNode[1] = p->aNode[n+1];
      p->aNode[n+1] = 0;
    }
    i = 0;
    while( (j = i*2+1)<n ){
      k = j+1;
      if( k<n && rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[j])<0 ){
        if( rtreeSearchPointCompare(&p->aPoint[k], &p->aPoint[i])<0 ){
          rtreeSearchPointSwap(p, i, k);
          i = k;
................................................................................
        rc = rtreeTestEntry(pCur, &cell, &eWithin);
      }else{
        rc = rtreeTestCell(pCur, &cell, &eWithin);
      }
      if( rc ) return rc;
      x = *p;
      p->iCell++;
      if( eWithin==NOT_WITHIN ) continue;
      if( p->iCell>=nCell ){
        RTREE_QUEUE_TRACE(pCur, "POP-S:");
        rtreeSearchPointPop(pCur);
      }

      pNew = rtreeSearchPointNew(pCur, /*rScore*/0.0, x.iLevel-1);
      if( pNew==0 ) return SQLITE_NOMEM;
      pNew->eWithin = eWithin;
      if( pNew->iLevel ){
        pNew->id = cell.iRowid;
        pNew->iCell = 0;
      }else{
        pNew->id = x.id;
        pNew->iCell = x.iCell;
      }
      p = pNew;
      RTREE_QUEUE_TRACE(pCur, "PUSH-S:");
      break;
    }
    if( p->iCell>=nCell ){
      RTREE_QUEUE_TRACE(pCur, "POP-Se:");
      rtreeSearchPointPop(pCur);
    }
  }
  pCur->atEOF = p==0;
  return SQLITE_OK;
}

/* 
** Rtree virtual table module xNext method.
*/
static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){
  RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor;
  int rc = SQLITE_OK;

  /* Move to the next entry that matches the configured constraints. */
  RTREE_QUEUE_TRACE(pCsr, "POP-Nx:");
  rtreeSearchPointPop(pCsr);
  rtreeStepToLeaf(pCsr);
  return rc;
}

/* 
** Rtree virtual table module xRowid method.
................................................................................
    p = rtreeSearchPointNew(pCsr, 0.0, 0);
    if( p==0 ) return SQLITE_NOMEM;
    rc = findLeafNode(pRtree, iRowid, &pLeaf, &p->id);
    pCsr->aNode[0] = pLeaf;
    p->eWithin = PARTLY_WITHIN;
    if( rc ) rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell);
    p->iCell = iCell;
    RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:");
  }else{
    /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array 
    ** with the configured constraints. 
    */
    if( argc>0 ){
      pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc);
      pCsr->nConstraint = argc;
................................................................................
      RtreeSearchPoint *pNew = rtreeSearchPointNew(pCsr, 0.0, pRtree->iDepth+1);
      if( pNew==0 ) return SQLITE_NOMEM;
      pNew->id = 1;
      pNew->iCell = 0;
      pNew->eWithin = PARTLY_WITHIN;
      assert( pCsr->bPoint==1 );
      pCsr->aNode[0] = pRoot;
      RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:");
      rc = rtreeStepToLeaf(pCsr);
    }
  }

  rtreeRelease(pRtree);
  return rc;
}
................................................................................
    int jj;

    nodeGetCell(&tree, &node, ii, &cell);
    sqlite3_snprintf(512-nCell,&zCell[nCell],"%lld", cell.iRowid);
    nCell = (int)strlen(zCell);
    for(jj=0; jj<tree.nDim*2; jj++){
#ifndef SQLITE_RTREE_INT_ONLY
      sqlite3_snprintf(512-nCell,&zCell[nCell], " %g",
                       (double)cell.aCoord[jj].f);
#else
      sqlite3_snprintf(512-nCell,&zCell[nCell], " %d",
                       cell.aCoord[jj].i);
#endif
      nCell = (int)strlen(zCell);
    }