Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch row-size-est Excluding Merge-Ins
This is equivalent to a diff from de78250ad2 to e97d7d3044
2013-10-10
| ||
12:38 | Estimate row sizes for tables and indices and use those estimates during query planning. Enhance the index_info pragma to show the estimated row sizes and to show the estimated row size for the main table as well. Allow an alternative row size estimate to be specified in the sqlite_stat1 table. (check-in: d27b88b8c2 user: drh tags: trunk) | |
2013-10-09
| ||
19:07 | Make sure the correct printf format is used for type tRowcnt regardless of whether 32-bit or 64-bit row counts are specified at compile-time. (Closed-Leaf check-in: e97d7d3044 user: drh tags: row-size-est) | |
2013-10-08
| ||
23:16 | Move a conditional inside of an #ifdef in order to make all branches reachable regardless of compile-time options used. (check-in: f7cc30d45b user: drh tags: row-size-est) | |
2013-10-05
| ||
18:16 | Begin an experimental refactoring to estimate the average number of bytes in table and index rows and to use that information in query planner. Begin by renaming WhereCost to LogEst and making that type and its conversion routines available outside of where.c. (check-in: 66c4a251d6 user: drh tags: row-size-est) | |
02:56 | In the index_list pragma, make sure the "r" column is the same on output as it was on input in the sqlite_stat1 table. (Closed-Leaf check-in: de78250ad2 user: drh tags: index-scan-rate) | |
2013-10-04
| ||
20:39 | Merge trunk changes. (check-in: c6ac80ed8d user: drh tags: index-scan-rate) | |
Changes to src/analyze.c.
︙ | ︙ | |||
739 740 741 742 743 744 745 | char *zRet = sqlite3MallocZero(p->nCol * 25); if( zRet==0 ){ sqlite3_result_error_nomem(context); return; } | | | | | | 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 | char *zRet = sqlite3MallocZero(p->nCol * 25); if( zRet==0 ){ sqlite3_result_error_nomem(context); return; } sqlite3_snprintf(24, zRet, "%llu", (u64)p->nRow); z = zRet + sqlite3Strlen30(zRet); for(i=0; i<(p->nCol-1); i++){ u64 nDistinct = p->current.anDLt[i] + 1; u64 iVal = (p->nRow + nDistinct - 1) / nDistinct; sqlite3_snprintf(24, z, " %llu", iVal); z += sqlite3Strlen30(z); assert( p->current.anEq[i] ); } assert( z[0]=='\0' && z>zRet ); sqlite3_result_text(context, zRet, -1, sqlite3_free); } |
︙ | ︙ | |||
785 786 787 788 789 790 791 | char *zRet = sqlite3MallocZero(p->nCol * 25); if( zRet==0 ){ sqlite3_result_error_nomem(context); }else{ int i; char *z = zRet; for(i=0; i<p->nCol; i++){ | | | 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 | char *zRet = sqlite3MallocZero(p->nCol * 25); if( zRet==0 ){ sqlite3_result_error_nomem(context); }else{ int i; char *z = zRet; for(i=0; i<p->nCol; i++){ sqlite3_snprintf(24, z, "%llu ", (u64)aCnt[i]); z += sqlite3Strlen30(z); } assert( z[0]=='\0' && z>zRet ); z[-1] = '\0'; sqlite3_result_text(context, zRet, -1, sqlite3_free); } } |
︙ | ︙ | |||
1270 1271 1272 1273 1274 1275 1276 | while( (c=z[0])>='0' && c<='9' ){ v = v*10 + c - '0'; z++; } aOut[i] = v; if( *z==' ' ) z++; } | > > > | > > | | < < < < < < < | | 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 | while( (c=z[0])>='0' && c<='9' ){ v = v*10 + c - '0'; z++; } aOut[i] = v; if( *z==' ' ) z++; } #ifndef SQLITE_ENABLE_STAT3_OR_STAT4 assert( pIndex!=0 ); #else if( pIndex ) #endif { if( strcmp(z, "unordered")==0 ){ pIndex->bUnordered = 1; }else if( sqlite3_strglob("sz=[0-9]*", z)==0 ){ int v32 = 0; sqlite3GetInt32(z+3, &v32); pIndex->szIdxRow = sqlite3LogEst(v32); } } } /* ** This callback is invoked once for each index when reading the ** sqlite_stat1 table. |
︙ | ︙ | |||
1326 1327 1328 1329 1330 1331 1332 | } z = argv[2]; if( pIndex ){ decodeIntArray((char*)z, pIndex->nColumn+1, pIndex->aiRowEst, pIndex); if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0]; }else{ | > > | > | 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 | } z = argv[2]; if( pIndex ){ decodeIntArray((char*)z, pIndex->nColumn+1, pIndex->aiRowEst, pIndex); if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0]; }else{ Index fakeIdx; fakeIdx.szIdxRow = pTable->szTabRow; decodeIntArray((char*)z, 1, &pTable->nRowEst, &fakeIdx); pTable->szTabRow = fakeIdx.szIdxRow; } return 0; } /* ** If the Index.aSample variable is not NULL, delete the aSample[] array |
︙ | ︙ |
Changes to src/btree.c.
︙ | ︙ | |||
2504 2505 2506 2507 2508 2509 2510 | pBt->max1bytePayload = 127; }else{ pBt->max1bytePayload = (u8)pBt->maxLocal; } assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) ); pBt->pPage1 = pPage1; pBt->nPage = nPage; | < | 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 | pBt->max1bytePayload = 127; }else{ pBt->max1bytePayload = (u8)pBt->maxLocal; } assert( pBt->maxLeaf + 23 <= MX_CELL_SIZE(pBt) ); pBt->pPage1 = pPage1; pBt->nPage = nPage; return SQLITE_OK; page1_init_failed: releasePage(pPage1); pBt->pPage1 = 0; return rc; } |
︙ | ︙ |
Changes to src/build.c.
︙ | ︙ | |||
875 876 877 878 879 880 881 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; | | | 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; pTable->nRowEst = 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. */ |
︙ | ︙ | |||
1504 1505 1506 1507 1508 1509 1510 | sqlite3_snprintf(n-k, &zStmt[k], "%s", zEnd); return zStmt; } /* ** Estimate the total row width for a table. */ | | | | < < | < | < < | 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 | sqlite3_snprintf(n-k, &zStmt[k], "%s", zEnd); return zStmt; } /* ** Estimate the total row width for a table. */ static void estimateTableWidth(Table *pTab){ unsigned wTable = 0; const Column *pTabCol; int i; for(i=pTab->nCol, pTabCol=pTab->aCol; i>0; i--, pTabCol++){ wTable += pTabCol->szEst; } if( pTab->iPKey<0 ) wTable++; pTab->szTabRow = sqlite3LogEst(wTable*4); } /* ** Estimate the average size of a row for an index. */ static void estimateIndexWidth(Index *pIdx){ unsigned wIndex = 1; int i; const Column *aCol = pIdx->pTable->aCol; for(i=0; i<pIdx->nColumn; i++){ assert( pIdx->aiColumn[i]>=0 && pIdx->aiColumn[i]<pIdx->pTable->nCol ); wIndex += aCol[pIdx->aiColumn[i]].szEst; } pIdx->szIdxRow = sqlite3LogEst(wIndex*4); } /* ** This routine is called to report the final ")" that terminates ** a CREATE TABLE statement. ** ** The table structure that other action routines have been building |
︙ | ︙ | |||
1564 1565 1566 1567 1568 1569 1570 | Token *pEnd, /* The final ')' token in the CREATE TABLE */ Select *pSelect /* Select from a "CREATE ... AS SELECT" */ ){ Table *p; /* The new table */ sqlite3 *db = pParse->db; /* The database connection */ int iDb; /* Database in which the table lives */ Index *pIdx; /* An implied index of the table */ | < | | | | 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 | Token *pEnd, /* The final ')' token in the CREATE TABLE */ Select *pSelect /* Select from a "CREATE ... AS SELECT" */ ){ Table *p; /* The new table */ sqlite3 *db = pParse->db; /* The database connection */ int iDb; /* Database in which the table lives */ Index *pIdx; /* An implied index of the table */ if( (pEnd==0 && pSelect==0) || db->mallocFailed ){ return; } p = pParse->pNewTable; if( p==0 ) return; assert( !db->init.busy || !pSelect ); iDb = sqlite3SchemaToIndex(db, p->pSchema); #ifndef SQLITE_OMIT_CHECK /* Resolve names in all CHECK constraint expressions. */ if( p->pCheck ){ sqlite3ResolveSelfReference(pParse, p, NC_IsCheck, 0, p->pCheck); } #endif /* !defined(SQLITE_OMIT_CHECK) */ /* Estimate the average row size for the table and for all implied indices */ estimateTableWidth(p); for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){ estimateIndexWidth(pIdx); } /* If the db->init.busy is 1 it means we are reading the SQL off the ** "sqlite_master" or "sqlite_temp_master" table on the disk. ** So do not write to the disk again. Extract the root page number ** for the table from the db->init.newTnum field. (The page number ** should have been put there by the sqliteOpenCb routine.) |
︙ | ︙ | |||
2814 2815 2816 2817 2818 2819 2820 | } pIndex->azColl[i] = zColl; requestedSortOrder = pListItem->sortOrder & sortOrderMask; pIndex->aSortOrder[i] = (u8)requestedSortOrder; if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0; } sqlite3DefaultRowEst(pIndex); | | < < | 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 | } pIndex->azColl[i] = zColl; requestedSortOrder = pListItem->sortOrder & sortOrderMask; pIndex->aSortOrder[i] = (u8)requestedSortOrder; if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0; } sqlite3DefaultRowEst(pIndex); if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex); if( pTab==pParse->pNewTable ){ /* This routine has been called to create an automatic index as a ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or ** a PRIMARY KEY or UNIQUE clause following the column definitions. ** i.e. one of: ** |
︙ | ︙ |
Changes to src/pragma.c.
︙ | ︙ | |||
204 205 206 207 208 209 210 211 212 213 214 215 216 217 | /* ePragFlag: */ 0, /* iArg: */ SQLITE_FullFSync }, #if defined(SQLITE_HAS_CODEC) { /* zName: */ "hexkey", /* ePragTyp: */ PragTyp_HEXKEY, /* ePragFlag: */ 0, /* iArg: */ 0 }, #endif #if !defined(SQLITE_OMIT_CHECK) { /* zName: */ "ignore_check_constraints", /* ePragTyp: */ PragTyp_FLAG, /* ePragFlag: */ 0, /* iArg: */ SQLITE_IgnoreChecks }, #endif | > > > > | 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 | /* ePragFlag: */ 0, /* iArg: */ SQLITE_FullFSync }, #if defined(SQLITE_HAS_CODEC) { /* zName: */ "hexkey", /* ePragTyp: */ PragTyp_HEXKEY, /* ePragFlag: */ 0, /* iArg: */ 0 }, { /* zName: */ "hexrekey", /* ePragTyp: */ PragTyp_HEXKEY, /* ePragFlag: */ 0, /* iArg: */ 0 }, #endif #if !defined(SQLITE_OMIT_CHECK) { /* zName: */ "ignore_check_constraints", /* ePragTyp: */ PragTyp_FLAG, /* ePragFlag: */ 0, /* iArg: */ SQLITE_IgnoreChecks }, #endif |
︙ | ︙ | |||
412 413 414 415 416 417 418 | /* iArg: */ 0 }, #endif { /* zName: */ "writable_schema", /* ePragTyp: */ PragTyp_FLAG, /* ePragFlag: */ 0, /* iArg: */ SQLITE_WriteSchema|SQLITE_RecoveryMode }, }; | | | 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 | /* iArg: */ 0 }, #endif { /* zName: */ "writable_schema", /* ePragTyp: */ PragTyp_FLAG, /* ePragFlag: */ 0, /* iArg: */ SQLITE_WriteSchema|SQLITE_RecoveryMode }, }; /* Number of pragmas: 55 on by default, 67 total. */ /* End of the automatically generated pragma table. ***************************************************************************/ /* ** Interpret the given string as a safety level. Return 0 for OFF, ** 1 for ON or NORMAL and 2 for FULL. Return 1 for an empty or ** unrecognized string argument. The FULL option is disallowed |
︙ | ︙ | |||
1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 | } } break; case PragTyp_INDEX_LIST: if( zRight ){ Index *pIdx; Table *pTab; pTab = sqlite3FindTable(db, zRight, zDb); if( pTab ){ v = sqlite3GetVdbe(pParse); | > < < < | | | | | | | > > > > > > | | | | | > | < < < | 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 | } } break; case PragTyp_INDEX_LIST: if( zRight ){ Index *pIdx; Table *pTab; int i; pTab = sqlite3FindTable(db, zRight, zDb); if( pTab ){ v = sqlite3GetVdbe(pParse); sqlite3VdbeSetNumCols(v, 4); pParse->nMem = 4; sqlite3CodeVerifySchema(pParse, iDb); sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "seq", SQLITE_STATIC); sqlite3VdbeSetColName(v, 1, COLNAME_NAME, "name", SQLITE_STATIC); sqlite3VdbeSetColName(v, 2, COLNAME_NAME, "unique", SQLITE_STATIC); sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "avgrowsize", SQLITE_STATIC); sqlite3VdbeAddOp2(v, OP_Integer, 0, 1); sqlite3VdbeAddOp2(v, OP_Null, 0, 2); sqlite3VdbeAddOp2(v, OP_Integer, 1, 3); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pTab->szTabRow), 4); sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4); for(pIdx=pTab->pIndex, i=1; pIdx; pIdx=pIdx->pNext, i++){ sqlite3VdbeAddOp2(v, OP_Integer, i, 1); sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0); sqlite3VdbeAddOp2(v, OP_Integer, pIdx->onError!=OE_None, 3); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pIdx->szIdxRow), 4); sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4); } } } break; case PragTyp_DATABASE_LIST: { int i; |
︙ | ︙ | |||
2175 2176 2177 2178 2179 2180 2181 | } case PragTyp_REKEY: { if( zRight ) sqlite3_rekey_v2(db, zDb, zRight, sqlite3Strlen30(zRight)); break; } case PragTyp_HEXKEY: { if( zRight ){ | > | | < | | | 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 | } case PragTyp_REKEY: { if( zRight ) sqlite3_rekey_v2(db, zDb, zRight, sqlite3Strlen30(zRight)); break; } case PragTyp_HEXKEY: { if( zRight ){ u8 iByte; int i; char zKey[40]; for(i=0, iByte=0; i<sizeof(zKey)*2 && sqlite3Isxdigit(zRight[i]); i++){ iByte = (iByte<<4) + sqlite3HexToInt(zRight[i]); if( (i&1)!=0 ) zKey[i/2] = iByte; } if( (zLeft[3] & 0xf)==0xb ){ sqlite3_key_v2(db, zDb, zKey, i/2); }else{ sqlite3_rekey_v2(db, zDb, zKey, i/2); } } |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 | sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0); } } /* ** Return a pointer to a string containing the 'declaration type' of the ** expression pExpr. The string may be treated as static by the caller. ** ** The declaration type is the exact datatype definition extracted from the ** original CREATE TABLE statement if the expression is a column. The ** declaration type for a ROWID field is INTEGER. Exactly when an expression ** is considered a column can be complex in the presence of subqueries. The ** result-set expression in all of the following SELECT statements is ** considered a column by this function. ** ** SELECT col FROM tbl; ** SELECT (SELECT col FROM tbl; ** SELECT (SELECT col FROM tbl); ** SELECT abc FROM (SELECT col AS abc FROM tbl); ** ** The declaration type for any expression other than a column is NULL. */ | > > > > > > > > | | | | > | | | > > > > > > > > | < > > | 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 | sqlite3VdbeAddOp2(v, OP_Close, pseudoTab, 0); } } /* ** Return a pointer to a string containing the 'declaration type' of the ** expression pExpr. The string may be treated as static by the caller. ** ** Also try to estimate the size of the returned value and return that ** result in *pEstWidth. ** ** The declaration type is the exact datatype definition extracted from the ** original CREATE TABLE statement if the expression is a column. The ** declaration type for a ROWID field is INTEGER. Exactly when an expression ** is considered a column can be complex in the presence of subqueries. The ** result-set expression in all of the following SELECT statements is ** considered a column by this function. ** ** SELECT col FROM tbl; ** SELECT (SELECT col FROM tbl; ** SELECT (SELECT col FROM tbl); ** SELECT abc FROM (SELECT col AS abc FROM tbl); ** ** The declaration type for any expression other than a column is NULL. ** ** This routine has either 3 or 6 parameters depending on whether or not ** the SQLITE_ENABLE_COLUMN_METADATA compile-time option is used. */ #ifdef SQLITE_ENABLE_COLUMN_METADATA # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,C,D,E,F) static const char *columnTypeImpl( NameContext *pNC, Expr *pExpr, const char **pzOrigDb, const char **pzOrigTab, const char **pzOrigCol, u8 *pEstWidth ){ char const *zOrigDb = 0; char const *zOrigTab = 0; char const *zOrigCol = 0; #else /* if !defined(SQLITE_ENABLE_COLUMN_METADATA) */ # define columnType(A,B,C,D,E,F) columnTypeImpl(A,B,F) static const char *columnTypeImpl( NameContext *pNC, Expr *pExpr, u8 *pEstWidth ){ #endif /* !defined(SQLITE_ENABLE_COLUMN_METADATA) */ char const *zType = 0; int j; u8 estWidth = 1; if( NEVER(pExpr==0) || pNC->pSrcList==0 ) return 0; switch( pExpr->op ){ case TK_AGG_COLUMN: case TK_COLUMN: { /* The expression is a column. Locate the table the column is being ** extracted from in NameContext.pSrcList. This table may be real ** database table or a subquery. */ |
︙ | ︙ | |||
1145 1146 1147 1148 1149 1150 1151 | ** test case misc2.2.2) - it always evaluates to NULL. */ NameContext sNC; Expr *p = pS->pEList->a[iCol].pExpr; sNC.pSrcList = pS->pSrc; sNC.pNext = pNC; sNC.pParse = pNC->pParse; | | > | | > | | > > > > > > > > | | > | | | | | > > | 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 | ** test case misc2.2.2) - it always evaluates to NULL. */ NameContext sNC; Expr *p = pS->pEList->a[iCol].pExpr; sNC.pSrcList = pS->pSrc; sNC.pNext = pNC; sNC.pParse = pNC->pParse; zType = columnType(&sNC, p,&zOrigDb,&zOrigTab,&zOrigCol, &estWidth); } }else if( ALWAYS(pTab->pSchema) ){ /* A real table */ assert( !pS ); if( iCol<0 ) iCol = pTab->iPKey; assert( iCol==-1 || (iCol>=0 && iCol<pTab->nCol) ); #ifdef SQLITE_ENABLE_COLUMN_METADATA if( iCol<0 ){ zType = "INTEGER"; zOrigCol = "rowid"; }else{ zType = pTab->aCol[iCol].zType; zOrigCol = pTab->aCol[iCol].zName; estWidth = pTab->aCol[iCol].szEst; } zOrigTab = pTab->zName; if( pNC->pParse ){ int iDb = sqlite3SchemaToIndex(pNC->pParse->db, pTab->pSchema); zOrigDb = pNC->pParse->db->aDb[iDb].zName; } #else if( iCol<0 ){ zType = "INTEGER"; }else{ zType = pTab->aCol[iCol].zType; estWidth = pTab->aCol[iCol].szEst; } #endif } break; } #ifndef SQLITE_OMIT_SUBQUERY case TK_SELECT: { /* The expression is a sub-select. Return the declaration type and ** origin info for the single column in the result set of the SELECT ** statement. */ NameContext sNC; Select *pS = pExpr->x.pSelect; Expr *p = pS->pEList->a[0].pExpr; assert( ExprHasProperty(pExpr, EP_xIsSelect) ); sNC.pSrcList = pS->pSrc; sNC.pNext = pNC; sNC.pParse = pNC->pParse; zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, &estWidth); break; } #endif } #ifdef SQLITE_ENABLE_COLUMN_METADATA if( pzOrigDb ){ assert( pzOrigTab && pzOrigCol ); *pzOrigDb = zOrigDb; *pzOrigTab = zOrigTab; *pzOrigCol = zOrigCol; } #endif if( pEstWidth ) *pEstWidth = estWidth; return zType; } /* ** Generate code that will tell the VDBE the declaration types of columns ** in the result set. */ |
︙ | ︙ | |||
1217 1218 1219 1220 1221 1222 1223 | for(i=0; i<pEList->nExpr; i++){ Expr *p = pEList->a[i].pExpr; const char *zType; #ifdef SQLITE_ENABLE_COLUMN_METADATA const char *zOrigDb = 0; const char *zOrigTab = 0; const char *zOrigCol = 0; | | | | | 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 | for(i=0; i<pEList->nExpr; i++){ Expr *p = pEList->a[i].pExpr; const char *zType; #ifdef SQLITE_ENABLE_COLUMN_METADATA const char *zOrigDb = 0; const char *zOrigTab = 0; const char *zOrigCol = 0; zType = columnType(&sNC, p, &zOrigDb, &zOrigTab, &zOrigCol, 0); /* The vdbe must make its own copy of the column-type and other ** column specific strings, in case the schema is reset before this ** virtual machine is deleted. */ sqlite3VdbeSetColName(v, i, COLNAME_DATABASE, zOrigDb, SQLITE_TRANSIENT); sqlite3VdbeSetColName(v, i, COLNAME_TABLE, zOrigTab, SQLITE_TRANSIENT); sqlite3VdbeSetColName(v, i, COLNAME_COLUMN, zOrigCol, SQLITE_TRANSIENT); #else zType = columnType(&sNC, p, 0, 0, 0, 0); #endif sqlite3VdbeSetColName(v, i, COLNAME_DECLTYPE, zType, SQLITE_TRANSIENT); } #endif /* !defined(SQLITE_OMIT_DECLTYPE) */ } /* ** Generate code that will tell the VDBE the names of columns ** in the result set. This information is used to provide the ** azCol[] values in the callback. */ |
︙ | ︙ | |||
1420 1421 1422 1423 1424 1425 1426 | ** routine goes through and adds the types and collations. ** ** This routine requires that all identifiers in the SELECT ** statement be resolved. */ static void selectAddColumnTypeAndCollation( Parse *pParse, /* Parsing contexts */ | | < > | | | > > | 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 | ** routine goes through and adds the types and collations. ** ** This routine requires that all identifiers in the SELECT ** statement be resolved. */ static void selectAddColumnTypeAndCollation( Parse *pParse, /* Parsing contexts */ Table *pTab, /* Add column type information to this table */ Select *pSelect /* SELECT used to determine types and collations */ ){ sqlite3 *db = pParse->db; NameContext sNC; Column *pCol; CollSeq *pColl; int i; Expr *p; struct ExprList_item *a; u64 szAll = 0; assert( pSelect!=0 ); assert( (pSelect->selFlags & SF_Resolved)!=0 ); assert( pTab->nCol==pSelect->pEList->nExpr || db->mallocFailed ); if( db->mallocFailed ) return; memset(&sNC, 0, sizeof(sNC)); sNC.pSrcList = pSelect->pSrc; a = pSelect->pEList->a; for(i=0, pCol=pTab->aCol; i<pTab->nCol; i++, pCol++){ p = a[i].pExpr; pCol->zType = sqlite3DbStrDup(db, columnType(&sNC, p,0,0,0, &pCol->szEst)); szAll += pCol->szEst; pCol->affinity = sqlite3ExprAffinity(p); if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_NONE; pColl = sqlite3ExprCollSeq(pParse, p); if( pColl ){ pCol->zColl = sqlite3DbStrDup(db, pColl->zName); } } pTab->szTabRow = sqlite3LogEst(szAll*4); } /* ** Given a SELECT statement, generate a Table structure that describes ** the result set of that SELECT. */ Table *sqlite3ResultSetOfSelect(Parse *pParse, Select *pSelect){ |
︙ | ︙ | |||
1476 1477 1478 1479 1480 1481 1482 | return 0; } /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside ** is disabled */ assert( db->lookaside.bEnabled==0 ); pTab->nRef = 1; pTab->zName = 0; | | | | 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 | 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->nRowEst = 1048576; selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol); selectAddColumnTypeAndCollation(pParse, pTab, pSelect); pTab->iPKey = -1; if( db->mallocFailed ){ sqlite3DeleteTable(db, pTab); return 0; } return pTab; } |
︙ | ︙ | |||
3390 3391 3392 3393 3394 3395 3396 | /* A sub-query in the FROM clause of a SELECT */ assert( pSel!=0 ); assert( pFrom->pTab==0 ); sqlite3WalkSelect(pWalker, pSel); pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; | | | | 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 | /* A sub-query in the FROM clause of a SELECT */ assert( pSel!=0 ); assert( pFrom->pTab==0 ); sqlite3WalkSelect(pWalker, pSel); 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->nRowEst = 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; |
︙ | ︙ | |||
3678 3679 3680 3681 3682 3683 3684 | for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){ Table *pTab = pFrom->pTab; if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){ /* A sub-query in the FROM clause of a SELECT */ Select *pSel = pFrom->pSelect; assert( pSel ); while( pSel->pPrior ) pSel = pSel->pPrior; | | | 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 | for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){ Table *pTab = pFrom->pTab; if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){ /* A sub-query in the FROM clause of a SELECT */ Select *pSel = pFrom->pSelect; assert( pSel ); while( pSel->pPrior ) pSel = pSel->pPrior; selectAddColumnTypeAndCollation(pParse, pTab, pSel); } } } return WRC_Continue; } #endif |
︙ | ︙ | |||
4604 4605 4606 4607 4608 4609 4610 | ** (2013-10-03) Do not count the entires in a partial index. ** ** In practice the KeyInfo structure will not be used. It is only ** passed to keep OP_OpenRead happy. */ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ if( pIdx->bUnordered==0 | | | | 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 | ** (2013-10-03) Do not count the entires in a partial index. ** ** In practice the KeyInfo structure will not be used. It is only ** passed to keep OP_OpenRead happy. */ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ if( pIdx->bUnordered==0 && pIdx->szIdxRow<pTab->szTabRow && pIdx->pPartIdxWhere==0 && (!pBest || pIdx->szIdxRow<pBest->szIdxRow) ){ pBest = pIdx; } } if( pBest ){ iRoot = pBest->tnum; pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest); |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
466 467 468 469 470 471 472 473 474 475 476 477 478 479 | */ #ifdef SQLITE_64BIT_STATS typedef u64 tRowcnt; /* 64-bit only if requested at compile-time */ #else typedef u32 tRowcnt; /* 32-bit is the default */ #endif /* ** Macros to determine whether the machine is big or little endian, ** evaluated at runtime. */ #ifdef SQLITE_AMALGAMATION const int sqlite3one = 1; #else | > > > > > > > > > > > > > > > > > > > > > > > > > | 466 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 492 493 494 495 496 497 498 499 500 501 502 503 504 | */ #ifdef SQLITE_64BIT_STATS typedef u64 tRowcnt; /* 64-bit only if requested at compile-time */ #else typedef u32 tRowcnt; /* 32-bit is the default */ #endif /* ** 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 quantatites are suppose to be estimates, ** not exact values, this imprecision is not a problem. ** ** "LogEst" is short for "Logarithimic 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 ** ** The LogEst can be negative to indicate fractional values. ** Examples: ** ** 0.5 -> -10 0.1 -> -33 0.0625 -> -40 */ typedef INT16_TYPE LogEst; /* ** Macros to determine whether the machine is big or little endian, ** evaluated at runtime. */ #ifdef SQLITE_AMALGAMATION const int sqlite3one = 1; #else |
︙ | ︙ | |||
1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 | ExprList *pCheck; /* All CHECK constraints */ #endif tRowcnt nRowEst; /* 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 */ u8 tabFlags; /* Mask of TF_* values */ u8 keyConf; /* What to do in case of uniqueness conflict on iPKey */ #ifndef SQLITE_OMIT_ALTERTABLE int addColOffset; /* Offset in CREATE TABLE stmt to add a new column */ #endif #ifndef SQLITE_OMIT_VIRTUALTABLE int nModuleArg; /* Number of arguments to the module */ | > | 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 | ExprList *pCheck; /* All CHECK constraints */ #endif tRowcnt nRowEst; /* 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 */ #ifndef SQLITE_OMIT_ALTERTABLE int addColOffset; /* Offset in CREATE TABLE stmt to add a new column */ #endif #ifndef SQLITE_OMIT_VIRTUALTABLE int nModuleArg; /* Number of arguments to the module */ |
︙ | ︙ | |||
1556 1557 1558 1559 1560 1561 1562 1563 | 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 */ int tnum; /* DB Page containing root of this index */ u16 nColumn; /* Number of columns in table used by this index */ | > < | | 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 | 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 */ int tnum; /* DB Page containing root of this index */ LogEst szIdxRow; /* Estimated average row size in bytes */ u16 nColumn; /* Number of columns in table used by this index */ u8 onError; /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */ unsigned autoIndex:2; /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */ unsigned bUnordered:1; /* Use this index for == or IN queries only */ unsigned uniqNotNull:1; /* True if UNIQUE and NOT NULL for all columns */ #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 int nSample; /* Number of elements in aSample[] */ int nSampleCol; /* Size of IndexSample.anEq[] and so on */ tRowcnt *aAvgEq; /* Average nEq values for keys not in aSample */ |
︙ | ︙ | |||
2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 | int sqlite3FixTriggerStep(DbFixer*, TriggerStep*); int sqlite3AtoF(const char *z, double*, int, u8); int sqlite3GetInt32(const char *, int*); int sqlite3Atoi(const char*); int sqlite3Utf16ByteLen(const void *pData, int nChar); int sqlite3Utf8CharLen(const char *pData, int nByte); u32 sqlite3Utf8Read(const u8**); /* ** Routines to read and write variable-length integers. These used to ** be defined locally, but now we use the varint routines in the util.c ** file. Code should use the MACRO forms below, as the Varint32 versions ** are coded to assume the single byte case is already handled (which ** the MACRO form does). | > > > > > > | 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 | int sqlite3FixTriggerStep(DbFixer*, TriggerStep*); int sqlite3AtoF(const char *z, double*, int, u8); int sqlite3GetInt32(const char *, int*); int sqlite3Atoi(const char*); int sqlite3Utf16ByteLen(const void *pData, int nChar); int sqlite3Utf8CharLen(const char *pData, int nByte); u32 sqlite3Utf8Read(const u8**); LogEst sqlite3LogEst(u64); LogEst sqlite3LogEstAdd(LogEst,LogEst); #ifndef SQLITE_OMIT_VIRTUALTABLE LogEst sqlite3LogEstFromDouble(double); #endif u64 sqlite3LogEstToInt(LogEst); /* ** Routines to read and write variable-length integers. These used to ** be defined locally, but now we use the varint routines in the util.c ** file. Code should use the MACRO forms below, as the Varint32 versions ** are coded to assume the single byte case is already handled (which ** the MACRO form does). |
︙ | ︙ |
Changes to src/test8.c.
︙ | ︙ | |||
261 262 263 264 265 266 267 268 269 270 271 272 273 274 | /* For each index, figure out the left-most column and set the ** corresponding entry in aIndex[] to 1. */ while( pStmt && sqlite3_step(pStmt)==SQLITE_ROW ){ const char *zIdx = (const char *)sqlite3_column_text(pStmt, 1); sqlite3_stmt *pStmt2 = 0; zSql = sqlite3_mprintf("PRAGMA index_info(%s)", zIdx); if( !zSql ){ rc = SQLITE_NOMEM; goto get_index_array_out; } rc = sqlite3_prepare(db, zSql, -1, &pStmt2, 0); sqlite3_free(zSql); | > | 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 | /* For each index, figure out the left-most column and set the ** corresponding entry in aIndex[] to 1. */ while( pStmt && sqlite3_step(pStmt)==SQLITE_ROW ){ const char *zIdx = (const char *)sqlite3_column_text(pStmt, 1); sqlite3_stmt *pStmt2 = 0; if( zIdx==0 ) continue; zSql = sqlite3_mprintf("PRAGMA index_info(%s)", zIdx); if( !zSql ){ rc = SQLITE_NOMEM; goto get_index_array_out; } rc = sqlite3_prepare(db, zSql, -1, &pStmt2, 0); sqlite3_free(zSql); |
︙ | ︙ |
Changes to src/util.c.
︙ | ︙ | |||
1204 1205 1206 1207 1208 1209 1210 | int i, sz; sz = sqlite3Strlen30(z); for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){} if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4); } } #endif | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | int i, sz; sz = sqlite3Strlen30(z); for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){} if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4); } } #endif /* ** Find (an approximate) sum of two LogEst values. This computation is ** not a simple "+" operator because LogEst is stored as a logarithmic ** value. ** */ LogEst sqlite3LogEstAdd(LogEst a, LogEst b){ static const unsigned char x[] = { 10, 10, /* 0,1 */ 9, 9, /* 2,3 */ 8, 8, /* 4,5 */ 7, 7, 7, /* 6,7,8 */ 6, 6, 6, /* 9,10,11 */ 5, 5, 5, /* 12-14 */ 4, 4, 4, 4, /* 15-18 */ 3, 3, 3, 3, 3, 3, /* 19-24 */ 2, 2, 2, 2, 2, 2, 2, /* 25-31 */ }; if( a>=b ){ if( a>b+49 ) return a; if( a>b+31 ) return a+1; return a+x[a-b]; }else{ 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 a ** good approximatation 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; } }else{ while( x>255 ){ y += 40; x >>= 4; } while( x>15 ){ y += 10; x >>= 1; } } return a[x&7] + y - 10; } #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Convert a double into a LogEst ** In other words, compute an approximation for 10*log2(x). */ LogEst sqlite3LogEstFromDouble(double x){ u64 a; LogEst e; assert( sizeof(x)==8 && sizeof(a)==8 ); if( x<=1 ) return 0; if( x<=2000000000 ) return sqlite3LogEst((u64)x); memcpy(&a, &x, 8); e = (a>>52) - 1022; return e*10; } #endif /* SQLITE_OMIT_VIRTUALTABLE */ /* ** Convert a LogEst into an integer. */ u64 sqlite3LogEstToInt(LogEst x){ u64 n; if( x<10 ) return 1; n = x%10; x /= 10; if( n>=5 ) n -= 2; else if( n>=1 ) n -= 1; if( x>=3 ) return (n+8)<<(x-3); return (n+8)>>(3-x); } |
Changes to src/where.c.
︙ | ︙ | |||
44 45 46 47 48 49 50 | typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; typedef struct WhereOrCost WhereOrCost; typedef struct WhereOrSet WhereOrSet; | < < < < < < < < < < < < < < < < < < < < | 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; typedef struct WhereLoopBuilder WhereLoopBuilder; typedef struct WhereScan WhereScan; typedef struct WhereOrCost WhereOrCost; typedef struct WhereOrSet WhereOrSet; /* ** This object contains information needed to implement a single nested ** loop in WHERE clause. ** ** Contrast this object with WhereLoop. This object describes the ** implementation of the loop. WhereLoop describes the algorithm. ** This object contains a pointer to the WhereLoop algorithm as one of |
︙ | ︙ | |||
128 129 130 131 132 133 134 | Bitmask prereq; /* Bitmask of other loops that must run first */ Bitmask maskSelf; /* Bitmask identifying table iTab */ #ifdef SQLITE_DEBUG char cId; /* Symbolic ID of this loop for debugging use */ #endif u8 iTab; /* Position in FROM clause of table for this loop */ u8 iSortIdx; /* Sorting index number. 0==None */ | | | | | 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | Bitmask prereq; /* Bitmask of other loops that must run first */ Bitmask maskSelf; /* Bitmask identifying table iTab */ #ifdef SQLITE_DEBUG char cId; /* Symbolic ID of this loop for debugging use */ #endif u8 iTab; /* Position in FROM clause of table for this loop */ u8 iSortIdx; /* Sorting index number. 0==None */ LogEst rSetup; /* One-time setup cost (ex: create transient index) */ LogEst rRun; /* Cost of running each loop */ LogEst nOut; /* Estimated number of output rows */ union { struct { /* Information for internal btree tables */ int nEq; /* Number of equality constraints */ Index *pIndex; /* Index used, or NULL */ } btree; struct { /* Information for virtual tables */ int idxNum; /* Index number */ |
︙ | ︙ | |||
160 161 162 163 164 165 166 | /* This object holds the prerequisites and the cost of running a ** subquery on one operand of an OR operator in the WHERE clause. ** See WhereOrSet for additional information */ struct WhereOrCost { Bitmask prereq; /* Prerequisites */ | | | | 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | /* This object holds the prerequisites and the cost of running a ** subquery on one operand of an OR operator in the WHERE clause. ** See WhereOrSet for additional information */ struct WhereOrCost { Bitmask prereq; /* Prerequisites */ LogEst rRun; /* Cost of running this subquery */ LogEst nOut; /* Number of outputs for this subquery */ }; /* The WhereOrSet object holds a set of possible WhereOrCosts that ** correspond to the subquery(s) of OR-clause processing. Only the ** best N_OR_COST elements are retained. */ #define N_OR_COST 3 |
︙ | ︙ | |||
199 200 201 202 203 204 205 | ** of length 2. And so forth until the length of WherePaths equals the ** number of nodes in the FROM clause. The best (lowest cost) WherePath ** at the end is the choosen query plan. */ struct WherePath { Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ | | | | 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | ** of length 2. And so forth until the length of WherePaths equals the ** number of nodes in the FROM clause. The best (lowest cost) WherePath ** at the end is the choosen query plan. */ struct WherePath { Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ LogEst nRow; /* Estimated number of rows generated by this path */ LogEst rCost; /* Total cost of this path */ u8 isOrdered; /* True if this path satisfies ORDER BY */ u8 isOrderedValid; /* True if the isOrdered field is valid */ WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */ }; /* ** The query generator uses an array of instances of this structure to |
︙ | ︙ | |||
266 267 268 269 270 271 272 | int iParent; /* Disable pWC->a[iParent] when this term disabled */ int leftCursor; /* Cursor number of X in "X <op> <expr>" */ union { int leftColumn; /* Column number of X in "X <op> <expr>" */ WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ } u; | | | 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 | int iParent; /* Disable pWC->a[iParent] when this term disabled */ int leftCursor; /* Cursor number of X in "X <op> <expr>" */ union { int leftColumn; /* Column number of X in "X <op> <expr>" */ WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */ } u; LogEst truthProb; /* Probability of truth for this expression */ u16 eOperator; /* A WO_xx value describing <op> */ u8 wtFlags; /* TERM_xxx bit flags. See below */ u8 nChild; /* Number of children that must disable us */ WhereClause *pWC; /* The clause this term is part of */ Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */ Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */ }; |
︙ | ︙ | |||
414 415 416 417 418 419 420 | struct WhereInfo { Parse *pParse; /* Parsing and code generating context */ SrcList *pTabList; /* List of tables in the join */ ExprList *pOrderBy; /* The ORDER BY clause or NULL */ ExprList *pResultSet; /* Result set. DISTINCT operates on these */ WhereLoop *pLoops; /* List of all WhereLoop objects */ Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ | | | 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 | struct WhereInfo { Parse *pParse; /* Parsing and code generating context */ SrcList *pTabList; /* List of tables in the join */ ExprList *pOrderBy; /* The ORDER BY clause or NULL */ ExprList *pResultSet; /* Result set. DISTINCT operates on these */ WhereLoop *pLoops; /* List of all WhereLoop objects */ Bitmask revMask; /* Mask of ORDER BY terms that need reversing */ LogEst nRowOut; /* Estimated number of output rows */ u16 wctrlFlags; /* Flags originally passed to sqlite3WhereBegin() */ u8 bOBSat; /* ORDER BY satisfied by indices */ u8 okOnePass; /* Ok to use one-pass algorithm for UPDATE/DELETE */ u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ u8 nLevel; /* Number of nested loop */ int iTop; /* The very beginning of the WHERE loop */ |
︙ | ︙ | |||
474 475 476 477 478 479 480 | #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ #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 */ | < < < < < < < < < < < < < < < | | 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 | #define WHERE_INDEXED 0x00000200 /* WhereLoop.u.btree.pIndex is valid */ #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 */ /* ** Return the estimated number of output rows from a WHERE clause */ u64 sqlite3WhereOutputRowCount(WhereInfo *pWInfo){ return sqlite3LogEstToInt(pWInfo->nRowOut); } /* ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this ** WHERE clause returns outputs for DISTINCT processing. */ int sqlite3WhereIsDistinct(WhereInfo *pWInfo){ |
︙ | ︙ | |||
555 556 557 558 559 560 561 | ** The new entry might overwrite an existing entry, or it might be ** appended, or it might be discarded. Do whatever is the right thing ** so that pSet keeps the N_OR_COST best entries seen so far. */ static int whereOrInsert( WhereOrSet *pSet, /* The WhereOrSet to be updated */ Bitmask prereq, /* Prerequisites of the new entry */ | | | | 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 | ** The new entry might overwrite an existing entry, or it might be ** appended, or it might be discarded. Do whatever is the right thing ** so that pSet keeps the N_OR_COST best entries seen so far. */ static int whereOrInsert( WhereOrSet *pSet, /* The WhereOrSet to be updated */ Bitmask prereq, /* Prerequisites of the new entry */ LogEst rRun, /* Run-cost of the new entry */ LogEst nOut /* Number of outputs for the new entry */ ){ u16 i; WhereOrCost *p; for(i=pSet->n, p=pSet->a; i>0; i--, p++){ if( rRun<=p->rRun && (prereq & p->prereq)==prereq ){ goto whereOrInsert_done; } |
︙ | ︙ | |||
641 642 643 644 645 646 647 | } } if( pWC->a!=pWC->aStatic ){ sqlite3DbFree(db, pWC->a); } } | < < < | 606 607 608 609 610 611 612 613 614 615 616 617 618 619 | } } if( pWC->a!=pWC->aStatic ){ sqlite3DbFree(db, pWC->a); } } /* ** Add a single new WhereTerm entry to the WhereClause object pWC. ** The new WhereTerm object is constructed from Expr p and with wtFlags. ** The index in pWC->a[] of the new WhereTerm is returned on success. ** 0 is returned if the new WhereTerm could not be added due to a memory ** allocation error. The memory allocation failure will be recorded in ** the db->mallocFailed flag so that higher-level functions can detect it. |
︙ | ︙ | |||
686 687 688 689 690 691 692 | if( pOld!=pWC->aStatic ){ sqlite3DbFree(db, pOld); } pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]); } pTerm = &pWC->a[idx = pWC->nTerm++]; if( p && ExprHasProperty(p, EP_Unlikely) ){ | | | 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 | if( pOld!=pWC->aStatic ){ sqlite3DbFree(db, pOld); } 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; |
︙ | ︙ | |||
1950 1951 1952 1953 1954 1955 1956 | return 1; } } return 0; } | < < < < < < < < < < < < < < < < < < < < < < < < < < | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | | | 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 | return 1; } } return 0; } /* ** Estimate the logarithm of the input value to base 2. */ static LogEst estLog(LogEst N){ LogEst x = sqlite3LogEst(N); return x>33 ? x - 33 : 0; } /* ** Two routines for printing the content of an sqlite3_index_info ** structure. Used for testing and debugging only. If neither ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines |
︙ | ︙ | |||
2531 2532 2533 2534 2535 2536 2537 | ** then nEq is set to 1 (as the range restricted column, b, is the second ** left-most column of the index). Or, if the query is: ** ** ... FROM t1 WHERE a > ? AND a < ? ... ** ** then nEq is set to 0. ** | | | | > | | < | 2430 2431 2432 2433 2434 2435 2436 2437 2438 2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 | ** then nEq is set to 1 (as the range restricted column, b, is the second ** left-most column of the index). Or, if the query is: ** ** ... FROM t1 WHERE a > ? AND a < ? ... ** ** then nEq is set to 0. ** ** When this function is called, *pnOut is set to the sqlite3LogEst() of the ** number of rows that the index scan is expected to visit without ** considering the range constraints. If nEq is 0, this is the number of ** rows in the index. Assuming no error occurs, *pnOut is adjusted (reduced) ** to account for the range contraints pLower and pUpper. ** ** In the absence of sqlite_stat4 ANALYZE data, or if such data cannot be ** used, each range inequality reduces the search space by a factor of 4. ** Hence a pair of constraints (x>? AND x<?) reduces the expected number of ** rows visited by a factor of 16. */ static int whereRangeScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */ WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */ WhereLoop *pLoop /* Modify the .nOut and maybe .rRun fields */ ){ int rc = SQLITE_OK; int nOut = pLoop->nOut; int nEq = pLoop->u.btree.nEq; LogEst nNew; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 Index *p = pLoop->u.btree.pIndex; if( p->nSample>0 && nEq==pBuilder->nRecValid && nEq<p->nSampleCol && OptimizationEnabled(pParse->db, SQLITE_Stat3) ){ UnpackedRecord *pRec = pBuilder->pRec; |
︙ | ︙ | |||
2636 2637 2638 2639 2640 2641 2642 | nOut--; } } pBuilder->pRec = pRec; if( rc==SQLITE_OK ){ if( iUpper>iLower ){ | | | | | | | | 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 | nOut--; } } pBuilder->pRec = pRec; if( rc==SQLITE_OK ){ if( iUpper>iLower ){ nNew = sqlite3LogEst(iUpper - iLower); }else{ nNew = 10; assert( 10==sqlite3LogEst(2) ); } if( nNew<nOut ){ nOut = nNew; } pLoop->nOut = (LogEst)nOut; WHERETRACE(0x100, ("range scan regions: %u..%u est=%d\n", (u32)iLower, (u32)iUpper, nOut)); return SQLITE_OK; } } #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(pBuilder); #endif assert( pLower || pUpper ); /* TUNING: Each inequality constraint reduces the search space 4-fold. ** A BETWEEN operator, therefore, reduces the search space 16-fold */ nNew = nOut; if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){ nNew -= 20; assert( 20==sqlite3LogEst(4) ); nOut--; } if( pUpper ){ nNew -= 20; assert( 20==sqlite3LogEst(4) ); nOut--; } if( nNew<10 ) nNew = 10; if( nNew<nOut ) nOut = nNew; pLoop->nOut = (LogEst)nOut; return rc; } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 /* ** Estimate the number of rows that will be returned based on ** an equality constraint x=VALUE and where that VALUE occurs in |
︙ | ︙ | |||
4311 4312 4313 4314 4315 4316 4317 | ** 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 */ Index *pProbe, /* An index on pSrc */ | | | | | | | | 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 | ** 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 */ Index *pProbe, /* An index on pSrc */ LogEst nInMul /* log(Number of iterations due to IN) */ ){ WhereInfo *pWInfo = pBuilder->pWInfo; /* WHERE analyse context */ Parse *pParse = pWInfo->pParse; /* Parsing context */ sqlite3 *db = pParse->db; /* Database connection malloc context */ WhereLoop *pNew; /* Template WhereLoop under construction */ WhereTerm *pTerm; /* A WhereTerm under consideration */ int opMask; /* Valid operators for constraints */ WhereScan scan; /* Iterator for WHERE terms */ Bitmask saved_prereq; /* Original value of pNew->prereq */ u16 saved_nLTerm; /* Original value of pNew->nLTerm */ int saved_nEq; /* Original value of pNew->u.btree.nEq */ 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 nRowEst; /* Estimated index selectivity */ 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->nColumn ); if( pNew->u.btree.nEq < pProbe->nColumn ){ iCol = pProbe->aiColumn[pNew->u.btree.nEq]; nRowEst = sqlite3LogEst(pProbe->aiRowEst[pNew->u.btree.nEq+1]); if( nRowEst==0 && pProbe->onError==OE_None ) nRowEst = 1; }else{ iCol = -1; nRowEst = 0; } pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, pProbe); saved_nEq = pNew->u.btree.nEq; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0])); for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 0; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 int nRecValid = pBuilder->nRecValid; #endif if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0) && (iCol<0 || pSrc->pTab->aCol[iCol].notNull) |
︙ | ︙ | |||
4389 4390 4391 4392 4393 4394 4395 | pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; pNew->rRun = rLogSize; /* Baseline cost is log2(N). Adjustments below */ if( pTerm->eOperator & 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 */ | | | | 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 | pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; pNew->rRun = rLogSize; /* Baseline cost is log2(N). Adjustments below */ if( pTerm->eOperator & 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); } pNew->rRun += nIn; pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0 || nInMul==0 ); |
︙ | ︙ | |||
4414 4415 4416 4417 4418 4419 4420 | } pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul; }else if( pTerm->eOperator & (WO_ISNULL) ){ pNew->wsFlags |= WHERE_COLUMN_NULL; pNew->u.btree.nEq++; /* TUNING: IS NULL selects 2 rows */ | | | | | | | 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 | } pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul; }else if( pTerm->eOperator & (WO_ISNULL) ){ pNew->wsFlags |= WHERE_COLUMN_NULL; pNew->u.btree.nEq++; /* TUNING: IS NULL selects 2 rows */ nIn = 10; assert( 10==sqlite3LogEst(2) ); pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_GT|WO_GE) ){ testcase( pTerm->eOperator & WO_GT ); testcase( pTerm->eOperator & WO_GE ); pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT; pBtm = pTerm; pTop = 0; }else{ assert( pTerm->eOperator & (WO_LT|WO_LE) ); testcase( pTerm->eOperator & WO_LT ); testcase( pTerm->eOperator & 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; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ assert( pNew->nOut==saved_nOut ); whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew); } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 if( nInMul==0 && pProbe->nSample && pNew->u.btree.nEq<=pProbe->nSampleCol && OptimizationEnabled(db, SQLITE_Stat3) ){ Expr *pExpr = pTerm->pExpr; tRowcnt nOut = 0; if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){ testcase( pTerm->eOperator & WO_EQ ); testcase( pTerm->eOperator & WO_ISNULL ); rc = whereEqualScanEst(pParse, pBuilder, pExpr->pRight, &nOut); }else if( (pTerm->eOperator & WO_IN) && !ExprHasProperty(pExpr, EP_xIsSelect) ){ rc = whereInScanEst(pParse, pBuilder, pExpr->x.pList, &nOut); } assert( nOut==0 || rc==SQLITE_OK ); if( nOut ){ nOut = sqlite3LogEst(nOut); pNew->nOut = MIN(nOut, saved_nOut); } } #endif if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){ /* Each row involves a step of the index, then a binary search of ** the main table */ pNew->rRun = sqlite3LogEstAdd(pNew->rRun,rLogSize>27 ? rLogSize-17 : 10); } /* Step cost for each output row */ pNew->rRun = sqlite3LogEstAdd(pNew->rRun, pNew->nOut); whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor); rc = whereLoopInsert(pBuilder, pNew); if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 && pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0)) ){ whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn); } |
︙ | ︙ | |||
4565 4566 4567 4568 4569 4570 4571 | int 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 */ | | | > > | | | | 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 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 | int 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 */ LogEst rSize; /* number of rows in the table */ LogEst rLogSize; /* Logarithm of the number of rows in the table */ WhereClause *pWC; /* The parsed WHERE clause */ Table *pTab; /* Table being queried */ pNew = pBuilder->pNew; pWInfo = pBuilder->pWInfo; pTabList = pWInfo->pTabList; pSrc = pTabList->a + pNew->iTab; pTab = pSrc->pTab; pWC = pBuilder->pWC; assert( !IsVirtual(pSrc->pTab) ); if( pSrc->pIndex ){ /* An INDEXED BY clause specifies a particular index to use */ pProbe = pSrc->pIndex; }else{ /* There is no INDEXED BY clause. Create a fake Index object in local ** 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.nColumn = 1; sPk.aiColumn = &aiColumnPk; sPk.aiRowEst = aiRowEstPk; sPk.onError = OE_Replace; sPk.pTable = pTab; aiRowEstPk[0] = pTab->nRowEst; aiRowEstPk[1] = 1; 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 = sqlite3LogEst(pTab->nRowEst); rLogSize = estLog(rSize); #ifndef SQLITE_OMIT_AUTOMATIC_INDEX /* Automatic indexes */ if( !pBuilder->pOrSet && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 && pSrc->pIndex==0 |
︙ | ︙ | |||
4626 4627 4628 4629 4630 4631 4632 | pNew->u.btree.nEq = 1; pNew->u.btree.pIndex = 0; pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; /* TUNING: One-time cost for computing the automatic index is ** approximately 7*N*log2(N) where N is the number of rows in ** the table being indexed. */ | | | | | 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 | pNew->u.btree.nEq = 1; pNew->u.btree.pIndex = 0; pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; /* TUNING: One-time cost for computing the automatic index is ** approximately 7*N*log2(N) where N is the number of rows in ** the table being indexed. */ pNew->rSetup = rLogSize + rSize + 28; assert( 28==sqlite3LogEst(7) ); /* TUNING: Each index lookup yields 20 rows in the table. This ** is more than the usual guess of 10 rows, since we have no way ** of knowning how selective the index will ultimately be. It would ** not be unreasonable to make this value much larger. */ pNew->nOut = 43; assert( 43==sqlite3LogEst(20) ); pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut); pNew->wsFlags = WHERE_AUTO_INDEX; pNew->prereq = mExtra | pTerm->prereqRight; rc = whereLoopInsert(pBuilder, pNew); } } } #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */ |
︙ | ︙ | |||
4665 4666 4667 4668 4669 4670 4671 | 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 3*(N + log2(N)). | | | | | | | | | > | 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 | 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 3*(N + log2(N)). ** + The extra 3 factor is to encourage the use of indexed lookups ** over full scans. FIXME */ pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 16; whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor); rc = whereLoopInsert(pBuilder, pNew); pNew->nOut = rSize; if( rc ) break; }else{ Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe); pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED; /* Full scan via index */ if( b || ( m==0 && pProbe->bUnordered==0 && pProbe->szIdxRow<pTab->szTabRow && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) ) ){ pNew->iSortIdx = b ? iSortIdx : 0; if( m==0 ){ /* TUNING: Cost of a covering index scan is K*(N + log2(N)). ** + The extra factor K of between 1.1 and 3.0 that depends ** on the relative sizes of the table and the index. K ** is smaller for smaller indices, thus favoring them. */ pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 1 + (15*pProbe->szIdxRow)/pTab->szTabRow; }else{ assert( b!=0 ); /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N) ** which we will simplify to just N*log2(N) */ pNew->rRun = rSize + rLogSize; } whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor); |
︙ | ︙ | |||
4871 4872 4873 4874 4875 4876 4877 | pNew->u.vtab.idxNum = pIdxInfo->idxNum; pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; pIdxInfo->needToFreeIdxStr = 0; pNew->u.vtab.idxStr = pIdxInfo->idxStr; pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0) && pIdxInfo->orderByConsumed); pNew->rSetup = 0; | | | | 4773 4774 4775 4776 4777 4778 4779 4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 | pNew->u.vtab.idxNum = pIdxInfo->idxNum; pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; pIdxInfo->needToFreeIdxStr = 0; pNew->u.vtab.idxStr = pIdxInfo->idxStr; pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0) && pIdxInfo->orderByConsumed); pNew->rSetup = 0; pNew->rRun = sqlite3LogEstFromDouble(pIdxInfo->estimatedCost); /* TUNING: Every virtual table query returns 25 rows */ pNew->nOut = 46; assert( 46==sqlite3LogEst(25) ); whereLoopInsert(pBuilder, pNew); if( pNew->u.vtab.needFree ){ sqlite3_free(pNew->u.vtab.idxStr); pNew->u.vtab.needFree = 0; } } } |
︙ | ︙ | |||
4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 | 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)); for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){ if( (pTerm->eOperator & WO_OR)!=0 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; WhereTerm *pOrTerm; int once = 1; int i, j; | > > < < | 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 | 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)); pItem = pWInfo->pTabList->a + pNew->iTab; iCur = pItem->iCursor; for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){ if( (pTerm->eOperator & WO_OR)!=0 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; WhereTerm *pOrTerm; int once = 1; int i, j; sSubBuild = *pBuilder; sSubBuild.pOrderBy = 0; sSubBuild.pOrSet = &sCur; for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ if( (pOrTerm->eOperator & WO_AND)!=0 ){ sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc; |
︙ | ︙ | |||
4963 4964 4965 4966 4967 4968 4969 | 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, | | | | 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 | 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; |
︙ | ︙ | |||
5302 5303 5304 5305 5306 5307 5308 | ** Assume that the total number of output rows that will need to be sorted ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting ** costs if nRowEst==0. ** ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation ** error occurs. */ | | | | | | | | 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 | ** Assume that the total number of output rows that will need to be sorted ** will be nRowEst (in the 10*log2 representation). Or, ignore sorting ** costs if nRowEst==0. ** ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation ** error occurs. */ static int wherePathSolver(WhereInfo *pWInfo, LogEst nRowEst){ int mxChoice; /* Maximum number of simultaneous paths tracked */ int nLoop; /* Number of terms in the join */ Parse *pParse; /* Parsing context */ sqlite3 *db; /* The database connection */ int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ int mxI = 0; /* Index of next entry to replace */ LogEst rCost; /* Cost of a path */ LogEst nOut; /* Number of outputs */ LogEst mxCost = 0; /* Maximum cost of a set of paths */ LogEst mxOut = 0; /* Maximum nOut value on the set of paths */ LogEst rSortCost; /* Cost to do a sort */ int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */ WherePath *aFrom; /* All nFrom paths at the previous level */ WherePath *aTo; /* The nTo best paths at the current level */ WherePath *pFrom; /* An element of aFrom[] that we are working on */ WherePath *pTo; /* An element of aTo[] that we are working on */ WhereLoop *pWLoop; /* One of the WhereLoop objects */ WhereLoop **pX; /* Used to divy up the pSpace memory */ |
︙ | ︙ | |||
5351 5352 5353 5354 5355 5356 5357 | } /* Seed the search with a single WherePath containing zero WhereLoops. ** ** TUNING: Do not let the number of iterations go above 25. If the cost ** of computing an automatic index is not paid back within the first 25 ** rows, then do not use the automatic index. */ | | | | > > | | | | 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 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 5314 | } /* Seed the search with a single WherePath containing zero WhereLoops. ** ** TUNING: Do not let the number of iterations go above 25. If the cost ** of computing an automatic index is not paid back within the first 25 ** rows, then do not use the automatic index. */ aFrom[0].nRow = MIN(pParse->nQueryLoop, 46); assert( 46==sqlite3LogEst(25) ); nFrom = 1; /* Precompute the cost of sorting the final result set, if the caller ** to sqlite3WhereBegin() was concerned about sorting */ rSortCost = 0; if( pWInfo->pOrderBy==0 || nRowEst==0 ){ aFrom[0].isOrderedValid = 1; }else{ /* TUNING: Estimated cost of sorting is 48*N*log2(N) where N is the ** number of output rows. The 48 is the expected size of a row to sort. ** FIXME: compute a better estimate of the 48 multiplier based on the ** result set expressions. */ rSortCost = nRowEst + estLog(nRowEst); WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost)); } /* Compute successively longer WherePaths using the previous generation ** of WherePaths as the basis for the next. Keep track of the mxChoice ** best paths at each generation */ for(iLoop=0; iLoop<nLoop; iLoop++){ nTo = 0; for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){ for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){ Bitmask maskNew; Bitmask revMask = 0; u8 isOrderedValid = pFrom->isOrderedValid; u8 isOrdered = pFrom->isOrdered; if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue; if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue; /* At this point, pWLoop is a candidate to be the next loop. ** Compute its cost */ rCost = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow); rCost = sqlite3LogEstAdd(rCost, pFrom->rCost); nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; if( !isOrderedValid ){ switch( wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, iLoop, pWLoop, &revMask) ){ case 1: /* Yes. pFrom+pWLoop does satisfy the ORDER BY clause */ isOrdered = 1; isOrderedValid = 1; break; case 0: /* No. pFrom+pWLoop will require a separate sort */ isOrdered = 0; isOrderedValid = 1; rCost = sqlite3LogEstAdd(rCost, rSortCost); break; default: /* Cannot tell yet. Try again on the next iteration */ break; } }else{ revMask = pFrom->revLoop; } |
︙ | ︙ | |||
5603 5604 5605 5606 5607 5608 5609 | pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0); if( pTerm ){ pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; pLoop->aLTerm[0] = pTerm; pLoop->nLTerm = 1; pLoop->u.btree.nEq = 1; /* TUNING: Cost of a rowid lookup is 10 */ | | | 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 5518 5519 5520 5521 | pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0); if( pTerm ){ pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; pLoop->aLTerm[0] = pTerm; pLoop->nLTerm = 1; pLoop->u.btree.nEq = 1; /* TUNING: Cost of a rowid lookup is 10 */ pLoop->rRun = 33; /* 33==sqlite3LogEst(10) */ }else{ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ assert( pLoop->aLTermSpace==pLoop->aLTerm ); assert( ArraySize(pLoop->aLTermSpace)==4 ); if( pIdx->onError==OE_None || pIdx->pPartIdxWhere!=0 || pIdx->nColumn>ArraySize(pLoop->aLTermSpace) |
︙ | ︙ | |||
5626 5627 5628 5629 5630 5631 5632 | if( (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){ pLoop->wsFlags |= WHERE_IDX_ONLY; } pLoop->nLTerm = j; pLoop->u.btree.nEq = j; pLoop->u.btree.pIndex = pIdx; /* TUNING: Cost of a unique index lookup is 15 */ | | | | 5530 5531 5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5547 5548 5549 | if( (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){ pLoop->wsFlags |= WHERE_IDX_ONLY; } pLoop->nLTerm = j; pLoop->u.btree.nEq = j; pLoop->u.btree.pIndex = pIdx; /* TUNING: Cost of a unique index lookup is 15 */ pLoop->rRun = 39; /* 39==sqlite3LogEst(15) */ break; } } if( pLoop->wsFlags ){ pLoop->nOut = (LogEst)1; pWInfo->a[0].pWLoop = pLoop; pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur); pWInfo->a[0].iTabCur = iCur; pWInfo->nRowOut = 1; if( pWInfo->pOrderBy ) pWInfo->bOBSat = 1; if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; |
︙ | ︙ |
Changes to test/e_select.test.
︙ | ︙ | |||
446 447 448 449 450 451 452 | } [concat {-60.06 {} {}} {-39.24 {} encompass -1}] # EVIDENCE-OF: R-44414-54710 There is a row in the cartesian product # dataset formed by combining each unique combination of a row from the # left-hand and right-hand datasets. # do_join_test e_select-1.4.2.1 { | | | < | > | < | > | 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 | } [concat {-60.06 {} {}} {-39.24 {} encompass -1}] # EVIDENCE-OF: R-44414-54710 There is a row in the cartesian product # dataset formed by combining each unique combination of a row from the # left-hand and right-hand datasets. # do_join_test e_select-1.4.2.1 { SELECT * FROM x2 %JOIN% x3 ORDER BY +c, +f } [list -60.06 {} {} -39.24 {} encompass -1 \ -60.06 {} {} alerting {} -93.79 {} \ -60.06 {} {} coldest -96 dramatists 82.3 \ -60.06 {} {} conducting -87.24 37.56 {} \ -60.06 {} {} presenting 51 reformation dignified \ -58 {} 1.21 -39.24 {} encompass -1 \ -58 {} 1.21 alerting {} -93.79 {} \ -58 {} 1.21 coldest -96 dramatists 82.3 \ -58 {} 1.21 conducting -87.24 37.56 {} \ -58 {} 1.21 presenting 51 reformation dignified \ ] # TODO: Come back and add a few more like the above. # EVIDENCE-OF: R-20659-43267 In other words, if the left-hand dataset # consists of Nlhs rows of Mlhs columns, and the right-hand dataset of # Nrhs rows of Mrhs columns, then the cartesian product is a dataset of # Nlhs.Nrhs rows, each containing Mlhs+Mrhs columns. |
︙ | ︙ |
Changes to test/pragma.test.
︙ | ︙ | |||
570 571 572 573 574 575 576 | pragma foreign_key_list(t5); } } {} do_test pragma-6.4 { execsql { pragma index_list(t3); } | | | 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 | pragma foreign_key_list(t5); } } {} do_test pragma-6.4 { execsql { pragma index_list(t3); } } {/0 {} 1 \d+ 1 sqlite_autoindex_t3_1 1 \d+/} } ifcapable {!foreignkey} { execsql {CREATE TABLE t3(a,b UNIQUE)} } do_test pragma-6.5.1 { execsql { CREATE INDEX t3i1 ON t3(a,b); |
︙ | ︙ | |||
643 644 645 646 647 648 649 | do_test pragma-7.1.1 { # Make sure a pragma knows to read the schema if it needs to db close sqlite3 db test.db execsql { pragma index_list(t3); } | | | 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 | do_test pragma-7.1.1 { # Make sure a pragma knows to read the schema if it needs to db close sqlite3 db test.db execsql { pragma index_list(t3); } } {/0 {} 1 \d+ 1 t3i1 0 \d+ 2 sqlite_autoindex_t3_1 1 \d+/} do_test pragma-7.1.2 { execsql { pragma index_list(t3_bogus); } } {} } ;# ifcapable schema_pragmas ifcapable {utf16} { |
︙ | ︙ | |||
1657 1658 1659 1660 1661 1662 1663 | db2 eval {PRAGMA index_info(i2)} } {0 2 c 1 3 d 2 1 b} do_test 23.3 { db eval { CREATE INDEX i3 ON t1(d,b,c); } db2 eval {PRAGMA index_list(t1)} | | | 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 | db2 eval {PRAGMA index_info(i2)} } {0 2 c 1 3 d 2 1 b} do_test 23.3 { db eval { CREATE INDEX i3 ON t1(d,b,c); } db2 eval {PRAGMA index_list(t1)} } {/0 {} 1 \d+ 1 i3 0 \d+ 2 i2 0 \d+ 3 i1 0 \d+/} do_test 23.4 { db eval { ALTER TABLE t1 ADD COLUMN e; } db2 eval { PRAGMA table_info(t1); } |
︙ | ︙ |
Changes to test/select1.test.
︙ | ︙ | |||
538 539 540 541 542 543 544 | SELECT * FROM test1 a, test1 b LIMIT 1 } } {a.f1 11 a.f2 22 b.f1 11 b.f2 22} do_test select1-6.9.7 { set x [execsql2 { SELECT * FROM test1 a, (select 5, 6) LIMIT 1 }] | | | 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 | SELECT * FROM test1 a, test1 b LIMIT 1 } } {a.f1 11 a.f2 22 b.f1 11 b.f2 22} do_test select1-6.9.7 { set x [execsql2 { SELECT * FROM test1 a, (select 5, 6) LIMIT 1 }] regsub -all {sq_[0-9a-fA-F_]+} $x {subquery} x set x } {a.f1 11 a.f2 22 sqlite_subquery.5 5 sqlite_subquery.6 6} do_test select1-6.9.8 { set x [execsql2 { SELECT * FROM test1 a, (select 5 AS x, 6 AS y) AS b LIMIT 1 }] regsub -all {subquery_[0-9a-fA-F]+_} $x {subquery} x |
︙ | ︙ |
Added tool/logest.c.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | /* ** 2013-06-10 ** ** 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 a simple command-line utility for converting from ** integers and LogEst values and back again and for doing simple ** arithmetic operations (multiple and add) on LogEst values. ** ** Usage: ** ** ./LogEst ARGS ** ** Arguments: ** ** 'x' Multiple the top two elements of the stack ** '+' Add the top two elements of the stack ** NUM Convert NUM from integer to LogEst and push onto the stack ** ^NUM Interpret NUM as a LogEst and push onto stack. ** ** Examples: ** ** To convert 123 from LogEst to integer: ** ** ./LogEst ^123 ** ** To convert 123456 from integer to LogEst: ** ** ./LogEst 123456 ** */ #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <assert.h> #include <string.h> #include "sqlite3.h" typedef short int LogEst; /* 10 times log2() */ LogEst logEstMultiply(LogEst a, LogEst b){ return a+b; } LogEst logEstAdd(LogEst a, LogEst b){ static const unsigned char x[] = { 10, 10, /* 0,1 */ 9, 9, /* 2,3 */ 8, 8, /* 4,5 */ 7, 7, 7, /* 6,7,8 */ 6, 6, 6, /* 9,10,11 */ 5, 5, 5, /* 12-14 */ 4, 4, 4, 4, /* 15-18 */ 3, 3, 3, 3, 3, 3, /* 19-24 */ 2, 2, 2, 2, 2, 2, 2, /* 25-31 */ }; if( a<b ){ LogEst t = a; a = b; b = t; } if( a>b+49 ) return a; if( a>b+31 ) return a+1; return a+x[a-b]; } LogEst logEstFromInteger(sqlite3_uint64 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; } }else{ while( x>255 ){ y += 40; x >>= 4; } while( x>15 ){ y += 10; x >>= 1; } } return a[x&7] + y - 10; } static sqlite3_uint64 logEstToInt(LogEst x){ sqlite3_uint64 n; if( x<10 ) return 1; n = x%10; x /= 10; if( n>=5 ) n -= 2; else if( n>=1 ) n -= 1; if( x>=3 ) return (n+8)<<(x-3); 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<1.0 ) return -logEstFromDouble(1/x); 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; } int isFloat(const char *z){ while( z[0] ){ if( z[0]=='.' || z[0]=='E' || z[0]=='e' ) return 1; z++; } return 0; } int main(int argc, char **argv){ int i; int n = 0; LogEst a[100]; for(i=1; i<argc; i++){ const char *z = argv[i]; if( z[0]=='+' ){ if( n>=2 ){ a[n-2] = logEstAdd(a[n-2],a[n-1]); n--; } }else if( z[0]=='x' ){ if( n>=2 ){ a[n-2] = logEstMultiply(a[n-2],a[n-1]); n--; } }else if( z[0]=='^' ){ a[n++] = atoi(z+1); }else if( isFloat(z) ){ a[n++] = logEstFromDouble(atof(z)); }else{ a[n++] = logEstFromInteger(atoi(z)); } } for(i=n-1; i>=0; i--){ if( a[i]<0 ){ printf("%d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i])); }else{ sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024; printf("%d (%lld.%02lld)\n", a[i], x/100, x%100); } } return 0; } |
Changes to tool/mkpragmatab.tcl.
︙ | ︙ | |||
250 251 252 253 254 255 256 257 258 259 260 261 262 263 | NAME: rekey IF: defined(SQLITE_HAS_CODEC) NAME: hexkey IF: defined(SQLITE_HAS_CODEC) NAME: activate_extensions IF: defined(SQLITE_HAS_CODEC) || defined(SQLITE_ENABLE_CEROD) NAME: soft_heap_limit } set name {} set type {} | > > > > | 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 | NAME: rekey IF: defined(SQLITE_HAS_CODEC) NAME: hexkey IF: defined(SQLITE_HAS_CODEC) NAME: hexrekey TYPE: HEXKEY IF: defined(SQLITE_HAS_CODEC) NAME: activate_extensions IF: defined(SQLITE_HAS_CODEC) || defined(SQLITE_ENABLE_CEROD) NAME: soft_heap_limit } set name {} set type {} |
︙ | ︙ |
Deleted tool/wherecosttest.c.
|
| < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < |