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

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.514 2006/06/26 21:35:45 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.515 2006/06/27 01:54:26 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** Extra interface definitions for those who need them
    21     21   */
................................................................................
  1115   1115   #define JT_ERROR     0x0040    /* unknown or unsupported join type */
  1116   1116   
  1117   1117   /*
  1118   1118   ** For each nested loop in a WHERE clause implementation, the WhereInfo
  1119   1119   ** structure contains a single instance of this structure.  This structure
  1120   1120   ** is intended to be private the the where.c module and should not be
  1121   1121   ** access or modified by other modules.
         1122  +**
         1123  +** The pIdxInfo and pBestIdx fields are used to help pick the best
         1124  +** index on a virtual table.  The pIdxInfo pointer contains indexing
         1125  +** information for the i-th table in the FROM clause before reordering.
         1126  +** All the pIdxInfo pointers are freed by whereInfoFree() in where.c.
         1127  +** The pBestIdx pointer is a copy of pIdxInfo for the i-th table after
         1128  +** FROM clause ordering.  This is a little confusing so I will repeat
         1129  +** it in different words.  WhereInfo.a[i].pIdxInfo is index information 
         1130  +** for WhereInfo.pTabList.a[i].  WhereInfo.a[i].pBestInfo is the
         1131  +** index information for the i-th loop of the join.  pBestInfo is always
         1132  +** either NULL or a copy of some pIdxInfo.  So for cleanup it is 
         1133  +** sufficient to free all of the pIdxInfo pointers.
         1134  +** 
  1122   1135   */
  1123   1136   struct WhereLevel {
  1124   1137     int iFrom;            /* Which entry in the FROM clause */
  1125   1138     int flags;            /* Flags associated with this level */
  1126   1139     int iMem;             /* First memory cell used by this level */
  1127   1140     int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  1128   1141     Index *pIdx;          /* Index used.  NULL if no index */
................................................................................
  1131   1144     int brk;              /* Jump here to break out of the loop */
  1132   1145     int cont;             /* Jump here to continue with the next loop cycle */
  1133   1146     int top;              /* First instruction of interior of the loop */
  1134   1147     int op, p1, p2;       /* Opcode used to terminate the loop */
  1135   1148     int nEq;              /* Number of == or IN constraints on this loop */
  1136   1149     int nIn;              /* Number of IN operators constraining this loop */
  1137   1150     int *aInLoop;         /* Loop terminators for IN operators */
  1138         -  sqlite3_index_info *pIdxInfo;  /* Index information for virtual tables */
         1151  +  sqlite3_index_info *pBestIdx;  /* Index information for this level */
         1152  +
         1153  +  /* The following field is really not part of the current level.  But
         1154  +  ** we need a place to cache index information for each table in the
         1155  +  ** FROM clause and the WhereLevel structure is a convenient place.
         1156  +  */
         1157  +  sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
  1139   1158   };
  1140   1159   
  1141   1160   /*
  1142   1161   ** The WHERE clause processing routine has two halves.  The
  1143   1162   ** first part does the start of the WHERE loop and the second
  1144   1163   ** half does the tail of the WHERE loop.  An instance of
  1145   1164   ** this structure is returned by the first half and passed
................................................................................
  1148   1167   struct WhereInfo {
  1149   1168     Parse *pParse;
  1150   1169     SrcList *pTabList;   /* List of tables in the join */
  1151   1170     int iTop;            /* The very beginning of the WHERE loop */
  1152   1171     int iContinue;       /* Jump here to continue with next record */
  1153   1172     int iBreak;          /* Jump here to break out of the loop */
  1154   1173     int nLevel;          /* Number of nested loop */
         1174  +  sqlite3_index_info **apInfo;  /* Array of pointers to index info structures */
  1155   1175     WhereLevel a[1];     /* Information about each nest loop in the WHERE */
  1156   1176   };
  1157   1177   
  1158   1178   /*
  1159   1179   ** A NameContext defines a context in which to resolve table and column
  1160   1180   ** names.  The context consists of a list of tables (the pSrcList) field and
  1161   1181   ** a list of named expression (pEList).  The named expression list may

Changes to src/where.c.

    12     12   ** This module contains C code that generates VDBE code used to process
    13     13   ** the WHERE clause of SQL statements.  This module is reponsible for
    14     14   ** generating the code that loops through a table looking for applicable
    15     15   ** rows.  Indices are selected and used to speed the search when doing
    16     16   ** so is applicable.  Because this module is responsible for selecting
    17     17   ** indices, you might also think of this module as the "query optimizer".
    18     18   **
    19         -** $Id: where.c,v 1.223 2006/06/24 11:51:35 danielk1977 Exp $
           19  +** $Id: where.c,v 1.224 2006/06/27 01:54:26 drh Exp $
    20     20   */
    21     21   #include "sqliteInt.h"
    22     22   
    23     23   /*
    24     24   ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
    25     25   */
    26     26   #define BMS  (sizeof(Bitmask)*8)
