Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Enhance the sqlite3_rtree_query_info object to report on the number of elements in the priority queue at each level. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | rtree-enhancements |
Files: | files | file ages | folders |
SHA1: |
f7dad408dd46a1e3612b6142a3afb1d0 |
User & Date: | drh 2014-04-25 16:29:03.796 |
Context
2014-04-28
| ||
17:51 | Add the sqlite3_rtree_query_callback() API to the RTree virtual table. (check-in: 3dca280935 user: drh tags: sessions) | |
2014-04-25
| ||
16:29 | Enhance the sqlite3_rtree_query_info object to report on the number of elements in the priority queue at each level. (Closed-Leaf check-in: f7dad408dd user: drh tags: rtree-enhancements) | |
2014-04-21
| ||
18:13 | Fix the generation of sqlite3_rtree_query_info.iRowid and add test cases to verify that it is fixed. (check-in: eba95ead49 user: drh tags: rtree-enhancements) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 | u8 atEOF; /* True if at end of search */ u8 bPoint; /* True if sPoint is valid */ int iStrategy; /* Copy of idxNum search parameter */ int nConstraint; /* Number of entries in aConstraint */ RtreeConstraint *aConstraint; /* Search constraints. */ int nPointAlloc; /* Number of slots allocated for aPoint[] */ int nPoint; /* Number of slots used in aPoint[] */ RtreeSearchPoint *aPoint; /* Priority queue for search points */ RtreeSearchPoint sPoint; /* Cached next search point */ RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */ }; /* Return the Rtree of a RtreeCursor */ #define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab)) /* ** A coordinate can be either a floating point number or a integer. All | > > | 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 | u8 atEOF; /* True if at end of search */ u8 bPoint; /* True if sPoint is valid */ int iStrategy; /* Copy of idxNum search parameter */ int nConstraint; /* Number of entries in aConstraint */ RtreeConstraint *aConstraint; /* Search constraints. */ int nPointAlloc; /* Number of slots allocated for aPoint[] */ int nPoint; /* Number of slots used in aPoint[] */ int mxLevel; /* iLevel value for root of the tree */ RtreeSearchPoint *aPoint; /* Priority queue for search points */ RtreeSearchPoint sPoint; /* Cached next search point */ RtreeNode *aNode[RTREE_CACHE_SZ]; /* Rtree node cache */ u32 anQueue[RTREE_MAX_DEPTH+1]; /* Number of queued entries by iLevel */ }; /* Return the Rtree of a RtreeCursor */ #define RTREE_OF_CURSOR(X) ((Rtree*)((X)->base.pVtab)) /* ** A coordinate can be either a floating point number or a integer. All |
︙ | ︙ | |||
1175 1176 1177 1178 1179 1180 1181 | if( pNew==0 ) return 0; pCur->aPoint = pNew; pCur->nPointAlloc = nNew; } i = pCur->nPoint++; pNew = pCur->aPoint + i; pNew->rScore = rScore; | | > | 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 | if( pNew==0 ) return 0; pCur->aPoint = pNew; pCur->nPointAlloc = nNew; } i = pCur->nPoint++; pNew = pCur->aPoint + i; pNew->rScore = rScore; pNew->iLevel = iLevel; assert( iLevel>=0 && iLevel<=RTREE_MAX_DEPTH ); while( i>0 ){ RtreeSearchPoint *pParent; j = (i-1)/2; pParent = pCur->aPoint + j; if( rtreeSearchPointCompare(pNew, pParent)>=0 ) break; rtreeSearchPointSwap(pCur, j, i); i = j; |
︙ | ︙ | |||
1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 | static RtreeSearchPoint *rtreeSearchPointNew( RtreeCursor *pCur, /* The cursor */ RtreeDValue rScore, /* Score for the new search point */ u8 iLevel /* Level for the new search point */ ){ 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); | > | 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 | static RtreeSearchPoint *rtreeSearchPointNew( RtreeCursor *pCur, /* The cursor */ RtreeDValue rScore, /* Score for the new search point */ u8 iLevel /* Level for the new search point */ ){ RtreeSearchPoint *pNew, *pFirst; pFirst = rtreeSearchPointFirst(pCur); pCur->anQueue[iLevel]++; if( pFirst==0 || pFirst->rScore>rScore || (pFirst->rScore==rScore && pFirst->iLevel>iLevel) ){ if( pCur->bPoint ){ int ii; pNew = rtreeEnqueue(pCur, rScore, iLevel); |
︙ | ︙ | |||
1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 | i = 1 - p->bPoint; assert( i==0 || i==1 ); if( p->aNode[i] ){ nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); 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; | > > | 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 | i = 1 - p->bPoint; assert( i==0 || i==1 ); if( p->aNode[i] ){ nodeRelease(RTREE_OF_CURSOR(p), p->aNode[i]); p->aNode[i] = 0; } if( p->bPoint ){ p->anQueue[p->sPoint.iLevel]--; p->bPoint = 0; }else if( p->nPoint ){ p->anQueue[p->aPoint[0].iLevel]--; 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; |
︙ | ︙ | |||
1549 1550 1551 1552 1553 1554 1555 | }else{ pCsr->atEOF = 1; } }else{ /* Normal case - r-tree scan. Set up the RtreeCursor.aConstraint array ** with the configured constraints. */ | > | > > > < < < < > > | 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 | }else{ 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 && argc>0 ){ pCsr->aConstraint = sqlite3_malloc(sizeof(RtreeConstraint)*argc); pCsr->nConstraint = argc; if( !pCsr->aConstraint ){ rc = SQLITE_NOMEM; }else{ memset(pCsr->aConstraint, 0, sizeof(RtreeConstraint)*argc); memset(pCsr->anQueue, 0, sizeof(u32)*(pRtree->iDepth + 1)); assert( (idxStr==0 && argc==0) || (idxStr && (int)strlen(idxStr)==argc*2) ); for(ii=0; ii<argc; ii++){ RtreeConstraint *p = &pCsr->aConstraint[ii]; p->op = idxStr[ii*2]; p->iCoord = idxStr[ii*2+1]-'0'; if( p->op>=RTREE_MATCH ){ /* A MATCH operator. The right-hand-side must be a blob that ** can be cast into an RtreeMatchArg object. One created using ** an sqlite3_rtree_geometry_callback() SQL user function. */ rc = deserializeGeometry(argv[ii], p); if( rc!=SQLITE_OK ){ break; } p->pInfo->nCoord = pRtree->nDim*2; p->pInfo->anQueue = pCsr->anQueue; p->pInfo->mxLevel = pRtree->iDepth + 1; }else{ #ifdef SQLITE_RTREE_INT_ONLY p->u.rValue = sqlite3_value_int64(argv[ii]); #else p->u.rValue = sqlite3_value_double(argv[ii]); #endif } } } } if( rc==SQLITE_OK ){ RtreeSearchPoint *pNew; pNew = rtreeSearchPointNew(pCsr, RTREE_ZERO, 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; pRoot = 0; RTREE_QUEUE_TRACE(pCsr, "PUSH-Fm:"); rc = rtreeStepToLeaf(pCsr); } } nodeRelease(pRtree, pRoot); rtreeRelease(pRtree); return rc; } /* ** Set the pIdxInfo->estimatedRows variable to nRow. Unless this ** extension is currently being used by a version of SQLite too old to |
︙ | ︙ |
Changes to ext/rtree/sqlite3rtree.h.
︙ | ︙ | |||
85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | 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 */ }; | > > | 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | 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 */ unsigned int *anQueue; /* Number of pending entries in the queue */ int nCoord; /* Number of coordinates */ int iLevel; /* Level of current node or entry */ int mxLevel; /* The largest iLevel value in the tree */ 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 */ }; |
︙ | ︙ |