Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Merge latest trunk enhancements and fixes into the orderby-planning branch. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | orderby-planning |
Files: | files | file ages | folders |
SHA1: |
84862d3a095629d20c8e7b8a16f4dc26 |
User & Date: | drh 2014-05-02 13:09:06.754 |
Context
2014-05-02
| ||
15:25 | Fix a faulty assert() statement. (check-in: 9196ce4073 user: drh tags: orderby-planning) | |
13:09 | Merge latest trunk enhancements and fixes into the orderby-planning branch. (check-in: 84862d3a09 user: drh tags: orderby-planning) | |
00:09 | Add a comment explaining why WhereLoop cost adjustments are omitted for skip-scan loops. (check-in: 3bc43594aa user: drh tags: trunk) | |
2014-04-24
| ||
16:25 | Improved header comment on the vdbesort.c module. No changes to code. (check-in: bf09ce24d0 user: drh tags: orderby-planning) | |
Changes
Changes to ext/rtree/rtree.c.
︙ | ︙ | |||
50 51 52 53 54 55 56 | ** of 4-byte coordinates. For leaf nodes the integer is the rowid ** of a record. For internal nodes it is the node number of a ** child page. */ #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < > > > | | | > | < | 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | ** of 4-byte coordinates. For leaf nodes the integer is the rowid ** of a record. For internal nodes it is the node number of a ** child page. */ #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_RTREE) #ifndef SQLITE_CORE #include "sqlite3ext.h" SQLITE_EXTENSION_INIT1 #else #include "sqlite3.h" #endif #include <string.h> #include <assert.h> #include <stdio.h> #ifndef SQLITE_AMALGAMATION #include "sqlite3rtree.h" typedef sqlite3_int64 i64; typedef unsigned char u8; typedef unsigned short u16; typedef unsigned int u32; #endif /* The following macro is used to suppress compiler warnings. */ #ifndef UNUSED_PARAMETER # define UNUSED_PARAMETER(x) (void)(x) #endif typedef struct Rtree Rtree; typedef struct RtreeCursor RtreeCursor; typedef struct RtreeNode RtreeNode; typedef struct RtreeCell RtreeCell; typedef struct RtreeConstraint RtreeConstraint; typedef struct RtreeMatchArg RtreeMatchArg; typedef struct RtreeGeomCallback RtreeGeomCallback; typedef union RtreeCoord RtreeCoord; typedef struct RtreeSearchPoint RtreeSearchPoint; /* The rtree may have between 1 and RTREE_MAX_DIMENSIONS dimensions. */ #define RTREE_MAX_DIMENSIONS 5 /* Size of hash table Rtree.aHash. This hash table is not expected to ** ever contain very many entries, so a fixed number of buckets is ** used. */ #define HASHSIZE 97 /* The xBestIndex method of this virtual table requires an estimate of ** the number of rows in the virtual table to calculate the costs of ** various strategies. If possible, this estimate is loaded from the ** sqlite_stat1 table (with RTREE_MIN_ROWEST as a hard-coded minimum). ** Otherwise, if no sqlite_stat1 entry is available, use ** RTREE_DEFAULT_ROWEST. */ #define RTREE_DEFAULT_ROWEST 1048576 #define RTREE_MIN_ROWEST 100 /* ** An rtree virtual-table object. */ struct Rtree { sqlite3_vtab base; /* Base class. Must be first */ sqlite3 *db; /* Host database connection */ int iNodeSize; /* Size in bytes of each node in the node table */ u8 nDim; /* Number of dimensions */ u8 eCoordType; /* RTREE_COORD_REAL32 or RTREE_COORD_INT32 */ u8 nBytesPerCell; /* Bytes consumed per cell */ int iDepth; /* Current depth of the r-tree structure */ char *zDb; /* Name of database containing r-tree table */ char *zName; /* Name of r-tree table */ int nBusy; /* Current number of users of this structure */ i64 nRowEst; /* Estimated number of rows in this table */ /* List of nodes removed during a CondenseTree operation. List is ** linked together via the pointer normally used for hash chains - ** RtreeNode.pNext. RtreeNode.iNode stores the depth of the sub-tree ** headed by the node (leaf nodes have RtreeNode.iNode==0). |
︙ | ︙ | |||
182 183 184 185 186 187 188 | sqlite3_stmt *pDeleteRowid; /* Statements to read/write/delete a record from xxx_parent */ sqlite3_stmt *pReadParent; sqlite3_stmt *pWriteParent; sqlite3_stmt *pDeleteParent; | | | > > > > > > > > > > > > > > > > > > > | 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | sqlite3_stmt *pDeleteRowid; /* Statements to read/write/delete a record from xxx_parent */ sqlite3_stmt *pReadParent; sqlite3_stmt *pWriteParent; sqlite3_stmt *pDeleteParent; RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */ }; /* Possible values for Rtree.eCoordType: */ #define RTREE_COORD_REAL32 0 #define RTREE_COORD_INT32 1 /* ** If SQLITE_RTREE_INT_ONLY is defined, then this virtual table will ** only deal with integer coordinates. No floating point operations ** will be done. */ #ifdef SQLITE_RTREE_INT_ONLY typedef sqlite3_int64 RtreeDValue; /* High accuracy coordinate */ typedef int RtreeValue; /* Low accuracy coordinate */ # define RTREE_ZERO 0 #else typedef double RtreeDValue; /* High accuracy coordinate */ typedef float RtreeValue; /* Low accuracy coordinate */ # define RTREE_ZERO 0.0 #endif /* ** When doing a search of an r-tree, instances of the following structure ** record intermediate results from the tree walk. ** ** The id is always a node-id. For iLevel>=1 the id is the node-id of ** the node that the RtreeSearchPoint represents. When iLevel==0, however, ** the id is of the parent node and the cell that RtreeSearchPoint ** represents is the iCell-th entry in the parent node. */ struct RtreeSearchPoint { RtreeDValue rScore; /* The score for this node. Smallest goes first. */ sqlite3_int64 id; /* Node ID */ u8 iLevel; /* 0=entries. 1=leaf node. 2+ for higher */ u8 eWithin; /* PARTLY_WITHIN or FULLY_WITHIN */ u8 iCell; /* Cell index within the node */ }; /* ** The minimum number of cells allowed for a node is a third of the ** maximum. In Gutman's notation: ** ** m = M/3 ** |
︙ | ︙ | |||
224 225 226 227 228 229 230 231 232 233 234 | ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates). ** Therefore all non-root nodes must contain at least 3 entries. Since ** 2^40 is greater than 2^64, an r-tree structure always has a depth of ** 40 or less. */ #define RTREE_MAX_DEPTH 40 /* ** An rtree cursor object. */ struct RtreeCursor { | > > > > > > > > | | | > > > > > > > > > > > > > > | | > | 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 | ** supported cell size is 48 bytes (8 byte rowid + ten 4 byte coordinates). ** Therefore all non-root nodes must contain at least 3 entries. Since ** 2^40 is greater than 2^64, an r-tree structure always has a depth of ** 40 or less. */ #define RTREE_MAX_DEPTH 40 /* ** Number of entries in the cursor RtreeNode cache. The first entry is ** used to cache the RtreeNode for RtreeCursor.sPoint. The remaining ** entries cache the RtreeNode for the first elements of the priority queue. */ #define RTREE_CACHE_SZ 5 /* ** An rtree cursor object. */ struct RtreeCursor { sqlite3_vtab_cursor base; /* Base class. Must be first */ 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 ** coordinates within a single R-Tree are always of the same time. */ union RtreeCoord { RtreeValue f; /* Floating point value */ int i; /* Integer value */ u32 u; /* Unsigned for byte-order conversions */ }; /* ** The argument is an RtreeCoord. Return the value stored within the RtreeCoord ** formatted as a RtreeDValue (double or int64). This macro assumes that local ** variable pRtree points to the Rtree structure associated with the ** RtreeCoord. |
︙ | ︙ | |||
263 264 265 266 267 268 269 | /* ** A search constraint. */ struct RtreeConstraint { int iCoord; /* Index of constrained coordinate */ int op; /* Constraining operation */ | > | | | > > | | | | | | > > | | | | | | > > | | | > > > > > > > > > > > > > > > > > > > > > > | > | | | < | | | < < < < < < < < < < < < < | 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 | /* ** A search constraint. */ struct RtreeConstraint { int iCoord; /* Index of constrained coordinate */ int op; /* Constraining operation */ union { RtreeDValue rValue; /* Constraint value. */ int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*); int (*xQueryFunc)(sqlite3_rtree_query_info*); } u; sqlite3_rtree_query_info *pInfo; /* xGeom and xQueryFunc argument */ }; /* Possible values for RtreeConstraint.op */ #define RTREE_EQ 0x41 /* A */ #define RTREE_LE 0x42 /* B */ #define RTREE_LT 0x43 /* C */ #define RTREE_GE 0x44 /* D */ #define RTREE_GT 0x45 /* E */ #define RTREE_MATCH 0x46 /* F: Old-style sqlite3_rtree_geometry_callback() */ #define RTREE_QUERY 0x47 /* G: New-style sqlite3_rtree_query_callback() */ /* ** An rtree structure node. */ struct RtreeNode { RtreeNode *pParent; /* Parent node */ i64 iNode; /* The node number */ int nRef; /* Number of references to this node */ int isDirty; /* True if the node needs to be written to disk */ u8 *zData; /* Content of the node, as should be on disk */ RtreeNode *pNext; /* Next node in this hash collision chain */ }; /* Return the number of cells in a node */ #define NCELL(pNode) readInt16(&(pNode)->zData[2]) /* ** A single cell from a node, deserialized */ struct RtreeCell { i64 iRowid; /* Node or entry ID */ RtreeCoord aCoord[RTREE_MAX_DIMENSIONS*2]; /* Bounding box coordinates */ }; /* ** This object becomes the sqlite3_user_data() for the SQL functions ** that are created by sqlite3_rtree_geometry_callback() and ** sqlite3_rtree_query_callback() and which appear on the right of MATCH ** operators in order to constrain a search. ** ** xGeom and xQueryFunc are the callback functions. Exactly one of ** xGeom and xQueryFunc fields is non-NULL, depending on whether the ** SQL function was created using sqlite3_rtree_geometry_callback() or ** sqlite3_rtree_query_callback(). ** ** This object is deleted automatically by the destructor mechanism in ** sqlite3_create_function_v2(). */ struct RtreeGeomCallback { int (*xGeom)(sqlite3_rtree_geometry*, int, RtreeDValue*, int*); int (*xQueryFunc)(sqlite3_rtree_query_info*); void (*xDestructor)(void*); void *pContext; }; /* ** Value for the first field of every RtreeMatchArg object. The MATCH ** operator tests that the first field of a blob operand matches this ** value to avoid operating on invalid blobs (which could cause a segfault). */ #define RTREE_GEOMETRY_MAGIC 0x891245AB /* ** An instance of this structure (in the form of a BLOB) is returned by ** the SQL functions that sqlite3_rtree_geometry_callback() and ** sqlite3_rtree_query_callback() create, and is read as the right-hand ** operand to the MATCH operator of an R-Tree. */ struct RtreeMatchArg { u32 magic; /* Always RTREE_GEOMETRY_MAGIC */ RtreeGeomCallback cb; /* Info about the callback functions */ int nParam; /* Number of parameters to the SQL function */ RtreeDValue aParam[1]; /* Values for parameters to the SQL function */ }; #ifndef MAX # define MAX(x,y) ((x) < (y) ? (y) : (x)) #endif #ifndef MIN # define MIN(x,y) ((x) > (y) ? (y) : (x)) |
︙ | ︙ | |||
422 423 424 425 426 427 428 | } /* ** Given a node number iNode, return the corresponding key to use ** in the Rtree.aHash table. */ static int nodeHash(i64 iNode){ | < < < | | 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 | } /* ** Given a node number iNode, return the corresponding key to use ** in the Rtree.aHash table. */ static int nodeHash(i64 iNode){ return iNode % HASHSIZE; } /* ** Search the node hash table for node iNode. If found, return a pointer ** to it. Otherwise, return 0. */ static RtreeNode *nodeHashLookup(Rtree *pRtree, i64 iNode){ |
︙ | ︙ | |||
485 486 487 488 489 490 491 | } return pNode; } /* ** Obtain a reference to an r-tree node. */ | | < | 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 | } return pNode; } /* ** Obtain a reference to an r-tree node. */ static int nodeAcquire( Rtree *pRtree, /* R-tree structure */ i64 iNode, /* Node number to load */ RtreeNode *pParent, /* Either the parent node or NULL */ RtreeNode **ppNode /* OUT: Acquired node */ ){ int rc; int rc2 = SQLITE_OK; |
︙ | ︙ | |||
575 576 577 578 579 580 581 | return rc; } /* ** Overwrite cell iCell of node pNode with the contents of pCell. */ static void nodeOverwriteCell( | | | | | | | < | | | < | | 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 | return rc; } /* ** Overwrite cell iCell of node pNode with the contents of pCell. */ static void nodeOverwriteCell( Rtree *pRtree, /* The overall R-Tree */ RtreeNode *pNode, /* The node into which the cell is to be written */ RtreeCell *pCell, /* The cell to write */ int iCell /* Index into pNode into which pCell is written */ ){ int ii; u8 *p = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; p += writeInt64(p, pCell->iRowid); for(ii=0; ii<(pRtree->nDim*2); ii++){ p += writeCoord(p, &pCell->aCoord[ii]); } pNode->isDirty = 1; } /* ** Remove the cell with index iCell from node pNode. */ static void nodeDeleteCell(Rtree *pRtree, RtreeNode *pNode, int iCell){ u8 *pDst = &pNode->zData[4 + pRtree->nBytesPerCell*iCell]; u8 *pSrc = &pDst[pRtree->nBytesPerCell]; int nByte = (NCELL(pNode) - iCell - 1) * pRtree->nBytesPerCell; memmove(pDst, pSrc, nByte); writeInt16(&pNode->zData[2], NCELL(pNode)-1); pNode->isDirty = 1; } /* ** Insert the contents of cell pCell into node pNode. If the insert ** is successful, return SQLITE_OK. ** ** If there is not enough free space in pNode, return SQLITE_FULL. */ static int nodeInsertCell( Rtree *pRtree, /* The overall R-Tree */ RtreeNode *pNode, /* Write new cell into this node */ RtreeCell *pCell /* The cell to be inserted */ ){ int nCell; /* Current number of cells in pNode */ int nMaxCell; /* Maximum number of cells for pNode */ nMaxCell = (pRtree->iNodeSize-4)/pRtree->nBytesPerCell; nCell = NCELL(pNode); assert( nCell<=nMaxCell ); if( nCell<nMaxCell ){ nodeOverwriteCell(pRtree, pNode, pCell, nCell); writeInt16(&pNode->zData[2], nCell+1); pNode->isDirty = 1; } return (nCell==nMaxCell); } /* ** If the node is dirty, write it out to the database. */ static int nodeWrite(Rtree *pRtree, RtreeNode *pNode){ int rc = SQLITE_OK; if( pNode->isDirty ){ sqlite3_stmt *p = pRtree->pWriteNode; if( pNode->iNode ){ sqlite3_bind_int64(p, 1, pNode->iNode); }else{ sqlite3_bind_null(p, 1); |
︙ | ︙ | |||
658 659 660 661 662 663 664 | return rc; } /* ** Release a reference to a node. If the node is dirty and the reference ** count drops to zero, the node data is written to the database. */ | < | | 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 | return rc; } /* ** Release a reference to a node. If the node is dirty and the reference ** count drops to zero, the node data is written to the database. */ static int nodeRelease(Rtree *pRtree, RtreeNode *pNode){ int rc = SQLITE_OK; if( pNode ){ assert( pNode->nRef>0 ); pNode->nRef--; if( pNode->nRef==0 ){ if( pNode->iNode==1 ){ pRtree->iDepth = -1; |
︙ | ︙ | |||
687 688 689 690 691 692 693 | /* ** Return the 64-bit integer value associated with cell iCell of ** node pNode. If pNode is a leaf node, this is a rowid. If it is ** an internal node, then the 64-bit integer is a child page number. */ static i64 nodeGetRowid( | | | | | | | | | | | | | | > > > | | > > | 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 | /* ** Return the 64-bit integer value associated with cell iCell of ** node pNode. If pNode is a leaf node, this is a rowid. If it is ** an internal node, then the 64-bit integer is a child page number. */ static i64 nodeGetRowid( Rtree *pRtree, /* The overall R-Tree */ RtreeNode *pNode, /* The node from which to extract the ID */ int iCell /* The cell index from which to extract the ID */ ){ assert( iCell<NCELL(pNode) ); return readInt64(&pNode->zData[4 + pRtree->nBytesPerCell*iCell]); } /* ** Return coordinate iCoord from cell iCell in node pNode. */ static void nodeGetCoord( Rtree *pRtree, /* The overall R-Tree */ RtreeNode *pNode, /* The node from which to extract a coordinate */ int iCell, /* The index of the cell within the node */ int iCoord, /* Which coordinate to extract */ RtreeCoord *pCoord /* OUT: Space to write result to */ ){ readCoord(&pNode->zData[12 + pRtree->nBytesPerCell*iCell + 4*iCoord], pCoord); } /* ** Deserialize cell iCell of node pNode. Populate the structure pointed ** to by pCell with the results. */ static void nodeGetCell( Rtree *pRtree, /* The overall R-Tree */ RtreeNode *pNode, /* The node containing the cell to be read */ int iCell, /* Index of the cell within the node */ RtreeCell *pCell /* OUT: Write the cell contents here */ ){ u8 *pData; u8 *pEnd; RtreeCoord *pCoord; pCell->iRowid = nodeGetRowid(pRtree, pNode, iCell); pData = pNode->zData + (12 + pRtree->nBytesPerCell*iCell); pEnd = pData + pRtree->nDim*8; pCoord = pCell->aCoord; for(; pData<pEnd; pData+=4, pCoord++){ readCoord(pData, pCoord); } } /* Forward declaration for the function that does the work of ** the virtual table module xCreate() and xConnect() methods. */ |
︙ | ︙ | |||
847 848 849 850 851 852 853 | /* ** Free the RtreeCursor.aConstraint[] array and its contents. */ static void freeCursorConstraints(RtreeCursor *pCsr){ if( pCsr->aConstraint ){ int i; /* Used to iterate through constraint array */ for(i=0; i<pCsr->nConstraint; i++){ | | | | | | > | | | > | > > > > | > > > > > > > < < < < < < < < < | < < | < < < | > > > > > > > > > | < < < < | < < < < < > | < | | | < < < < < | > < < < > > | > | | | | | | | | | | | | < | < < < | > > | < > > | > > > > > > > > | | > > > > > > > > | | < < < < < < < < < < < < < | < < | | > > > > > | | < > > | < < | < < < < | < < < < < < < | < < > > > > | | | | > > > > > | > > | < | > > > | | > | < < < < < < < < < < < < < < < < < > > > > | | | | | < > | < | < < < < | < < > > | < > | | | | | < | > | | < < < | | < < < < < | < < < > | 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 | /* ** Free the RtreeCursor.aConstraint[] array and its contents. */ static void freeCursorConstraints(RtreeCursor *pCsr){ if( pCsr->aConstraint ){ int i; /* Used to iterate through constraint array */ for(i=0; i<pCsr->nConstraint; i++){ sqlite3_rtree_query_info *pInfo = pCsr->aConstraint[i].pInfo; if( pInfo ){ if( pInfo->xDelUser ) pInfo->xDelUser(pInfo->pUser); sqlite3_free(pInfo); } } sqlite3_free(pCsr->aConstraint); pCsr->aConstraint = 0; } } /* ** Rtree virtual table module xClose method. */ static int rtreeClose(sqlite3_vtab_cursor *cur){ Rtree *pRtree = (Rtree *)(cur->pVtab); int ii; RtreeCursor *pCsr = (RtreeCursor *)cur; freeCursorConstraints(pCsr); sqlite3_free(pCsr->aPoint); for(ii=0; ii<RTREE_CACHE_SZ; ii++) nodeRelease(pRtree, pCsr->aNode[ii]); sqlite3_free(pCsr); return SQLITE_OK; } /* ** Rtree virtual table module xEof method. ** ** Return non-zero if the cursor does not currently point to a valid ** record (i.e if the scan has finished), or zero otherwise. */ static int rtreeEof(sqlite3_vtab_cursor *cur){ RtreeCursor *pCsr = (RtreeCursor *)cur; return pCsr->atEOF; } /* ** Convert raw bits from the on-disk RTree record into a coordinate value. ** The on-disk format is big-endian and needs to be converted for little- ** endian platforms. The on-disk record stores integer coordinates if ** eInt is true and it stores 32-bit floating point records if eInt is ** false. a[] is the four bytes of the on-disk record to be decoded. ** Store the results in "r". ** ** There are three versions of this macro, one each for little-endian and ** big-endian processors and a third generic implementation. The endian- ** specific implementations are much faster and are preferred if the ** processor endianness is known at compile-time. The SQLITE_BYTEORDER ** macro is part of sqliteInt.h and hence the endian-specific ** implementation will only be used if this module is compiled as part ** of the amalgamation. */ #if defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==1234 #define RTREE_DECODE_COORD(eInt, a, r) { \ RtreeCoord c; /* Coordinate decoded */ \ memcpy(&c.u,a,4); \ c.u = ((c.u>>24)&0xff)|((c.u>>8)&0xff00)| \ ((c.u&0xff)<<24)|((c.u&0xff00)<<8); \ r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ } #elif defined(SQLITE_BYTEORDER) && SQLITE_BYTEORDER==4321 #define RTREE_DECODE_COORD(eInt, a, r) { \ RtreeCoord c; /* Coordinate decoded */ \ memcpy(&c.u,a,4); \ r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ } #else #define RTREE_DECODE_COORD(eInt, a, r) { \ RtreeCoord c; /* Coordinate decoded */ \ c.u = ((u32)a[0]<<24) + ((u32)a[1]<<16) \ +((u32)a[2]<<8) + a[3]; \ r = eInt ? (sqlite3_rtree_dbl)c.i : (sqlite3_rtree_dbl)c.f; \ } #endif /* ** Check the RTree node or entry given by pCellData and p against the MATCH ** constraint pConstraint. */ static int rtreeCallbackConstraint( RtreeConstraint *pConstraint, /* The constraint to test */ int eInt, /* True if RTree holding integer coordinates */ u8 *pCellData, /* Raw cell content */ RtreeSearchPoint *pSearch, /* Container of this cell */ sqlite3_rtree_dbl *prScore, /* OUT: score for the cell */ int *peWithin /* OUT: visibility of the cell */ ){ int i; /* Loop counter */ sqlite3_rtree_query_info *pInfo = pConstraint->pInfo; /* Callback info */ int nCoord = pInfo->nCoord; /* No. of coordinates */ int rc; /* Callback return code */ sqlite3_rtree_dbl aCoord[RTREE_MAX_DIMENSIONS*2]; /* Decoded coordinates */ assert( pConstraint->op==RTREE_MATCH || pConstraint->op==RTREE_QUERY ); assert( nCoord==2 || nCoord==4 || nCoord==6 || nCoord==8 || nCoord==10 ); if( pConstraint->op==RTREE_QUERY && pSearch->iLevel==1 ){ pInfo->iRowid = readInt64(pCellData); } pCellData += 8; for(i=0; i<nCoord; i++, pCellData += 4){ RTREE_DECODE_COORD(eInt, pCellData, aCoord[i]); } if( pConstraint->op==RTREE_MATCH ){ rc = pConstraint->u.xGeom((sqlite3_rtree_geometry*)pInfo, nCoord, aCoord, &i); if( i==0 ) *peWithin = NOT_WITHIN; *prScore = RTREE_ZERO; }else{ pInfo->aCoord = aCoord; pInfo->iLevel = pSearch->iLevel - 1; pInfo->rScore = pInfo->rParentScore = pSearch->rScore; pInfo->eWithin = pInfo->eParentWithin = pSearch->eWithin; rc = pConstraint->u.xQueryFunc(pInfo); if( pInfo->eWithin<*peWithin ) *peWithin = pInfo->eWithin; if( pInfo->rScore<*prScore || *prScore<RTREE_ZERO ){ *prScore = pInfo->rScore; } } return rc; } /* ** Check the internal RTree node given by pCellData against constraint p. ** If this constraint cannot be satisfied by any child within the node, ** set *peWithin to NOT_WITHIN. */ static void rtreeNonleafConstraint( RtreeConstraint *p, /* The constraint to test */ int eInt, /* True if RTree holds integer coordinates */ u8 *pCellData, /* Raw cell content as appears on disk */ int *peWithin /* Adjust downward, as appropriate */ ){ sqlite3_rtree_dbl val; /* Coordinate value convert to a double */ /* p->iCoord might point to either a lower or upper bound coordinate ** in a coordinate pair. But make pCellData point to the lower bound. */ pCellData += 8 + 4*(p->iCoord&0xfe); assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE || p->op==RTREE_GT || p->op==RTREE_EQ ); switch( p->op ){ case RTREE_LE: case RTREE_LT: case RTREE_EQ: RTREE_DECODE_COORD(eInt, pCellData, val); /* val now holds the lower bound of the coordinate pair */ if( p->u.rValue>=val ) return; if( p->op!=RTREE_EQ ) break; /* RTREE_LE and RTREE_LT end here */ /* Fall through for the RTREE_EQ case */ default: /* RTREE_GT or RTREE_GE, or fallthrough of RTREE_EQ */ pCellData += 4; RTREE_DECODE_COORD(eInt, pCellData, val); /* val now holds the upper bound of the coordinate pair */ if( p->u.rValue<=val ) return; } *peWithin = NOT_WITHIN; } /* ** Check the leaf RTree cell given by pCellData against constraint p. ** If this constraint is not satisfied, set *peWithin to NOT_WITHIN. ** If the constraint is satisfied, leave *peWithin unchanged. ** ** The constraint is of the form: xN op $val ** ** The op is given by p->op. The xN is p->iCoord-th coordinate in ** pCellData. $val is given by p->u.rValue. */ static void rtreeLeafConstraint( RtreeConstraint *p, /* The constraint to test */ int eInt, /* True if RTree holds integer coordinates */ u8 *pCellData, /* Raw cell content as appears on disk */ int *peWithin /* Adjust downward, as appropriate */ ){ RtreeDValue xN; /* Coordinate value converted to a double */ assert(p->op==RTREE_LE || p->op==RTREE_LT || p->op==RTREE_GE || p->op==RTREE_GT || p->op==RTREE_EQ ); pCellData += 8 + p->iCoord*4; RTREE_DECODE_COORD(eInt, pCellData, xN); switch( p->op ){ case RTREE_LE: if( xN <= p->u.rValue ) return; break; case RTREE_LT: if( xN < p->u.rValue ) return; break; case RTREE_GE: if( xN >= p->u.rValue ) return; break; case RTREE_GT: if( xN > p->u.rValue ) return; break; default: if( xN == p->u.rValue ) return; break; } *peWithin = NOT_WITHIN; } /* ** One of the cells in node pNode is guaranteed to have a 64-bit ** integer value equal to iRowid. Return the index of this cell. */ static int nodeRowidIndex( Rtree *pRtree, RtreeNode *pNode, i64 iRowid, int *piIndex ){ int ii; int nCell = NCELL(pNode); assert( nCell<200 ); for(ii=0; ii<nCell; ii++){ if( nodeGetRowid(pRtree, pNode, ii)==iRowid ){ *piIndex = ii; return SQLITE_OK; } } return SQLITE_CORRUPT_VTAB; |
︙ | ︙ | |||
1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 | RtreeNode *pParent = pNode->pParent; if( pParent ){ return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex); } *piIndex = -1; return SQLITE_OK; } /* ** Rtree virtual table module xNext method. */ static int rtreeNext(sqlite3_vtab_cursor *pVtabCursor){ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < < < < < < < < < < < < | < | < < < < < < < < < < < < < < | < < < < | < | > | > | | | > > > > > > < | | | < | > > > > > > | | | > | < < | | | | > > | < < | < | | | > | > > > > | < > > > | | > > | < > > | > > > > > | > | | > > > | | < < | < > | | | | < | < < < < < < | | > | | < | | | | 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 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 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 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 1298 1299 1300 1301 1302 1303 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 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 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 | RtreeNode *pParent = pNode->pParent; if( pParent ){ return nodeRowidIndex(pRtree, pParent, pNode->iNode, piIndex); } *piIndex = -1; return SQLITE_OK; } /* ** Compare two search points. Return negative, zero, or positive if the first ** is less than, equal to, or greater than the second. ** ** The rScore is the primary key. Smaller rScore values come first. ** If the rScore is a tie, then use iLevel as the tie breaker with smaller ** iLevel values coming first. In this way, if rScore is the same for all ** SearchPoints, then iLevel becomes the deciding factor and the result ** is a depth-first search, which is the desired default behavior. */ static int rtreeSearchPointCompare( const RtreeSearchPoint *pA, const RtreeSearchPoint *pB ){ if( pA->rScore<pB->rScore ) return -1; if( pA->rScore>pB->rScore ) return +1; if( pA->iLevel<pB->iLevel ) return -1; if( pA->iLevel>pB->iLevel ) return +1; return 0; } /* ** 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. */ static RtreeSearchPoint *rtreeSearchPointFirst(RtreeCursor *pCur){ return pCur->bPoint ? &pCur->sPoint : pCur->nPoint ? pCur->aPoint : 0; } /* ** Get the RtreeNode for the search point with the lowest score. */ static RtreeNode *rtreeNodeOfFirstSearchPoint(RtreeCursor *pCur, int *pRC){ sqlite3_int64 id; int ii = 1 - pCur->bPoint; assert( ii==0 || ii==1 ); assert( pCur->bPoint || pCur->nPoint ); if( pCur->aNode[ii]==0 ){ assert( pRC!=0 ); id = ii ? pCur->aPoint[0].id : pCur->sPoint.id; *pRC = nodeAcquire(RTREE_OF_CURSOR(pCur), id, 0, &pCur->aNode[ii]); } return pCur->aNode[ii]; } /* ** Push a new element onto the priority queue */ static RtreeSearchPoint *rtreeEnqueue( RtreeCursor *pCur, /* The cursor */ RtreeDValue rScore, /* Score for the new search point */ u8 iLevel /* Level for the new search point */ ){ int i, j; RtreeSearchPoint *pNew; if( pCur->nPoint>=pCur->nPointAlloc ){ int nNew = pCur->nPointAlloc*2 + 8; pNew = sqlite3_realloc(pCur->aPoint, nNew*sizeof(pCur->aPoint[0])); 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; pNew = pParent; } return pNew; } /* ** Allocate a new RtreeSearchPoint and return a pointer to it. Return ** NULL if malloc fails. */ 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); 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); } } # define RTREE_QUEUE_TRACE(A,B) traceQueue(A,B) #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 = 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; 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; }else{ break; } }else{ if( rtreeSearchPointCompare(&p->aPoint[j], &p->aPoint[i])<0 ){ rtreeSearchPointSwap(p, i, j); i = j; }else{ break; } } } } } /* ** Continue the search on cursor pCur until the front of the queue ** contains an entry suitable for returning as a result-set row, ** or until the RtreeSearchPoint queue is empty, indicating that the ** query has completed. */ static int rtreeStepToLeaf(RtreeCursor *pCur){ RtreeSearchPoint *p; Rtree *pRtree = RTREE_OF_CURSOR(pCur); RtreeNode *pNode; int eWithin; int rc = SQLITE_OK; int nCell; int nConstraint = pCur->nConstraint; int ii; int eInt; RtreeSearchPoint x; eInt = pRtree->eCoordType==RTREE_COORD_INT32; while( (p = rtreeSearchPointFirst(pCur))!=0 && p->iLevel>0 ){ pNode = rtreeNodeOfFirstSearchPoint(pCur, &rc); if( rc ) return rc; nCell = NCELL(pNode); assert( nCell<200 ); while( p->iCell<nCell ){ sqlite3_rtree_dbl rScore = (sqlite3_rtree_dbl)-1; u8 *pCellData = pNode->zData + (4+pRtree->nBytesPerCell*p->iCell); eWithin = FULLY_WITHIN; for(ii=0; ii<nConstraint; ii++){ RtreeConstraint *pConstraint = pCur->aConstraint + ii; if( pConstraint->op>=RTREE_MATCH ){ rc = rtreeCallbackConstraint(pConstraint, eInt, pCellData, p, &rScore, &eWithin); if( rc ) return rc; }else if( p->iLevel==1 ){ rtreeLeafConstraint(pConstraint, eInt, pCellData, &eWithin); }else{ rtreeNonleafConstraint(pConstraint, eInt, pCellData, &eWithin); } if( eWithin==NOT_WITHIN ) break; } p->iCell++; if( eWithin==NOT_WITHIN ) continue; x.iLevel = p->iLevel - 1; if( x.iLevel ){ x.id = readInt64(pCellData); x.iCell = 0; }else{ x.id = p->id; x.iCell = p->iCell - 1; } if( p->iCell>=nCell ){ RTREE_QUEUE_TRACE(pCur, "POP-S:"); rtreeSearchPointPop(pCur); } if( rScore<RTREE_ZERO ) rScore = RTREE_ZERO; p = rtreeSearchPointNew(pCur, rScore, x.iLevel); if( p==0 ) return SQLITE_NOMEM; p->eWithin = eWithin; p->id = x.id; p->iCell = x.iCell; 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); rc = rtreeStepToLeaf(pCsr); return rc; } /* ** Rtree virtual table module xRowid method. */ static int rtreeRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){ RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); int rc = SQLITE_OK; RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); if( rc==SQLITE_OK && p ){ *pRowid = nodeGetRowid(RTREE_OF_CURSOR(pCsr), pNode, p->iCell); } return rc; } /* ** Rtree virtual table module xColumn method. */ static int rtreeColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ Rtree *pRtree = (Rtree *)cur->pVtab; RtreeCursor *pCsr = (RtreeCursor *)cur; RtreeSearchPoint *p = rtreeSearchPointFirst(pCsr); RtreeCoord c; int rc = SQLITE_OK; RtreeNode *pNode = rtreeNodeOfFirstSearchPoint(pCsr, &rc); if( rc ) return rc; if( p==0 ) return SQLITE_OK; if( i==0 ){ sqlite3_result_int64(ctx, nodeGetRowid(pRtree, pNode, p->iCell)); }else{ if( rc ) return rc; nodeGetCoord(pRtree, pNode, p->iCell, i-1, &c); #ifndef SQLITE_RTREE_INT_ONLY if( pRtree->eCoordType==RTREE_COORD_REAL32 ){ sqlite3_result_double(ctx, c.f); }else #endif { assert( pRtree->eCoordType==RTREE_COORD_INT32 ); sqlite3_result_int(ctx, c.i); } } return SQLITE_OK; } /* ** Use nodeAcquire() to obtain the leaf node containing the record with ** rowid iRowid. If successful, set *ppLeaf to point to the node and ** return SQLITE_OK. If there is no such record in the table, set ** *ppLeaf to 0 and return SQLITE_OK. If an error occurs, set *ppLeaf ** to zero and return an SQLite error code. */ static int findLeafNode( Rtree *pRtree, /* RTree to search */ i64 iRowid, /* The rowid searching for */ RtreeNode **ppLeaf, /* Write the node here */ sqlite3_int64 *piNode /* Write the node-id here */ ){ int rc; *ppLeaf = 0; sqlite3_bind_int64(pRtree->pReadRowid, 1, iRowid); if( sqlite3_step(pRtree->pReadRowid)==SQLITE_ROW ){ i64 iNode = sqlite3_column_int64(pRtree->pReadRowid, 0); if( piNode ) *piNode = iNode; rc = nodeAcquire(pRtree, iNode, 0, ppLeaf); sqlite3_reset(pRtree->pReadRowid); }else{ rc = sqlite3_reset(pRtree->pReadRowid); } return rc; } /* ** This function is called to configure the RtreeConstraint object passed ** as the second argument for a MATCH constraint. The value passed as the ** first argument to this function is the right-hand operand to the MATCH ** operator. */ static int deserializeGeometry(sqlite3_value *pValue, RtreeConstraint *pCons){ RtreeMatchArg *pBlob; /* BLOB returned by geometry function */ sqlite3_rtree_query_info *pInfo; /* Callback information */ int nBlob; /* Size of the geometry function blob */ int nExpected; /* Expected size of the BLOB */ /* Check that value is actually a blob. */ if( sqlite3_value_type(pValue)!=SQLITE_BLOB ) return SQLITE_ERROR; /* Check that the blob is roughly the right size. */ nBlob = sqlite3_value_bytes(pValue); if( nBlob<(int)sizeof(RtreeMatchArg) || ((nBlob-sizeof(RtreeMatchArg))%sizeof(RtreeDValue))!=0 ){ return SQLITE_ERROR; } pInfo = (sqlite3_rtree_query_info*)sqlite3_malloc( sizeof(*pInfo)+nBlob ); if( !pInfo ) return SQLITE_NOMEM; memset(pInfo, 0, sizeof(*pInfo)); pBlob = (RtreeMatchArg*)&pInfo[1]; memcpy(pBlob, sqlite3_value_blob(pValue), nBlob); nExpected = (int)(sizeof(RtreeMatchArg) + (pBlob->nParam-1)*sizeof(RtreeDValue)); if( pBlob->magic!=RTREE_GEOMETRY_MAGIC || nBlob!=nExpected ){ sqlite3_free(pInfo); return SQLITE_ERROR; } pInfo->pContext = pBlob->cb.pContext; pInfo->nParam = pBlob->nParam; pInfo->aParam = pBlob->aParam; if( pBlob->cb.xGeom ){ pCons->u.xGeom = pBlob->cb.xGeom; }else{ pCons->op = RTREE_QUERY; pCons->u.xQueryFunc = pBlob->cb.xQueryFunc; } pCons->pInfo = pInfo; return SQLITE_OK; } /* ** Rtree virtual table module xFilter method. */ static int rtreeFilter( sqlite3_vtab_cursor *pVtabCursor, int idxNum, const char *idxStr, int argc, sqlite3_value **argv ){ Rtree *pRtree = (Rtree *)pVtabCursor->pVtab; RtreeCursor *pCsr = (RtreeCursor *)pVtabCursor; RtreeNode *pRoot = 0; int ii; int rc = SQLITE_OK; int iCell = 0; rtreeReference(pRtree); freeCursorConstraints(pCsr); pCsr->iStrategy = idxNum; if( idxNum==1 ){ /* Special case - lookup by rowid. */ RtreeNode *pLeaf; /* Leaf on which the required cell resides */ RtreeSearchPoint *p; /* Search point for the the leaf */ i64 iRowid = sqlite3_value_int64(argv[0]); i64 iNode = 0; rc = findLeafNode(pRtree, iRowid, &pLeaf, &iNode); if( rc==SQLITE_OK && pLeaf!=0 ){ p = rtreeSearchPointNew(pCsr, RTREE_ZERO, 0); assert( p!=0 ); /* Always returns pCsr->sPoint */ pCsr->aNode[0] = pLeaf; p->id = iNode; p->eWithin = PARTLY_WITHIN; rc = nodeRowidIndex(pRtree, pLeaf, iRowid, &iCell); p->iCell = iCell; RTREE_QUEUE_TRACE(pCsr, "PUSH-F1:"); }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 |
︙ | ︙ | |||
1447 1448 1449 1450 1451 1452 1453 | case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break; default: assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH ); op = RTREE_MATCH; break; } zIdxStr[iIdx++] = op; | | | 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 | case SQLITE_INDEX_CONSTRAINT_GE: op = RTREE_GE; break; default: assert( p->op==SQLITE_INDEX_CONSTRAINT_MATCH ); op = RTREE_MATCH; break; } zIdxStr[iIdx++] = op; zIdxStr[iIdx++] = p->iColumn - 1 + '0'; pIdxInfo->aConstraintUsage[ii].argvIndex = (iIdx/2); pIdxInfo->aConstraintUsage[ii].omit = 1; } } pIdxInfo->idxNum = 2; pIdxInfo->needToFreeIdxStr = 1; |
︙ | ︙ | |||
1540 1541 1542 1543 1544 1545 1546 | RtreeCell cell; memcpy(&cell, p, sizeof(RtreeCell)); area = cellArea(pRtree, &cell); cellUnion(pRtree, &cell, pCell); return (cellArea(pRtree, &cell)-area); } | < | < | < < < < < < < | | | | < | | < | | | | | | | | | < < < < < < < < < < < < < < < < < < < | 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 | RtreeCell cell; memcpy(&cell, p, sizeof(RtreeCell)); area = cellArea(pRtree, &cell); cellUnion(pRtree, &cell, pCell); return (cellArea(pRtree, &cell)-area); } static RtreeDValue cellOverlap( Rtree *pRtree, RtreeCell *p, RtreeCell *aCell, int nCell ){ int ii; RtreeDValue overlap = RTREE_ZERO; for(ii=0; ii<nCell; ii++){ int jj; RtreeDValue o = (RtreeDValue)1; for(jj=0; jj<(pRtree->nDim*2); jj+=2){ RtreeDValue x1, x2; x1 = MAX(DCOORD(p->aCoord[jj]), DCOORD(aCell[ii].aCoord[jj])); x2 = MIN(DCOORD(p->aCoord[jj+1]), DCOORD(aCell[ii].aCoord[jj+1])); if( x2<x1 ){ o = (RtreeDValue)0; break; }else{ o = o * (x2-x1); } } overlap += o; } return overlap; } /* ** This function implements the ChooseLeaf algorithm from Gutman[84]. ** ChooseSubTree in r*tree terminology. */ static int ChooseLeaf( |
︙ | ︙ | |||
1617 1618 1619 1620 1621 1622 1623 | RtreeNode *pNode; rc = nodeAcquire(pRtree, 1, 0, &pNode); for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){ int iCell; sqlite3_int64 iBest = 0; | | | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 | RtreeNode *pNode; rc = nodeAcquire(pRtree, 1, 0, &pNode); for(ii=0; rc==SQLITE_OK && ii<(pRtree->iDepth-iHeight); ii++){ int iCell; sqlite3_int64 iBest = 0; RtreeDValue fMinGrowth = RTREE_ZERO; RtreeDValue fMinArea = RTREE_ZERO; int nCell = NCELL(pNode); RtreeCell cell; RtreeNode *pChild; RtreeCell *aCell = 0; /* Select the child node which will be enlarged the least if pCell ** is inserted into it. Resolve ties by choosing the entry with ** the smallest area. */ for(iCell=0; iCell<nCell; iCell++){ int bBest = 0; RtreeDValue growth; RtreeDValue area; nodeGetCell(pRtree, pNode, iCell, &cell); growth = cellGrowth(pRtree, &cell, pCell); area = cellArea(pRtree, &cell); if( iCell==0||growth<fMinGrowth||(growth==fMinGrowth && area<fMinArea) ){ bBest = 1; } if( bBest ){ fMinGrowth = growth; fMinArea = area; iBest = cell.iRowid; } } |
︙ | ︙ | |||
1747 1748 1749 1750 1751 1752 1753 | sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar); sqlite3_step(pRtree->pWriteParent); return sqlite3_reset(pRtree->pWriteParent); } static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int); | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 | sqlite3_bind_int64(pRtree->pWriteParent, 2, iPar); sqlite3_step(pRtree->pWriteParent); return sqlite3_reset(pRtree->pWriteParent); } static int rtreeInsertCell(Rtree *, RtreeNode *, RtreeCell *, int); /* ** Arguments aIdx, aDistance and aSpare all point to arrays of size ** nIdx. The aIdx array contains the set of integers from 0 to ** (nIdx-1) in no particular order. This function sorts the values ** in aIdx according to the indexed values in aDistance. For ** example, assuming the inputs: |
︙ | ︙ | |||
2036 2037 2038 2039 2040 2041 2042 | assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) ); } } #endif } } | < | | | | | 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 | assert( xleft1<=xright1 && (xleft1<xright1 || xleft2<=xright2) ); } } #endif } } /* ** Implementation of the R*-tree variant of SplitNode from Beckman[1990]. */ static int splitNodeStartree( Rtree *pRtree, RtreeCell *aCell, int nCell, RtreeNode *pLeft, RtreeNode *pRight, RtreeCell *pBboxLeft, RtreeCell *pBboxRight ){ int **aaSorted; int *aSpare; int ii; int iBestDim = 0; int iBestSplit = 0; RtreeDValue fBestMargin = RTREE_ZERO; int nByte = (pRtree->nDim+1)*(sizeof(int*)+nCell*sizeof(int)); aaSorted = (int **)sqlite3_malloc(nByte); if( !aaSorted ){ return SQLITE_NOMEM; } aSpare = &((int *)&aaSorted[pRtree->nDim])[pRtree->nDim*nCell]; memset(aaSorted, 0, nByte); for(ii=0; ii<pRtree->nDim; ii++){ int jj; aaSorted[ii] = &((int *)&aaSorted[pRtree->nDim])[ii*nCell]; for(jj=0; jj<nCell; jj++){ aaSorted[ii][jj] = jj; } SortByDimension(pRtree, aaSorted[ii], nCell, ii, aCell, aSpare); } for(ii=0; ii<pRtree->nDim; ii++){ RtreeDValue margin = RTREE_ZERO; RtreeDValue fBestOverlap = RTREE_ZERO; RtreeDValue fBestArea = RTREE_ZERO; int iBestLeft = 0; int nLeft; for( nLeft=RTREE_MINCELLS(pRtree); nLeft<=(nCell-RTREE_MINCELLS(pRtree)); nLeft++ |
︙ | ︙ | |||
2104 2105 2106 2107 2108 2109 2110 | cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]); }else{ cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]); } } margin += cellMargin(pRtree, &left); margin += cellMargin(pRtree, &right); | | | 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 | cellUnion(pRtree, &left, &aCell[aaSorted[ii][kk]]); }else{ cellUnion(pRtree, &right, &aCell[aaSorted[ii][kk]]); } } margin += cellMargin(pRtree, &left); margin += cellMargin(pRtree, &right); overlap = cellOverlap(pRtree, &left, &right, 1); area = cellArea(pRtree, &left) + cellArea(pRtree, &right); if( (nLeft==RTREE_MINCELLS(pRtree)) || (overlap<fBestOverlap) || (overlap==fBestOverlap && area<fBestArea) ){ iBestLeft = nLeft; fBestOverlap = overlap; |
︙ | ︙ | |||
2136 2137 2138 2139 2140 2141 2142 | nodeInsertCell(pRtree, pTarget, pCell); cellUnion(pRtree, pBbox, pCell); } sqlite3_free(aaSorted); return SQLITE_OK; } | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 | nodeInsertCell(pRtree, pTarget, pCell); cellUnion(pRtree, pBbox, pCell); } sqlite3_free(aaSorted); return SQLITE_OK; } static int updateMapping( Rtree *pRtree, i64 iRowid, RtreeNode *pNode, int iHeight ){ |
︙ | ︙ | |||
2270 2271 2272 2273 2274 2275 2276 | rc = SQLITE_NOMEM; goto splitnode_out; } memset(pLeft->zData, 0, pRtree->iNodeSize); memset(pRight->zData, 0, pRtree->iNodeSize); | | > | 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 | rc = SQLITE_NOMEM; goto splitnode_out; } memset(pLeft->zData, 0, pRtree->iNodeSize); memset(pRight->zData, 0, pRtree->iNodeSize); rc = splitNodeStartree(pRtree, aCell, nCell, pLeft, pRight, &leftbbox, &rightbbox); if( rc!=SQLITE_OK ){ goto splitnode_out; } /* Ensure both child nodes have node numbers assigned to them by calling ** nodeWrite(). Node pRight always needs a node number, as it was created ** by nodeNew() above. But node pLeft sometimes already has a node number. |
︙ | ︙ | |||
2553 2554 2555 2556 2557 2558 2559 | } } for(iDim=0; iDim<pRtree->nDim; iDim++){ aCenterCoord[iDim] = (aCenterCoord[iDim]/(nCell*(RtreeDValue)2)); } for(ii=0; ii<nCell; ii++){ | | | 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 | } } for(iDim=0; iDim<pRtree->nDim; iDim++){ aCenterCoord[iDim] = (aCenterCoord[iDim]/(nCell*(RtreeDValue)2)); } for(ii=0; ii<nCell; ii++){ aDistance[ii] = RTREE_ZERO; for(iDim=0; iDim<pRtree->nDim; iDim++){ RtreeDValue coord = (DCOORD(aCell[ii].aCoord[iDim*2+1]) - DCOORD(aCell[ii].aCoord[iDim*2])); aDistance[ii] += (coord-aCenterCoord[iDim])*(coord-aCenterCoord[iDim]); } } |
︙ | ︙ | |||
2619 2620 2621 2622 2623 2624 2625 | if( pChild ){ nodeRelease(pRtree, pChild->pParent); nodeReference(pNode); pChild->pParent = pNode; } } if( nodeInsertCell(pRtree, pNode, pCell) ){ | < < < < | 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 | if( pChild ){ nodeRelease(pRtree, pChild->pParent); nodeReference(pNode); pChild->pParent = pNode; } } if( nodeInsertCell(pRtree, pNode, pCell) ){ if( iHeight<=pRtree->iReinsertHeight || pNode->iNode==1){ rc = SplitNode(pRtree, pNode, pCell, iHeight); }else{ pRtree->iReinsertHeight = iHeight; rc = Reinsert(pRtree, pNode, pCell, iHeight); } }else{ rc = AdjustTree(pRtree, pNode, pCell); if( rc==SQLITE_OK ){ if( iHeight==0 ){ rc = rowidWrite(pRtree, pCell->iRowid, pNode->iNode); }else{ rc = parentWrite(pRtree, pCell->iRowid, pNode->iNode); |
︙ | ︙ | |||
2698 2699 2700 2701 2702 2703 2704 | /* Obtain a reference to the root node to initialize Rtree.iDepth */ rc = nodeAcquire(pRtree, 1, 0, &pRoot); /* Obtain a reference to the leaf node that contains the entry ** about to be deleted. */ if( rc==SQLITE_OK ){ | | | 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 | /* Obtain a reference to the root node to initialize Rtree.iDepth */ rc = nodeAcquire(pRtree, 1, 0, &pRoot); /* Obtain a reference to the leaf node that contains the entry ** about to be deleted. */ if( rc==SQLITE_OK ){ rc = findLeafNode(pRtree, iDelete, &pLeaf, 0); } /* Delete the cell in question from the leaf node. */ if( rc==SQLITE_OK ){ int rc2; rc = nodeRowidIndex(pRtree, pLeaf, iDelete, &iCell); if( rc==SQLITE_OK ){ |
︙ | ︙ | |||
3035 3036 3037 3038 3039 3040 3041 | pRtree->db = db; if( isCreate ){ char *zCreate = sqlite3_mprintf( "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);" "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);" | | > | 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 | pRtree->db = db; if( isCreate ){ char *zCreate = sqlite3_mprintf( "CREATE TABLE \"%w\".\"%w_node\"(nodeno INTEGER PRIMARY KEY, data BLOB);" "CREATE TABLE \"%w\".\"%w_rowid\"(rowid INTEGER PRIMARY KEY, nodeno INTEGER);" "CREATE TABLE \"%w\".\"%w_parent\"(nodeno INTEGER PRIMARY KEY," " parentnode INTEGER);" "INSERT INTO '%q'.'%q_node' VALUES(1, zeroblob(%d))", zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, zDb, zPrefix, pRtree->iNodeSize ); if( !zCreate ){ return SQLITE_NOMEM; } rc = sqlite3_exec(db, zCreate, 0, 0, 0); |
︙ | ︙ | |||
3249 3250 3251 3252 3253 3254 3255 | } /* ** Implementation of a scalar function that decodes r-tree nodes to ** human readable strings. This can be used for debugging and analysis. ** | | | | | | 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 | } /* ** Implementation of a scalar function that decodes r-tree nodes to ** human readable strings. This can be used for debugging and analysis. ** ** The scalar function takes two arguments: (1) the number of dimensions ** to the rtree (between 1 and 5, inclusive) and (2) a blob of data containing ** an r-tree node. For a two-dimensional r-tree structure called "rt", to ** deserialize all nodes, a statement like: ** ** SELECT rtreenode(2, data) FROM rt_node; ** ** The human readable string takes the form of a Tcl list with one ** entry for each cell in the r-tree node. Each entry is itself a ** list, containing the 8-byte rowid/pageno followed by the ** <num-dimension>*2 coordinates. |
︙ | ︙ | |||
3285 3286 3287 3288 3289 3290 3291 | 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 | | > > > > > > > > > | 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 | 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); } if( zText ){ char *zTextNew = sqlite3_mprintf("%s {%s}", zText, zCell); sqlite3_free(zText); zText = zTextNew; }else{ zText = sqlite3_mprintf("{%s}", zCell); } } sqlite3_result_text(ctx, zText, -1, sqlite3_free); } /* This routine implements an SQL function that returns the "depth" parameter ** from the front of a blob that is an r-tree node. For example: ** ** SELECT rtreedepth(data) FROM rt_node WHERE nodeno=1; ** ** The depth value is 0 for all nodes other than the root node, and the root ** node always has nodeno=1, so the example above is the primary use for this ** routine. This routine is intended for testing and analysis only. */ static void rtreedepth(sqlite3_context *ctx, int nArg, sqlite3_value **apArg){ UNUSED_PARAMETER(nArg); if( sqlite3_value_type(apArg[0])!=SQLITE_BLOB || sqlite3_value_bytes(apArg[0])<2 ){ sqlite3_result_error(ctx, "Invalid argument to rtreedepth()", -1); }else{ |
︙ | ︙ | |||
3348 3349 3350 3351 3352 3353 3354 | rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); } return rc; } /* | | | > | | | > > | | | | > > > > | > > | < | | | | | > > > > > | | > > > > > > > > > > > > | > > > > > > > | | | 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 | rc = sqlite3_create_module_v2(db, "rtree_i32", &rtreeModule, c, 0); } return rc; } /* ** This routine deletes the RtreeGeomCallback object that was attached ** one of the SQL functions create by sqlite3_rtree_geometry_callback() ** or sqlite3_rtree_query_callback(). In other words, this routine is the ** destructor for an RtreeGeomCallback objecct. This routine is called when ** the corresponding SQL function is deleted. */ static void rtreeFreeCallback(void *p){ RtreeGeomCallback *pInfo = (RtreeGeomCallback*)p; if( pInfo->xDestructor ) pInfo->xDestructor(pInfo->pContext); sqlite3_free(p); } /* ** Each call to sqlite3_rtree_geometry_callback() or ** sqlite3_rtree_query_callback() creates an ordinary SQLite ** scalar function that is implemented by this routine. ** ** All this function does is construct an RtreeMatchArg object that ** contains the geometry-checking callback routines and a list of ** parameters to this function, then return that RtreeMatchArg object ** as a BLOB. ** ** The R-Tree MATCH operator will read the returned BLOB, deserialize ** the RtreeMatchArg object, and use the RtreeMatchArg object to figure ** out which elements of the R-Tree should be returned by the query. */ static void geomCallback(sqlite3_context *ctx, int nArg, sqlite3_value **aArg){ RtreeGeomCallback *pGeomCtx = (RtreeGeomCallback *)sqlite3_user_data(ctx); RtreeMatchArg *pBlob; int nBlob; nBlob = sizeof(RtreeMatchArg) + (nArg-1)*sizeof(RtreeDValue); pBlob = (RtreeMatchArg *)sqlite3_malloc(nBlob); if( !pBlob ){ sqlite3_result_error_nomem(ctx); }else{ int i; pBlob->magic = RTREE_GEOMETRY_MAGIC; pBlob->cb = pGeomCtx[0]; pBlob->nParam = nArg; for(i=0; i<nArg; i++){ #ifdef SQLITE_RTREE_INT_ONLY pBlob->aParam[i] = sqlite3_value_int64(aArg[i]); #else pBlob->aParam[i] = sqlite3_value_double(aArg[i]); #endif } sqlite3_result_blob(ctx, pBlob, nBlob, sqlite3_free); } } /* ** Register a new geometry function for use with the r-tree MATCH operator. */ int sqlite3_rtree_geometry_callback( sqlite3 *db, /* Register SQL function on this connection */ const char *zGeom, /* Name of the new SQL function */ int (*xGeom)(sqlite3_rtree_geometry*,int,RtreeDValue*,int*), /* Callback */ void *pContext /* Extra data associated with the callback */ ){ RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ /* Allocate and populate the context object. */ pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); if( !pGeomCtx ) return SQLITE_NOMEM; pGeomCtx->xGeom = xGeom; pGeomCtx->xQueryFunc = 0; pGeomCtx->xDestructor = 0; pGeomCtx->pContext = pContext; return sqlite3_create_function_v2(db, zGeom, -1, SQLITE_ANY, (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback ); } /* ** Register a new 2nd-generation geometry function for use with the ** r-tree MATCH operator. */ int sqlite3_rtree_query_callback( sqlite3 *db, /* Register SQL function on this connection */ const char *zQueryFunc, /* Name of new SQL function */ int (*xQueryFunc)(sqlite3_rtree_query_info*), /* Callback */ void *pContext, /* Extra data passed into the callback */ void (*xDestructor)(void*) /* Destructor for the extra data */ ){ RtreeGeomCallback *pGeomCtx; /* Context object for new user-function */ /* Allocate and populate the context object. */ pGeomCtx = (RtreeGeomCallback *)sqlite3_malloc(sizeof(RtreeGeomCallback)); if( !pGeomCtx ) return SQLITE_NOMEM; pGeomCtx->xGeom = 0; pGeomCtx->xQueryFunc = xQueryFunc; pGeomCtx->xDestructor = xDestructor; pGeomCtx->pContext = pContext; return sqlite3_create_function_v2(db, zQueryFunc, -1, SQLITE_ANY, (void *)pGeomCtx, geomCallback, 0, 0, rtreeFreeCallback ); } #if !SQLITE_CORE #ifdef _WIN32 __declspec(dllexport) #endif |
︙ | ︙ |
Changes to ext/rtree/rtree1.test.
︙ | ︙ | |||
116 117 118 119 120 121 122 | } return $out } # Test that it is possible to open an existing database that contains # r-tree tables. # | | < | | > > > | < | 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 | } return $out } # Test that it is possible to open an existing database that contains # r-tree tables. # do_execsql_test rtree-1.4.1a { CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2); INSERT INTO t1 VALUES(1, 5.0, 10.0); SELECT substr(hex(data),1,40) FROM t1_node; } {00000001000000000000000140A0000041200000} do_execsql_test rtree-1.4.1b { INSERT INTO t1 VALUES(2, 15.0, 20.0); } {} do_test rtree-1.4.2 { db close sqlite3 db test.db execsql_intout { SELECT * FROM t1 ORDER BY ii } } {1 5 10 2 15 20} do_test rtree-1.4.3 { |
︙ | ︙ | |||
431 432 433 434 435 436 437 | } } {2} #------------------------------------------------------------------------- # Test on-conflict clause handling. # db_delete_and_reopen | | > > > < | 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 | } } {2} #------------------------------------------------------------------------- # Test on-conflict clause handling. # db_delete_and_reopen do_execsql_test 12.0.1 { CREATE VIRTUAL TABLE t1 USING rtree_i32(idx, x1, x2, y1, y2); INSERT INTO t1 VALUES(1, 1, 2, 3, 4); SELECT substr(hex(data),1,56) FROM t1_node; } {00000001000000000000000100000001000000020000000300000004} do_execsql_test 12.0.2 { INSERT INTO t1 VALUES(2, 2, 3, 4, 5); INSERT INTO t1 VALUES(3, 3, 4, 5, 6); CREATE TABLE source(idx, x1, x2, y1, y2); INSERT INTO source VALUES(5, 8, 8, 8, 8); INSERT INTO source VALUES(2, 7, 7, 7, 7); } db_save_and_close foreach {tn sql_template testdata} { 1 "INSERT %CONF% INTO t1 VALUES(2, 7, 7, 7, 7)" { ROLLBACK 0 1 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6} ABORT 0 1 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7} IGNORE 0 0 {1 1 2 3 4 2 2 3 4 5 3 3 4 5 6 4 4 5 6 7} |
︙ | ︙ |
Changes to ext/rtree/rtree6.test.
︙ | ︙ | |||
53 54 55 56 57 58 59 | CREATE TABLE t2(k INTEGER PRIMARY KEY, v); CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2); } } {} do_test rtree6-1.2 { rtree_strategy {SELECT * FROM t1 WHERE x1>10} | | | | | | | | | 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | CREATE TABLE t2(k INTEGER PRIMARY KEY, v); CREATE VIRTUAL TABLE t1 USING rtree(ii, x1, x2, y1, y2); } } {} do_test rtree6-1.2 { rtree_strategy {SELECT * FROM t1 WHERE x1>10} } {E0} do_test rtree6-1.3 { rtree_strategy {SELECT * FROM t1 WHERE x1<10} } {C0} do_test rtree6-1.4 { rtree_strategy {SELECT * FROM t1,t2 WHERE k=ii AND x1<10} } {C0} do_test rtree6-1.5 { rtree_strategy {SELECT * FROM t1,t2 WHERE k=+ii AND x1<10} } {C0} do_eqp_test rtree6.2.1 { SELECT * FROM t1,t2 WHERE k=+ii AND x1<10 } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)} } do_eqp_test rtree6.2.2 { SELECT * FROM t1,t2 WHERE k=ii AND x1<10 } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0} 0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)} } do_eqp_test rtree6.2.3 { SELECT * FROM t1,t2 WHERE k=ii } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} 0 1 1 {SEARCH TABLE t2 USING INTEGER PRIMARY KEY (rowid=?)} } do_eqp_test rtree6.2.4 { SELECT * FROM t1,t2 WHERE v=10 and x1<10 and x2>10 } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:C0E1} 0 1 1 {SEARCH TABLE t2 USING AUTOMATIC COVERING INDEX (v=?)} } do_eqp_test rtree6.2.5 { SELECT * FROM t1,t2 WHERE k=ii AND x1<v } { 0 0 0 {SCAN TABLE t1 VIRTUAL TABLE INDEX 2:} |
︙ | ︙ | |||
122 123 124 125 126 127 128 | rtree_strategy { SELECT * FROM t3 WHERE x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 } | | | | 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | rtree_strategy { SELECT * FROM t3 WHERE x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 } } {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0} do_test rtree6.3.3 { rtree_strategy { SELECT * FROM t3 WHERE x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 } } {E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0E0} do_execsql_test rtree6-3.4 { SELECT * FROM t3 WHERE x1>0.5 AND x1>0.8 AND x1>1.1 } {} do_execsql_test rtree6-3.5 { SELECT * FROM t3 WHERE x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND x1>0.5 AND |
︙ | ︙ |
Changes to ext/rtree/rtreeB.test.
︙ | ︙ | |||
37 38 39 40 41 42 43 | INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0); INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0); INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0); INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0); INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400); SELECT rtreenode(2, data) FROM t1_node; } | | | 37 38 39 40 41 42 43 44 45 46 47 | INSERT INTO t1 VALUES(1073741824, 0.0, 0.0, 100.0, 100.0); INSERT INTO t1 VALUES(2147483646, 0.0, 0.0, 200.0, 200.0); INSERT INTO t1 VALUES(4294967296, 0.0, 0.0, 300.0, 300.0); INSERT INTO t1 VALUES(8589934592, 20.0, 20.0, 150.0, 150.0); INSERT INTO t1 VALUES(9223372036854775807, 150, 150, 400, 400); SELECT rtreenode(2, data) FROM t1_node; } } {{{1073741824 0 0 100 100} {2147483646 0 0 200 200} {4294967296 0 0 300 300} {8589934592 20 20 150 150} {9223372036854775807 150 150 400 400}}} } finish_test |
Changes to ext/rtree/rtreeC.test.
︙ | ︙ | |||
25 26 27 28 29 30 31 | } do_eqp_test 1.1 { SELECT * FROM r_tree, t WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y } { 0 0 1 {SCAN TABLE t} | | | | | 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | } do_eqp_test 1.1 { SELECT * FROM r_tree, t WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y } { 0 0 1 {SCAN TABLE t} 0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0} } do_eqp_test 1.2 { SELECT * FROM t, r_tree WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y } { 0 0 0 {SCAN TABLE t} 0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0} } do_eqp_test 1.3 { SELECT * FROM t, r_tree WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y } { 0 0 0 {SCAN TABLE t} 0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0} } do_eqp_test 1.5 { SELECT * FROM t, r_tree } { 0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:} 0 1 0 {SCAN TABLE t} |
︙ | ︙ | |||
78 79 80 81 82 83 84 | sqlite3 db test.db do_eqp_test 2.1 { SELECT * FROM r_tree, t WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y } { 0 0 1 {SCAN TABLE t} | | | | | 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | sqlite3 db test.db do_eqp_test 2.1 { SELECT * FROM r_tree, t WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y } { 0 0 1 {SCAN TABLE t} 0 1 0 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0} } do_eqp_test 2.2 { SELECT * FROM t, r_tree WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND t.x<=max_y } { 0 0 0 {SCAN TABLE t} 0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0} } do_eqp_test 2.3 { SELECT * FROM t, r_tree WHERE t.x>=min_x AND t.x<=max_x AND t.y>=min_y AND ?<=max_y } { 0 0 0 {SCAN TABLE t} 0 1 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:D3B2D1B0} } do_eqp_test 2.5 { SELECT * FROM t, r_tree } { 0 0 1 {SCAN TABLE r_tree VIRTUAL TABLE INDEX 2:} 0 1 0 {SCAN TABLE t} |
︙ | ︙ | |||
267 268 269 270 271 272 273 | execsql { SELECT * FROM rt } } {1 2.0 3.0} db close } finish_test | < | 267 268 269 270 271 272 273 | execsql { SELECT * FROM rt } } {1 2.0 3.0} db close } finish_test |
Added ext/rtree/rtreeE.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | # 2010 August 28 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file contains tests for the r-tree module. Specifically, it tests # that new-style custom r-tree queries (geometry callbacks) work. # if {![info exists testdir]} { set testdir [file join [file dirname [info script]] .. .. test] } source $testdir/tester.tcl ifcapable !rtree { finish_test ; return } ifcapable rtree_int_only { finish_test; return } #------------------------------------------------------------------------- # Test the example 2d "circle" geometry callback. # register_circle_geom db do_execsql_test rtreeE-1.1 { PRAGMA page_size=512; CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1); /* A tight pattern of small boxes near 0,0 */ WITH RECURSIVE x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4), y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4) INSERT INTO rt1 SELECT x+5*y, x, x+2, y, y+2 FROM x, y; /* A looser pattern of small boxes near 100, 0 */ WITH RECURSIVE x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4), y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4) INSERT INTO rt1 SELECT 100+x+5*y, x*3+100, x*3+102, y*3, y*3+2 FROM x, y; /* A looser pattern of larger boxes near 0, 200 */ WITH RECURSIVE x(x) AS (VALUES(0) UNION ALL SELECT x+1 FROM x WHERE x<4), y(y) AS (VALUES(0) UNION ALL SELECT y+1 FROM y WHERE y<4) INSERT INTO rt1 SELECT 200+x+5*y, x*7, x*7+15, y*7+200, y*7+215 FROM x, y; } {} # Queries against each of the three clusters */ do_execsql_test rtreeE-1.1 { SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 0.0, 50.0, 3) ORDER BY id; } {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24} do_execsql_test rtreeE-1.2 { SELECT id FROM rt1 WHERE id MATCH Qcircle(100.0, 0.0, 50.0, 3) ORDER BY id; } {100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124} do_execsql_test rtreeE-1.3 { SELECT id FROM rt1 WHERE id MATCH Qcircle(0.0, 200.0, 50.0, 3) ORDER BY id; } {200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224} # The Qcircle geometry function gives a lower score to larger leaf-nodes. # This causes the 200s to sort before the 100s and the 0s to sort before # last. # do_execsql_test rtreeE-1.4 { SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,3) AND id%100==0 } {200 100 0} # Exclude odd rowids on a depth-first search do_execsql_test rtreeE-1.5 { SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,4) ORDER BY +id } {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224} # Exclude odd rowids on a breadth-first search. do_execsql_test rtreeE-1.6 { SELECT id FROM rt1 WHERE id MATCH Qcircle(0,0,1000,5) ORDER BY +id } {0 2 4 6 8 10 12 14 16 18 20 22 24 100 102 104 106 108 110 112 114 116 118 120 122 124 200 202 204 206 208 210 212 214 216 218 220 222 224} # Construct a large 2-D RTree with thousands of random entries. # do_test rtreeE-2.1 { db eval { CREATE TABLE t2(id,x0,x1,y0,y1); CREATE VIRTUAL TABLE rt2 USING rtree(id,x0,x1,y0,y1); BEGIN; } expr srand(0) for {set i 1} {$i<=10000} {incr i} { set dx [expr {int(rand()*40)+1}] set dy [expr {int(rand()*40)+1}] set x0 [expr {int(rand()*(10000 - $dx))}] set x1 [expr {$x0+$dx}] set y0 [expr {int(rand()*(10000 - $dy))}] set y1 [expr {$y0+$dy}] set id [expr {$i+10000}] db eval {INSERT INTO t2 VALUES($id,$x0,$x1,$y0,$y1)} } db eval { INSERT INTO rt2 SELECT * FROM t2; COMMIT; } } {} for {set i 1} {$i<=200} {incr i} { set dx [expr {int(rand()*100)}] set dy [expr {int(rand()*100)}] set x0 [expr {int(rand()*(10000 - $dx))}] set x1 [expr {$x0+$dx}] set y0 [expr {int(rand()*(10000 - $dy))}] set y1 [expr {$y0+$dy}] set ans [db eval {SELECT id FROM t2 WHERE x1>=$x0 AND x0<=$x1 AND y1>=$y0 AND y0<=$y1 ORDER BY id}] do_execsql_test rtreeE-2.2.$i { SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ORDER BY id } $ans } # Run query that have very deep priority queues # set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=5000 AND y1>=0 AND y0<=5000 ORDER BY id}] do_execsql_test rtreeE-2.3 { SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,5000,0,5000) ORDER BY id } $ans set ans [db eval {SELECT id FROM t2 WHERE x1>=0 AND x0<=10000 AND y1>=0 AND y0<=10000 ORDER BY id}] do_execsql_test rtreeE-2.4 { SELECT id FROM rt2 WHERE id MATCH breadthfirstsearch(0,10000,0,10000) ORDER BY id } $ans finish_test |
Changes to ext/rtree/sqlite3rtree.h.
︙ | ︙ | |||
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <sqlite3.h> #ifdef __cplusplus extern "C" { #endif typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry; /* ** Register a geometry callback named zGeom that can be used as part of an ** R-Tree geometry query as follows: ** ** SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...) */ int sqlite3_rtree_geometry_callback( sqlite3 *db, const char *zGeom, | > > > > > > > > > > < < < | < | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <sqlite3.h> #ifdef __cplusplus extern "C" { #endif typedef struct sqlite3_rtree_geometry sqlite3_rtree_geometry; typedef struct sqlite3_rtree_query_info sqlite3_rtree_query_info; /* The double-precision datatype used by RTree depends on the ** SQLITE_RTREE_INT_ONLY compile-time option. */ #ifdef SQLITE_RTREE_INT_ONLY typedef sqlite3_int64 sqlite3_rtree_dbl; #else typedef double sqlite3_rtree_dbl; #endif /* ** Register a geometry callback named zGeom that can be used as part of an ** R-Tree geometry query as follows: ** ** SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zGeom(... params ...) */ int sqlite3_rtree_geometry_callback( sqlite3 *db, const char *zGeom, int (*xGeom)(sqlite3_rtree_geometry*, int, sqlite3_rtree_dbl*,int*), void *pContext ); /* ** A pointer to a structure of the following type is passed as the first ** argument to callbacks registered using rtree_geometry_callback(). */ struct sqlite3_rtree_geometry { void *pContext; /* Copy of pContext passed to s_r_g_c() */ int nParam; /* Size of array aParam[] */ sqlite3_rtree_dbl *aParam; /* Parameters passed to SQL geom function */ void *pUser; /* Callback implementation user data */ void (*xDelUser)(void *); /* Called by SQLite to clean up pUser */ }; /* ** Register a 2nd-generation geometry callback named zScore that can be ** used as part of an R-Tree geometry query as follows: ** ** SELECT ... FROM <rtree> WHERE <rtree col> MATCH $zQueryFunc(... params ...) */ int sqlite3_rtree_query_callback( sqlite3 *db, const char *zQueryFunc, int (*xQueryFunc)(sqlite3_rtree_query_info*), void *pContext, void (*xDestructor)(void*) ); /* ** A pointer to a structure of the following type is passed as the ** argument to scored geometry callback registered using ** sqlite3_rtree_query_callback(). ** ** Note that the first 5 fields of this structure are identical to ** sqlite3_rtree_geometry. This structure is a subclass of ** sqlite3_rtree_geometry. */ 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 */ }; /* ** Allowed values for sqlite3_rtree_query.eWithin and .eParentWithin. */ #define NOT_WITHIN 0 /* Object completely outside of query region */ #define PARTLY_WITHIN 1 /* Object partially overlaps query region */ #define FULLY_WITHIN 2 /* Object fully contained within query region */ #ifdef __cplusplus } /* end of the 'extern "C"' block */ #endif #endif /* ifndef _SQLITE3RTREE_H_ */ |
Changes to main.mk.
︙ | ︙ | |||
472 473 474 475 476 477 478 | parse.c: $(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk cp $(TOP)/src/parse.y . rm -f parse.h ./lemon $(OPTS) parse.y mv parse.h parse.h.temp $(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h | | | 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 | parse.c: $(TOP)/src/parse.y lemon $(TOP)/addopcodes.awk cp $(TOP)/src/parse.y . rm -f parse.h ./lemon $(OPTS) parse.y mv parse.h parse.h.temp $(NAWK) -f $(TOP)/addopcodes.awk parse.h.temp >parse.h sqlite3.h: $(TOP)/src/sqlite.h.in $(TOP)/manifest.uuid $(TOP)/VERSION $(TOP)/ext/rtree/sqlite3rtree.h tclsh $(TOP)/tool/mksqlite3h.tcl $(TOP) >sqlite3.h keywordhash.h: $(TOP)/tool/mkkeywordhash.c $(BCC) -o mkkeywordhash $(OPTS) $(TOP)/tool/mkkeywordhash.c ./mkkeywordhash >keywordhash.h |
︙ | ︙ |
Changes to src/analyze.c.
︙ | ︙ | |||
1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 | ** list of space separated integers. Read the first nOut of these into ** the array aOut[]. */ static void decodeIntArray( char *zIntArray, /* String containing int array to decode */ int nOut, /* Number of slots in aOut[] */ tRowcnt *aOut, /* Store integers here */ Index *pIndex /* Handle extra flags for this index, if not NULL */ ){ char *z = zIntArray; int c; int i; tRowcnt v; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 if( z==0 ) z = ""; #else if( NEVER(z==0) ) z = ""; #endif for(i=0; *z && i<nOut; i++){ v = 0; while( (c=z[0])>='0' && c<='9' ){ v = v*10 + c - '0'; z++; } | > > > | > > > > > > > > | 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 | ** list of space separated integers. Read the first nOut of these into ** the array aOut[]. */ static void decodeIntArray( char *zIntArray, /* String containing int array to decode */ int nOut, /* Number of slots in aOut[] */ tRowcnt *aOut, /* Store integers here */ LogEst *aLog, /* Or, if aOut==0, here */ Index *pIndex /* Handle extra flags for this index, if not NULL */ ){ char *z = zIntArray; int c; int i; tRowcnt v; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 if( z==0 ) z = ""; #else if( NEVER(z==0) ) z = ""; #endif for(i=0; *z && i<nOut; i++){ v = 0; while( (c=z[0])>='0' && c<='9' ){ v = v*10 + c - '0'; z++; } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 if( aOut ){ aOut[i] = v; }else #else assert( aOut==0 ); UNUSED_PARAMETER(aOut); #endif { aLog[i] = sqlite3LogEst(v); } if( *z==' ' ) z++; } #ifndef SQLITE_ENABLE_STAT3_OR_STAT4 assert( pIndex!=0 ); #else if( pIndex ) #endif |
︙ | ︙ | |||
1441 1442 1443 1444 1445 1446 1447 | pIndex = sqlite3PrimaryKeyIndex(pTable); }else{ pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase); } z = argv[2]; if( pIndex ){ | | | | | 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 | pIndex = sqlite3PrimaryKeyIndex(pTable); }else{ pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase); } z = argv[2]; if( pIndex ){ decodeIntArray((char*)z, pIndex->nKeyCol+1, 0, pIndex->aiRowLogEst, pIndex); if( pIndex->pPartIdxWhere==0 ) pTable->nRowLogEst = pIndex->aiRowLogEst[0]; }else{ Index fakeIdx; fakeIdx.szIdxRow = pTable->szTabRow; decodeIntArray((char*)z, 1, 0, &pTable->nRowLogEst, &fakeIdx); pTable->szTabRow = fakeIdx.szIdxRow; } return 0; } /* |
︙ | ︙ | |||
1638 1639 1640 1641 1642 1643 1644 | nCol = pIdx->nSampleCol; if( bStat3 && nCol>1 ) continue; if( pIdx!=pPrevIdx ){ initAvgEq(pPrevIdx); pPrevIdx = pIdx; } pSample = &pIdx->aSample[pIdx->nSample]; | | | | | 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 | nCol = pIdx->nSampleCol; if( bStat3 && nCol>1 ) continue; if( pIdx!=pPrevIdx ){ initAvgEq(pPrevIdx); pPrevIdx = pIdx; } pSample = &pIdx->aSample[pIdx->nSample]; decodeIntArray((char*)sqlite3_column_text(pStmt,1),nCol,pSample->anEq,0,0); decodeIntArray((char*)sqlite3_column_text(pStmt,2),nCol,pSample->anLt,0,0); decodeIntArray((char*)sqlite3_column_text(pStmt,3),nCol,pSample->anDLt,0,0); /* Take a copy of the sample. Add two 0x00 bytes the end of the buffer. ** This is in case the sample record is corrupted. In that case, the ** sqlite3VdbeRecordCompare() may read up to two varints past the ** end of the allocated buffer before it realizes it is dealing with ** a corrupt record. Adding the two 0x00 bytes prevents this from causing ** a buffer overread. */ |
︙ | ︙ |
Changes to src/build.c.
︙ | ︙ | |||
901 902 903 904 905 906 907 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; | | | 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; pTable->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) ); assert( pParse->pNewTable==0 ); pParse->pNewTable = pTable; /* If this is the magic sqlite_sequence table used by autoincrement, ** then record a pointer to this table in the main database structure ** so that INSERT can find the table easily. */ |
︙ | ︙ | |||
2726 2727 2728 2729 2730 2731 2732 | char **ppExtra /* Pointer to the "extra" space */ ){ Index *p; /* Allocated index object */ int nByte; /* Bytes of space for Index object + arrays */ nByte = ROUND8(sizeof(Index)) + /* Index structure */ ROUND8(sizeof(char*)*nCol) + /* Index.azColl */ | | | | | | 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 | char **ppExtra /* Pointer to the "extra" space */ ){ Index *p; /* Allocated index object */ int nByte; /* Bytes of space for Index object + arrays */ nByte = ROUND8(sizeof(Index)) + /* Index structure */ ROUND8(sizeof(char*)*nCol) + /* Index.azColl */ ROUND8(sizeof(LogEst)*(nCol+1) + /* Index.aiRowLogEst */ sizeof(i16)*nCol + /* Index.aiColumn */ sizeof(u8)*nCol); /* Index.aSortOrder */ p = sqlite3DbMallocZero(db, nByte + nExtra); if( p ){ char *pExtra = ((char*)p)+ROUND8(sizeof(Index)); p->azColl = (char**)pExtra; pExtra += ROUND8(sizeof(char*)*nCol); p->aiRowLogEst = (LogEst*)pExtra; pExtra += sizeof(LogEst)*(nCol+1); p->aiColumn = (i16*)pExtra; pExtra += sizeof(i16)*nCol; p->aSortOrder = (u8*)pExtra; p->nColumn = nCol; p->nKeyCol = nCol - 1; *ppExtra = ((char*)p) + nByte; } return p; } |
︙ | ︙ | |||
2964 2965 2966 2967 2968 2969 2970 | nName = sqlite3Strlen30(zName); nExtraCol = pPk ? pPk->nKeyCol : 1; pIndex = sqlite3AllocateIndexObject(db, pList->nExpr + nExtraCol, nName + nExtra + 1, &zExtra); if( db->mallocFailed ){ goto exit_create_index; } | | | 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 | nName = sqlite3Strlen30(zName); nExtraCol = pPk ? pPk->nKeyCol : 1; pIndex = sqlite3AllocateIndexObject(db, pList->nExpr + nExtraCol, nName + nExtra + 1, &zExtra); if( db->mallocFailed ){ goto exit_create_index; } assert( EIGHT_BYTE_ALIGNMENT(pIndex->aiRowLogEst) ); assert( EIGHT_BYTE_ALIGNMENT(pIndex->azColl) ); pIndex->zName = zExtra; zExtra += nName + 1; memcpy(pIndex->zName, zName, nName+1); pIndex->pTable = pTab; pIndex->onError = (u8)onError; pIndex->uniqNotNull = onError!=OE_None; |
︙ | ︙ | |||
3245 3246 3247 3248 3249 3250 3251 | ** Fill the Index.aiRowEst[] array with default information - information ** to be used when we have not run the ANALYZE command. ** ** aiRowEst[0] is suppose to contain the number of elements in the index. ** Since we do not know, guess 1 million. aiRowEst[1] is an estimate of the ** number of rows in the table that match any particular value of the ** first column of the index. aiRowEst[2] is an estimate of the number | | > > | > | < > > > | | | > > > | | < < < | > > | 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 | ** Fill the Index.aiRowEst[] array with default information - information ** to be used when we have not run the ANALYZE command. ** ** aiRowEst[0] is suppose to contain the number of elements in the index. ** Since we do not know, guess 1 million. aiRowEst[1] is an estimate of the ** number of rows in the table that match any particular value of the ** first column of the index. aiRowEst[2] is an estimate of the number ** of rows that match any particular combination of the first 2 columns ** of the index. And so forth. It must always be the case that * ** aiRowEst[N]<=aiRowEst[N-1] ** aiRowEst[N]>=1 ** ** Apart from that, we have little to go on besides intuition as to ** how aiRowEst[] should be initialized. The numbers generated here ** are based on typical values found in actual indices. */ void sqlite3DefaultRowEst(Index *pIdx){ /* 10, 9, 8, 7, 6 */ LogEst aVal[] = { 33, 32, 30, 28, 26 }; LogEst *a = pIdx->aiRowLogEst; int nCopy = MIN(ArraySize(aVal), pIdx->nKeyCol); int i; /* Set the first entry (number of rows in the index) to the estimated ** number of rows in the table. Or 10, if the estimated number of rows ** in the table is less than that. */ a[0] = pIdx->pTable->nRowLogEst; if( a[0]<33 ) a[0] = 33; assert( 33==sqlite3LogEst(10) ); /* Estimate that a[1] is 10, a[2] is 9, a[3] is 8, a[4] is 7, a[5] is ** 6 and each subsequent value (if any) is 5. */ memcpy(&a[1], aVal, nCopy*sizeof(LogEst)); for(i=nCopy+1; i<=pIdx->nKeyCol; i++){ a[i] = 23; assert( 23==sqlite3LogEst(5) ); } assert( 0==sqlite3LogEst(1) ); if( pIdx->onError!=OE_None ) a[pIdx->nKeyCol] = 0; } /* ** This routine will drop an existing named index. This routine ** implements the DROP INDEX statement. */ void sqlite3DropIndex(Parse *pParse, SrcList *pName, int ifExists){ |
︙ | ︙ |
Changes to src/insert.c.
︙ | ︙ | |||
1861 1862 1863 1864 1865 1866 1867 | if( pDest->nCol!=pSrc->nCol ){ return 0; /* Number of columns must be the same in tab1 and tab2 */ } if( pDest->iPKey!=pSrc->iPKey ){ return 0; /* Both tables must have the same INTEGER PRIMARY KEY */ } for(i=0; i<pDest->nCol; i++){ | | > > | | > > > > > > > | 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 | if( pDest->nCol!=pSrc->nCol ){ return 0; /* Number of columns must be the same in tab1 and tab2 */ } if( pDest->iPKey!=pSrc->iPKey ){ return 0; /* Both tables must have the same INTEGER PRIMARY KEY */ } for(i=0; i<pDest->nCol; i++){ Column *pDestCol = &pDest->aCol[i]; Column *pSrcCol = &pSrc->aCol[i]; if( pDestCol->affinity!=pSrcCol->affinity ){ return 0; /* Affinity must be the same on all columns */ } if( !xferCompatibleCollation(pDestCol->zColl, pSrcCol->zColl) ){ return 0; /* Collating sequence must be the same on all columns */ } if( pDestCol->notNull && !pSrcCol->notNull ){ return 0; /* tab2 must be NOT NULL if tab1 is */ } /* Default values for second and subsequent columns need to match. */ if( i>0 && ((pDestCol->zDflt==0)!=(pSrcCol->zDflt==0) || (pDestCol->zDflt && strcmp(pDestCol->zDflt, pSrcCol->zDflt)!=0)) ){ return 0; /* Default values must be the same for all columns */ } } for(pDestIdx=pDest->pIndex; pDestIdx; pDestIdx=pDestIdx->pNext){ if( pDestIdx->onError!=OE_None ){ destHasUniqueIdx = 1; } for(pSrcIdx=pSrc->pIndex; pSrcIdx; pSrcIdx=pSrcIdx->pNext){ |
︙ | ︙ |
Changes to src/pragma.c.
︙ | ︙ | |||
1484 1485 1486 1487 1488 1489 1490 | sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "height", SQLITE_STATIC); for(i=sqliteHashFirst(&pDb->pSchema->tblHash); i; i=sqliteHashNext(i)){ Table *pTab = sqliteHashData(i); sqlite3VdbeAddOp4(v, OP_String8, 0, 1, 0, pTab->zName, 0); sqlite3VdbeAddOp2(v, OP_Null, 0, 2); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pTab->szTabRow), 3); | | > | > | 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 | sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "height", SQLITE_STATIC); for(i=sqliteHashFirst(&pDb->pSchema->tblHash); i; i=sqliteHashNext(i)){ Table *pTab = sqliteHashData(i); sqlite3VdbeAddOp4(v, OP_String8, 0, 1, 0, pTab->zName, 0); sqlite3VdbeAddOp2(v, OP_Null, 0, 2); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pTab->szTabRow), 3); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pTab->nRowLogEst), 4); sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4); for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pIdx->szIdxRow), 3); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pIdx->aiRowLogEst[0]), 4); sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4); } } } break; case PragTyp_INDEX_INFO: if( zRight ){ |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
467 468 469 470 471 472 473 | int nPrefixReg /* No. of reg prior to regData available for use */ ){ Vdbe *v = pParse->pVdbe; /* Stmt under construction */ int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0); int nExpr = pSort->pOrderBy->nExpr; /* No. of ORDER BY terms */ int nBase = nExpr + bSeq + nData; /* Fields in sorter record */ int regBase; /* Regs for sorter record */ | | | > | 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 | int nPrefixReg /* No. of reg prior to regData available for use */ ){ Vdbe *v = pParse->pVdbe; /* Stmt under construction */ int bSeq = ((pSort->sortFlags & SORTFLAG_UseSorter)==0); int nExpr = pSort->pOrderBy->nExpr; /* No. of ORDER BY terms */ int nBase = nExpr + bSeq + nData; /* Fields in sorter record */ int regBase; /* Regs for sorter record */ int regRecord = ++pParse->nMem; /* Assembled sorter record */ int nOBSat = pSort->nOBSat; /* ORDER BY terms to skip */ int op; /* Opcode to add sorter record to sorter */ assert( bSeq==0 || bSeq==1 ); if( nPrefixReg ){ assert( nPrefixReg==nExpr+bSeq ); regBase = regData - nExpr - bSeq; }else{ regBase = pParse->nMem + 1; pParse->nMem += nBase; } sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, SQLITE_ECEL_DUP); if( bSeq ){ sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr); } if( nPrefixReg==0 ){ sqlite3VdbeAddOp3(v, OP_Move, regData, regBase+nExpr+bSeq, nData); |
︙ | ︙ | |||
507 508 509 510 511 512 513 | }else{ addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor); } VdbeCoverage(v); sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat); pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex); if( pParse->db->mallocFailed ) return; | | < < < < < < | 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 | }else{ addrFirst = sqlite3VdbeAddOp1(v, OP_SequenceTest, pSort->iECursor); } VdbeCoverage(v); sqlite3VdbeAddOp3(v, OP_Compare, regPrevKey, regBase, pSort->nOBSat); pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex); if( pParse->db->mallocFailed ) return; pOp->p2 = nKey + nData; pKI = pOp->p4.pKeyInfo; memset(pKI->aSortOrder, 0, pKI->nField); /* Makes OP_Jump below testable */ sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO); pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat, 1); addrJmp = sqlite3VdbeCurrentAddr(v); sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v); pSort->labelBkOut = sqlite3VdbeMakeLabel(v); pSort->regReturn = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut); sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor); sqlite3VdbeJumpHere(v, addrFirst); sqlite3VdbeAddOp3(v, OP_Move, regBase, regPrevKey, pSort->nOBSat); sqlite3VdbeJumpHere(v, addrJmp); } if( pSort->sortFlags & SORTFLAG_UseSorter ){ op = OP_SorterInsert; }else{ op = OP_IdxInsert; } sqlite3VdbeAddOp2(v, op, pSort->iECursor, regRecord); if( pSelect->iLimit ){ int addr1, addr2; int iLimit; if( pSelect->iOffset ){ iLimit = pSelect->iOffset+1; }else{ iLimit = pSelect->iLimit; |
︙ | ︙ | |||
1718 1719 1720 1721 1722 1723 1724 | return 0; } /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside ** is disabled */ assert( db->lookaside.bEnabled==0 ); pTab->nRef = 1; pTab->zName = 0; | | | 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 | return 0; } /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside ** is disabled */ assert( db->lookaside.bEnabled==0 ); pTab->nRef = 1; pTab->zName = 0; pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) ); selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol); selectAddColumnTypeAndCollation(pParse, pTab, pSelect); pTab->iPKey = -1; if( db->mallocFailed ){ sqlite3DeleteTable(db, pTab); return 0; } |
︙ | ︙ | |||
3857 3858 3859 3860 3861 3862 3863 | assert( pFrom->pTab==0 ); pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3DbStrDup(db, pCte->zName); pTab->iPKey = -1; | | | 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 | assert( pFrom->pTab==0 ); pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3DbStrDup(db, pCte->zName); pTab->iPKey = -1; pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) ); pTab->tabFlags |= TF_Ephemeral; pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0); if( db->mallocFailed ) return SQLITE_NOMEM; assert( pFrom->pSelect ); /* Check if this is a recursive CTE. */ pSel = pFrom->pSelect; |
︙ | ︙ | |||
4033 4034 4035 4036 4037 4038 4039 | pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab); while( pSel->pPrior ){ pSel = pSel->pPrior; } selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol); pTab->iPKey = -1; | | | 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 | pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab); while( pSel->pPrior ){ pSel = pSel->pPrior; } selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol); pTab->iPKey = -1; pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) ); pTab->tabFlags |= TF_Ephemeral; #endif }else{ /* An ordinary table or view name in the FROM clause */ assert( pFrom->pTab==0 ); pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom); if( pTab==0 ) return WRC_Abort; |
︙ | ︙ | |||
4683 4684 4685 4686 4687 4688 4689 | pItem->regReturn = ++pParse->nMem; sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop); VdbeComment((v, "%s", pItem->pTab->zName)); pItem->addrFillSub = addrTop; sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); | | | 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 | pItem->regReturn = ++pParse->nMem; sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop); VdbeComment((v, "%s", pItem->pTab->zName)); pItem->addrFillSub = addrTop; sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); pItem->viaCoroutine = 1; pItem->regResult = dest.iSdst; sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn); sqlite3VdbeJumpHere(v, addrTop-1); sqlite3ClearTempRegCache(pParse); }else{ /* Generate a subroutine that will fill an ephemeral table with |
︙ | ︙ | |||
4714 4715 4716 4717 4718 4719 4720 | VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName)); }else{ VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName)); } sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); | | | 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 | VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName)); }else{ VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName)); } sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr); retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn); VdbeComment((v, "end %s", pItem->pTab->zName)); sqlite3VdbeChangeP1(v, topAddr, retAddr); sqlite3ClearTempRegCache(pParse); } if( /*pParse->nErr ||*/ db->mallocFailed ){ |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
521 522 523 524 525 526 527 | /* ** Estimated quantities used for query planning are stored as 16-bit ** logarithms. For quantity X, the value stored is 10*log2(X). This ** gives a possible range of values of approximately 1.0e986 to 1e-986. ** But the allowed values are "grainy". Not every value is representable. ** For example, quantities 16 and 17 are both represented by a LogEst | | | | 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 | /* ** Estimated quantities used for query planning are stored as 16-bit ** logarithms. For quantity X, the value stored is 10*log2(X). This ** gives a possible range of values of approximately 1.0e986 to 1e-986. ** But the allowed values are "grainy". Not every value is representable. ** For example, quantities 16 and 17 are both represented by a LogEst ** of 40. However, since LogEst quantaties are suppose to be estimates, ** not exact values, this imprecision is not a problem. ** ** "LogEst" is short for "Logarithmic Estimate". ** ** Examples: ** 1 -> 0 20 -> 43 10000 -> 132 ** 2 -> 10 25 -> 46 25000 -> 146 ** 3 -> 16 100 -> 66 1000000 -> 199 ** 4 -> 20 1000 -> 99 1048576 -> 200 ** 10 -> 33 1024 -> 100 4294967296 -> 320 |
︙ | ︙ | |||
1467 1468 1469 1470 1471 1472 1473 | Index *pIndex; /* List of SQL indexes on this table. */ Select *pSelect; /* NULL for tables. Points to definition if a view. */ FKey *pFKey; /* Linked list of all foreign keys in this table */ char *zColAff; /* String defining the affinity of each column */ #ifndef SQLITE_OMIT_CHECK ExprList *pCheck; /* All CHECK constraints */ #endif | | | 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 | Index *pIndex; /* List of SQL indexes on this table. */ Select *pSelect; /* NULL for tables. Points to definition if a view. */ FKey *pFKey; /* Linked list of all foreign keys in this table */ char *zColAff; /* String defining the affinity of each column */ #ifndef SQLITE_OMIT_CHECK ExprList *pCheck; /* All CHECK constraints */ #endif LogEst nRowLogEst; /* Estimated rows in table - from sqlite_stat1 table */ int tnum; /* Root BTree node for this table (see note above) */ i16 iPKey; /* If not negative, use aCol[iPKey] as the primary key */ i16 nCol; /* Number of columns in this table */ u16 nRef; /* Number of pointers to this Table */ LogEst szTabRow; /* Estimated size of each table row in bytes */ u8 tabFlags; /* Mask of TF_* values */ u8 keyConf; /* What to do in case of uniqueness conflict on iPKey */ |
︙ | ︙ | |||
1676 1677 1678 1679 1680 1681 1682 | ** and the value of Index.onError indicate the which conflict resolution ** algorithm to employ whenever an attempt is made to insert a non-unique ** element. */ struct Index { char *zName; /* Name of this index */ i16 *aiColumn; /* Which columns are used by this index. 1st is 0 */ | | | 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 | ** and the value of Index.onError indicate the which conflict resolution ** algorithm to employ whenever an attempt is made to insert a non-unique ** element. */ struct Index { char *zName; /* Name of this index */ i16 *aiColumn; /* Which columns are used by this index. 1st is 0 */ LogEst *aiRowLogEst; /* From ANALYZE: Est. rows selected by each column */ Table *pTable; /* The SQL table being indexed */ char *zColAff; /* String defining the affinity of each column */ Index *pNext; /* The next index associated with the same table */ Schema *pSchema; /* Schema containing this index */ u8 *aSortOrder; /* for each column: True==DESC, False==ASC */ char **azColl; /* Array of collation sequence names for index */ Expr *pPartIdxWhere; /* WHERE clause for partial indices */ |
︙ | ︙ |
Changes to src/test_rtree.c.
︙ | ︙ | |||
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | double xmax; double ymin; double ymax; } aBox[2]; double centerx; double centery; double radius; }; /* ** Destructor function for Circle objects allocated by circle_geom(). */ static void circle_del(void *p){ sqlite3_free(p); } /* ** Implementation of "circle" r-tree geometry callback. */ static int circle_geom( sqlite3_rtree_geometry *p, int nCoord, | > > < < < | < > > > > | > | 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | double xmax; double ymin; double ymax; } aBox[2]; double centerx; double centery; double radius; double mxArea; int eScoreType; }; /* ** Destructor function for Circle objects allocated by circle_geom(). */ static void circle_del(void *p){ sqlite3_free(p); } /* ** Implementation of "circle" r-tree geometry callback. */ static int circle_geom( sqlite3_rtree_geometry *p, int nCoord, sqlite3_rtree_dbl *aCoord, int *pRes ){ int i; /* Iterator variable */ Circle *pCircle; /* Structure defining circular region */ double xmin, xmax; /* X dimensions of box being tested */ double ymin, ymax; /* X dimensions of box being tested */ xmin = aCoord[0]; xmax = aCoord[1]; ymin = aCoord[2]; ymax = aCoord[3]; pCircle = (Circle *)p->pUser; if( pCircle==0 ){ /* If pUser is still 0, then the parameter values have not been tested ** for correctness or stored into a Circle structure yet. Do this now. */ /* This geometry callback is for use with a 2-dimensional r-tree table. ** Return an error if the table does not have exactly 2 dimensions. */ if( nCoord!=4 ) return SQLITE_ERROR; |
︙ | ︙ | |||
104 105 106 107 108 109 110 111 112 | pCircle->aBox[0].xmax = pCircle->centerx; pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius; pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius; pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius; pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius; pCircle->aBox[1].ymin = pCircle->centery; pCircle->aBox[1].ymax = pCircle->centery; } | > < < < < < < | 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | pCircle->aBox[0].xmax = pCircle->centerx; pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius; pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius; pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius; pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius; pCircle->aBox[1].ymin = pCircle->centery; pCircle->aBox[1].ymax = pCircle->centery; pCircle->mxArea = (xmax - xmin)*(ymax - ymin) + 1.0; } /* Check if any of the 4 corners of the bounding-box being tested lie ** inside the circular region. If they do, then the bounding-box does ** intersect the region of interest. Set the output variable to true and ** return SQLITE_OK in this case. */ for(i=0; i<4; i++){ double x = (i&0x01) ? xmax : xmin; double y = (i&0x02) ? ymax : ymin; |
︙ | ︙ | |||
149 150 151 152 153 154 155 156 157 158 159 160 161 162 | } /* The specified bounding box does not intersect the circular region. Set ** the output variable to zero and return SQLITE_OK. */ *pRes = 0; return SQLITE_OK; } /* END of implementation of "circle" geometry callback. ************************************************************************** *************************************************************************/ #include <assert.h> #include "tcl.h" | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 | } /* The specified bounding box does not intersect the circular region. Set ** the output variable to zero and return SQLITE_OK. */ *pRes = 0; return SQLITE_OK; } /* ** Implementation of "circle" r-tree geometry callback using the ** 2nd-generation interface that allows scoring. */ static int circle_query_func(sqlite3_rtree_query_info *p){ int i; /* Iterator variable */ Circle *pCircle; /* Structure defining circular region */ double xmin, xmax; /* X dimensions of box being tested */ double ymin, ymax; /* X dimensions of box being tested */ int nWithin = 0; /* Number of corners inside the circle */ xmin = p->aCoord[0]; xmax = p->aCoord[1]; ymin = p->aCoord[2]; ymax = p->aCoord[3]; pCircle = (Circle *)p->pUser; if( pCircle==0 ){ /* If pUser is still 0, then the parameter values have not been tested ** for correctness or stored into a Circle structure yet. Do this now. */ /* This geometry callback is for use with a 2-dimensional r-tree table. ** Return an error if the table does not have exactly 2 dimensions. */ if( p->nCoord!=4 ) return SQLITE_ERROR; /* Test that the correct number of parameters (4) have been supplied, ** and that the parameters are in range (that the radius of the circle ** radius is greater than zero). */ if( p->nParam!=4 || p->aParam[2]<0.0 ) return SQLITE_ERROR; /* Allocate a structure to cache parameter data in. Return SQLITE_NOMEM ** if the allocation fails. */ pCircle = (Circle *)(p->pUser = sqlite3_malloc(sizeof(Circle))); if( !pCircle ) return SQLITE_NOMEM; p->xDelUser = circle_del; /* Record the center and radius of the circular region. One way that ** tested bounding boxes that intersect the circular region are detected ** is by testing if each corner of the bounding box lies within radius ** units of the center of the circle. */ pCircle->centerx = p->aParam[0]; pCircle->centery = p->aParam[1]; pCircle->radius = p->aParam[2]; pCircle->eScoreType = (int)p->aParam[3]; /* Define two bounding box regions. The first, aBox[0], extends to ** infinity in the X dimension. It covers the same range of the Y dimension ** as the circular region. The second, aBox[1], extends to infinity in ** the Y dimension and is constrained to the range of the circle in the ** X dimension. ** ** Then imagine each box is split in half along its short axis by a line ** that intersects the center of the circular region. A bounding box ** being tested can be said to intersect the circular region if it contains ** points from each half of either of the two infinite bounding boxes. */ pCircle->aBox[0].xmin = pCircle->centerx; pCircle->aBox[0].xmax = pCircle->centerx; pCircle->aBox[0].ymin = pCircle->centery + pCircle->radius; pCircle->aBox[0].ymax = pCircle->centery - pCircle->radius; pCircle->aBox[1].xmin = pCircle->centerx + pCircle->radius; pCircle->aBox[1].xmax = pCircle->centerx - pCircle->radius; pCircle->aBox[1].ymin = pCircle->centery; pCircle->aBox[1].ymax = pCircle->centery; pCircle->mxArea = 200.0*200.0; } /* Check if any of the 4 corners of the bounding-box being tested lie ** inside the circular region. If they do, then the bounding-box does ** intersect the region of interest. Set the output variable to true and ** return SQLITE_OK in this case. */ for(i=0; i<4; i++){ double x = (i&0x01) ? xmax : xmin; double y = (i&0x02) ? ymax : ymin; double d2; d2 = (x-pCircle->centerx)*(x-pCircle->centerx); d2 += (y-pCircle->centery)*(y-pCircle->centery); if( d2<(pCircle->radius*pCircle->radius) ) nWithin++; } /* Check if the bounding box covers any other part of the circular region. ** See comments above for a description of how this test works. If it does ** cover part of the circular region, set the output variable to true ** and return SQLITE_OK. */ if( nWithin==0 ){ for(i=0; i<2; i++){ if( xmin<=pCircle->aBox[i].xmin && xmax>=pCircle->aBox[i].xmax && ymin<=pCircle->aBox[i].ymin && ymax>=pCircle->aBox[i].ymax ){ nWithin = 1; break; } } } if( pCircle->eScoreType==1 ){ /* Depth first search */ p->rScore = p->iLevel; }else if( pCircle->eScoreType==2 ){ /* Breadth first search */ p->rScore = 100 - p->iLevel; }else if( pCircle->eScoreType==3 ){ /* Depth-first search, except sort the leaf nodes by area with ** the largest area first */ if( p->iLevel==1 ){ p->rScore = 1.0 - (xmax-xmin)*(ymax-ymin)/pCircle->mxArea; if( p->rScore<0.01 ) p->rScore = 0.01; }else{ p->rScore = 0.0; } }else if( pCircle->eScoreType==4 ){ /* Depth-first search, except exclude odd rowids */ p->rScore = p->iLevel; if( p->iRowid&1 ) nWithin = 0; }else{ /* Breadth-first search, except exclude odd rowids */ p->rScore = 100 - p->iLevel; if( p->iRowid&1 ) nWithin = 0; } if( nWithin==0 ){ p->eWithin = NOT_WITHIN; }else if( nWithin>=4 ){ p->eWithin = FULLY_WITHIN; }else{ p->eWithin = PARTLY_WITHIN; } return SQLITE_OK; } /* ** Implementation of "breadthfirstsearch" r-tree geometry callback using the ** 2nd-generation interface that allows scoring. ** ** ... WHERE id MATCH breadthfirstsearch($x0,$x1,$y0,$y1) ... ** ** It returns all entries whose bounding boxes overlap with $x0,$x1,$y0,$y1. */ static int bfs_query_func(sqlite3_rtree_query_info *p){ double x0,x1,y0,y1; /* Dimensions of box being tested */ double bx0,bx1,by0,by1; /* Boundary of the query function */ if( p->nParam!=4 ) return SQLITE_ERROR; x0 = p->aCoord[0]; x1 = p->aCoord[1]; y0 = p->aCoord[2]; y1 = p->aCoord[3]; bx0 = p->aParam[0]; bx1 = p->aParam[1]; by0 = p->aParam[2]; by1 = p->aParam[3]; p->rScore = 100 - p->iLevel; if( p->eParentWithin==FULLY_WITHIN ){ p->eWithin = FULLY_WITHIN; }else if( x0>=bx0 && x1<=bx1 && y0>=by0 && y1<=by1 ){ p->eWithin = FULLY_WITHIN; }else if( x1>=bx0 && x0<=bx1 && y1>=by0 && y0<=by1 ){ p->eWithin = PARTLY_WITHIN; }else{ p->eWithin = NOT_WITHIN; } return SQLITE_OK; } /* END of implementation of "circle" geometry callback. ************************************************************************** *************************************************************************/ #include <assert.h> #include "tcl.h" |
︙ | ︙ | |||
190 191 192 193 194 195 196 | ** cube(x, y, z, width, height, depth) ** ** The width, height and depth parameters must all be greater than zero. */ static int cube_geom( sqlite3_rtree_geometry *p, int nCoord, | < < < | < | 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 | ** cube(x, y, z, width, height, depth) ** ** The width, height and depth parameters must all be greater than zero. */ static int cube_geom( sqlite3_rtree_geometry *p, int nCoord, sqlite3_rtree_dbl *aCoord, int *piRes ){ Cube *pCube = (Cube *)p->pUser; assert( p->pContext==(void *)&gHere ); if( pCube==0 ){ |
︙ | ︙ | |||
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 | if( objc!=2 ){ Tcl_WrongNumArgs(interp, 1, objv, "DB"); return TCL_ERROR; } if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR; rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0); Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC); #endif return TCL_OK; } int Sqlitetestrtree_Init(Tcl_Interp *interp){ Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0); Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0); return TCL_OK; } | > > > > > > > > | 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 | if( objc!=2 ){ Tcl_WrongNumArgs(interp, 1, objv, "DB"); return TCL_ERROR; } if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR; rc = sqlite3_rtree_geometry_callback(db, "circle", circle_geom, 0); if( rc==SQLITE_OK ){ rc = sqlite3_rtree_query_callback(db, "Qcircle", circle_query_func, 0, 0); } if( rc==SQLITE_OK ){ rc = sqlite3_rtree_query_callback(db, "breadthfirstsearch", bfs_query_func, 0, 0); } Tcl_SetResult(interp, (char *)sqlite3ErrName(rc), TCL_STATIC); #endif return TCL_OK; } int Sqlitetestrtree_Init(Tcl_Interp *interp){ Tcl_CreateObjCommand(interp, "register_cube_geom", register_cube_geom, 0, 0); Tcl_CreateObjCommand(interp, "register_circle_geom",register_circle_geom,0,0); return TCL_OK; } |
Changes to src/test_vfstrace.c.
︙ | ︙ | |||
674 675 676 677 678 679 680 | const char *zPath, int flags, int *pResOut ){ vfstrace_info *pInfo = (vfstrace_info*)pVfs->pAppData; sqlite3_vfs *pRoot = pInfo->pRootVfs; int rc; | | | 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 | const char *zPath, int flags, int *pResOut ){ vfstrace_info *pInfo = (vfstrace_info*)pVfs->pAppData; sqlite3_vfs *pRoot = pInfo->pRootVfs; int rc; vfstrace_printf(pInfo, "%s.xAccess(\"%s\",%d)", pInfo->zVfsName, zPath, flags); rc = pRoot->xAccess(pRoot, zPath, flags, pResOut); vfstrace_print_errcode(pInfo, " -> %s", rc); vfstrace_printf(pInfo, ", out=%d\n", *pResOut); return rc; } |
︙ | ︙ |
Changes to src/util.c.
︙ | ︙ | |||
1242 1243 1244 1245 1246 1247 1248 | if( b>a+49 ) return b; if( b>a+31 ) return b+1; return b+x[b-a]; } } /* | | | | 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 | if( b>a+49 ) return b; if( b>a+31 ) return b+1; return b+x[b-a]; } } /* ** Convert an integer into a LogEst. In other words, compute an ** approximation for 10*log2(x). */ LogEst sqlite3LogEst(u64 x){ static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 }; LogEst y = 40; if( x<8 ){ if( x<2 ) return 0; while( x<8 ){ y -= 10; x <<= 1; } |
︙ | ︙ |
Changes to src/vdbe.c.
︙ | ︙ | |||
4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 | case OP_SorterData: { VdbeCursor *pC; pOut = &aMem[pOp->p2]; pC = p->apCsr[pOp->p1]; assert( isSorter(pC) ); rc = sqlite3VdbeSorterRowkey(pC, pOut); break; } /* Opcode: RowData P1 P2 * * * ** Synopsis: r[P2]=data ** ** Write into register P2 the complete row data for cursor P1. | > | 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 | case OP_SorterData: { VdbeCursor *pC; pOut = &aMem[pOp->p2]; pC = p->apCsr[pOp->p1]; assert( isSorter(pC) ); rc = sqlite3VdbeSorterRowkey(pC, pOut); assert( rc!=SQLITE_OK || (pOut->flags & MEM_Blob) ); break; } /* Opcode: RowData P1 P2 * * * ** Synopsis: r[P2]=data ** ** Write into register P2 the complete row data for cursor P1. |
︙ | ︙ | |||
6337 6338 6339 6340 6341 6342 6343 | ** readability. From this point on down, the normal indentation rules are ** restored. *****************************************************************************/ } #ifdef VDBE_PROFILE { | | | | 6338 6339 6340 6341 6342 6343 6344 6345 6346 6347 6348 6349 6350 6351 6352 6353 | ** readability. From this point on down, the normal indentation rules are ** restored. *****************************************************************************/ } #ifdef VDBE_PROFILE { u64 endTime = sqlite3Hwtime(); if( endTime>start ) pOp->cycles += endTime - start; pOp->cnt++; } #endif /* The following code adds nothing to the actual functionality ** of the program. It is only here for testing and debugging. ** On the other hand, it does burn CPU cycles every time through |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
223 224 225 226 227 228 229 | } pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]); } pTerm = &pWC->a[idx = pWC->nTerm++]; if( p && ExprHasProperty(p, EP_Unlikely) ){ pTerm->truthProb = sqlite3LogEst(p->iTable) - 99; }else{ | | | 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 | } pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]); } pTerm = &pWC->a[idx = pWC->nTerm++]; if( p && ExprHasProperty(p, EP_Unlikely) ){ pTerm->truthProb = sqlite3LogEst(p->iTable) - 99; }else{ pTerm->truthProb = 1; } pTerm->pExpr = sqlite3ExprSkipCollate(p); pTerm->wtFlags = wtFlags; pTerm->pWC = pWC; pTerm->iParent = -1; return idx; } |
︙ | ︙ | |||
1952 1953 1954 1955 1956 1957 1958 | aStat[1] = aSample[i].anEq[iCol]; }else{ tRowcnt iLower, iUpper, iGap; if( i==0 ){ iLower = 0; iUpper = aSample[0].anLt[iCol]; }else{ | > | > > > > > > > > > > > > > > > > > > > > > > > | 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 | aStat[1] = aSample[i].anEq[iCol]; }else{ tRowcnt iLower, iUpper, iGap; if( i==0 ){ iLower = 0; iUpper = aSample[0].anLt[iCol]; }else{ i64 nRow0 = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]); iUpper = i>=pIdx->nSample ? nRow0 : aSample[i].anLt[iCol]; iLower = aSample[i-1].anEq[iCol] + aSample[i-1].anLt[iCol]; } aStat[1] = (pIdx->nKeyCol>iCol ? pIdx->aAvgEq[iCol] : 1); if( iLower>=iUpper ){ iGap = 0; }else{ iGap = iUpper - iLower; } if( roundUp ){ iGap = (iGap*2)/3; }else{ iGap = iGap/3; } aStat[0] = iLower + iGap; } } #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ /* ** If it is not NULL, pTerm is a term that provides an upper or lower ** bound on a range scan. Without considering pTerm, it is estimated ** that the scan will visit nNew rows. This function returns the number ** estimated to be visited after taking pTerm into account. ** ** If the user explicitly specified a likelihood() value for this term, ** then the return value is the likelihood multiplied by the number of ** input rows. Otherwise, this function assumes that an "IS NOT NULL" term ** has a likelihood of 0.50, and any other term a likelihood of 0.25. */ static LogEst whereRangeAdjust(WhereTerm *pTerm, LogEst nNew){ LogEst nRet = nNew; if( pTerm ){ if( pTerm->truthProb<=0 ){ nRet += pTerm->truthProb; }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){ nRet -= 20; assert( 20==sqlite3LogEst(4) ); } } return nRet; } /* ** This function is used to estimate the number of rows that will be visited ** by scanning an index for a range of values. The range may have an upper ** bound, a lower bound, or both. The WHERE clause terms that set the upper ** and lower bounds are represented by pLower and pUpper respectively. For ** example, assuming that index p is on t1(a): |
︙ | ︙ | |||
2063 2064 2065 2066 2067 2068 2069 | aff = SQLITE_AFF_INTEGER; }else{ aff = p->pTable->aCol[p->aiColumn[nEq]].affinity; } /* Determine iLower and iUpper using ($P) only. */ if( nEq==0 ){ iLower = 0; | | | 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 | aff = SQLITE_AFF_INTEGER; }else{ aff = p->pTable->aCol[p->aiColumn[nEq]].affinity; } /* Determine iLower and iUpper using ($P) only. */ if( nEq==0 ){ iLower = 0; iUpper = sqlite3LogEstToInt(p->aiRowLogEst[0]); }else{ /* Note: this call could be optimized away - since the same values must ** have been requested when testing key $P in whereEqualScanEst(). */ whereKeyStats(pParse, p, pRec, 0, a); iLower = a[0]; iUpper = a[0] + a[1]; } |
︙ | ︙ | |||
2123 2124 2125 2126 2127 2128 2129 | } } #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(pBuilder); #endif assert( pLower || pUpper ); | < < < | < | > | | > > > > | < | > | 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 | } } #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(pBuilder); #endif assert( pLower || pUpper ); assert( pUpper==0 || (pUpper->wtFlags & TERM_VNULL)==0 ); nNew = whereRangeAdjust(pLower, nOut); nNew = whereRangeAdjust(pUpper, nNew); /* TUNING: If there is both an upper and lower limit, assume the range is ** reduced by an additional 75%. This means that, by default, an open-ended ** range query (e.g. col > ?) is assumed to match 1/4 of the rows in the ** index. While a closed range (e.g. col BETWEEN ? AND ?) is estimated to ** match 1/64 of the index. */ if( pLower && pUpper ) nNew -= 20; nOut -= (pLower!=0) + (pUpper!=0); if( nNew<10 ) nNew = 10; if( nNew<nOut ) nOut = nNew; pLoop->nOut = (LogEst)nOut; return rc; } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
︙ | ︙ | |||
2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 | static int whereInScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */ tRowcnt *pnRow /* Write the revised row estimate here */ ){ Index *p = pBuilder->pNew->u.btree.pIndex; int nRecValid = pBuilder->nRecValid; int rc = SQLITE_OK; /* Subfunction return code */ tRowcnt nEst; /* Number of rows for a single term */ tRowcnt nRowEst = 0; /* New estimate of the number of rows */ int i; /* Loop counter */ assert( p->aSample!=0 ); for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){ | > | | | 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 | static int whereInScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */ tRowcnt *pnRow /* Write the revised row estimate here */ ){ Index *p = pBuilder->pNew->u.btree.pIndex; i64 nRow0 = sqlite3LogEstToInt(p->aiRowLogEst[0]); int nRecValid = pBuilder->nRecValid; int rc = SQLITE_OK; /* Subfunction return code */ tRowcnt nEst; /* Number of rows for a single term */ tRowcnt nRowEst = 0; /* New estimate of the number of rows */ int i; /* Loop counter */ assert( p->aSample!=0 ); for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){ nEst = nRow0; rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst); nRowEst += nEst; pBuilder->nRecValid = nRecValid; } if( rc==SQLITE_OK ){ if( nRowEst > nRow0 ) nRowEst = nRow0; *pnRow = nRowEst; WHERETRACE(0x10,("IN row estimate: est=%g\n", nRowEst)); } assert( pBuilder->nRecValid==nRecValid ); return rc; } #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ |
︙ | ︙ | |||
3753 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 3766 3767 3768 3769 3770 3771 3772 | ** ** (2) pTemplate costs more than any other WhereLoops for which pTemplate ** is a proper subset. ** ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer ** WHERE clause terms than Y and that every WHERE clause term used by X is ** also used by Y. */ static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){ if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return; for(; p; p=p->pNextLoop){ if( p->iTab!=pTemplate->iTab ) continue; if( (p->wsFlags & WHERE_INDEXED)==0 ) continue; if( whereLoopCheaperProperSubset(p, pTemplate) ){ /* Adjust pTemplate cost downward so that it is cheaper than its ** subset p */ pTemplate->rRun = p->rRun; pTemplate->nOut = p->nOut - 1; }else if( whereLoopCheaperProperSubset(pTemplate, p) ){ /* Adjust pTemplate cost upward so that it is costlier than p since | > > > > > > > > > > > > > | 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 | ** ** (2) pTemplate costs more than any other WhereLoops for which pTemplate ** is a proper subset. ** ** To say "WhereLoop X is a proper subset of Y" means that X uses fewer ** WHERE clause terms than Y and that every WHERE clause term used by X is ** also used by Y. ** ** This adjustment is omitted for SKIPSCAN loops. In a SKIPSCAN loop, the ** WhereLoop.nLTerm field is not an accurate measure of the number of WHERE ** clause terms covered, since some of the first nLTerm entries in aLTerm[] ** will be NULL (because they are skipped). That makes it more difficult ** to compare the loops. We could add extra code to do the comparison, and ** perhaps we will someday. But SKIPSCAN is sufficiently uncommon, and this ** adjustment is sufficient minor, that it is very difficult to construct ** a test case where the extra code would improve the query plan. Better ** to avoid the added complexity and just omit cost adjustments to SKIPSCAN ** loops. */ static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){ if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return; if( (pTemplate->wsFlags & WHERE_SKIPSCAN)!=0 ) return; for(; p; p=p->pNextLoop){ if( p->iTab!=pTemplate->iTab ) continue; if( (p->wsFlags & WHERE_INDEXED)==0 ) continue; if( (p->wsFlags & WHERE_SKIPSCAN)!=0 ) continue; if( whereLoopCheaperProperSubset(p, pTemplate) ){ /* Adjust pTemplate cost downward so that it is cheaper than its ** subset p */ pTemplate->rRun = p->rRun; pTemplate->nOut = p->nOut - 1; }else if( whereLoopCheaperProperSubset(pTemplate, p) ){ /* Adjust pTemplate cost upward so that it is costlier than p since |
︙ | ︙ | |||
3983 3984 3985 3986 3987 3988 3989 | if( (pTerm->prereqAll & notAllowed)!=0 ) continue; for(j=pLoop->nLTerm-1; j>=0; j--){ pX = pLoop->aLTerm[j]; if( pX==0 ) continue; if( pX==pTerm ) break; if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; } | | > > | | > > > > > | 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046 4047 4048 4049 | if( (pTerm->prereqAll & notAllowed)!=0 ) continue; for(j=pLoop->nLTerm-1; j>=0; j--){ pX = pLoop->aLTerm[j]; if( pX==0 ) continue; if( pX==pTerm ) break; if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break; } if( j<0 ){ pLoop->nOut += (pTerm->truthProb<=0 ? pTerm->truthProb : -1); } } } /* ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the ** index pIndex. Try to match one more. ** ** When this function is called, pBuilder->pNew->nOut contains the ** number of rows expected to be visited by filtering using the nEq ** terms only. If it is modified, this value is restored before this ** function returns. ** ** If pProbe->tnum==0, that means pIndex is a fake index used for the ** INTEGER PRIMARY KEY. */ static int whereLoopAddBtreeIndex( WhereLoopBuilder *pBuilder, /* The WhereLoop factory */ struct SrcList_item *pSrc, /* FROM clause term being analyzed */ |
︙ | ︙ | |||
4015 4016 4017 4018 4019 4020 4021 | u16 saved_nLTerm; /* Original value of pNew->nLTerm */ u16 saved_nEq; /* Original value of pNew->u.btree.nEq */ u16 saved_nSkip; /* Original value of pNew->u.btree.nSkip */ u32 saved_wsFlags; /* Original value of pNew->wsFlags */ LogEst saved_nOut; /* Original value of pNew->nOut */ int iCol; /* Index of the column in the table */ int rc = SQLITE_OK; /* Return code */ | < < < < | | < < | > > > > > > > | | < | | > > > | < < | > > > > > > | | < < | < < < < | < < < | < < < < | | | | | | | > > | > > | > > > > > > | > > > > > > > > > | | | | > > | | < | | | | | < | | | > > | | | > | | > > > > > > > > > > > > > > > > > > > < < | | > | > > > > > > > > | 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 4262 4263 4264 4265 4266 4267 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 4286 4287 | u16 saved_nLTerm; /* Original value of pNew->nLTerm */ u16 saved_nEq; /* Original value of pNew->u.btree.nEq */ u16 saved_nSkip; /* Original value of pNew->u.btree.nSkip */ u32 saved_wsFlags; /* Original value of pNew->wsFlags */ LogEst saved_nOut; /* Original value of pNew->nOut */ int iCol; /* Index of the column in the table */ int rc = SQLITE_OK; /* Return code */ LogEst rLogSize; /* Logarithm of table size */ WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */ pNew = pBuilder->pNew; if( db->mallocFailed ) return SQLITE_NOMEM; assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 ); assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 ); if( pNew->wsFlags & WHERE_BTM_LIMIT ){ opMask = WO_LT|WO_LE; }else if( pProbe->tnum<=0 || (pSrc->jointype & JT_LEFT)!=0 ){ opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE; }else{ opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE; } if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE); assert( pNew->u.btree.nEq<=pProbe->nKeyCol ); if( pNew->u.btree.nEq < pProbe->nKeyCol ){ iCol = pProbe->aiColumn[pNew->u.btree.nEq]; }else{ iCol = -1; } pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, pProbe); saved_nEq = pNew->u.btree.nEq; saved_nSkip = pNew->u.btree.nSkip; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(pProbe->aiRowLogEst[0]); /* Consider using a skip-scan if there are no WHERE clause constraints ** available for the left-most terms of the index, and if the average ** number of repeats in the left-most terms is at least 18. ** ** The magic number 18 is selected on the basis that scanning 17 rows ** is almost always quicker than an index seek (even though if the index ** contains fewer than 2^17 rows we assume otherwise in other parts of ** the code). And, even if it is not, it should not be too much slower. ** On the other hand, the extra seeks could end up being significantly ** more expensive. */ assert( 42==sqlite3LogEst(18) ); if( pTerm==0 && saved_nEq==saved_nSkip && saved_nEq+1<pProbe->nKeyCol && pProbe->aiRowLogEst[saved_nEq+1]>=42 /* TUNING: Minimum for skip-scan */ && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK ){ LogEst nIter; pNew->u.btree.nEq++; pNew->u.btree.nSkip++; pNew->aLTerm[pNew->nLTerm++] = 0; pNew->wsFlags |= WHERE_SKIPSCAN; nIter = pProbe->aiRowLogEst[saved_nEq] - pProbe->aiRowLogEst[saved_nEq+1]; pNew->nOut -= nIter; whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter + nInMul); pNew->nOut = saved_nOut; } for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ u16 eOp = pTerm->eOperator; /* Shorthand for pTerm->eOperator */ LogEst rCostIdx; LogEst nOutUnadjusted; /* nOut before IN() and WHERE adjustments */ int nIn = 0; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 int nRecValid = pBuilder->nRecValid; #endif if( (eOp==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0) && (iCol<0 || pSrc->pTab->aCol[iCol].notNull) ){ continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */ } if( pTerm->prereqRight & pNew->maskSelf ) continue; pNew->wsFlags = saved_wsFlags; pNew->u.btree.nEq = saved_nEq; pNew->nLTerm = saved_nLTerm; if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */ pNew->aLTerm[pNew->nLTerm++] = pTerm; pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; assert( nInMul==0 || (pNew->wsFlags & WHERE_COLUMN_NULL)!=0 || (pNew->wsFlags & WHERE_COLUMN_IN)!=0 || (pNew->wsFlags & WHERE_SKIPSCAN)!=0 ); if( eOp & WO_IN ){ Expr *pExpr = pTerm->pExpr; pNew->wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */ nIn = 46; assert( 46==sqlite3LogEst(25) ); }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nIn = sqlite3LogEst(pExpr->x.pList->nExpr); } assert( nIn>0 ); /* RHS always has 2 or more terms... The parser ** changes "x IN (?)" into "x=?". */ }else if( eOp & (WO_EQ) ){ pNew->wsFlags |= WHERE_COLUMN_EQ; if( iCol<0 || (nInMul==0 && pNew->u.btree.nEq==pProbe->nKeyCol-1) ){ if( iCol>=0 && pProbe->onError==OE_None ){ pNew->wsFlags |= WHERE_UNQ_WANTED; }else{ pNew->wsFlags |= WHERE_ONEROW; } } }else if( eOp & WO_ISNULL ){ pNew->wsFlags |= WHERE_COLUMN_NULL; }else if( eOp & (WO_GT|WO_GE) ){ testcase( eOp & WO_GT ); testcase( eOp & WO_GE ); pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT; pBtm = pTerm; pTop = 0; }else{ assert( eOp & (WO_LT|WO_LE) ); testcase( eOp & WO_LT ); testcase( eOp & WO_LE ); pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT; pTop = pTerm; pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? pNew->aLTerm[pNew->nLTerm-2] : 0; } /* At this point pNew->nOut is set to the number of rows expected to ** be visited by the index scan before considering term pTerm, or the ** values of nIn and nInMul. In other words, assuming that all ** "x IN(...)" terms are replaced with "x = ?". This block updates ** the value of pNew->nOut to account for pTerm (but not nIn/nInMul). */ assert( pNew->nOut==saved_nOut ); if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut using stat3/stat4 data. Or, if there is no stat3/stat4 ** data, using some other estimate. */ whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew); }else{ int nEq = ++pNew->u.btree.nEq; assert( eOp & (WO_ISNULL|WO_EQ|WO_IN) ); assert( pNew->nOut==saved_nOut ); if( pTerm->truthProb<=0 && iCol>=0 ){ assert( (eOp & WO_IN) || nIn==0 ); testcase( eOp & WO_IN ); pNew->nOut += pTerm->truthProb; pNew->nOut -= nIn; pNew->wsFlags |= WHERE_LIKELIHOOD; }else{ #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 tRowcnt nOut = 0; if( nInMul==0 && pProbe->nSample && pNew->u.btree.nEq<=pProbe->nSampleCol && OptimizationEnabled(db, SQLITE_Stat3) && ((eOp & WO_IN)==0 || !ExprHasProperty(pTerm->pExpr, EP_xIsSelect)) && (pNew->wsFlags & WHERE_LIKELIHOOD)==0 ){ Expr *pExpr = pTerm->pExpr; if( (eOp & (WO_EQ|WO_ISNULL))!=0 ){ testcase( eOp & WO_EQ ); testcase( eOp & WO_ISNULL ); rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut); }else{ rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut); } assert( rc!=SQLITE_OK || nOut>0 ); if( rc==SQLITE_NOTFOUND ) rc = SQLITE_OK; if( rc!=SQLITE_OK ) break; /* Jump out of the pTerm loop */ if( nOut ){ pNew->nOut = sqlite3LogEst(nOut); if( pNew->nOut>saved_nOut ) pNew->nOut = saved_nOut; pNew->nOut -= nIn; } } if( nOut==0 ) #endif { pNew->nOut += (pProbe->aiRowLogEst[nEq] - pProbe->aiRowLogEst[nEq-1]); if( eOp & WO_ISNULL ){ /* TUNING: If there is no likelihood() value, assume that a ** "col IS NULL" expression matches twice as many rows ** as (col=?). */ pNew->nOut += 10; } } } } /* Set rCostIdx to the cost of visiting selected rows in index. Add ** it to pNew->rRun, which is currently set to the cost of the index ** seek only. Then, if this is a non-covering index, add the cost of ** visiting the rows in the main table. */ rCostIdx = pNew->nOut + 1 + (15*pProbe->szIdxRow)/pSrc->pTab->szTabRow; pNew->rRun = sqlite3LogEstAdd(rLogSize, rCostIdx); if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){ pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut + 16); } nOutUnadjusted = pNew->nOut; pNew->rRun += nInMul + nIn; pNew->nOut += nInMul + nIn; whereLoopOutputAdjust(pBuilder->pWC, pNew); rc = whereLoopInsert(pBuilder, pNew); if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ pNew->nOut = saved_nOut; }else{ pNew->nOut = nOutUnadjusted; } if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->u.btree.nEq<(pProbe->nKeyCol + (pProbe->zName!=0)) ){ whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn); } pNew->nOut = saved_nOut; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 |
︙ | ︙ | |||
4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 | return 0; } /* ** Add all WhereLoop objects for a single table of the join where the table ** is idenfied by pBuilder->pNew->iTab. That table is guaranteed to be ** a b-tree table, not a virtual table. */ static int whereLoopAddBtree( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ WhereInfo *pWInfo; /* WHERE analysis context */ Index *pProbe; /* An index we are evaluating */ Index sPk; /* A fake index object for the primary key */ | > > > > > > > > > > > > > > > > > > > > > > > | | 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 | return 0; } /* ** Add all WhereLoop objects for a single table of the join where the table ** is idenfied by pBuilder->pNew->iTab. That table is guaranteed to be ** a b-tree table, not a virtual table. ** ** The costs (WhereLoop.rRun) of the b-tree loops added by this function ** are calculated as follows: ** ** For a full scan, assuming the table (or index) contains nRow rows: ** ** cost = nRow * 3.0 // full-table scan ** cost = nRow * K // scan of covering index ** cost = nRow * (K+3.0) // scan of non-covering index ** ** where K is a value between 1.1 and 3.0 set based on the relative ** estimated average size of the index and table records. ** ** For an index scan, where nVisit is the number of index rows visited ** by the scan, and nSeek is the number of seek operations required on ** the index b-tree: ** ** cost = nSeek * (log(nRow) + K * nVisit) // covering index ** cost = nSeek * (log(nRow) + (K+3.0) * nVisit) // non-covering index ** ** Normally, nSeek is 1. nSeek values greater than 1 come about if the ** WHERE clause includes "x IN (....)" terms used in place of "x=?". Or when ** implicit "x IN (SELECT x FROM tbl)" terms are added for skip-scans. */ static int whereLoopAddBtree( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ WhereInfo *pWInfo; /* WHERE analysis context */ Index *pProbe; /* An index we are evaluating */ Index sPk; /* A fake index object for the primary key */ LogEst aiRowEstPk[2]; /* The aiRowLogEst[] value for the sPk index */ i16 aiColumnPk = -1; /* The aColumn[] value for the sPk index */ SrcList *pTabList; /* The FROM clause */ struct SrcList_item *pSrc; /* The FROM clause btree term to add */ WhereLoop *pNew; /* Template WhereLoop object */ int rc = SQLITE_OK; /* Return code */ int iSortIdx = 1; /* Index number */ int b; /* A boolean value */ |
︙ | ︙ | |||
4312 4313 4314 4315 4316 4317 4318 | ** variable sPk to represent the rowid primary key index. Make this ** fake index the first in a chain of Index objects with all of the real ** indices to follow */ Index *pFirst; /* First of real indices on the table */ memset(&sPk, 0, sizeof(Index)); sPk.nKeyCol = 1; sPk.aiColumn = &aiColumnPk; | | > | | | | 4423 4424 4425 4426 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 | ** variable sPk to represent the rowid primary key index. Make this ** fake index the first in a chain of Index objects with all of the real ** indices to follow */ Index *pFirst; /* First of real indices on the table */ memset(&sPk, 0, sizeof(Index)); sPk.nKeyCol = 1; sPk.aiColumn = &aiColumnPk; sPk.aiRowLogEst = aiRowEstPk; sPk.onError = OE_Replace; sPk.pTable = pTab; sPk.szIdxRow = pTab->szTabRow; aiRowEstPk[0] = pTab->nRowLogEst; aiRowEstPk[1] = 0; pFirst = pSrc->pTab->pIndex; if( pSrc->notIndexed==0 ){ /* The real indices of the table are only considered if the ** NOT INDEXED qualifier is omitted from the FROM clause */ sPk.pNext = pFirst; } pProbe = &sPk; } rSize = pTab->nRowLogEst; rLogSize = estLog(rSize); #ifndef SQLITE_OMIT_AUTOMATIC_INDEX /* Automatic indexes */ if( !pBuilder->pOrSet && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 && pSrc->pIndex==0 |
︙ | ︙ | |||
4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 | /* Loop over all indices */ for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){ if( pProbe->pPartIdxWhere!=0 && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){ continue; /* Partial index inappropriate for this query */ } pNew->u.btree.nEq = 0; pNew->u.btree.nSkip = 0; pNew->nLTerm = 0; pNew->iSortIdx = 0; pNew->rSetup = 0; pNew->prereq = mExtra; pNew->nOut = rSize; pNew->u.btree.pIndex = pProbe; b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor); /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */ assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 ); if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; /* Full table scan */ pNew->iSortIdx = b ? iSortIdx : 0; | > | < < | | 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 | /* Loop over all indices */ for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){ if( pProbe->pPartIdxWhere!=0 && !whereUsablePartialIndex(pNew->iTab, pWC, pProbe->pPartIdxWhere) ){ continue; /* Partial index inappropriate for this query */ } rSize = pProbe->aiRowLogEst[0]; pNew->u.btree.nEq = 0; pNew->u.btree.nSkip = 0; pNew->nLTerm = 0; pNew->iSortIdx = 0; pNew->rSetup = 0; pNew->prereq = mExtra; pNew->nOut = rSize; pNew->u.btree.pIndex = pProbe; b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor); /* The ONEPASS_DESIRED flags never occurs together with ORDER BY */ assert( (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || b==0 ); if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; /* Full table scan */ pNew->iSortIdx = b ? iSortIdx : 0; /* TUNING: Cost of full table scan is (N*3.0). */ pNew->rRun = rSize + 16; whereLoopOutputAdjust(pWC, pNew); rc = whereLoopInsert(pBuilder, pNew); pNew->nOut = rSize; if( rc ) break; }else{ Bitmask m; if( pProbe->isCovering ){ |
︙ | ︙ | |||
4422 4423 4424 4425 4426 4427 4428 | && (pProbe->szIdxRow<pTab->szTabRow) && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) ) ){ pNew->iSortIdx = b ? iSortIdx : 0; | | < < < < | < | < < < | < > | < < < < < < < < < < < | < | > | 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 | && (pProbe->szIdxRow<pTab->szTabRow) && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) ) ){ pNew->iSortIdx = b ? iSortIdx : 0; /* The cost of visiting the index rows is N*K, where K is ** between 1.1 and 3.0, depending on the relative sizes of the ** index and table rows. If this is a non-covering index scan, ** also add the cost of visiting table rows (N*3.0). */ pNew->rRun = rSize + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow; if( m!=0 ){ pNew->rRun = sqlite3LogEstAdd(pNew->rRun, rSize+16); } whereLoopOutputAdjust(pWC, pNew); rc = whereLoopInsert(pBuilder, pNew); pNew->nOut = rSize; if( rc ) break; } } |
︙ | ︙ | |||
4654 4655 4656 4657 4658 4659 4660 | WhereClause *pWC; WhereLoop *pNew; WhereTerm *pTerm, *pWCEnd; int rc = SQLITE_OK; int iCur; WhereClause tempWC; WhereLoopBuilder sSubBuild; | | | 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 4757 4758 4759 4760 | WhereClause *pWC; WhereLoop *pNew; WhereTerm *pTerm, *pWCEnd; int rc = SQLITE_OK; int iCur; WhereClause tempWC; WhereLoopBuilder sSubBuild; WhereOrSet sSum, sCur; struct SrcList_item *pItem; pWC = pBuilder->pWC; if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; memset(&sSum, 0, sizeof(sSum)); |
︙ | ︙ | |||
4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 | if( sCur.n==0 ){ sSum.n = 0; break; }else if( once ){ whereOrMove(&sSum, &sCur); once = 0; }else{ whereOrMove(&sPrev, &sSum); sSum.n = 0; for(i=0; i<sPrev.n; i++){ for(j=0; j<sCur.n; j++){ whereOrInsert(&sSum, sPrev.a[i].prereq | sCur.a[j].prereq, sqlite3LogEstAdd(sPrev.a[i].rRun, sCur.a[j].rRun), sqlite3LogEstAdd(sPrev.a[i].nOut, sCur.a[j].nOut)); } } } } pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; pNew->wsFlags = WHERE_MULTI_OR; pNew->rSetup = 0; pNew->iSortIdx = 0; memset(&pNew->u, 0, sizeof(pNew->u)); for(i=0; rc==SQLITE_OK && i<sSum.n; i++){ | > | > > > > > > > > > > > | | 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 | if( sCur.n==0 ){ sSum.n = 0; break; }else if( once ){ whereOrMove(&sSum, &sCur); once = 0; }else{ WhereOrSet sPrev; whereOrMove(&sPrev, &sSum); sSum.n = 0; for(i=0; i<sPrev.n; i++){ for(j=0; j<sCur.n; j++){ whereOrInsert(&sSum, sPrev.a[i].prereq | sCur.a[j].prereq, sqlite3LogEstAdd(sPrev.a[i].rRun, sCur.a[j].rRun), sqlite3LogEstAdd(sPrev.a[i].nOut, sCur.a[j].nOut)); } } } } pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; pNew->wsFlags = WHERE_MULTI_OR; pNew->rSetup = 0; pNew->iSortIdx = 0; memset(&pNew->u, 0, sizeof(pNew->u)); for(i=0; rc==SQLITE_OK && i<sSum.n; i++){ /* TUNING: Currently sSum.a[i].rRun is set to the sum of the costs ** of all sub-scans required by the OR-scan. However, due to rounding ** errors, it may be that the cost of the OR-scan is equal to its ** most expensive sub-scan. Add the smallest possible penalty ** (equivalent to multiplying the cost by 1.07) to ensure that ** this does not happen. Otherwise, for WHERE clauses such as the ** following where there is an index on "y": ** ** WHERE likelihood(x=?, 0.99) OR y=? ** ** the planner may elect to "OR" together a full-table scan and an ** index lookup. And other similarly odd results. */ pNew->rRun = sSum.a[i].rRun + 1; pNew->nOut = sSum.a[i].nOut; pNew->prereq = sSum.a[i].prereq; rc = whereLoopInsert(pBuilder, pNew); } } } return rc; |
︙ | ︙ | |||
4853 4854 4855 4856 4857 4858 4859 | ** ** The rowid for a table is always UNIQUE and NOT NULL so whenever the ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is ** automatically order-distinct. */ assert( pOrderBy!=0 ); | < < < < < < < < | > > > | 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 | ** ** The rowid for a table is always UNIQUE and NOT NULL so whenever the ** rowid appears in the ORDER BY clause, the corresponding WhereLoop is ** automatically order-distinct. */ assert( pOrderBy!=0 ); if( nLoop && OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return 0; nOrderBy = pOrderBy->nExpr; testcase( nOrderBy==BMS-1 ); if( nOrderBy>BMS-1 ) return 0; /* Cannot optimize overly large ORDER BYs */ isOrderDistinct = 1; obDone = MASKBIT(nOrderBy)-1; orderDistinctMask = 0; ready = 0; for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){ if( iLoop>0 ) ready |= pLoop->maskSelf; pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast; if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){ if( pLoop->u.vtab.isOrdered ) obSat = obDone; break; } iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; /* Mark off any ORDER BY term X that is a column in the table of ** the current loop for which there is term in the WHERE ** clause of the form X IS NULL or X=? that reference only outer ** loops. */ |
︙ | ︙ | |||
5180 5181 5182 5183 5184 5185 5186 | nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; if( isOrdered<0 ){ isOrdered = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, iLoop, pWLoop, &revMask); if( isOrdered>=0 && isOrdered<nOrderBy ){ | | > > > > | | | | < < | | > > | | > | | | 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309 5310 5311 5312 5313 | nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; if( isOrdered<0 ){ isOrdered = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, iLoop, pWLoop, &revMask); if( isOrdered>=0 && isOrdered<nOrderBy ){ /* TUNING: Estimated cost of a full external sort, where N is ** the number of rows to sort is: ** ** cost = (3.0 * N * log(N)). ** ** Or, if the order-by clause has X terms but only the last Y ** terms are out of order, then block-sorting will reduce the ** sorting cost to: ** ** cost = (3.0 * N * log(N)) * (Y/X) ** ** The (Y/X) term is implemented using stack variable rScale ** below. */ LogEst rScale, rSortCost; assert( nOrderBy>0 && 66==sqlite3LogEst(100) ); rScale = sqlite3LogEst((nOrderBy-isOrdered)*100/nOrderBy) - 66; rSortCost = nRowEst + estLog(nRowEst) + rScale + 16; /* TUNING: The cost of implementing DISTINCT using a B-TREE is ** similar but with a larger constant of proportionality. ** Multiply by an additional factor of 3.0. */ if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ rSortCost += 16; } WHERETRACE(0x002, ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n", rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost, sqlite3LogEstAdd(rCost,rSortCost))); |
︙ | ︙ |
Changes to src/whereInt.h.
︙ | ︙ | |||
454 455 456 457 458 459 460 | #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ #define WHERE_UNQ_WANTED 0x00010000 /* WHERE_ONEROW would have been helpful*/ | > | 454 455 456 457 458 459 460 461 | #define WHERE_VIRTUALTABLE 0x00000400 /* WhereLoop.u.vtab is valid */ #define WHERE_IN_ABLE 0x00000800 /* Able to support an IN operator */ #define WHERE_ONEROW 0x00001000 /* Selects no more than one row */ #define WHERE_MULTI_OR 0x00002000 /* OR using multiple indices */ #define WHERE_AUTO_INDEX 0x00004000 /* Uses an ephemeral index */ #define WHERE_SKIPSCAN 0x00008000 /* Uses the skip-scan algorithm */ #define WHERE_UNQ_WANTED 0x00010000 /* WHERE_ONEROW would have been helpful*/ #define WHERE_LIKELIHOOD 0x00020000 /* A likelihood() is affecting nOut */ |
Changes to test/analyze3.test.
︙ | ︙ | |||
99 100 101 102 103 104 105 106 107 108 109 110 | ifcapable stat4 { execsql { SELECT count(*)>0 FROM sqlite_stat4; } } else { execsql { SELECT count(*)>0 FROM sqlite_stat3; } } } {1} do_eqp_test analyze3-1.1.2 { SELECT sum(y) FROM t1 WHERE x>200 AND x<300 } {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (x>? AND x<?)}} do_eqp_test analyze3-1.1.3 { SELECT sum(y) FROM t1 WHERE x>0 AND x<1100 | > > > > > > > > > | | | | > > > > > | | | | > > > > | | | | | 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 | ifcapable stat4 { execsql { SELECT count(*)>0 FROM sqlite_stat4; } } else { execsql { SELECT count(*)>0 FROM sqlite_stat3; } } } {1} do_execsql_test analyze3-1.1.x { SELECT count(*) FROM t1 WHERE x>200 AND x<300; SELECT count(*) FROM t1 WHERE x>0 AND x<1100; } {99 1000} # The first of the following two SELECT statements visits 99 rows. So # it is better to use the index. But the second visits every row in # the table (1000 in total) so it is better to do a full-table scan. # do_eqp_test analyze3-1.1.2 { SELECT sum(y) FROM t1 WHERE x>200 AND x<300 } {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (x>? AND x<?)}} do_eqp_test analyze3-1.1.3 { SELECT sum(y) FROM t1 WHERE x>0 AND x<1100 } {0 0 0 {SCAN TABLE t1}} do_test analyze3-1.1.4 { sf_execsql { SELECT sum(y) FROM t1 WHERE x>200 AND x<300 } } {199 0 14850} do_test analyze3-1.1.5 { set l [string range "200" 0 end] set u [string range "300" 0 end] sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u } } {199 0 14850} do_test analyze3-1.1.6 { set l [expr int(200)] set u [expr int(300)] sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u } } {199 0 14850} do_test analyze3-1.1.7 { sf_execsql { SELECT sum(y) FROM t1 WHERE x>0 AND x<1100 } } {999 999 499500} do_test analyze3-1.1.8 { set l [string range "0" 0 end] set u [string range "1100" 0 end] sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u } } {999 999 499500} do_test analyze3-1.1.9 { set l [expr int(0)] set u [expr int(1100)] sf_execsql { SELECT sum(y) FROM t1 WHERE x>$l AND x<$u } } {999 999 499500} # The following tests are similar to the block above. The difference is # that the indexed column has TEXT affinity in this case. In the tests # above the affinity is INTEGER. # do_test analyze3-1.2.1 { execsql { BEGIN; CREATE TABLE t2(x TEXT, y); INSERT INTO t2 SELECT * FROM t1; CREATE INDEX i2 ON t2(x); COMMIT; ANALYZE; } } {} do_execsql_test analyze3-2.1.x { SELECT count(*) FROM t2 WHERE x>1 AND x<2; SELECT count(*) FROM t2 WHERE x>0 AND x<99; } {200 990} do_eqp_test analyze3-1.2.2 { SELECT sum(y) FROM t2 WHERE x>1 AND x<2 } {0 0 0 {SEARCH TABLE t2 USING INDEX i2 (x>? AND x<?)}} do_eqp_test analyze3-1.2.3 { SELECT sum(y) FROM t2 WHERE x>0 AND x<99 } {0 0 0 {SCAN TABLE t2}} do_test analyze3-1.2.4 { sf_execsql { SELECT sum(y) FROM t2 WHERE x>12 AND x<20 } } {161 0 4760} do_test analyze3-1.2.5 { set l [string range "12" 0 end] set u [string range "20" 0 end] sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u} } {161 0 text text 4760} do_test analyze3-1.2.6 { set l [expr int(12)] set u [expr int(20)] sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u} } {161 0 integer integer 4760} do_test analyze3-1.2.7 { sf_execsql { SELECT sum(y) FROM t2 WHERE x>0 AND x<99 } } {999 999 490555} do_test analyze3-1.2.8 { set l [string range "0" 0 end] set u [string range "99" 0 end] sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u} } {999 999 text text 490555} do_test analyze3-1.2.9 { set l [expr int(0)] set u [expr int(99)] sf_execsql {SELECT typeof($l), typeof($u), sum(y) FROM t2 WHERE x>$l AND x<$u} } {999 999 integer integer 490555} # Same tests a third time. This time, column x has INTEGER affinity and # is not the leftmost column of the table. This triggered a bug causing # SQLite to use sub-optimal query plans in 3.6.18 and earlier. # do_test analyze3-1.3.1 { execsql { BEGIN; CREATE TABLE t3(y TEXT, x INTEGER); INSERT INTO t3 SELECT y, x FROM t1; CREATE INDEX i3 ON t3(x); COMMIT; ANALYZE; } } {} do_execsql_test analyze3-1.3.x { SELECT count(*) FROM t3 WHERE x>200 AND x<300; SELECT count(*) FROM t3 WHERE x>0 AND x<1100 } {99 1000} do_eqp_test analyze3-1.3.2 { SELECT sum(y) FROM t3 WHERE x>200 AND x<300 } {0 0 0 {SEARCH TABLE t3 USING INDEX i3 (x>? AND x<?)}} do_eqp_test analyze3-1.3.3 { SELECT sum(y) FROM t3 WHERE x>0 AND x<1100 } {0 0 0 {SCAN TABLE t3}} do_test analyze3-1.3.4 { sf_execsql { SELECT sum(y) FROM t3 WHERE x>200 AND x<300 } } {199 0 14850} do_test analyze3-1.3.5 { set l [string range "200" 0 end] set u [string range "300" 0 end] sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u } } {199 0 14850} do_test analyze3-1.3.6 { set l [expr int(200)] set u [expr int(300)] sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u } } {199 0 14850} do_test analyze3-1.3.7 { sf_execsql { SELECT sum(y) FROM t3 WHERE x>0 AND x<1100 } } {999 999 499500} do_test analyze3-1.3.8 { set l [string range "0" 0 end] set u [string range "1100" 0 end] sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u } } {999 999 499500} do_test analyze3-1.3.9 { set l [expr int(0)] set u [expr int(1100)] sf_execsql { SELECT sum(y) FROM t3 WHERE x>$l AND x<$u } } {999 999 499500} #------------------------------------------------------------------------- # Test that the values of bound SQL variables may be used for the LIKE # optimization. # drop_all_tables do_test analyze3-2.1 { |
︙ | ︙ |
Changes to test/analyze9.test.
︙ | ︙ | |||
562 563 564 565 566 567 568 | #------------------------------------------------------------------------- # Check that affinities are taken into account when using stat4 data to # estimate the number of rows scanned by a rowid constraint. # drop_all_tables do_test 13.1 { execsql { | | | | | | | 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 | #------------------------------------------------------------------------- # Check that affinities are taken into account when using stat4 data to # estimate the number of rows scanned by a rowid constraint. # drop_all_tables do_test 13.1 { execsql { CREATE TABLE t1(a, b, c, d); CREATE INDEX i1 ON t1(a); CREATE INDEX i2 ON t1(b, c); } for {set i 0} {$i<100} {incr i} { if {$i %2} {set a abc} else {set a def} execsql { INSERT INTO t1(rowid, a, b, c) VALUES($i, $a, $i, $i) } } execsql ANALYZE } {} do_eqp_test 13.2.1 { SELECT * FROM t1 WHERE a='abc' AND rowid<15 AND b<12 } {/SEARCH TABLE t1 USING INDEX i1/} do_eqp_test 13.2.2 { SELECT * FROM t1 WHERE a='abc' AND rowid<'15' AND b<12 } {/SEARCH TABLE t1 USING INDEX i1/} do_eqp_test 13.3.1 { SELECT * FROM t1 WHERE a='abc' AND rowid<100 AND b<12 } {/SEARCH TABLE t1 USING INDEX i2/} do_eqp_test 13.3.2 { SELECT * FROM t1 WHERE a='abc' AND rowid<'100' AND b<12 } {/SEARCH TABLE t1 USING INDEX i2/} #------------------------------------------------------------------------- # Check also that affinities are taken into account when using stat4 data # to estimate the number of rows scanned by any other constraint on a # column other than the leftmost. # |
︙ | ︙ |
Changes to test/autoindex1.test.
︙ | ︙ | |||
93 94 95 96 97 98 99 100 101 102 103 104 105 106 | db status autoindex } {0} do_test autoindex1-210 { db eval { PRAGMA automatic_index=ON; ANALYZE; UPDATE sqlite_stat1 SET stat='10000' WHERE tbl='t1'; ANALYZE sqlite_master; SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1; } } {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988} do_test autoindex1-211 { db status step } {7} | > > | 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | db status autoindex } {0} do_test autoindex1-210 { db eval { PRAGMA automatic_index=ON; ANALYZE; UPDATE sqlite_stat1 SET stat='10000' WHERE tbl='t1'; -- Table t2 actually contains 8 rows. UPDATE sqlite_stat1 SET stat='16' WHERE tbl='t2'; ANALYZE sqlite_master; SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1; } } {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988} do_test autoindex1-211 { db status step } {7} |
︙ | ︙ |
Added test/cost.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 | # 2014-04-26 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix cost do_execsql_test 1.1 { CREATE TABLE t3(id INTEGER PRIMARY KEY, b NOT NULL); CREATE TABLE t4(c, d, e); CREATE UNIQUE INDEX i3 ON t3(b); CREATE UNIQUE INDEX i4 ON t4(c, d); } do_eqp_test 1.2 { SELECT e FROM t3, t4 WHERE b=c ORDER BY b, d; } { 0 0 0 {SCAN TABLE t3 USING COVERING INDEX i3} 0 1 1 {SEARCH TABLE t4 USING INDEX i4 (c=?)} } do_execsql_test 2.1 { CREATE TABLE t1(a, b); CREATE INDEX i1 ON t1(a); } # It is better to use an index for ORDER BY than sort externally, even # if the index is a non-covering index. do_eqp_test 2.2 { SELECT * FROM t1 ORDER BY a; } { 0 0 0 {SCAN TABLE t1 USING INDEX i1} } do_execsql_test 3.1 { CREATE TABLE t5(a INTEGER PRIMARY KEY,b,c,d,e,f,g); CREATE INDEX t5b ON t5(b); CREATE INDEX t5c ON t5(c); CREATE INDEX t5d ON t5(d); CREATE INDEX t5e ON t5(e); CREATE INDEX t5f ON t5(f); CREATE INDEX t5g ON t5(g); } do_eqp_test 3.2 { SELECT a FROM t5 WHERE b IS NULL OR c IS NULL OR d IS NULL ORDER BY a; } { 0 0 0 {SEARCH TABLE t5 USING INDEX t5b (b=?)} 0 0 0 {SEARCH TABLE t5 USING INDEX t5c (c=?)} 0 0 0 {SEARCH TABLE t5 USING INDEX t5d (d=?)} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } #------------------------------------------------------------------------- # If there is no likelihood() or stat3 data, SQLite assumes that a closed # range scan (e.g. one constrained by "col BETWEEN ? AND ?" constraint) # visits 1/64 of the rows in a table. # # Note: 1/63 =~ 0.016 # Note: 1/65 =~ 0.015 # reset_db do_execsql_test 4.1 { CREATE TABLE t1(a, b); CREATE INDEX i1 ON t1(a); CREATE INDEX i2 ON t1(b); } do_eqp_test 4.2 { SELECT * FROM t1 WHERE likelihood(a=?, 0.014) AND b BETWEEN ? AND ?; } { 0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)} } do_eqp_test 4.3 { SELECT * FROM t1 WHERE likelihood(a=?, 0.016) AND b BETWEEN ? AND ?; } { 0 0 0 {SEARCH TABLE t1 USING INDEX i2 (b>? AND b<?)} } #------------------------------------------------------------------------- # reset_db do_execsql_test 5.1 { CREATE TABLE t2(x, y); CREATE INDEX t2i1 ON t2(x); } do_eqp_test 5.2 { SELECT * FROM t2 ORDER BY x, y; } { 0 0 0 {SCAN TABLE t2 USING INDEX t2i1} 0 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY} } do_eqp_test 5.3 { SELECT * FROM t2 WHERE x BETWEEN ? AND ? ORDER BY rowid; } { 0 0 0 {SEARCH TABLE t2 USING INDEX t2i1 (x>? AND x<?)} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } # where7.test, where8.test: # do_execsql_test 6.1 { CREATE TABLE t3(a INTEGER PRIMARY KEY, b, c); CREATE INDEX t3i1 ON t3(b); CREATE INDEX t3i2 ON t3(c); } do_eqp_test 6.2 { SELECT a FROM t3 WHERE (b BETWEEN 2 AND 4) OR c=100 ORDER BY a } { 0 0 0 {SEARCH TABLE t3 USING INDEX t3i1 (b>? AND b<?)} 0 0 0 {SEARCH TABLE t3 USING INDEX t3i2 (c=?)} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } #------------------------------------------------------------------------- # reset_db do_execsql_test 7.1 { CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c,d,e,f,g); CREATE INDEX t1b ON t1(b); CREATE INDEX t1c ON t1(c); CREATE INDEX t1d ON t1(d); CREATE INDEX t1e ON t1(e); CREATE INDEX t1f ON t1(f); CREATE INDEX t1g ON t1(g); } do_eqp_test 7.2 { SELECT a FROM t1 WHERE (b>=950 AND b<=1010) OR (b IS NULL AND c NOT NULL) ORDER BY a } { 0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b>? AND b<?)} 0 0 0 {SEARCH TABLE t1 USING INDEX t1b (b=?)} 0 0 0 {USE TEMP B-TREE FOR ORDER BY} } do_eqp_test 7.3 { SELECT rowid FROM t1 WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL) OR (b NOT NULL AND c IS NULL AND d NOT NULL) OR (b NOT NULL AND c NOT NULL AND d IS NULL) } { 0 0 0 {SCAN TABLE t1} } do_eqp_test 7.4 { SELECT rowid FROM t1 WHERE (+b IS NULL AND c NOT NULL) OR c IS NULL } { 0 0 0 {SCAN TABLE t1} } #------------------------------------------------------------------------- # reset_db do_execsql_test 8.1 { CREATE TABLE composer( cid INTEGER PRIMARY KEY, cname TEXT ); CREATE TABLE album( aid INTEGER PRIMARY KEY, aname TEXT ); CREATE TABLE track( tid INTEGER PRIMARY KEY, cid INTEGER REFERENCES composer, aid INTEGER REFERENCES album, title TEXT ); CREATE INDEX track_i1 ON track(cid); CREATE INDEX track_i2 ON track(aid); } do_eqp_test 8.2 { SELECT DISTINCT aname FROM album, composer, track WHERE cname LIKE '%bach%' AND unlikely(composer.cid=track.cid) AND unlikely(album.aid=track.aid); } { 0 0 2 {SCAN TABLE track} 0 1 0 {SEARCH TABLE album USING INTEGER PRIMARY KEY (rowid=?)} 0 2 1 {SEARCH TABLE composer USING INTEGER PRIMARY KEY (rowid=?)} 0 0 0 {USE TEMP B-TREE FOR DISTINCT} } #------------------------------------------------------------------------- # do_execsql_test 9.1 { CREATE TABLE t1( a,b,c,d,e, f,g,h,i,j, k,l,m,n,o, p,q,r,s,t ); CREATE INDEX i1 ON t1(k,l,m,n,o,p,q,r,s,t); } do_test 9.2 { for {set i 0} {$i < 100} {incr i} { execsql { INSERT INTO t1 DEFAULT VALUES } } execsql { ANALYZE; CREATE INDEX i2 ON t1(a,b,c,d,e,f,g,h,i,j); } } {} set L [list a=? b=? c=? d=? e=? f=? g=? h=? i=? j=?] foreach {tn nTerm nRow} { 1 1 10 2 2 9 3 3 8 4 4 7 5 5 6 6 6 5 7 7 5 8 8 5 9 9 5 10 10 5 } { set w [join [lrange $L 0 [expr $nTerm-1]] " AND "] set p1 [expr ($nRow-1) / 100.0] set p2 [expr ($nRow+1) / 100.0] set sql1 "SELECT * FROM t1 WHERE likelihood(k=?, $p1) AND $w" set sql2 "SELECT * FROM t1 WHERE likelihood(k=?, $p2) AND $w" do_eqp_test 9.3.$tn.1 $sql1 {/INDEX i1/} do_eqp_test 9.3.$tn.2 $sql2 {/INDEX i2/} } finish_test |
Changes to test/e_createtable.test.
︙ | ︙ | |||
880 881 882 883 884 885 886 | h DEFAULT ( substr('abcd', 0, 2) || 'cd' ), i DEFAULT CURRENT_TIME, j DEFAULT CURRENT_DATE, k DEFAULT CURRENT_TIMESTAMP ); } {} | | > | | 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 | h DEFAULT ( substr('abcd', 0, 2) || 'cd' ), i DEFAULT CURRENT_TIME, j DEFAULT CURRENT_DATE, k DEFAULT CURRENT_TIMESTAMP ); } {} # EVIDENCE-OF: R-36381-62919 For the purposes of the DEFAULT clause, an # expression is considered constant provided that it does not contain # any sub-queries, column or table references, or string literals # enclosed in double-quotes instead of single-quotes. # do_createtable_tests 3.4.1 -error { default value of column [x] is not constant } { 1 {CREATE TABLE t5(x DEFAULT ( (SELECT 1) ))} {} 2 {CREATE TABLE t5(x DEFAULT ( "abc" ))} {} 3 {CREATE TABLE t5(x DEFAULT ( 1 IN (SELECT 1) ))} {} |
︙ | ︙ |
Changes to test/e_fkey.test.
︙ | ︙ | |||
131 132 133 134 135 136 137 | #------------------------------------------------------------------------- # EVIDENCE-OF: R-07280-60510 Assuming the library is compiled with # foreign key constraints enabled, it must still be enabled by the # application at runtime, using the PRAGMA foreign_keys command. # # This also tests that foreign key constraints are disabled by default. # | | | | 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 | #------------------------------------------------------------------------- # EVIDENCE-OF: R-07280-60510 Assuming the library is compiled with # foreign key constraints enabled, it must still be enabled by the # application at runtime, using the PRAGMA foreign_keys command. # # This also tests that foreign key constraints are disabled by default. # # EVIDENCE-OF: R-44261-39702 Foreign key constraints are disabled by # default (for backwards compatibility), so must be enabled separately # for each database connection. # drop_all_tables do_test e_fkey-4.1 { execsql { CREATE TABLE p(i PRIMARY KEY); CREATE TABLE c(j REFERENCES p ON UPDATE CASCADE); INSERT INTO p VALUES('hello'); |
︙ | ︙ | |||
159 160 161 162 163 164 165 | INSERT INTO c VALUES('hello'); UPDATE p SET i = 'world'; SELECT * FROM c; } } {world} #------------------------------------------------------------------------- | | > | 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 | INSERT INTO c VALUES('hello'); UPDATE p SET i = 'world'; SELECT * FROM c; } } {world} #------------------------------------------------------------------------- # EVIDENCE-OF: R-08013-37737 The application can also use a PRAGMA # foreign_keys statement to determine if foreign keys are currently # enabled. # # This also tests the example code in section 2 of foreignkeys.in. # # EVIDENCE-OF: R-11255-19907 # reset_db do_test e_fkey-5.1 { |
︙ | ︙ | |||
2986 2987 2988 2989 2990 2991 2992 | } {5} } #------------------------------------------------------------------------- # The setting of the recursive_triggers pragma does not affect foreign # key actions. # | | | | 2987 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 | } {5} } #------------------------------------------------------------------------- # The setting of the recursive_triggers pragma does not affect foreign # key actions. # # EVIDENCE-OF: R-44355-00270 The PRAGMA recursive_triggers setting does # not affect the operation of foreign key actions. # foreach recursive_triggers_setting [list 0 1 ON OFF] { drop_all_tables execsql "PRAGMA recursive_triggers = $recursive_triggers_setting" do_test e_fkey-64.$recursive_triggers_setting.1 { execsql { |
︙ | ︙ |
Changes to test/eqp.test.
︙ | ︙ | |||
308 309 310 311 312 313 314 | 0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (UNION ALL)} } do_eqp_test 4.2.3 { SELECT * FROM t1 UNION SELECT * FROM t2 ORDER BY 1 } { 1 0 0 {SCAN TABLE t1} 1 0 0 {USE TEMP B-TREE FOR ORDER BY} | | | | | | | | 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 | 0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (UNION ALL)} } do_eqp_test 4.2.3 { SELECT * FROM t1 UNION SELECT * FROM t2 ORDER BY 1 } { 1 0 0 {SCAN TABLE t1} 1 0 0 {USE TEMP B-TREE FOR ORDER BY} 2 0 0 {SCAN TABLE t2 USING INDEX t2i1} 2 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY} 0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (UNION)} } do_eqp_test 4.2.4 { SELECT * FROM t1 INTERSECT SELECT * FROM t2 ORDER BY 1 } { 1 0 0 {SCAN TABLE t1} 1 0 0 {USE TEMP B-TREE FOR ORDER BY} 2 0 0 {SCAN TABLE t2 USING INDEX t2i1} 2 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY} 0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (INTERSECT)} } do_eqp_test 4.2.5 { SELECT * FROM t1 EXCEPT SELECT * FROM t2 ORDER BY 1 } { 1 0 0 {SCAN TABLE t1} 1 0 0 {USE TEMP B-TREE FOR ORDER BY} 2 0 0 {SCAN TABLE t2 USING INDEX t2i1} 2 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY} 0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (EXCEPT)} } do_eqp_test 4.3.1 { SELECT x FROM t1 UNION SELECT x FROM t2 } { 1 0 0 {SCAN TABLE t1} |
︙ | ︙ |
Changes to test/index6.test.
︙ | ︙ | |||
141 142 143 144 145 146 147 | # Queries use partial indices as appropriate times. # do_test index6-2.1 { execsql { CREATE TABLE t2(a,b); INSERT INTO t2(a,b) SELECT value, value FROM nums WHERE value<1000; | | | > | 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 | # Queries use partial indices as appropriate times. # do_test index6-2.1 { execsql { CREATE TABLE t2(a,b); INSERT INTO t2(a,b) SELECT value, value FROM nums WHERE value<1000; UPDATE t2 SET a=NULL WHERE b%2==0; CREATE INDEX t2a1 ON t2(a) WHERE a IS NOT NULL; SELECT count(*) FROM t2 WHERE a IS NOT NULL; } } {500} do_test index6-2.2 { execsql { EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE a=5; } } {/.* TABLE t2 USING INDEX t2a1 .*/} ifcapable stat4||stat3 { execsql ANALYZE do_test index6-2.3stat4 { execsql { EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE a IS NOT NULL; } } {/.* TABLE t2 USING INDEX t2a1 .*/} } else { |
︙ | ︙ |
Changes to test/orderby5.test.
︙ | ︙ | |||
76 77 78 79 80 81 82 83 84 | INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9'); INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5'); ANALYZE sqlite_master; EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c; } {~/B-TREE/} do_execsql_test 2.1b { EXPLAIN QUERY PLAN | > | < | 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | INSERT INTO sqlite_stat1 VALUES('t1','t1bc','1000000 10 9'); INSERT INTO sqlite_stat1 VALUES('t2','t2bc','100 10 5'); ANALYZE sqlite_master; EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE a=0 ORDER BY a, b, c; } {~/B-TREE/} do_execsql_test 2.1b { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE likelihood(a=0, 0.05) ORDER BY a, b, c; } {/B-TREE/} do_execsql_test 2.2 { EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE +a=0 ORDER BY a, b, c; } {/B-TREE/} do_execsql_test 2.3 { EXPLAIN QUERY PLAN |
︙ | ︙ |
Added test/orderby7.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | # 2014-04-25 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing ORDER BY optimizations on joins # that involve virtual tables. # set testdir [file dirname $argv0] source $testdir/tester.tcl set ::testprefix orderby7 ifcapable !fts3 { finish_test return } do_execsql_test 1.0 { CREATE VIRTUAL TABLE fts USING fts3(content TEXT); INSERT INTO fts(rowid,content) VALUES(1,'this is a test of the fts3 virtual'), (2,'table used as part of a join together'), (3,'with the DISTINCT keyword. There was'), (4,'a bug at one time (2013-06 through 2014-04)'), (5,'that prevented this from working correctly.'), (11,'a row that occurs twice'), (12,'a row that occurs twice'); CREATE TABLE t1(x TEXT PRIMARY KEY, y); INSERT OR IGNORE INTO t1 SELECT content, rowid+100 FROM fts; } {} do_execsql_test 1.1 { SELECT DISTINCT fts.rowid, t1.y FROM fts, t1 WHERE fts MATCH 'that twice' AND content=x ORDER BY y; } {11 111 12 111} do_execsql_test 1.2 { SELECT DISTINCT fts.rowid, t1.x FROM fts, t1 WHERE fts MATCH 'that twice' AND content=x ORDER BY 1; } {11 {a row that occurs twice} 12 {a row that occurs twice}} do_execsql_test 1.3 { SELECT DISTINCT t1.x FROM fts, t1 WHERE fts MATCH 'that twice' AND content=x ORDER BY 1; } {{a row that occurs twice}} do_execsql_test 1.4 { SELECT t1.x FROM fts, t1 WHERE fts MATCH 'that twice' AND content=x ORDER BY 1; } {{a row that occurs twice} {a row that occurs twice}} do_execsql_test 1.5 { SELECT DISTINCT t1.x FROM fts, t1 WHERE fts MATCH 'that twice' AND content=x; } {{a row that occurs twice}} do_execsql_test 1.6 { SELECT t1.x FROM fts, t1 WHERE fts MATCH 'that twice' AND content=x; } {{a row that occurs twice} {a row that occurs twice}} do_execsql_test 2.1 { SELECT DISTINCT t1.x FROM fts, t1 WHERE fts.rowid=11 AND content=x ORDER BY fts.rowid; } {{a row that occurs twice}} do_execsql_test 2.2 { SELECT DISTINCT t1.* FROM fts, t1 WHERE fts.rowid=11 AND content=x ORDER BY fts.rowid; } {{a row that occurs twice} 111} do_execsql_test 2.3 { SELECT DISTINCT t1.* FROM fts, t1 WHERE fts.rowid=11 AND content=x ORDER BY t1.y } {{a row that occurs twice} 111} finish_test |
Changes to test/selectA.test.
︙ | ︙ | |||
17 18 19 20 21 22 23 24 25 26 27 28 29 30 | # explicit sort order and explicit collating secquites) and # with and without optional LIMIT and OFFSET clauses. # # $Id: selectA.test,v 1.6 2008/08/21 14:24:29 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl ifcapable !compound { finish_test return } do_test selectA-1.0 { | > | 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | # explicit sort order and explicit collating secquites) and # with and without optional LIMIT and OFFSET clauses. # # $Id: selectA.test,v 1.6 2008/08/21 14:24:29 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix selectA ifcapable !compound { finish_test return } do_test selectA-1.0 { |
︙ | ︙ | |||
1305 1306 1307 1308 1309 1310 1311 1312 1313 | UNION SELECT a,b,c FROM t3 ORDER BY y COLLATE NOCASE DESC,x,z))) UNION ALL SELECT n || '+' FROM xyz WHERE length(n)<5 ) SELECT n FROM xyz ORDER BY +n; } {MAD MAD+ MAD++} finish_test | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 | UNION SELECT a,b,c FROM t3 ORDER BY y COLLATE NOCASE DESC,x,z))) UNION ALL SELECT n || '+' FROM xyz WHERE length(n)<5 ) SELECT n FROM xyz ORDER BY +n; } {MAD MAD+ MAD++} #------------------------------------------------------------------------- # At one point the following code exposed a temp register reuse problem. # proc f {args} { return 1 } db func f f do_execsql_test 4.1.1 { CREATE TABLE t4(a, b); CREATE TABLE t5(c, d); INSERT INTO t5 VALUES(1, 'x'); INSERT INTO t5 VALUES(2, 'x'); INSERT INTO t4 VALUES(3, 'x'); INSERT INTO t4 VALUES(4, 'x'); CREATE INDEX i1 ON t4(a); CREATE INDEX i2 ON t5(c); } do_eqp_test 4.1.2 { SELECT c, d FROM t5 UNION ALL SELECT a, b FROM t4 WHERE f()==f() ORDER BY 1,2 } { 1 0 0 {SCAN TABLE t5 USING INDEX i2} 1 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY} 2 0 0 {SCAN TABLE t4 USING INDEX i1} 2 0 0 {USE TEMP B-TREE FOR RIGHT PART OF ORDER BY} 0 0 0 {COMPOUND SUBQUERIES 1 AND 2 (UNION ALL)} } do_execsql_test 4.1.3 { SELECT c, d FROM t5 UNION ALL SELECT a, b FROM t4 WHERE f()==f() ORDER BY 1,2 } { 1 x 2 x 3 x 4 x } do_execsql_test 4.2.1 { CREATE TABLE t6(a, b); CREATE TABLE t7(c, d); INSERT INTO t7 VALUES(2, 9); INSERT INTO t6 VALUES(3, 0); INSERT INTO t6 VALUES(4, 1); INSERT INTO t7 VALUES(5, 6); INSERT INTO t6 VALUES(6, 0); INSERT INTO t7 VALUES(7, 6); CREATE INDEX i6 ON t6(a); CREATE INDEX i7 ON t7(c); } do_execsql_test 4.2.2 { SELECT c, f(d,c,d,c,d) FROM t7 UNION ALL SELECT a, b FROM t6 ORDER BY 1,2 } {/2 . 3 . 4 . 5 . 6 . 7 ./} finish_test |
Added test/show_speedtest1_rtree.tcl.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | #!/usr/bin/tclsh # # This script displays the field of rectangles used by --testset rtree # of speedtest1. Run this script as follows: # # rm test.db # ./speedtest1 --testset rtree --size 25 test.db # sqlite3 --separator ' ' test.db 'SELECT * FROM rt1' >data.txt # wish show_speedtest1_rtree.tcl # # The filename "data.txt" is hard coded into this script and so that name # must be used on lines 3 and 4 above. Elsewhere, different filenames can # be used. The --size N parameter can be adjusted as desired. # package require Tk set f [open data.txt rb] set data [read $f] close $f canvas .c frame .b button .b.b1 -text X-Y -command refill-xy button .b.b2 -text X-Z -command refill-xz button .b.b3 -text Y-Z -command refill-yz pack .b.b1 .b.b2 .b.b3 -side left pack .c -side top -fill both -expand 1 pack .b -side top proc resize_canvas_to_fit {} { foreach {x0 y0 x1 y1} [.c bbox all] break set w [expr {$x1-$x0}] set h [expr {$y1-$y0}] .c config -width $w -height $h } proc refill-xy {} { .c delete all foreach {id x0 x1 y0 y1 z0 z1} $::data { .c create rectangle $x0 $y0 $x1 $y1 } .c scale all 0 0 0.05 0.05 resize_canvas_to_fit } proc refill-xz {} { .c delete all foreach {id x0 x1 y0 y1 z0 z1} $::data { .c create rectangle $x0 $z0 $x1 $z1 } .c scale all 0 0 0.05 0.05 resize_canvas_to_fit } proc refill-yz {} { .c delete all foreach {id x0 x1 y0 y1 z0 z1} $::data { .c create rectangle $y0 $z0 $y1 $z1 } .c scale all 0 0 0.05 0.05 resize_canvas_to_fit } refill-xy |
Changes to test/skipscan2.test.
︙ | ︙ | |||
70 71 72 73 74 75 76 77 78 79 80 81 82 83 | # do_execsql_test skipscan2-1.4 { ANALYZE; -- We do not have enough people above to actually force the use -- of a skip-scan. So make a manual adjustment to the stat1 table -- to make it seem like there are many more. UPDATE sqlite_stat1 SET stat='10000 5000 20' WHERE idx='people_idx1'; ANALYZE sqlite_master; } db cache flush do_execsql_test skipscan2-1.5 { SELECT name FROM people WHERE height>=180 ORDER BY +name; } {David Jack Patrick Quiana Xavier} do_execsql_test skipscan2-1.5eqp { | > | 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | # do_execsql_test skipscan2-1.4 { ANALYZE; -- We do not have enough people above to actually force the use -- of a skip-scan. So make a manual adjustment to the stat1 table -- to make it seem like there are many more. UPDATE sqlite_stat1 SET stat='10000 5000 20' WHERE idx='people_idx1'; UPDATE sqlite_stat1 SET stat='10000 1' WHERE idx='sqlite_autoindex_people_1'; ANALYZE sqlite_master; } db cache flush do_execsql_test skipscan2-1.5 { SELECT name FROM people WHERE height>=180 ORDER BY +name; } {David Jack Patrick Quiana Xavier} do_execsql_test skipscan2-1.5eqp { |
︙ | ︙ |
Changes to test/speedtest1.c.
︙ | ︙ | |||
25 26 27 28 29 30 31 32 33 34 35 36 37 38 | " --sqlonly No-op. Only show the SQL that would have been run.\n" " --size N Relative test size. Default=100\n" " --stats Show statistics at the end\n" " --testset T Run test-set T\n" " --trace Turn on SQL tracing\n" " --utf16be Set text encoding to UTF-16BE\n" " --utf16le Set text encoding to UTF-16LE\n" " --without-rowid Use WITHOUT ROWID where appropriate\n" ; #include "sqlite3.h" #include <assert.h> #include <stdio.h> | > | 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | " --sqlonly No-op. Only show the SQL that would have been run.\n" " --size N Relative test size. Default=100\n" " --stats Show statistics at the end\n" " --testset T Run test-set T\n" " --trace Turn on SQL tracing\n" " --utf16be Set text encoding to UTF-16BE\n" " --utf16le Set text encoding to UTF-16LE\n" " --verify Run additional verification steps.\n" " --without-rowid Use WITHOUT ROWID where appropriate\n" ; #include "sqlite3.h" #include <assert.h> #include <stdio.h> |
︙ | ︙ | |||
47 48 49 50 51 52 53 54 55 56 57 58 59 60 | sqlite3_stmt *pStmt; /* Current SQL statement */ sqlite3_int64 iStart; /* Start-time for the current test */ sqlite3_int64 iTotal; /* Total time */ int bWithoutRowid; /* True for --without-rowid */ int bReprepare; /* True to reprepare the SQL on each rerun */ int bSqlOnly; /* True to print the SQL once only */ int bExplain; /* Print SQL with EXPLAIN prefix */ int szTest; /* Scale factor for test iterations */ const char *zWR; /* Might be WITHOUT ROWID */ const char *zNN; /* Might be NOT NULL */ const char *zPK; /* Might be UNIQUE or PRIMARY KEY */ unsigned int x, y; /* Pseudo-random number generator state */ int nResult; /* Size of the current result */ char zResult[3000]; /* Text of the current result */ | > | 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | sqlite3_stmt *pStmt; /* Current SQL statement */ sqlite3_int64 iStart; /* Start-time for the current test */ sqlite3_int64 iTotal; /* Total time */ int bWithoutRowid; /* True for --without-rowid */ int bReprepare; /* True to reprepare the SQL on each rerun */ int bSqlOnly; /* True to print the SQL once only */ int bExplain; /* Print SQL with EXPLAIN prefix */ int bVerify; /* Try to verify that results are correct */ int szTest; /* Scale factor for test iterations */ const char *zWR; /* Might be WITHOUT ROWID */ const char *zNN; /* Might be NOT NULL */ const char *zPK; /* Might be UNIQUE or PRIMARY KEY */ unsigned int x, y; /* Pseudo-random number generator state */ int nResult; /* Size of the current result */ char zResult[3000]; /* Text of the current result */ |
︙ | ︙ | |||
926 927 928 929 930 931 932 933 934 935 936 937 938 939 | ");", nElem, nElem ); speedtest1_run(); speedtest1_end_test(); } /* ** A testset used for debugging speedtest1 itself. */ void testset_debug1(void){ unsigned i, n; unsigned x1, x2; | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 | ");", nElem, nElem ); speedtest1_run(); speedtest1_end_test(); } /* Generate two numbers between 1 and mx. The first number is less than ** the second. Usually the numbers are near each other but can sometimes ** be far apart. */ static void twoCoords( int p1, int p2, /* Parameters adjusting sizes */ unsigned mx, /* Range of 1..mx */ unsigned *pX0, unsigned *pX1 /* OUT: write results here */ ){ unsigned d, x0, x1, span; span = mx/100 + 1; if( speedtest1_random()%3==0 ) span *= p1; if( speedtest1_random()%p2==0 ) span = mx/2; d = speedtest1_random()%span + 1; x0 = speedtest1_random()%(mx-d) + 1; x1 = x0 + d; *pX0 = x0; *pX1 = x1; } /* The following routine is an R-Tree geometry callback. It returns ** true if the object overlaps a slice on the Y coordinate between the ** two values given as arguments. In other words ** ** SELECT count(*) FROM rt1 WHERE id MATCH xslice(10,20); ** ** Is the same as saying: ** ** SELECT count(*) FROM rt1 WHERE y1>=10 AND y0<=20; */ static int xsliceGeometryCallback( sqlite3_rtree_geometry *p, int nCoord, double *aCoord, int *pRes ){ *pRes = aCoord[3]>=p->aParam[0] && aCoord[2]<=p->aParam[1]; return SQLITE_OK; } /* ** A testset for the R-Tree virtual table */ void testset_rtree(int p1, int p2){ unsigned i, n; unsigned mxCoord; unsigned x0, x1, y0, y1, z0, z1; unsigned iStep; int *aCheck = sqlite3_malloc( sizeof(int)*g.szTest*100 ); mxCoord = 15000; n = g.szTest*100; speedtest1_begin_test(100, "%d INSERTs into an r-tree", n); speedtest1_exec("BEGIN"); speedtest1_exec("CREATE VIRTUAL TABLE rt1 USING rtree(id,x0,x1,y0,y1,z0,z1)"); speedtest1_prepare("INSERT INTO rt1(id,x0,x1,y0,y1,z0,z1)" "VALUES(?1,?2,?3,?4,?5,?6,?7)"); for(i=1; i<=n; i++){ twoCoords(p1, p2, mxCoord, &x0, &x1); twoCoords(p1, p2, mxCoord, &y0, &y1); twoCoords(p1, p2, mxCoord, &z0, &z1); sqlite3_bind_int(g.pStmt, 1, i); sqlite3_bind_int(g.pStmt, 2, x0); sqlite3_bind_int(g.pStmt, 3, x1); sqlite3_bind_int(g.pStmt, 4, y0); sqlite3_bind_int(g.pStmt, 5, y1); sqlite3_bind_int(g.pStmt, 6, z0); sqlite3_bind_int(g.pStmt, 7, z1); speedtest1_run(); } speedtest1_exec("COMMIT"); speedtest1_end_test(); speedtest1_begin_test(101, "Copy from rtree to a regular table"); speedtest1_exec("CREATE TABLE t1(id INTEGER PRIMARY KEY,x0,x1,y0,y1,z0,z1)"); speedtest1_exec("INSERT INTO t1 SELECT * FROM rt1"); speedtest1_end_test(); n = g.szTest*20; speedtest1_begin_test(110, "%d one-dimensional intersect slice queries", n); speedtest1_prepare("SELECT count(*) FROM rt1 WHERE x0>=?1 AND x1<=?2"); iStep = mxCoord/n; for(i=0; i<n; i++){ sqlite3_bind_int(g.pStmt, 1, i*iStep); sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep); speedtest1_run(); aCheck[i] = atoi(g.zResult); } speedtest1_end_test(); if( g.bVerify ){ n = g.szTest*20; speedtest1_begin_test(111, "Verify result from 1-D intersect slice queries"); speedtest1_prepare("SELECT count(*) FROM t1 WHERE x0>=?1 AND x1<=?2"); iStep = mxCoord/n; for(i=0; i<n; i++){ sqlite3_bind_int(g.pStmt, 1, i*iStep); sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep); speedtest1_run(); if( aCheck[i]!=atoi(g.zResult) ){ fatal_error("Count disagree step %d: %d..%d. %d vs %d", i, i*iStep, (i+1)*iStep, aCheck[i], atoi(g.zResult)); } } speedtest1_end_test(); } n = g.szTest*20; speedtest1_begin_test(120, "%d one-dimensional overlap slice queries", n); speedtest1_prepare("SELECT count(*) FROM rt1 WHERE y1>=?1 AND y0<=?2"); iStep = mxCoord/n; for(i=0; i<n; i++){ sqlite3_bind_int(g.pStmt, 1, i*iStep); sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep); speedtest1_run(); aCheck[i] = atoi(g.zResult); } speedtest1_end_test(); if( g.bVerify ){ n = g.szTest*20; speedtest1_begin_test(121, "Verify result from 1-D overlap slice queries"); speedtest1_prepare("SELECT count(*) FROM t1 WHERE y1>=?1 AND y0<=?2"); iStep = mxCoord/n; for(i=0; i<n; i++){ sqlite3_bind_int(g.pStmt, 1, i*iStep); sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep); speedtest1_run(); if( aCheck[i]!=atoi(g.zResult) ){ fatal_error("Count disagree step %d: %d..%d. %d vs %d", i, i*iStep, (i+1)*iStep, aCheck[i], atoi(g.zResult)); } } speedtest1_end_test(); } n = g.szTest*20; speedtest1_begin_test(125, "%d custom geometry callback queries", n); sqlite3_rtree_geometry_callback(g.db, "xslice", xsliceGeometryCallback, 0); speedtest1_prepare("SELECT count(*) FROM rt1 WHERE id MATCH xslice(?1,?2)"); iStep = mxCoord/n; for(i=0; i<n; i++){ sqlite3_bind_int(g.pStmt, 1, i*iStep); sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep); speedtest1_run(); if( aCheck[i]!=atoi(g.zResult) ){ fatal_error("Count disagree step %d: %d..%d. %d vs %d", i, i*iStep, (i+1)*iStep, aCheck[i], atoi(g.zResult)); } } speedtest1_end_test(); n = g.szTest*80; speedtest1_begin_test(130, "%d three-dimensional intersect box queries", n); speedtest1_prepare("SELECT count(*) FROM rt1 WHERE x1>=?1 AND x0<=?2" " AND y1>=?1 AND y0<=?2 AND z1>=?1 AND z0<=?2"); iStep = mxCoord/n; for(i=0; i<n; i++){ sqlite3_bind_int(g.pStmt, 1, i*iStep); sqlite3_bind_int(g.pStmt, 2, (i+1)*iStep); speedtest1_run(); aCheck[i] = atoi(g.zResult); } speedtest1_end_test(); n = g.szTest*100; speedtest1_begin_test(140, "%d rowid queries", n); speedtest1_prepare("SELECT * FROM rt1 WHERE id=?1"); for(i=1; i<=n; i++){ sqlite3_bind_int(g.pStmt, 1, i); speedtest1_run(); } speedtest1_end_test(); } /* ** A testset used for debugging speedtest1 itself. */ void testset_debug1(void){ unsigned i, n; unsigned x1, x2; |
︙ | ︙ | |||
1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 | zTSet = argv[++i]; }else if( strcmp(z,"trace")==0 ){ doTrace = 1; }else if( strcmp(z,"utf16le")==0 ){ zEncoding = "utf16le"; }else if( strcmp(z,"utf16be")==0 ){ zEncoding = "utf16be"; }else if( strcmp(z,"without-rowid")==0 ){ g.zWR = "WITHOUT ROWID"; g.zPK = "PRIMARY KEY"; }else if( strcmp(z, "help")==0 || strcmp(z,"?")==0 ){ printf(zHelp, argv[0]); exit(0); }else{ | > > | 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 | zTSet = argv[++i]; }else if( strcmp(z,"trace")==0 ){ doTrace = 1; }else if( strcmp(z,"utf16le")==0 ){ zEncoding = "utf16le"; }else if( strcmp(z,"utf16be")==0 ){ zEncoding = "utf16be"; }else if( strcmp(z,"verify")==0 ){ g.bVerify = 1; }else if( strcmp(z,"without-rowid")==0 ){ g.zWR = "WITHOUT ROWID"; g.zPK = "PRIMARY KEY"; }else if( strcmp(z, "help")==0 || strcmp(z,"?")==0 ){ printf(zHelp, argv[0]); exit(0); }else{ |
︙ | ︙ | |||
1137 1138 1139 1140 1141 1142 1143 1144 | if( g.bExplain ) printf(".explain\n.echo on\n"); if( strcmp(zTSet,"main")==0 ){ testset_main(); }else if( strcmp(zTSet,"debug1")==0 ){ testset_debug1(); }else if( strcmp(zTSet,"cte")==0 ){ testset_cte(); }else{ | > > | > | 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 | if( g.bExplain ) printf(".explain\n.echo on\n"); if( strcmp(zTSet,"main")==0 ){ testset_main(); }else if( strcmp(zTSet,"debug1")==0 ){ testset_debug1(); }else if( strcmp(zTSet,"cte")==0 ){ testset_cte(); }else if( strcmp(zTSet,"rtree")==0 ){ testset_rtree(6, 147); }else{ fatal_error("unknown testset: \"%s\"\nChoices: main debug1 cte rtree\n", zTSet); } speedtest1_final(); /* Database connection statistics printed after both prepared statements ** have been finalized */ #if SQLITE_VERSION_NUMBER>=3007009 if( showStats ){ |
︙ | ︙ |
Added test/tkt-f67b41381a.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | # 2014 April 26 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # Test that ticket f67b41381a has been resolved. # set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix tkt-f67b41381a do_execsql_test 1.0 { CREATE TABLE t1(a); INSERT INTO t1 VALUES(1); ALTER TABLE t1 ADD COLUMN b DEFAULT 2; CREATE TABLE t2(a, b); INSERT INTO t2 SELECT * FROM t1; SELECT * FROM t2; } {1 2} db cache size 0 foreach {tn tbls xfer} { 1 { CREATE TABLE t1(a, b); CREATE TABLE t2(a, b) } 1 2 { CREATE TABLE t1(a, b DEFAULT 'x'); CREATE TABLE t2(a, b) } 0 3 { CREATE TABLE t1(a, b DEFAULT 'x'); CREATE TABLE t2(a, b DEFAULT 'x') } 1 4 { CREATE TABLE t1(a, b DEFAULT NULL); CREATE TABLE t2(a, b) } 0 5 { CREATE TABLE t1(a DEFAULT 2, b); CREATE TABLE t2(a DEFAULT 1, b) } 1 6 { CREATE TABLE t1(a DEFAULT 1, b); CREATE TABLE t2(a DEFAULT 1, b) } 1 7 { CREATE TABLE t1(a DEFAULT 1, b DEFAULT 1); CREATE TABLE t2(a DEFAULT 3, b DEFAULT 1) } 1 8 { CREATE TABLE t1(a DEFAULT 1, b DEFAULT 1); CREATE TABLE t2(a DEFAULT 3, b DEFAULT 3) } 0 } { execsql { DROP TABLE t1; DROP TABLE t2 } execsql $tbls set res 1 db eval { EXPLAIN INSERT INTO t1 SELECT * FROM t2 } { if {$opcode == "Column"} { set res 0 } } do_test 2.$tn [list set res] $xfer } finish_test |
Changes to test/unordered.test.
︙ | ︙ | |||
38 39 40 41 42 43 44 | } db close sqlite3 db test.db foreach {tn sql r(ordered) r(unordered)} { 1 "SELECT * FROM t1 ORDER BY a" {0 0 0 {SCAN TABLE t1 USING INDEX i1}} {0 0 0 {SCAN TABLE t1} 0 0 0 {USE TEMP B-TREE FOR ORDER BY}} | | | 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | } db close sqlite3 db test.db foreach {tn sql r(ordered) r(unordered)} { 1 "SELECT * FROM t1 ORDER BY a" {0 0 0 {SCAN TABLE t1 USING INDEX i1}} {0 0 0 {SCAN TABLE t1} 0 0 0 {USE TEMP B-TREE FOR ORDER BY}} 2 "SELECT * FROM t1 WHERE a > 100" {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?)}} {0 0 0 {SCAN TABLE t1}} 3 "SELECT * FROM t1 WHERE a = ? ORDER BY rowid" {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)}} {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)} 0 0 0 {USE TEMP B-TREE FOR ORDER BY}} 4 "SELECT max(a) FROM t1" |
︙ | ︙ |
Changes to test/wal2.test.
︙ | ︙ | |||
807 808 809 810 811 812 813 | CREATE TABLE t1(a, b); } file size test.db } {4096} do_test wal2-7.1.2 { forcecopy test.db test2.db forcecopy test.db-wal test2.db-wal | > > > > > > | | 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 | CREATE TABLE t1(a, b); } file size test.db } {4096} do_test wal2-7.1.2 { forcecopy test.db test2.db forcecopy test.db-wal test2.db-wal # The first 32 bytes of the WAL file contain the WAL header. Offset 48 # is the first byte of the checksum for the first frame in the WAL. # The following three lines replaces the contents of that byte with # a different value. set newval FF if {$newval == [hexio_read test2.db-wal 48 1]} { set newval 00 } hexio_write test2.db-wal 48 $newval } {1} do_test wal2-7.1.3 { sqlite3 db2 test2.db execsql { PRAGMA wal_checkpoint } db2 execsql { SELECT * FROM sqlite_master } db2 } {} db close |
︙ | ︙ |
Changes to test/where3.test.
︙ | ︙ | |||
227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 | # the planner into use a table for the outer loop that might be indexable # if held until an inner loop. # do_execsql_test where3-3.0 { CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c); CREATE INDEX t301c ON t301(c); INSERT INTO t301 VALUES(1,2,3); CREATE TABLE t302(x, y); INSERT INTO t302 VALUES(4,5); ANALYZE; explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y; } { 0 0 0 {SCAN TABLE t302} 0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)} } do_execsql_test where3-3.1 { explain query plan SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y; } { 0 0 1 {SCAN TABLE t302} 0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)} } do_execsql_test where3-3.2 { SELECT * FROM t301 WHERE c=3 AND a IS NULL; } {} do_execsql_test where3-3.3 { SELECT * FROM t301 WHERE c=3 AND a IS NOT NULL; | > | | 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 | # the planner into use a table for the outer loop that might be indexable # if held until an inner loop. # do_execsql_test where3-3.0 { CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c); CREATE INDEX t301c ON t301(c); INSERT INTO t301 VALUES(1,2,3); INSERT INTO t301 VALUES(2,2,3); CREATE TABLE t302(x, y); INSERT INTO t302 VALUES(4,5); ANALYZE; explain query plan SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y; } { 0 0 0 {SCAN TABLE t302} 0 1 1 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)} } do_execsql_test where3-3.1 { explain query plan SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y; } { 0 0 1 {SCAN TABLE t302} 0 1 0 {SEARCH TABLE t301 USING INTEGER PRIMARY KEY (rowid=?)} } do_execsql_test where3-3.2 { SELECT * FROM t301 WHERE c=3 AND a IS NULL; } {} do_execsql_test where3-3.3 { SELECT * FROM t301 WHERE c=3 AND a IS NOT NULL; } {1 2 3 2 2 3} if 0 { # Query planner no longer does this # Verify that when there are multiple tables in a join which must be # full table scans that the query planner attempts put the table with # the fewest number of output rows as the outer loop. # do_execsql_test where3-4.0 { |
︙ | ︙ |
Changes to test/whereG.test.
︙ | ︙ | |||
10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #*********************************************************************** # # Test cases for query planning decisions and the unlikely() and # likelihood() functions. set testdir [file dirname $argv0] source $testdir/tester.tcl do_execsql_test whereG-1.0 { CREATE TABLE composer( cid INTEGER PRIMARY KEY, cname TEXT ); CREATE TABLE album( | > | 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #*********************************************************************** # # Test cases for query planning decisions and the unlikely() and # likelihood() functions. set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix whereG do_execsql_test whereG-1.0 { CREATE TABLE composer( cid INTEGER PRIMARY KEY, cname TEXT ); CREATE TABLE album( |
︙ | ︙ | |||
175 176 177 178 179 180 181 | INSERT INTO t4 VALUES('right'),('wrong'); SELECT DISTINCT x FROM (SELECT x FROM t4 GROUP BY x) WHERE x='right' ORDER BY x; } {right} | > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 | INSERT INTO t4 VALUES('right'),('wrong'); SELECT DISTINCT x FROM (SELECT x FROM t4 GROUP BY x) WHERE x='right' ORDER BY x; } {right} #------------------------------------------------------------------------- # Test that likelihood() specifications on indexed terms are taken into # account by various forms of loops. # # 5.1.*: open ended range scans # 5.2.*: skip-scans # reset_db do_execsql_test 5.1 { CREATE TABLE t1(a, b, c); CREATE INDEX i1 ON t1(a, b); } do_eqp_test 5.1.2 { SELECT * FROM t1 WHERE a>? } {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a>?)}} do_eqp_test 5.1.3 { SELECT * FROM t1 WHERE likelihood(a>?, 0.9) } {0 0 0 {SCAN TABLE t1}} do_test 5.2 { for {set i 0} {$i < 100} {incr i} { execsql { INSERT INTO t1 VALUES('abc', $i, $i); } } execsql { INSERT INTO t1 SELECT 'def', b, c FROM t1; } execsql { ANALYZE } } {} do_eqp_test 5.2.2 { SELECT * FROM t1 WHERE likelihood(b>?, 0.01) } {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (ANY(a) AND b>?)}} do_eqp_test 5.2.3 { SELECT * FROM t1 WHERE likelihood(b>?, 0.9) } {0 0 0 {SCAN TABLE t1}} do_eqp_test 5.3.1 { SELECT * FROM t1 WHERE a=? } {0 0 0 {SEARCH TABLE t1 USING INDEX i1 (a=?)}} do_eqp_test 5.3.2 { SELECT * FROM t1 WHERE likelihood(a=?, 0.9) } {0 0 0 {SCAN TABLE t1}} finish_test |
Changes to tool/logest.c.
︙ | ︙ | |||
79 80 81 82 83 84 85 | return (n+8)>>(3-x); } static LogEst logEstFromDouble(double x){ sqlite3_uint64 a; LogEst e; assert( sizeof(x)==8 && sizeof(a)==8 ); if( x<=0.0 ) return -32768; | | > | 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | return (n+8)>>(3-x); } static LogEst logEstFromDouble(double x){ sqlite3_uint64 a; LogEst e; assert( sizeof(x)==8 && sizeof(a)==8 ); if( x<=0.0 ) return -32768; if( x<0.01 ) return -logEstFromDouble(1.0/x); if( x<1.0 ) return logEstFromDouble(100.0*x) - 66; if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100; if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x); memcpy(&a, &x, 8); e = (a>>52) - 1022; return e*10; } |
︙ | ︙ | |||
152 153 154 155 156 157 158 | }else if( isFloat(z) && z[0]!='-' ){ a[n++] = logEstFromDouble(atof(z)); }else{ showHelp(argv[0]); } } for(i=n-1; i>=0; i--){ | | > > | 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | }else if( isFloat(z) && z[0]!='-' ){ a[n++] = logEstFromDouble(atof(z)); }else{ showHelp(argv[0]); } } for(i=n-1; i>=0; i--){ if( a[i]<-40 ){ printf("%5d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i])); }else if( a[i]<10 ){ printf("%5d (%f)\n", a[i], logEstToInt(a[i]+100)/1024.0); }else{ sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024; printf("%5d (%lld.%02lld)\n", a[i], x/100, x%100); } } return 0; } |