................................................................................
   945    945     while( N>x ){
   946    946       logN += 1;
   947    947       x *= 10;
   948    948     }
   949    949     return logN;
   950    950   }
   951    951   
          952  +/*
          953  +** Two routines for printing the content of an sqlite3_index_info
          954  +** structure.  Used for testing and debugging only.  If neither
          955  +** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
          956  +** are no-ops.
          957  +*/
          958  +#if !defined(SQLITE_OMIT_VIRTUALTABLE) && \
          959  +        (defined(SQLITE_TEST) || defined(SQLITE_DEBUG))
          960  +static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
          961  +  int i;
          962  +  if( !sqlite3_where_trace ) return;
          963  +  for(i=0; i<p->nConstraint; i++){
          964  +    sqlite3DebugPrintf("  constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
          965  +       i,
          966  +       p->aConstraint[i].iColumn,
          967  +       p->aConstraint[i].iTermOffset,
          968  +       p->aConstraint[i].op,
          969  +       p->aConstraint[i].usable);
          970  +  }
          971  +  for(i=0; i<p->nOrderBy; i++){
          972  +    sqlite3DebugPrintf("  orderby[%d]: col=%d desc=%d\n",
          973  +       i,
          974  +       p->aOrderBy[i].iColumn,
          975  +       p->aOrderBy[i].desc);
          976  +  }
          977  +}
          978  +static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
          979  +  int i;
          980  +  if( !sqlite3_where_trace ) return;
          981  +  for(i=0; i<p->nConstraint; i++){
          982  +    sqlite3DebugPrintf("  usage[%d]: argvIdx=%d omit=%d\n",
          983  +       i,
          984  +       p->aConstraintUsage[i].argvIndex,
          985  +       p->aConstraintUsage[i].omit);
          986  +  }
          987  +  sqlite3DebugPrintf("  idxNum=%d\n", p->idxNum);
          988  +  sqlite3DebugPrintf("  idxStr=%s\n", p->idxStr);
          989  +  sqlite3DebugPrintf("  orderByConsumed=%d\n", p->orderByConsumed);
          990  +  sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
          991  +}
          992  +#else
          993  +#define TRACE_IDX_INPUTS(A)
          994  +#define TRACE_IDX_OUTPUTS(A)
          995  +#endif
          996  +
   952    997   #ifndef SQLITE_OMIT_VIRTUALTABLE
   953    998   /*
   954    999   ** Compute the best index for a virtual table.
   955   1000   **
   956   1001   ** The best index is computed by the xBestIndex method of the virtual
   957   1002   ** table module.  This routine is really just a wrapper that sets up
   958   1003   ** the sqlite3_index_info structure that is used to communicate with
................................................................................
   989   1034     ** allocated and initialized for this virtual table, then allocate
   990   1035     ** and initialize it now
   991   1036     */
   992   1037     pIdxInfo = *ppIdxInfo;
   993   1038     if( pIdxInfo==0 ){
   994   1039       WhereTerm *pTerm;
   995   1040       int nTerm;
         1041  +    TRACE(("Recomputing index info for %s...\n", pTab->zName));
   996   1042   
   997   1043       /* Count the number of possible WHERE clause constraints referring
   998   1044       ** to this virtual table */
   999   1045       for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
  1000   1046         if( pTerm->leftCursor != pSrc->iCursor ) continue;
  1001   1047         if( pTerm->eOperator==WO_IN ) continue;
  1002   1048         nTerm++;
................................................................................
  1121   1167     pIdxInfo->estimatedCost = SQLITE_BIG_DBL / 2.0;
  1122   1168     nOrderBy = pIdxInfo->nOrderBy;
  1123   1169     if( pIdxInfo->nOrderBy && !orderByUsable ){
  1124   1170       *(int*)&pIdxInfo->nOrderBy = 0;
  1125   1171     }
  1126   1172   
  1127   1173     sqlite3SafetyOff(pParse->db);
         1174  +  TRACE(("xBestIndex for %s\n", pTab->zName));
         1175  +  TRACE_IDX_INPUTS(pIdxInfo);
  1128   1176     rc = pTab->pVtab->pModule->xBestIndex(pTab->pVtab, pIdxInfo);
         1177  +  TRACE_IDX_OUTPUTS(pIdxInfo);
  1129   1178     if( rc!=SQLITE_OK ){
  1130   1179       if( rc==SQLITE_NOMEM ){
  1131   1180         sqlite3FailedMalloc();
  1132   1181       }else {
  1133   1182         sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
  1134   1183       }
  1135   1184       sqlite3SafetyOn(pParse->db);
  1136   1185     }else{
  1137   1186       rc = sqlite3SafetyOn(pParse->db);
  1138   1187     }
  1139         -
  1140   1188     *(int*)&pIdxInfo->nOrderBy = nOrderBy;
  1141   1189     return pIdxInfo->estimatedCost;
  1142   1190   }
  1143   1191   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  1144   1192   
  1145   1193   /*
  1146   1194   ** Find the best index for accessing a particular table.  Return a pointer
................................................................................
  1788   1836       Index *pBest = 0;           /* The best index seen so far */
  1789   1837       int bestFlags = 0;          /* Flags associated with pBest */
  1790   1838       int bestNEq = 0;            /* nEq associated with pBest */
  1791   1839       double lowestCost;          /* Cost of the pBest */
  1792   1840       int bestJ = 0;              /* The value of j */
  1793   1841       Bitmask m;                  /* Bitmask value for j or bestJ */
  1794   1842       int once = 0;               /* True when first table is seen */
  1795         -    sqlite3_index_info *pBestIndex = 0;
  1796         -    sqlite3_index_info *pIndex = 0;
         1843  +    sqlite3_index_info *pIndex; /* Current virtual index */
  1797   1844   
  1798   1845       lowestCost = SQLITE_BIG_DBL;
  1799   1846       for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
  1800   1847         int doNotReorder;  /* True if this table should not be reordered */
  1801   1848   
  1802   1849         doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0
  1803   1850                      || (j>0 && (pTabItem[-1].jointype & (JT_LEFT|JT_CROSS))!=0);
