/ Check-in [8b4aa0c7]
Login

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

Overview
Comment:Completely remove the iScanRatio field. The PRAGMA index_list(TABLE) command shows the estimated row size in the forth column. It also generates a row for the table with an index name of NULL. The query planner still does not take row size estimates into account - that is the next step.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | row-size-est
Files: files | file ages | folders
SHA1: 8b4aa0c7a2122bbe60432edadf27e490e31ec987
User & Date: drh 2013-10-05 19:18:00
Context
2013-10-05
20:18
Fix an issue in the test8.c test module that arises because of the change to PRAGMA index_list(). Remove an unused local variable. check-in: 029430c5 user: drh tags: row-size-est
19:18
Completely remove the iScanRatio field. The PRAGMA index_list(TABLE) command shows the estimated row size in the forth column. It also generates a row for the table with an index name of NULL. The query planner still does not take row size estimates into account - that is the next step. check-in: 8b4aa0c7 user: drh tags: row-size-est
18:32
Improvements to the LogEst command-line tool used to convert between ordinary numbers and the LogEst representation. check-in: 5252aeb6 user: drh tags: row-size-est
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/analyze.c.

  1273   1273       }
  1274   1274       aOut[i] = v;
  1275   1275       if( *z==' ' ) z++;
  1276   1276     }
  1277   1277     if( pIndex ){
  1278   1278       if( strcmp(z, "unordered")==0 ){
  1279   1279         pIndex->bUnordered = 1;
  1280         -    }else if( sqlite3_strglob("r=[0-9]*", z)==0 ){
         1280  +    }else if( sqlite3_strglob("sz=[0-9]*", z)==0 ){
  1281   1281         int v32 = 0;
  1282         -      sqlite3GetInt32(z+2, &v32);
  1283         -      if( v32>=200 ){
  1284         -        v32 = 255;
  1285         -      }else if( v32<=0 ){
  1286         -        v32 = 1;
  1287         -      }else{
  1288         -        v32 = (128*v32)/100;
  1289         -      }
  1290         -      pIndex->iScanRatio = (u8)v32;
         1282  +      sqlite3GetInt32(z+3, &v32);
         1283  +      pIndex->szIdxRow = sqlite3LogEst(v32);
  1291   1284       }
  1292   1285     }
  1293   1286   }
  1294   1287   
  1295   1288   /*
  1296   1289   ** This callback is invoked once for each index when reading the
  1297   1290   ** sqlite_stat1 table.  

Changes to src/build.c.

  1504   1504     sqlite3_snprintf(n-k, &zStmt[k], "%s", zEnd);
  1505   1505     return zStmt;
  1506   1506   }
  1507   1507   
  1508   1508   /*
  1509   1509   ** Estimate the total row width for a table.
  1510   1510   */
  1511         -static unsigned estimatedTableWidth(const Table *pTab){
         1511  +static void estimateTableWidth(Table *pTab){
  1512   1512     unsigned wTable = 0;
  1513   1513     const Column *pTabCol;
  1514   1514     int i;
  1515   1515     for(i=pTab->nCol, pTabCol=pTab->aCol; i>0; i--, pTabCol++){
  1516   1516       wTable += pTabCol->szEst;
  1517   1517     }
  1518   1518     if( pTab->iPKey<0 ) wTable++;
  1519         -  return wTable;
         1519  +  pTab->szTabRow = sqlite3LogEst(wTable*4);
  1520   1520   }
  1521   1521   
  1522   1522   /*
  1523         -** Set the iScanRatio for an index based on estimates of the average
  1524         -** table row width and average index row width.  Estimates are derived
  1525         -** from the declared datatypes of the various columns.
         1523  +** Estimate the average size of a row for an index.
  1526   1524   */
  1527         -static void setIndexScanRatio(Index *pIdx, unsigned wTable){
         1525  +static void estimateIndexWidth(Index *pIdx){
  1528   1526     unsigned wIndex = 1;
  1529   1527     int i;
  1530   1528     const Column *aCol = pIdx->pTable->aCol;
  1531   1529     for(i=0; i<pIdx->nColumn; i++){
  1532   1530       assert( pIdx->aiColumn[i]>=0 && pIdx->aiColumn[i]<pIdx->pTable->nCol );
  1533   1531       wIndex += aCol[pIdx->aiColumn[i]].szEst;
  1534   1532     }
  1535         -  assert( 100*wIndex/wTable <= 255 );
  1536         -  pIdx->iScanRatio = (u8)(128*wIndex/wTable);
  1537         -  /* printf("%s: wIndex=%d wTable=%d ratio=%d\n",
  1538         -  ** pIdx->zName, wIndex, wTable, (100*pIdx->iScanRatio)/128); */
         1533  +  pIdx->szIdxRow = sqlite3LogEst(wIndex*4);
  1539   1534   }
  1540   1535   
  1541   1536   /*
  1542   1537   ** This routine is called to report the final ")" that terminates
  1543   1538   ** a CREATE TABLE statement.
  1544   1539   **
  1545   1540   ** The table structure that other action routines have been building
................................................................................
  1584   1579     /* Resolve names in all CHECK constraint expressions.
  1585   1580     */
  1586   1581     if( p->pCheck ){
  1587   1582       sqlite3ResolveSelfReference(pParse, p, NC_IsCheck, 0, p->pCheck);
  1588   1583     }
  1589   1584   #endif /* !defined(SQLITE_OMIT_CHECK) */
  1590   1585   
  1591         -  /* Compute the iScanRatio of implied indices */
  1592         -  wTable = estimatedTableWidth(p);
         1586  +  /* Estimate the average row size for the table and for all implied indices */
         1587  +  estimateTableWidth(p);
  1593   1588     for(pIdx=p->pIndex; pIdx; pIdx=pIdx->pNext){
  1594         -    setIndexScanRatio(pIdx, wTable);
         1589  +    estimateIndexWidth(pIdx);
  1595   1590     }
  1596   1591   
  1597   1592     /* If the db->init.busy is 1 it means we are reading the SQL off the
  1598   1593     ** "sqlite_master" or "sqlite_temp_master" table on the disk.
  1599   1594     ** So do not write to the disk again.  Extract the root page number
  1600   1595     ** for the table from the db->init.newTnum field.  (The page number
  1601   1596     ** should have been put there by the sqliteOpenCb routine.)
................................................................................
  2814   2809       }
  2815   2810       pIndex->azColl[i] = zColl;
  2816   2811       requestedSortOrder = pListItem->sortOrder & sortOrderMask;
  2817   2812       pIndex->aSortOrder[i] = (u8)requestedSortOrder;
  2818   2813       if( pTab->aCol[j].notNull==0 ) pIndex->uniqNotNull = 0;
  2819   2814     }
  2820   2815     sqlite3DefaultRowEst(pIndex);
  2821         -  if( pParse->pNewTable==0 ){
  2822         -    setIndexScanRatio(pIndex, estimatedTableWidth(pTab));
  2823         -  }
         2816  +  if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex);
  2824   2817   
  2825   2818     if( pTab==pParse->pNewTable ){
  2826   2819       /* This routine has been called to create an automatic index as a
  2827   2820       ** result of a PRIMARY KEY or UNIQUE clause on a column definition, or
  2828   2821       ** a PRIMARY KEY or UNIQUE clause following the column definitions.
  2829   2822       ** i.e. one of:
  2830   2823       **

Changes to src/pragma.c.

  1445   1445       }
  1446   1446     }
  1447   1447     break;
  1448   1448   
  1449   1449     case PragTyp_INDEX_LIST: if( zRight ){
  1450   1450       Index *pIdx;
  1451   1451       Table *pTab;
         1452  +    int i;
  1452   1453       pTab = sqlite3FindTable(db, zRight, zDb);
  1453   1454       if( pTab ){
  1454   1455         v = sqlite3GetVdbe(pParse);
  1455         -      pIdx = pTab->pIndex;
  1456         -      if( pIdx ){
  1457         -        int i = 0; 
  1458         -        sqlite3VdbeSetNumCols(v, 4);
  1459         -        pParse->nMem = 4;
  1460         -        sqlite3CodeVerifySchema(pParse, iDb);
  1461         -        sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "seq", SQLITE_STATIC);
  1462         -        sqlite3VdbeSetColName(v, 1, COLNAME_NAME, "name", SQLITE_STATIC);
  1463         -        sqlite3VdbeSetColName(v, 2, COLNAME_NAME, "unique", SQLITE_STATIC);
  1464         -        sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "r", SQLITE_STATIC);
  1465         -        while(pIdx){
  1466         -          sqlite3VdbeAddOp2(v, OP_Integer, i, 1);
  1467         -          sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
  1468         -          sqlite3VdbeAddOp2(v, OP_Integer, pIdx->onError!=OE_None, 3);
  1469         -          sqlite3VdbeAddOp2(v, OP_Integer, (pIdx->iScanRatio*100+127)/128, 4);
  1470         -          sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
  1471         -          ++i;
  1472         -          pIdx = pIdx->pNext;
  1473         -        }
         1456  +      sqlite3VdbeSetNumCols(v, 4);
         1457  +      pParse->nMem = 4;
         1458  +      sqlite3CodeVerifySchema(pParse, iDb);
         1459  +      sqlite3VdbeSetColName(v, 0, COLNAME_NAME, "seq", SQLITE_STATIC);
         1460  +      sqlite3VdbeSetColName(v, 1, COLNAME_NAME, "name", SQLITE_STATIC);
         1461  +      sqlite3VdbeSetColName(v, 2, COLNAME_NAME, "unique", SQLITE_STATIC);
         1462  +      sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "avgrowsize", SQLITE_STATIC);
         1463  +      sqlite3VdbeAddOp2(v, OP_Integer, 0, 1);
         1464  +      sqlite3VdbeAddOp2(v, OP_Null, 0, 2);
         1465  +      sqlite3VdbeAddOp2(v, OP_Integer, 1, 3);
         1466  +      sqlite3VdbeAddOp2(v, OP_Integer,
         1467  +                           (int)sqlite3LogEstToInt(pTab->szTabRow), 4);
         1468  +      sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
         1469  +      for(pIdx=pTab->pIndex, i=1; pIdx; pIdx=pIdx->pNext, i++){
         1470  +        sqlite3VdbeAddOp2(v, OP_Integer, i, 1);
         1471  +        sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
         1472  +        sqlite3VdbeAddOp2(v, OP_Integer, pIdx->onError!=OE_None, 3);
         1473  +        sqlite3VdbeAddOp2(v, OP_Integer,
         1474  +                             (int)sqlite3LogEstToInt(pIdx->szIdxRow), 4);
         1475  +        sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
  1474   1476         }
  1475   1477       }
  1476   1478     }
  1477   1479     break;
  1478   1480   
  1479   1481     case PragTyp_DATABASE_LIST: {
  1480   1482       int i;

Changes to src/select.c.

  4604   4604           ** (2013-10-03) Do not count the entires in a partial index.
  4605   4605           **
  4606   4606           ** In practice the KeyInfo structure will not be used. It is only 
  4607   4607           ** passed to keep OP_OpenRead happy.
  4608   4608           */
  4609   4609           for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
  4610   4610             if( pIdx->bUnordered==0
  4611         -           && pIdx->iScanRatio<128
         4611  +           && pIdx->szIdxRow<pTab->szTabRow
  4612   4612              && pIdx->pPartIdxWhere==0
  4613         -           && (!pBest || pIdx->iScanRatio<pBest->iScanRatio)
         4613  +           && (!pBest || pIdx->szIdxRow<pBest->szIdxRow)
  4614   4614             ){
  4615   4615               pBest = pIdx;
  4616   4616             }
  4617   4617           }
  4618   4618           if( pBest ){
  4619   4619             iRoot = pBest->tnum;
  4620   4620             pKeyInfo = sqlite3IndexKeyinfo(pParse, pBest);

Changes to src/sqliteInt.h.

  1584   1584     Schema *pSchema;         /* Schema containing this index */
  1585   1585     u8 *aSortOrder;          /* for each column: True==DESC, False==ASC */
  1586   1586     char **azColl;           /* Array of collation sequence names for index */
  1587   1587     Expr *pPartIdxWhere;     /* WHERE clause for partial indices */
  1588   1588     int tnum;                /* DB Page containing root of this index */
  1589   1589     LogEst szIdxRow;         /* Estimated average row size in bytes */
  1590   1590     u16 nColumn;             /* Number of columns in table used by this index */
  1591         -  u8 iScanRatio;           /* Scan rate relative to the main table */
  1592   1591     u8 onError;              /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  1593   1592     unsigned autoIndex:2;    /* 1==UNIQUE, 2==PRIMARY KEY, 0==CREATE INDEX */
  1594   1593     unsigned bUnordered:1;   /* Use this index for == or IN queries only */
  1595   1594     unsigned uniqNotNull:1;  /* True if UNIQUE and NOT NULL for all columns */
  1596   1595   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  1597   1596     int nSample;             /* Number of elements in aSample[] */
  1598   1597     int nSampleCol;          /* Size of IndexSample.anEq[] and so on */

Changes to src/where.c.

  4565   4565         /* Integer primary key index */
  4566   4566         pNew->wsFlags = WHERE_IPK;
  4567   4567   
  4568   4568         /* Full table scan */
  4569   4569         pNew->iSortIdx = b ? iSortIdx : 0;
  4570   4570         /* TUNING: Cost of full table scan is 3*(N + log2(N)).
  4571   4571         **  +  The extra 3 factor is to encourage the use of indexed lookups
  4572         -      **     over full scans. */
         4572  +      **     over full scans.  FIXME */
  4573   4573         pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 16;
  4574   4574         whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
  4575   4575         rc = whereLoopInsert(pBuilder, pNew);
  4576   4576         pNew->nOut = rSize;
  4577   4577         if( rc ) break;
  4578   4578       }else{
  4579   4579         Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
  4580   4580         pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
  4581   4581   
  4582   4582         /* Full scan via index */
  4583   4583         if( b
  4584   4584          || ( m==0
  4585   4585            && pProbe->bUnordered==0
  4586         -         && pProbe->iScanRatio<128
  4587   4586            && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
  4588   4587            && sqlite3GlobalConfig.bUseCis
  4589   4588            && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
  4590   4589             )
  4591   4590         ){
  4592   4591           pNew->iSortIdx = b ? iSortIdx : 0;
  4593   4592           if( m==0 ){
  4594   4593             /* TUNING: Cost of a covering index scan is K*(N + log2(N)).
  4595   4594             **  +  The extra factor K of between 1.1 (iScanRatio between 0
  4596   4595             **     and 9) and 2.8 (iScanRatio between 126 and 127) is added
  4597         -          **     to encourage the use of indexed lookups.
         4596  +          **     to encourage the use of indexed lookups.  FIXME
  4598   4597             */
  4599         -          pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + pProbe->iScanRatio/9 + 1;
         4598  +          pNew->rRun = sqlite3LogEstAdd(rSize,rLogSize) + 10;
  4600   4599           }else{
  4601   4600             assert( b!=0 ); 
  4602   4601             /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
  4603   4602             ** which we will simplify to just N*log2(N) */
  4604   4603             pNew->rRun = rSize + rLogSize;
  4605   4604           }
  4606   4605           whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);