................................................................................
  1805   1852         m = getMask(&maskSet, pTabItem->iCursor);
  1806   1853         if( (m & notReady)==0 ){
  1807   1854           if( j==iFrom ) iFrom++;
  1808   1855           continue;
  1809   1856         }
  1810   1857         assert( pTabItem->pTab );
  1811   1858   #ifndef SQLITE_OMIT_VIRTUALTABLE
         1859  +      pIndex = 0;
  1812   1860         if( IsVirtual(pTabItem->pTab) ){
         1861  +        sqlite3_index_info **ppIdxInfo = &pWInfo->a[j].pIdxInfo;
  1813   1862           cost = bestVirtualIndex(pParse, &wc, pTabItem, notReady,
  1814   1863                                   ppOrderBy ? *ppOrderBy : 0, i==0,
  1815         -                                &pIndex);
         1864  +                                ppIdxInfo);
  1816   1865           flags = WHERE_VIRTUALTABLE;
         1866  +        pIndex = *ppIdxInfo;
  1817   1867           if( pIndex && pIndex->orderByConsumed ){
  1818   1868             flags = WHERE_VIRTUALTABLE | WHERE_ORDERBY;
  1819   1869           }
  1820   1870           pIdx = 0;
  1821   1871           nEq = 0;
  1822   1872         }else 
  1823   1873   #endif
................................................................................
  1830   1880           once = 1;
  1831   1881           lowestCost = cost;
  1832   1882           pBest = pIdx;
  1833   1883           bestFlags = flags;
  1834   1884           bestNEq = nEq;
  1835   1885           bestJ = j;
  1836   1886   #ifndef SQLITE_OMIT_VIRTUALTABLE
  1837         -        sqliteFree(pBestIndex);
  1838         -        pBestIndex = pIndex;
  1839         -        pIndex = 0;
  1840         -      }else{
  1841         -        sqliteFree(pIndex);
  1842         -        pIndex = 0;
         1887  +        pLevel->pBestIdx = pIndex;
  1843   1888   #endif
  1844   1889         }
  1845   1890         if( doNotReorder ) break;
  1846   1891       }
  1847   1892       TRACE(("*** Optimizer choose table %d for loop %d\n", bestJ,
  1848   1893              pLevel-pWInfo->a));
  1849   1894       if( (bestFlags & WHERE_ORDERBY)!=0 ){
................................................................................
  1851   1896       }
  1852   1897       andFlags &= bestFlags;
  1853   1898       pLevel->flags = bestFlags;
  1854   1899       pLevel->pIdx = pBest;
  1855   1900       pLevel->nEq = bestNEq;
  1856   1901       pLevel->aInLoop = 0;
  1857   1902       pLevel->nIn = 0;
  1858         -    pLevel->pIdxInfo = pBestIndex;
  1859   1903       if( pBest ){
  1860   1904         pLevel->iIdxCur = pParse->nTab++;
  1861   1905       }else{
  1862   1906         pLevel->iIdxCur = -1;
  1863   1907       }
  1864   1908       notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor);
  1865   1909       pLevel->iFrom = bestJ;
................................................................................
  1894   1938         }
  1895   1939         if( (pIx = pLevel->pIdx)!=0 ){
  1896   1940           zMsg = sqlite3MPrintf("%z WITH INDEX %s", zMsg, pIx->zName);
  1897   1941         }else if( pLevel->flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
  1898   1942           zMsg = sqlite3MPrintf("%z USING PRIMARY KEY", zMsg);
  1899   1943         }
  1900   1944   #ifndef SQLITE_OMIT_VIRTUALTABLE
  1901         -      else if( pLevel->pIdxInfo ){
  1902         -        sqlite3_index_info *pIdxInfo = pLevel->pIdxInfo;
         1945  +      else if( pLevel->pBestIdx ){
         1946  +        sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
  1903   1947           zMsg = sqlite3MPrintf("%z VIRTUAL TABLE INDEX %d:%s", zMsg,
  1904         -                    pIdxInfo->idxNum, pIdxInfo->idxStr);
         1948  +                    pBestIdx->idxNum, pBestIdx->idxStr);
  1905   1949         }
  1906   1950   #endif
  1907   1951         if( pLevel->flags & WHERE_ORDERBY ){
  1908   1952           zMsg = sqlite3MPrintf("%z ORDER BY", zMsg);
  1909   1953         }
  1910   1954         sqlite3VdbeOp3(v, OP_Explain, i, pLevel->iFrom, zMsg, P3_DYNAMIC);
  1911   1955       }
  1912   1956   #endif /* SQLITE_OMIT_EXPLAIN */
  1913   1957       pTabItem = &pTabList->a[pLevel->iFrom];
  1914   1958       pTab = pTabItem->pTab;
  1915   1959       iDb = sqlite3SchemaToIndex(pParse->db, pTab->pSchema);
  1916   1960       if( pTab->isEphem || pTab->pSelect ) continue;
  1917   1961   #ifndef SQLITE_OMIT_VIRTUALTABLE
  1918         -    if( pLevel->pIdxInfo ){
         1962  +    if( pLevel->pBestIdx ){
  1919   1963         int iCur = pTabItem->iCursor;
  1920   1964         sqlite3VdbeOp3(v, OP_VOpen, iCur, 0, (const char*)pTab->pVtab, P3_VTAB);
  1921   1965       }else
  1922   1966   #endif
  1923   1967       if( (pLevel->flags & WHERE_IDX_ONLY)==0 ){
  1924   1968         sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, OP_OpenRead);
  1925   1969         if( pTab->nCol<(sizeof(Bitmask)*8) ){
................................................................................
  1984   2028         if( !pParse->nMem ) pParse->nMem++;
  1985   2029         pLevel->iLeftJoin = pParse->nMem++;
  1986   2030         sqlite3VdbeAddOp(v, OP_MemInt, 0, pLevel->iLeftJoin);
  1987   2031         VdbeComment((v, "# init LEFT JOIN no-match flag"));
  1988   2032       }
  1989   2033   
  1990   2034   #ifndef SQLITE_OMIT_VIRTUALTABLE
  1991         -    if( pLevel->pIdxInfo ){
         2035  +    if( pLevel->pBestIdx ){
  1992   2036         /* Case 0:  The table is a virtual-table.  Use the VFilter and VNext
  1993   2037         **          to access the data.
  1994   2038         */
  1995   2039         int ii;
  1996         -      sqlite3_index_info *pIdxInfo = pLevel->pIdxInfo;
  1997         -      int nConstraint = pIdxInfo->nConstraint;
         2040  +      sqlite3_index_info *pBestIdx = pLevel->pBestIdx;
         2041  +      int nConstraint = pBestIdx->nConstraint;
  1998   2042         struct sqlite3_index_constraint_usage *aUsage =
  1999         -                                                  pIdxInfo->aConstraintUsage;
         2043  +                                                  pBestIdx->aConstraintUsage;
  2000   2044         const struct sqlite3_index_constraint *aConstraint =
  2001         -                                                  pIdxInfo->aConstraint;
         2045  +                                                  pBestIdx->aConstraint;
  2002   2046   
  2003   2047         for(ii=1; ii<=nConstraint; ii++){
  2004   2048           int j;
  2005   2049           for(j=0; j<nConstraint; j++){
  2006   2050             if( aUsage[j].argvIndex==ii ){
  2007   2051               int k = aConstraint[j].iTermOffset;
  2008   2052               sqlite3ExprCode(pParse, wc.a[k].pExpr->pRight);
  2009   2053               break;
  2010   2054             }
  2011   2055           }
  2012   2056           if( j==nConstraint ) break;
  2013   2057         }
  2014   2058         sqlite3VdbeAddOp(v, OP_Integer, ii-1, 0);
  2015         -      sqlite3VdbeAddOp(v, OP_Integer, pIdxInfo->idxNum, 0);
  2016         -      sqlite3VdbeOp3(v, OP_VFilter, iCur, brk, pIdxInfo->idxStr,
  2017         -                      pIdxInfo->needToFreeIdxStr ? P3_MPRINTF : P3_STATIC);
  2018         -      pIdxInfo->needToFreeIdxStr = 0;
  2019         -      for(ii=0; ii<pIdxInfo->nConstraint; ii++){
  2020         -        if( pIdxInfo->aConstraintUsage[ii].omit ){
         2059  +      sqlite3VdbeAddOp(v, OP_Integer, pBestIdx->idxNum, 0);
         2060  +      sqlite3VdbeOp3(v, OP_VFilter, iCur, brk, pBestIdx->idxStr,
         2061  +                      pBestIdx->needToFreeIdxStr ? P3_MPRINTF : P3_STATIC);
         2062  +      pBestIdx->needToFreeIdxStr = 0;
         2063  +      for(ii=0; ii<pBestIdx->nConstraint; ii++){
         2064  +        if( pBestIdx->aConstraintUsage[ii].omit ){
  2021   2065             disableTerm(pLevel, &wc.a[ii]);
  2022   2066           }
  2023   2067         }
  2024   2068         pLevel->op = OP_VNext;
  2025   2069         pLevel->p1 = iCur;
  2026   2070         pLevel->p2 = sqlite3VdbeCurrentAddr(v);
  2027   2071       }else