/ Check-in [bf7b8d86]
Login

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

Overview
Comment:Merge automatic index changes into the trunk.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:bf7b8d863665870a38f0b2335cc71de856a515b4
User & Date: drh 2010-04-08 01:16:20
References
2011-07-08
16:00 Ticket [54844eea] Incorrect caching of sub-query results in the FROM clause of a scalar sub-query. status still Open with 3 other changes artifact: cb377e71 user: dan
Context
2010-04-08
11:35
Make sure F_OK, R_OK, and W_OK are defined in test_demovfs.c. Define them manually if they are not. This is necessary to get the module to compile on some systems. check-in: 7c8afc32 user: drh tags: trunk
01:16
Merge automatic index changes into the trunk. check-in: bf7b8d86 user: drh tags: trunk
00:40
When constructing automatic indices do not include the same column more than once. Closed-Leaf check-in: d067d9f7 user: drh tags: experimental
2010-04-07
20:29
When rolling back a savepoint to the beginning of the transaction, make sure to initialize the database size in the btree layer correctly even if the database size field of the header is zeroed. check-in: a3540c6a user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/ctime.c.

   166    166     "OMIT_AUTHORIZATION",
   167    167   #endif
   168    168   #ifdef SQLITE_OMIT_AUTOINCREMENT
   169    169     "OMIT_AUTOINCREMENT",
   170    170   #endif
   171    171   #ifdef SQLITE_OMIT_AUTOINIT
   172    172     "OMIT_AUTOINIT",
          173  +#endif
          174  +#ifdef SQLITE_OMIT_AUTOMATIC_INDEX
          175  +  "OMIT_AUTOMATIC_INDEX",
   173    176   #endif
   174    177   #ifdef SQLITE_OMIT_AUTOVACUUM
   175    178     "OMIT_AUTOVACUUM",
   176    179   #endif
   177    180   #ifdef SQLITE_OMIT_BETWEEN_OPTIMIZATION
   178    181     "OMIT_BETWEEN_OPTIMIZATION",
   179    182   #endif

Changes to src/main.c.

  1604   1604     db->aDb = db->aDbStatic;
  1605   1605   
  1606   1606     assert( sizeof(db->aLimit)==sizeof(aHardLimit) );
  1607   1607     memcpy(db->aLimit, aHardLimit, sizeof(db->aLimit));
  1608   1608     db->autoCommit = 1;
  1609   1609     db->nextAutovac = -1;
  1610   1610     db->nextPagesize = 0;
  1611         -  db->flags |= SQLITE_ShortColNames
         1611  +  db->flags |= SQLITE_ShortColNames | SQLITE_AutoIndex
  1612   1612   #if SQLITE_DEFAULT_FILE_FORMAT<4
  1613   1613                    | SQLITE_LegacyFileFmt
  1614   1614   #endif
  1615   1615   #ifdef SQLITE_ENABLE_LOAD_EXTENSION
  1616   1616                    | SQLITE_LoadExtension
  1617   1617   #endif
  1618   1618   #if SQLITE_DEFAULT_RECURSIVE_TRIGGERS

Changes to src/pragma.c.

   169    169       { "full_column_names",        SQLITE_FullColNames  },
   170    170       { "short_column_names",       SQLITE_ShortColNames },
   171    171       { "count_changes",            SQLITE_CountRows     },
   172    172       { "empty_result_callbacks",   SQLITE_NullCallback  },
   173    173       { "legacy_file_format",       SQLITE_LegacyFileFmt },
   174    174       { "fullfsync",                SQLITE_FullFSync     },
   175    175       { "reverse_unordered_selects", SQLITE_ReverseOrder  },
          176  +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
          177  +    { "automatic_index",          SQLITE_AutoIndex     },
          178  +#endif
   176    179   #ifdef SQLITE_DEBUG
   177    180       { "sql_trace",                SQLITE_SqlTrace      },
   178    181       { "vdbe_listing",             SQLITE_VdbeListing   },
   179    182       { "vdbe_trace",               SQLITE_VdbeTrace     },
   180    183   #endif
   181    184   #ifndef SQLITE_OMIT_CHECK
   182    185       { "ignore_check_constraints", SQLITE_IgnoreChecks  },

Changes to src/prepare.c.

   575    575         }
   576    576       }
   577    577     }
   578    578   
   579    579     sqlite3VtabUnlockList(db);
   580    580   
   581    581     pParse->db = db;
          582  +  pParse->nQueryLoop = (double)1;
   582    583     if( nBytes>=0 && (nBytes==0 || zSql[nBytes-1]!=0) ){
   583    584       char *zSqlCopy;
   584    585       int mxLen = db->aLimit[SQLITE_LIMIT_SQL_LENGTH];
   585    586       testcase( nBytes==mxLen );
   586    587       testcase( nBytes==mxLen+1 );
   587    588       if( nBytes>mxLen ){
   588    589         sqlite3Error(db, SQLITE_TOOBIG, "statement too long");
................................................................................
   596    597         pParse->zTail = &zSql[pParse->zTail-zSqlCopy];
   597    598       }else{
   598    599         pParse->zTail = &zSql[nBytes];
   599    600       }
   600    601     }else{
   601    602       sqlite3RunParser(pParse, zSql, &zErrMsg);
   602    603     }
          604  +  assert( 1==(int)pParse->nQueryLoop );
   603    605   
   604    606     if( db->mallocFailed ){
   605    607       pParse->rc = SQLITE_NOMEM;
   606    608     }
   607    609     if( pParse->rc==SQLITE_DONE ) pParse->rc = SQLITE_OK;
   608    610     if( pParse->checkSchema ){
   609    611       schemaIsValid(pParse);

Changes to src/sqlite.h.in.

  5195   5195   ** careful use of indices.</dd>
  5196   5196   **
  5197   5197   ** <dt>SQLITE_STMTSTATUS_SORT</dt>
  5198   5198   ** <dd>^This is the number of sort operations that have occurred.
  5199   5199   ** A non-zero value in this counter may indicate an opportunity to
  5200   5200   ** improvement performance through careful use of indices.</dd>
  5201   5201   **
         5202  +** <dt>SQLITE_STMTSTATUS_AUTOINDEX</dt>
         5203  +** <dd>^This is the number of rows inserted into transient indices that
         5204  +** were created automatically in order to help joins run faster.
         5205  +** A non-zero value in this counter may indicate an opportunity to
         5206  +** improvement performance by adding permanent indices that do not
         5207  +** need to be reinitialized each time the statement is run.</dd>
         5208  +**
  5202   5209   ** </dl>
  5203   5210   */
  5204   5211   #define SQLITE_STMTSTATUS_FULLSCAN_STEP     1
  5205   5212   #define SQLITE_STMTSTATUS_SORT              2
         5213  +#define SQLITE_STMTSTATUS_AUTOINDEX         3
  5206   5214   
  5207   5215   /*
  5208   5216   ** CAPI3REF: Custom Page Cache Object
  5209   5217   **
  5210   5218   ** The sqlite3_pcache type is opaque.  It is implemented by
  5211   5219   ** the pluggable module.  The SQLite core has no knowledge of
  5212   5220   ** its size or internal structure and never deals with the

Changes to src/sqliteInt.h.

   297    297   
   298    298   /*
   299    299   ** If compiling for a processor that lacks floating point support,
   300    300   ** substitute integer for floating-point
   301    301   */
   302    302   #ifdef SQLITE_OMIT_FLOATING_POINT
   303    303   # define double sqlite_int64
          304  +# define float sqlite_int64
   304    305   # define LONGDOUBLE_TYPE sqlite_int64
   305    306   # ifndef SQLITE_BIG_DBL
   306    307   #   define SQLITE_BIG_DBL (((sqlite3_int64)1)<<50)
   307    308   # endif
   308    309   # define SQLITE_OMIT_DATETIME_FUNCS 1
   309    310   # define SQLITE_OMIT_TRACE 1
   310    311   # undef SQLITE_MIXED_ENDIAN_64BIT_FLOAT
................................................................................
   907    908   #define SQLITE_LegacyFileFmt  0x00100000  /* Create new databases in format 1 */
   908    909   #define SQLITE_FullFSync      0x00200000  /* Use full fsync on the backend */
   909    910   #define SQLITE_LoadExtension  0x00400000  /* Enable load_extension */
   910    911   #define SQLITE_RecoveryMode   0x00800000  /* Ignore schema errors */
   911    912   #define SQLITE_ReverseOrder   0x01000000  /* Reverse unordered SELECTs */
   912    913   #define SQLITE_RecTriggers    0x02000000  /* Enable recursive triggers */
   913    914   #define SQLITE_ForeignKeys    0x04000000  /* Enforce foreign key constraints  */
          915  +#define SQLITE_AutoIndex      0x08000000  /* Enable automatic indexes */
   914    916   
   915    917   /*
   916    918   ** Bits of the sqlite3.flags field that are used by the
   917    919   ** sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS,...) interface.
   918    920   ** These must be the low-order bits of the flags field.
   919    921   */
   920    922   #define SQLITE_QueryFlattener 0x01        /* Disable query flattening */
................................................................................
  1769   1771   ** such a table must be a simple name: ID.  But in SQLite, the table can
  1770   1772   ** now be identified by a database name, a dot, then the table name: ID.ID.
  1771   1773   **
  1772   1774   ** The jointype starts out showing the join type between the current table
  1773   1775   ** and the next table on the list.  The parser builds the list this way.
  1774   1776   ** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each
  1775   1777   ** jointype expresses the join between the table and the previous table.
         1778  +**
         1779  +** In the colUsed field, the high-order bit (bit 63) is set if the table
         1780  +** contains more than 63 columns and the 64-th or later column is used.
  1776   1781   */
  1777   1782   struct SrcList {
  1778   1783     i16 nSrc;        /* Number of tables or subqueries in the FROM clause */
  1779   1784     i16 nAlloc;      /* Number of entries allocated in a[] below */
  1780   1785     struct SrcList_item {
  1781   1786       char *zDatabase;  /* Name of database holding this table */
  1782   1787       char *zName;      /* Name of the table */
................................................................................
  1880   1885   ** and the WhereInfo.wctrlFlags member.
  1881   1886   */
  1882   1887   #define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */
  1883   1888   #define WHERE_ORDERBY_MIN      0x0001 /* ORDER BY processing for min() func */
  1884   1889   #define WHERE_ORDERBY_MAX      0x0002 /* ORDER BY processing for max() func */
  1885   1890   #define WHERE_ONEPASS_DESIRED  0x0004 /* Want to do one-pass UPDATE/DELETE */
  1886   1891   #define WHERE_DUPLICATES_OK    0x0008 /* Ok to return a row more than once */
  1887         -#define WHERE_OMIT_OPEN        0x0010 /* Table cursor are already open */
         1892  +#define WHERE_OMIT_OPEN        0x0010 /* Table cursors are already open */
  1888   1893   #define WHERE_OMIT_CLOSE       0x0020 /* Omit close of table & index cursors */
  1889   1894   #define WHERE_FORCE_TABLE      0x0040 /* Do not use an index-only search */
  1890   1895   #define WHERE_ONETABLE_ONLY    0x0080 /* Only code the 1st table in pTabList */
  1891   1896   
  1892   1897   /*
  1893   1898   ** The WHERE clause processing routine has two halves.  The
  1894   1899   ** first part does the start of the WHERE loop and the second
................................................................................
  1903   1908     u8 untestedTerms;    /* Not all WHERE terms resolved by outer loop */
  1904   1909     SrcList *pTabList;             /* List of tables in the join */
  1905   1910     int iTop;                      /* The very beginning of the WHERE loop */
  1906   1911     int iContinue;                 /* Jump here to continue with next record */
  1907   1912     int iBreak;                    /* Jump here to break out of the loop */
  1908   1913     int nLevel;                    /* Number of nested loop */
  1909   1914     struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
         1915  +  double savedNQueryLoop;        /* pParse->nQueryLoop outside the WHERE loop */
  1910   1916     WhereLevel a[1];               /* Information about each nest loop in WHERE */
  1911   1917   };
  1912   1918   
  1913   1919   /*
  1914   1920   ** A NameContext defines a context in which to resolve table and column
  1915   1921   ** names.  The context consists of a list of tables (the pSrcList) field and
  1916   1922   ** a list of named expression (pEList).  The named expression list may
................................................................................
  2144   2150     Parse *pToplevel;    /* Parse structure for main program (or NULL) */
  2145   2151     Table *pTriggerTab;  /* Table triggers are being coded for */
  2146   2152     u32 oldmask;         /* Mask of old.* columns referenced */
  2147   2153     u32 newmask;         /* Mask of new.* columns referenced */
  2148   2154     u8 eTriggerOp;       /* TK_UPDATE, TK_INSERT or TK_DELETE */
  2149   2155     u8 eOrconf;          /* Default ON CONFLICT policy for trigger steps */
  2150   2156     u8 disableTriggers;  /* True to disable triggers */
         2157  +  double nQueryLoop;   /* Estimated number of iterations of a query */
  2151   2158   
  2152   2159     /* Above is constant between recursions.  Below is reset before and after
  2153   2160     ** each recursion */
  2154   2161   
  2155   2162     int nVar;            /* Number of '?' variables seen in the SQL so far */
  2156   2163     int nVarExpr;        /* Number of used slots in apVarExpr[] */
  2157   2164     int nVarExprAlloc;   /* Number of allocated slots in apVarExpr[] */

Changes to src/tclsqlite.c.

   128    128     int rc;                    /* Return code of most recent sqlite3_exec() */
   129    129     Tcl_Obj *pCollateNeeded;   /* Collation needed script */
   130    130     SqlPreparedStmt *stmtList; /* List of prepared statements*/
   131    131     SqlPreparedStmt *stmtLast; /* Last statement in the list */
   132    132     int maxStmt;               /* The next maximum number of stmtList */
   133    133     int nStmt;                 /* Number of statements in stmtList */
   134    134     IncrblobChannel *pIncrblob;/* Linked list of open incrblob channels */
   135         -  int nStep, nSort;          /* Statistics for most recent operation */
          135  +  int nStep, nSort, nIndex;  /* Statistics for most recent operation */
   136    136     int nTransaction;          /* Number of nested [transaction] methods */
   137    137   };
   138    138   
   139    139   struct IncrblobChannel {
   140    140     sqlite3_blob *pBlob;      /* sqlite3 blob handle */
   141    141     SqliteDb *pDb;            /* Associated database connection */
   142    142     int iSeek;                /* Current seek offset */
................................................................................
  1347   1347         if( p->pArray ){
  1348   1348           dbEvalRowInfo(p, 0, 0);
  1349   1349         }
  1350   1350         rcs = sqlite3_reset(pStmt);
  1351   1351   
  1352   1352         pDb->nStep = sqlite3_stmt_status(pStmt,SQLITE_STMTSTATUS_FULLSCAN_STEP,1);
  1353   1353         pDb->nSort = sqlite3_stmt_status(pStmt,SQLITE_STMTSTATUS_SORT,1);
         1354  +      pDb->nIndex = sqlite3_stmt_status(pStmt,SQLITE_STMTSTATUS_AUTOINDEX,1);
  1354   1355         dbReleaseColumnNames(p);
  1355   1356         p->pPreStmt = 0;
  1356   1357   
  1357   1358         if( rcs!=SQLITE_OK ){
  1358   1359           /* If a run-time error occurs, report the error and stop reading
  1359   1360           ** the SQL.  */
  1360   1361           Tcl_SetObjResult(pDb->interp, dbTextToObj(sqlite3_errmsg(pDb->db)));
................................................................................
  2524   2525         rc = TCL_ERROR;
  2525   2526       }
  2526   2527       sqlite3_close(pSrc);
  2527   2528       break;
  2528   2529     }
  2529   2530   
  2530   2531     /*
  2531         -  **     $db status (step|sort)
         2532  +  **     $db status (step|sort|autoindex)
  2532   2533     **
  2533   2534     ** Display SQLITE_STMTSTATUS_FULLSCAN_STEP or 
  2534   2535     ** SQLITE_STMTSTATUS_SORT for the most recent eval.
  2535   2536     */
  2536   2537     case DB_STATUS: {
  2537   2538       int v;
  2538   2539       const char *zOp;
................................................................................
  2541   2542         return TCL_ERROR;
  2542   2543       }
  2543   2544       zOp = Tcl_GetString(objv[2]);
  2544   2545       if( strcmp(zOp, "step")==0 ){
  2545   2546         v = pDb->nStep;
  2546   2547       }else if( strcmp(zOp, "sort")==0 ){
  2547   2548         v = pDb->nSort;
         2549  +    }else if( strcmp(zOp, "autoindex")==0 ){
         2550  +      v = pDb->nIndex;
  2548   2551       }else{
  2549         -      Tcl_AppendResult(interp, "bad argument: should be step or sort", 
         2552  +      Tcl_AppendResult(interp, 
         2553  +            "bad argument: should be autoindex, step, or sort", 
  2550   2554               (char*)0);
  2551   2555         return TCL_ERROR;
  2552   2556       }
  2553   2557       Tcl_SetObjResult(interp, Tcl_NewIntObj(v));
  2554   2558       break;
  2555   2559     }
  2556   2560     

Changes to src/test1.c.

  2021   2021   
  2022   2022     static const struct {
  2023   2023       const char *zName;
  2024   2024       int op;
  2025   2025     } aOp[] = {
  2026   2026       { "SQLITE_STMTSTATUS_FULLSCAN_STEP",   SQLITE_STMTSTATUS_FULLSCAN_STEP   },
  2027   2027       { "SQLITE_STMTSTATUS_SORT",            SQLITE_STMTSTATUS_SORT            },
         2028  +    { "SQLITE_STMTSTATUS_AUTOINDEX",       SQLITE_STMTSTATUS_AUTOINDEX       },
  2028   2029     };
  2029   2030     if( objc!=4 ){
  2030   2031       Tcl_WrongNumArgs(interp, 1, objv, "STMT PARAMETER RESETFLAG");
  2031   2032       return TCL_ERROR;
  2032   2033     }
  2033   2034     if( getStmtPointer(interp, Tcl_GetString(objv[1]), &pStmt) ) return TCL_ERROR;
  2034   2035     zOpName = Tcl_GetString(objv[2]);

Changes to src/test_config.c.

   122    122   #endif
   123    123   
   124    124   #ifdef SQLITE_OMIT_AUTOINCREMENT
   125    125     Tcl_SetVar2(interp, "sqlite_options", "autoinc", "0", TCL_GLOBAL_ONLY);
   126    126   #else
   127    127     Tcl_SetVar2(interp, "sqlite_options", "autoinc", "1", TCL_GLOBAL_ONLY);
   128    128   #endif
          129  +
          130  +#ifdef SQLITE_OMIT_AUTOMATIC_INDEX
          131  +  Tcl_SetVar2(interp, "sqlite_options", "autoindex", "0", TCL_GLOBAL_ONLY);
          132  +#else
          133  +  Tcl_SetVar2(interp, "sqlite_options", "autoindex", "1", TCL_GLOBAL_ONLY);
          134  +#endif
   129    135   
   130    136   #ifdef SQLITE_OMIT_AUTOVACUUM
   131    137     Tcl_SetVar2(interp, "sqlite_options", "autovacuum", "0", TCL_GLOBAL_ONLY);
   132    138   #else
   133    139     Tcl_SetVar2(interp, "sqlite_options", "autovacuum", "1", TCL_GLOBAL_ONLY);
   134    140   #endif /* SQLITE_OMIT_AUTOVACUUM */
   135    141   #if !defined(SQLITE_DEFAULT_AUTOVACUUM)

Changes to src/trigger.c.

   822    822     memset(&sNC, 0, sizeof(sNC));
   823    823     sNC.pParse = pSubParse;
   824    824     pSubParse->db = db;
   825    825     pSubParse->pTriggerTab = pTab;
   826    826     pSubParse->pToplevel = pTop;
   827    827     pSubParse->zAuthContext = pTrigger->zName;
   828    828     pSubParse->eTriggerOp = pTrigger->op;
          829  +  pSubParse->nQueryLoop = pParse->nQueryLoop;
   829    830   
   830    831     v = sqlite3GetVdbe(pSubParse);
   831    832     if( v ){
   832    833       VdbeComment((v, "Start: %s.%s (%s %s%s%s ON %s)", 
   833    834         pTrigger->zName, onErrorText(orconf),
   834    835         (pTrigger->tr_tm==TRIGGER_BEFORE ? "BEFORE" : "AFTER"),
   835    836           (pTrigger->op==TK_UPDATE ? "UPDATE" : ""),

Changes to src/vdbe.c.

  1379   1379   
  1380   1380     assert( n==0 || (pOp->p2>0 && pOp->p2+n<=p->nMem+1) );
  1381   1381     assert( pOp->p3<pOp->p2 || pOp->p3>=pOp->p2+n );
  1382   1382     pArg = &aMem[pOp->p2];
  1383   1383     for(i=0; i<n; i++, pArg++){
  1384   1384       apVal[i] = pArg;
  1385   1385       sqlite3VdbeMemStoreType(pArg);
  1386         -    REGISTER_TRACE(pOp->p2, pArg);
         1386  +    REGISTER_TRACE(pOp->p2+i, pArg);
  1387   1387     }
  1388   1388   
  1389   1389     assert( pOp->p4type==P4_FUNCDEF || pOp->p4type==P4_VDBEFUNC );
  1390   1390     if( pOp->p4type==P4_FUNCDEF ){
  1391   1391       ctx.pFunc = pOp->p4.pFunc;
  1392   1392       ctx.pVdbeFunc = 0;
  1393   1393     }else{
................................................................................
  3078   3078   **
  3079   3079   ** This opcode was once called OpenTemp.  But that created
  3080   3080   ** confusion because the term "temp table", might refer either
  3081   3081   ** to a TEMP table at the SQL level, or to a table opened by
  3082   3082   ** this opcode.  Then this opcode was call OpenVirtual.  But
  3083   3083   ** that created confusion with the whole virtual-table idea.
  3084   3084   */
         3085  +/* Opcode: OpenAutoindex P1 P2 * P4 *
         3086  +**
         3087  +** This opcode works the same as OP_OpenEphemeral.  It has a
         3088  +** different name to distinguish its use.  Tables created using
         3089  +** by this opcode will be used for automatically created transient
         3090  +** indices in joins.
         3091  +*/
         3092  +case OP_OpenAutoindex: 
  3085   3093   case OP_OpenEphemeral: {
  3086   3094     VdbeCursor *pCx;
  3087   3095     static const int openFlags = 
  3088   3096         SQLITE_OPEN_READWRITE |
  3089   3097         SQLITE_OPEN_CREATE |
  3090   3098         SQLITE_OPEN_EXCLUSIVE |
  3091   3099         SQLITE_OPEN_DELETEONCLOSE |

Changes to src/vdbeInt.h.

   307    307     u8 usesStmtJournal;     /* True if uses a statement journal */
   308    308     u8 readOnly;            /* True for read-only statements */
   309    309     u8 isPrepareV2;         /* True if prepared with prepare_v2() */
   310    310     int nChange;            /* Number of db changes made since last reset */
   311    311     int btreeMask;          /* Bitmask of db->aDb[] entries referenced */
   312    312     i64 startTime;          /* Time when query started - used for profiling */
   313    313     BtreeMutexArray aMutex; /* An array of Btree used here and needing locks */
   314         -  int aCounter[2];        /* Counters used by sqlite3_stmt_status() */
          314  +  int aCounter[3];        /* Counters used by sqlite3_stmt_status() */
   315    315     char *zSql;             /* Text of the SQL statement that generated this */
   316    316     void *pFree;            /* Free this when deleting the vdbe */
   317    317     i64 nFkConstraint;      /* Number of imm. FK constraints this VM */
   318    318     i64 nStmtDefCons;       /* Number of def. constraints when stmt started */
   319    319     int iStatement;         /* Statement number (or 0 if has not opened stmt) */
   320    320   #ifdef SQLITE_DEBUG
   321    321     FILE *trace;            /* Write an execution trace here, if not NULL */

Changes to src/vtab.c.

   653    653   
   654    654     pParse = sqlite3StackAllocZero(db, sizeof(*pParse));
   655    655     if( pParse==0 ){
   656    656       rc = SQLITE_NOMEM;
   657    657     }else{
   658    658       pParse->declareVtab = 1;
   659    659       pParse->db = db;
          660  +    pParse->nQueryLoop = 1;
   660    661     
   661    662       if( SQLITE_OK==sqlite3RunParser(pParse, zCreateTable, &zErr) 
   662    663        && pParse->pNewTable
   663    664        && !db->mallocFailed
   664    665        && !pParse->pNewTable->pSelect
   665    666        && (pParse->pNewTable->tabFlags & TF_Virtual)==0
   666    667       ){

Changes to src/where.c.

   231    231   #define WHERE_ROWID_EQ     0x00001000  /* rowid=EXPR or rowid IN (...) */
   232    232   #define WHERE_ROWID_RANGE  0x00002000  /* rowid<EXPR and/or rowid>EXPR */
   233    233   #define WHERE_COLUMN_EQ    0x00010000  /* x=EXPR or x IN (...) or x IS NULL */
   234    234   #define WHERE_COLUMN_RANGE 0x00020000  /* x<EXPR and/or x>EXPR */
   235    235   #define WHERE_COLUMN_IN    0x00040000  /* x IN (...) */
   236    236   #define WHERE_COLUMN_NULL  0x00080000  /* x IS NULL */
   237    237   #define WHERE_INDEXED      0x000f0000  /* Anything that uses an index */
          238  +#define WHERE_NOT_FULLSCAN 0x000f3000  /* Does not do a full table scan */
   238    239   #define WHERE_IN_ABLE      0x000f1000  /* Able to support an IN operator */
   239    240   #define WHERE_TOP_LIMIT    0x00100000  /* x<EXPR or x<=EXPR constraint */
   240    241   #define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
   241    242   #define WHERE_IDX_ONLY     0x00800000  /* Use index only - omit table */
   242    243   #define WHERE_ORDERBY      0x01000000  /* Output will appear in correct order */
   243    244   #define WHERE_REVERSE      0x02000000  /* Scan in reverse order */
   244    245   #define WHERE_UNIQUE       0x04000000  /* Selects no more than one row */
   245    246   #define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
   246    247   #define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
          248  +#define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
   247    249   
   248    250   /*
   249    251   ** Initialize a preallocated WhereClause structure.
   250    252   */
   251    253   static void whereClauseInit(
   252    254     WhereClause *pWC,        /* The WhereClause to be initialized */
   253    255     Parse *pParse,           /* The parsing context */
................................................................................
  1631   1633           pCost->plan.u.pTerm = pTerm;
  1632   1634         }
  1633   1635       }
  1634   1636     }
  1635   1637   #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
  1636   1638   }
  1637   1639   
         1640  +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
         1641  +/*
         1642  +** Return TRUE if the WHERE clause term pTerm is of a form where it
         1643  +** could be used with an index to access pSrc, assuming an appropriate
         1644  +** index existed.
         1645  +*/
         1646  +static int termCanDriveIndex(
         1647  +  WhereTerm *pTerm,              /* WHERE clause term to check */
         1648  +  struct SrcList_item *pSrc,     /* Table we are trying to access */
         1649  +  Bitmask notReady               /* Tables in outer loops of the join */
         1650  +){
         1651  +  char aff;
         1652  +  if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
         1653  +  if( pTerm->eOperator!=WO_EQ ) return 0;
         1654  +  if( (pTerm->prereqRight & notReady)!=0 ) return 0;
         1655  +  aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
         1656  +  if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
         1657  +  return 1;
         1658  +}
         1659  +#endif
         1660  +
         1661  +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
         1662  +/*
         1663  +** If the query plan for pSrc specified in pCost is a full table scan
         1664  +** and indexing is allows (if there is no NOT INDEXED clause) and it
         1665  +** possible to construct a transient index that would perform better
         1666  +** than a full table scan even when the cost of constructing the index
         1667  +** is taken into account, then alter the query plan to use the
         1668  +** transient index.
         1669  +*/
         1670  +static void bestAutomaticIndex(
         1671  +  Parse *pParse,              /* The parsing context */
         1672  +  WhereClause *pWC,           /* The WHERE clause */
         1673  +  struct SrcList_item *pSrc,  /* The FROM clause term to search */
         1674  +  Bitmask notReady,           /* Mask of cursors that are not available */
         1675  +  WhereCost *pCost            /* Lowest cost query plan */
         1676  +){
         1677  +  double nTableRow;           /* Rows in the input table */
         1678  +  double logN;                /* log(nTableRow) */
         1679  +  double costTempIdx;         /* per-query cost of the transient index */
         1680  +  WhereTerm *pTerm;           /* A single term of the WHERE clause */
         1681  +  WhereTerm *pWCEnd;          /* End of pWC->a[] */
         1682  +  Table *pTable;              /* Table tht might be indexed */
         1683  +
         1684  +  if( (pParse->db->flags & SQLITE_AutoIndex)==0 ){
         1685  +    /* Automatic indices are disabled at run-time */
         1686  +    return;
         1687  +  }
         1688  +  if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
         1689  +    /* We already have some kind of index in use for this query. */
         1690  +    return;
         1691  +  }
         1692  +  if( pSrc->notIndexed ){
         1693  +    /* The NOT INDEXED clause appears in the SQL. */
         1694  +    return;
         1695  +  }
         1696  +
         1697  +  assert( pParse->nQueryLoop >= (double)1 );
         1698  +  nTableRow = pSrc->pIndex ? pSrc->pIndex->aiRowEst[0] : 1000000;
         1699  +  logN = estLog(nTableRow);
         1700  +  costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
         1701  +  if( costTempIdx>=pCost->rCost ){
         1702  +    /* The cost of creating the transient table would be greater than
         1703  +    ** doing the full table scan */
         1704  +    return;
         1705  +  }
         1706  +
         1707  +  /* Search for any equality comparison term */
         1708  +  pTable = pSrc->pTab;
         1709  +  pWCEnd = &pWC->a[pWC->nTerm];
         1710  +  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
         1711  +    if( termCanDriveIndex(pTerm, pSrc, notReady) ){
         1712  +      WHERETRACE(("auto-index reduces cost from %.2f to %.2f\n",
         1713  +                    pCost->rCost, costTempIdx));
         1714  +      pCost->rCost = costTempIdx;
         1715  +      pCost->nRow = logN + 1;
         1716  +      pCost->plan.wsFlags = WHERE_TEMP_INDEX;
         1717  +      pCost->used = pTerm->prereqRight;
         1718  +      break;
         1719  +    }
         1720  +  }
         1721  +}
         1722  +#else
         1723  +# define bestAutomaticIndex(A,B,C,D,E)  /* no-op */
         1724  +#endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
         1725  +
         1726  +
         1727  +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
         1728  +/*
         1729  +** Generate code to construct the Index object for an automatic index
         1730  +** and to set up the WhereLevel object pLevel so that the code generator
         1731  +** makes use of the automatic index.
         1732  +*/
         1733  +static void constructAutomaticIndex(
         1734  +  Parse *pParse,              /* The parsing context */
         1735  +  WhereClause *pWC,           /* The WHERE clause */
         1736  +  struct SrcList_item *pSrc,  /* The FROM clause term to get the next index */
         1737  +  Bitmask notReady,           /* Mask of cursors that are not available */
         1738  +  WhereLevel *pLevel          /* Write new index here */
         1739  +){
         1740  +  int nColumn;                /* Number of columns in the constructed index */
         1741  +  WhereTerm *pTerm;           /* A single term of the WHERE clause */
         1742  +  WhereTerm *pWCEnd;          /* End of pWC->a[] */
         1743  +  int nByte;                  /* Byte of memory needed for pIdx */
         1744  +  Index *pIdx;                /* Object describing the transient index */
         1745  +  Vdbe *v;                    /* Prepared statement under construction */
         1746  +  int regIsInit;              /* Register set by initialization */
         1747  +  int addrInit;               /* Address of the initialization bypass jump */
         1748  +  Table *pTable;              /* The table being indexed */
         1749  +  KeyInfo *pKeyinfo;          /* Key information for the index */   
         1750  +  int addrTop;                /* Top of the index fill loop */
         1751  +  int regRecord;              /* Register holding an index record */
         1752  +  int n;                      /* Column counter */
         1753  +  int i;                      /* Loop counter */
         1754  +  int mxBitCol;               /* Maximum column in pSrc->colUsed */
         1755  +  CollSeq *pColl;             /* Collating sequence to on a column */
         1756  +  Bitmask idxCols;            /* Bitmap of columns used for indexing */
         1757  +  Bitmask extraCols;          /* Bitmap of additional columns */
         1758  +
         1759  +  /* Generate code to skip over the creation and initialization of the
         1760  +  ** transient index on 2nd and subsequent iterations of the loop. */
         1761  +  v = pParse->pVdbe;
         1762  +  assert( v!=0 );
         1763  +  regIsInit = ++pParse->nMem;
         1764  +  addrInit = sqlite3VdbeAddOp1(v, OP_If, regIsInit);
         1765  +  sqlite3VdbeAddOp2(v, OP_Integer, 1, regIsInit);
         1766  +
         1767  +  /* Count the number of columns that will be added to the index
         1768  +  ** and used to match WHERE clause constraints */
         1769  +  nColumn = 0;
         1770  +  pTable = pSrc->pTab;
         1771  +  pWCEnd = &pWC->a[pWC->nTerm];
         1772  +  idxCols = 0;
         1773  +  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
         1774  +    if( termCanDriveIndex(pTerm, pSrc, notReady) ){
         1775  +      int iCol = pTerm->u.leftColumn;
         1776  +      Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
         1777  +      if( (idxCols & cMask)==0 ){
         1778  +        nColumn++;
         1779  +        idxCols |= cMask;
         1780  +      }
         1781  +    }
         1782  +  }
         1783  +  assert( nColumn>0 );
         1784  +  pLevel->plan.nEq = nColumn;
         1785  +
         1786  +  /* Count the number of additional columns needed to create a
         1787  +  ** covering index.  A "covering index" is an index that contains all
         1788  +  ** columns that are needed by the query.  With a covering index, the
         1789  +  ** original table never needs to be accessed.  Automatic indices must
         1790  +  ** be a covering index because the index will not be updated if the
         1791  +  ** original table changes and the index and table cannot both be used
         1792  +  ** if they go out of sync.
         1793  +  */
         1794  +  extraCols = pSrc->colUsed & (~idxCols | (((Bitmask)1)<<(BMS-1)));
         1795  +  mxBitCol = (pTable->nCol >= BMS-1) ? BMS-1 : pTable->nCol;
         1796  +  for(i=0; i<mxBitCol; i++){
         1797  +    if( extraCols & (1<<i) ) nColumn++;
         1798  +  }
         1799  +  if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
         1800  +    nColumn += pTable->nCol - BMS + 1;
         1801  +  }
         1802  +  pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WO_EQ;
         1803  +
         1804  +  /* Construct the Index object to describe this index */
         1805  +  nByte = sizeof(Index);
         1806  +  nByte += nColumn*sizeof(int);     /* Index.aiColumn */
         1807  +  nByte += nColumn*sizeof(char*);   /* Index.azColl */
         1808  +  nByte += nColumn;                 /* Index.aSortOrder */
         1809  +  pIdx = sqlite3DbMallocZero(pParse->db, nByte);
         1810  +  if( pIdx==0 ) return;
         1811  +  pLevel->plan.u.pIdx = pIdx;
         1812  +  pIdx->azColl = (char**)&pIdx[1];
         1813  +  pIdx->aiColumn = (int*)&pIdx->azColl[nColumn];
         1814  +  pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn];
         1815  +  pIdx->zName = "auto-index";
         1816  +  pIdx->nColumn = nColumn;
         1817  +  pIdx->pTable = pTable;
         1818  +  n = 0;
         1819  +  idxCols = 0;
         1820  +  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
         1821  +    if( termCanDriveIndex(pTerm, pSrc, notReady) ){
         1822  +      int iCol = pTerm->u.leftColumn;
         1823  +      Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
         1824  +      if( (idxCols & cMask)==0 ){
         1825  +        Expr *pX = pTerm->pExpr;
         1826  +        idxCols |= cMask;
         1827  +        pIdx->aiColumn[n] = pTerm->u.leftColumn;
         1828  +        pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
         1829  +        pIdx->azColl[n] = pColl->zName;
         1830  +        n++;
         1831  +      }
         1832  +    }
         1833  +  }
         1834  +  assert( n==pLevel->plan.nEq );
         1835  +
         1836  +  /* Add additional columns needed to make the automatic index into
         1837  +  ** a covering index */
         1838  +  for(i=0; i<mxBitCol; i++){
         1839  +    if( extraCols & (1<<i) ){
         1840  +      pIdx->aiColumn[n] = i;
         1841  +      pIdx->azColl[n] = "BINARY";
         1842  +      n++;
         1843  +    }
         1844  +  }
         1845  +  if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
         1846  +    for(i=BMS-1; i<pTable->nCol; i++){
         1847  +      pIdx->aiColumn[n] = i;
         1848  +      pIdx->azColl[n] = "BINARY";
         1849  +      n++;
         1850  +    }
         1851  +  }
         1852  +  assert( n==nColumn );
         1853  +
         1854  +  /* Create the automatic index */
         1855  +  pKeyinfo = sqlite3IndexKeyinfo(pParse, pIdx);
         1856  +  assert( pLevel->iIdxCur>=0 );
         1857  +  sqlite3VdbeAddOp4(v, OP_OpenAutoindex, pLevel->iIdxCur, nColumn+1, 0,
         1858  +                    (char*)pKeyinfo, P4_KEYINFO_HANDOFF);
         1859  +  VdbeComment((v, "for %s", pTable->zName));
         1860  +
         1861  +  /* Fill the automatic index with content */
         1862  +  addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur);
         1863  +  regRecord = sqlite3GetTempReg(pParse);
         1864  +  sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1);
         1865  +  sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);
         1866  +  sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
         1867  +  sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1);
         1868  +  sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX);
         1869  +  sqlite3VdbeJumpHere(v, addrTop);
         1870  +  sqlite3ReleaseTempReg(pParse, regRecord);
         1871  +  
         1872  +  /* Jump here when skipping the initialization */
         1873  +  sqlite3VdbeJumpHere(v, addrInit);
         1874  +}
         1875  +#endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
         1876  +
  1638   1877   #ifndef SQLITE_OMIT_VIRTUALTABLE
  1639   1878   /*
  1640   1879   ** Allocate and populate an sqlite3_index_info structure. It is the 
  1641   1880   ** responsibility of the caller to eventually release the structure
  1642   1881   ** by passing the pointer returned by this function to sqlite3_free().
  1643   1882   */
  1644   1883   static sqlite3_index_info *allocateIndexInfo(
................................................................................
  2419   2658         }else{
  2420   2659           bSort = 1;
  2421   2660         }
  2422   2661       }
  2423   2662   
  2424   2663       /* If currently calculating the cost of using an index (not the IPK
  2425   2664       ** index), determine if all required column data may be obtained without 
  2426         -    ** seeking to entries in the main table (i.e. if the index is a covering
         2665  +    ** using the main table (i.e. if the index is a covering
  2427   2666       ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
  2428   2667       ** wsFlags. Otherwise, set the bLookup variable to true.  */
  2429   2668       if( pIdx && wsFlags ){
  2430   2669         Bitmask m = pSrc->colUsed;
  2431   2670         int j;
  2432   2671         for(j=0; j<pIdx->nColumn; j++){
  2433   2672           int x = pIdx->aiColumn[j];
................................................................................
  2477   2716       */
  2478   2717       if( pIdx && bLookup==0 ){
  2479   2718         cost /= (double)2;
  2480   2719       }
  2481   2720       /**** Cost of using this index has now been computed ****/
  2482   2721   
  2483   2722       WHERETRACE((
  2484         -      "tbl=%s idx=%s nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d"
  2485         -      " wsFlags=%d   (nRow=%.2f cost=%.2f)\n",
         2723  +      "%s(%s): nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
         2724  +      "         notReady=0x%llx nRow=%.2f cost=%.2f used=0x%llx\n",
  2486   2725         pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
  2487         -      nEq, nInMul, nBound, bSort, bLookup, wsFlags, nRow, cost
         2726  +      nEq, nInMul, nBound, bSort, bLookup, wsFlags, notReady, nRow, cost, used
  2488   2727       ));
  2489   2728   
  2490   2729       /* If this index is the best we have seen so far, then record this
  2491   2730       ** index and its cost in the pCost structure.
  2492   2731       */
  2493   2732       if( (!pIdx || wsFlags) && cost<pCost->rCost ){
  2494   2733         pCost->rCost = cost;
................................................................................
  2525   2764     );
  2526   2765   
  2527   2766     WHERETRACE(("best index is: %s\n", 
  2528   2767       (pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
  2529   2768     ));
  2530   2769     
  2531   2770     bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
         2771  +  bestAutomaticIndex(pParse, pWC, pSrc, notReady, pCost);
  2532   2772     pCost->plan.wsFlags |= eqTermMask;
  2533   2773   }
  2534   2774   
  2535   2775   /*
  2536   2776   ** Find the query plan for accessing table pSrc->pTab. Write the
  2537   2777   ** best query plan and its cost into the WhereCost object supplied 
  2538   2778   ** as the last parameter. This function may calculate the cost of
................................................................................
  3467   3707         if( pInfo ){
  3468   3708           /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
  3469   3709           if( pInfo->needToFreeIdxStr ){
  3470   3710             sqlite3_free(pInfo->idxStr);
  3471   3711           }
  3472   3712           sqlite3DbFree(db, pInfo);
  3473   3713         }
         3714  +      if( pWInfo->a[i].plan.wsFlags & WHERE_TEMP_INDEX ){
         3715  +        Index *pIdx = pWInfo->a[i].plan.u.pIdx;
         3716  +        if( pIdx ){
         3717  +          sqlite3DbFree(db, pIdx->zColAff);
         3718  +          sqlite3DbFree(db, pIdx);
         3719  +        }
         3720  +      }
  3474   3721       }
  3475   3722       whereClauseClear(pWInfo->pWC);
  3476   3723       sqlite3DbFree(db, pWInfo);
  3477   3724     }
  3478   3725   }
  3479   3726   
  3480   3727   
................................................................................
  3613   3860     nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
  3614   3861     pWInfo = sqlite3DbMallocZero(db, 
  3615   3862         nByteWInfo + 
  3616   3863         sizeof(WhereClause) +
  3617   3864         sizeof(WhereMaskSet)
  3618   3865     );
  3619   3866     if( db->mallocFailed ){
         3867  +    sqlite3DbFree(db, pWInfo);
         3868  +    pWInfo = 0;
  3620   3869       goto whereBeginError;
  3621   3870     }
  3622   3871     pWInfo->nLevel = nTabList;
  3623   3872     pWInfo->pParse = pParse;
  3624   3873     pWInfo->pTabList = pTabList;
  3625   3874     pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
  3626   3875     pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
  3627   3876     pWInfo->wctrlFlags = wctrlFlags;
         3877  +  pWInfo->savedNQueryLoop = pParse->nQueryLoop;
  3628   3878     pMaskSet = (WhereMaskSet*)&pWC[1];
  3629   3879   
  3630   3880     /* Split the WHERE clause into separate subexpressions where each
  3631   3881     ** subexpression is separated by an AND operator.
  3632   3882     */
  3633   3883     initMaskSet(pMaskSet);
  3634   3884     whereClauseInit(pWC, pParse, pMaskSet);
................................................................................
  3800   4050       WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
  3801   4051              pLevel-pWInfo->a));
  3802   4052       if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
  3803   4053         *ppOrderBy = 0;
  3804   4054       }
  3805   4055       andFlags &= bestPlan.plan.wsFlags;
  3806   4056       pLevel->plan = bestPlan.plan;
  3807         -    if( bestPlan.plan.wsFlags & WHERE_INDEXED ){
         4057  +    testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
         4058  +    testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );
         4059  +    if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){
  3808   4060         pLevel->iIdxCur = pParse->nTab++;
  3809   4061       }else{
  3810   4062         pLevel->iIdxCur = -1;
  3811   4063       }
  3812   4064       notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
  3813   4065       pLevel->iFrom = (u8)bestJ;
         4066  +    if( bestPlan.nRow>=(double)1 ) pParse->nQueryLoop *= bestPlan.nRow;
  3814   4067   
  3815   4068       /* Check that if the table scanned by this loop iteration had an
  3816   4069       ** INDEXED BY clause attached to it, that the named index is being
  3817   4070       ** used for the scan. If not, then query compilation has failed.
  3818   4071       ** Return an error.
  3819   4072       */
  3820   4073       pIdx = pTabList->a[bestJ].pIndex;
................................................................................
  3853   4106       pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  3854   4107     }
  3855   4108   
  3856   4109     /* Open all tables in the pTabList and any indices selected for
  3857   4110     ** searching those tables.
  3858   4111     */
  3859   4112     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
         4113  +  notReady = ~(Bitmask)0;
  3860   4114     for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
  3861   4115       Table *pTab;     /* Table to open */
  3862   4116       int iDb;         /* Index of database containing table/index */
  3863   4117   
  3864   4118   #ifndef SQLITE_OMIT_EXPLAIN
  3865   4119       if( pParse->explain==2 ){
  3866   4120         char *zMsg;
  3867   4121         struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
  3868   4122         zMsg = sqlite3MPrintf(db, "TABLE %s", pItem->zName);
  3869   4123         if( pItem->zAlias ){
  3870   4124           zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
  3871   4125         }
  3872         -      if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
         4126  +      if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
         4127  +        zMsg = sqlite3MAppendf(db, zMsg, "%s WITH AUTOMATIC INDEX", zMsg);
         4128  +      }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
  3873   4129           zMsg = sqlite3MAppendf(db, zMsg, "%s WITH INDEX %s",
  3874   4130              zMsg, pLevel->plan.u.pIdx->zName);
  3875   4131         }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
  3876   4132           zMsg = sqlite3MAppendf(db, zMsg, "%s VIA MULTI-INDEX UNION", zMsg);
  3877   4133         }else if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
  3878   4134           zMsg = sqlite3MAppendf(db, zMsg, "%s USING PRIMARY KEY", zMsg);
  3879   4135         }
................................................................................
  3888   4144           zMsg = sqlite3MAppendf(db, zMsg, "%s ORDER BY", zMsg);
  3889   4145         }
  3890   4146         sqlite3VdbeAddOp4(v, OP_Explain, i, pLevel->iFrom, 0, zMsg, P4_DYNAMIC);
  3891   4147       }
  3892   4148   #endif /* SQLITE_OMIT_EXPLAIN */
  3893   4149       pTabItem = &pTabList->a[pLevel->iFrom];
  3894   4150       pTab = pTabItem->pTab;
         4151  +    pLevel->iTabCur = pTabItem->iCursor;
  3895   4152       iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
  3896         -    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
         4153  +    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
         4154  +      /* Do nothing */
         4155  +    }else
  3897   4156   #ifndef SQLITE_OMIT_VIRTUALTABLE
  3898   4157       if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  3899   4158         const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
  3900   4159         int iCur = pTabItem->iCursor;
  3901   4160         sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
  3902   4161       }else
  3903   4162   #endif
................................................................................
  3912   4171           sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1, 
  3913   4172                               SQLITE_INT_TO_PTR(n), P4_INT32);
  3914   4173           assert( n<=pTab->nCol );
  3915   4174         }
  3916   4175       }else{
  3917   4176         sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
  3918   4177       }
  3919         -    pLevel->iTabCur = pTabItem->iCursor;
         4178  +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
         4179  +    if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
         4180  +      constructAutomaticIndex(pParse, pWC, pTabItem, notReady, pLevel);
         4181  +    }else
         4182  +#endif
  3920   4183       if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
  3921   4184         Index *pIx = pLevel->plan.u.pIdx;
  3922   4185         KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
  3923   4186         int iIdxCur = pLevel->iIdxCur;
  3924   4187         assert( pIx->pSchema==pTab->pSchema );
  3925   4188         assert( iIdxCur>=0 );
  3926   4189         sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
  3927   4190                           (char*)pKey, P4_KEYINFO_HANDOFF);
  3928   4191         VdbeComment((v, "%s", pIx->zName));
  3929   4192       }
  3930   4193       sqlite3CodeVerifySchema(pParse, iDb);
         4194  +    notReady &= ~getMask(pWC->pMaskSet, pTabItem->iCursor);
  3931   4195     }
  3932   4196     pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
         4197  +  if( db->mallocFailed ) goto whereBeginError;
  3933   4198   
  3934   4199     /* Generate the code to do the search.  Each iteration of the for
  3935   4200     ** loop below generates code for a single nested loop of the VM
  3936   4201     ** program.
  3937   4202     */
  3938   4203     notReady = ~(Bitmask)0;
  3939   4204     for(i=0; i<nTabList; i++){
................................................................................
  3993   4258     /* Record the continuation address in the WhereInfo structure.  Then
  3994   4259     ** clean up and return.
  3995   4260     */
  3996   4261     return pWInfo;
  3997   4262   
  3998   4263     /* Jump here if malloc fails */
  3999   4264   whereBeginError:
  4000         -  whereInfoFree(db, pWInfo);
         4265  +  if( pWInfo ){
         4266  +    pParse->nQueryLoop = pWInfo->savedNQueryLoop;
         4267  +    whereInfoFree(db, pWInfo);
         4268  +  }
  4001   4269     return 0;
  4002   4270   }
  4003   4271   
  4004   4272   /*
  4005   4273   ** Generate the end of the WHERE loop.  See comments on 
  4006   4274   ** sqlite3WhereBegin() for additional information.
  4007   4275   */
................................................................................
  4063   4331     /* Close all of the cursors that were opened by sqlite3WhereBegin.
  4064   4332     */
  4065   4333     assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
  4066   4334     for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
  4067   4335       struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
  4068   4336       Table *pTab = pTabItem->pTab;
  4069   4337       assert( pTab!=0 );
  4070         -    if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ) continue;
  4071         -    if( (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0 ){
  4072         -      if( !pWInfo->okOnePass && (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
         4338  +    if( (pTab->tabFlags & TF_Ephemeral)==0
         4339  +     && pTab->pSelect==0
         4340  +     && (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0
         4341  +    ){
         4342  +      int ws = pLevel->plan.wsFlags;
         4343  +      if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
  4073   4344           sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
  4074   4345         }
  4075         -      if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
         4346  +      if( (ws & (WHERE_INDEXED|WHERE_TEMP_INDEX)) == WHERE_INDEXED ){
  4076   4347           sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
  4077   4348         }
  4078   4349       }
  4079   4350   
  4080   4351       /* If this scan uses an index, make code substitutions to read data
  4081   4352       ** from the index in preference to the table. Sometimes, this means
  4082   4353       ** the table need never be read from. This is a performance boost,
................................................................................
  4116   4387           }
  4117   4388         }
  4118   4389       }
  4119   4390     }
  4120   4391   
  4121   4392     /* Final cleanup
  4122   4393     */
  4123         -  whereInfoFree(db, pWInfo);
         4394  +  if( pWInfo ){
         4395  +    pParse->nQueryLoop = pWInfo->savedNQueryLoop;
         4396  +    whereInfoFree(db, pWInfo);
         4397  +  }
  4124   4398     return;
  4125   4399   }

Added test/autoindex1.test.

            1  +# 2010 April 07
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#*************************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this script is testing automatic index creation logic.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +
           18  +# If the library is not compiled with automatic index support then
           19  +# skip all tests in this file.
           20  +#
           21  +ifcapable {!autoindex} {
           22  +  finish_test
           23  +  return
           24  +}
           25  +
           26  +# With automatic index turned off, we do a full scan of the T2 table
           27  +do_test autoindex1-100 {
           28  +  db eval {
           29  +    CREATE TABLE t1(a,b);
           30  +    INSERT INTO t1 VALUES(1,11);
           31  +    INSERT INTO t1 VALUES(2,22);
           32  +    INSERT INTO t1 SELECT a+2, b+22 FROM t1;
           33  +    INSERT INTO t1 SELECT a+4, b+44 FROM t1;
           34  +    CREATE TABLE t2(c,d);
           35  +    INSERT INTO t2 SELECT a, 900+b FROM t1;
           36  +  }
           37  +  db eval {
           38  +    PRAGMA automatic_index=OFF;
           39  +    SELECT b, d FROM t1 JOIN t2 ON a=c ORDER BY b;
           40  +  }
           41  +} {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
           42  +do_test autoindex1-101 {
           43  +  db status step
           44  +} {63}
           45  +do_test autoindex1-102 {
           46  +  db status autoindex
           47  +} {0}
           48  +
           49  +# With autoindex turned on, we build an index once and then use that index
           50  +# to find T2 values.
           51  +do_test autoindex1-110 {
           52  +  db eval {
           53  +    PRAGMA automatic_index=ON;
           54  +    SELECT b, d FROM t1 JOIN t2 ON a=c ORDER BY b;
           55  +  }
           56  +} {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
           57  +do_test autoindex1-111 {
           58  +  db status step
           59  +} {7}
           60  +do_test autoindex1-112 {
           61  +  db status autoindex
           62  +} {7}
           63  +
           64  +# The same test as above, but this time the T2 query is a subquery rather
           65  +# than a join.
           66  +do_test autoindex1-200 {
           67  +  db eval {
           68  +    PRAGMA automatic_index=OFF;
           69  +    SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1;
           70  +  }
           71  +} {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
           72  +do_test autoindex1-201 {
           73  +  db status step
           74  +} {35}
           75  +do_test autoindex1-202 {
           76  +  db status autoindex
           77  +} {0}
           78  +do_test autoindex1-210 {
           79  +  db eval {
           80  +    PRAGMA automatic_index=ON;
           81  +    SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1;
           82  +  }
           83  +} {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
           84  +do_test autoindex1-211 {
           85  +  db status step
           86  +} {7}
           87  +do_test autoindex1-212 {
           88  +  db status autoindex
           89  +} {7}
           90  +
           91  +
           92  +
           93  +finish_test

Changes to test/collate4.test.

   317    317   # defined collation sequences are involved. 
   318    318   #
   319    319   # Indices may optimise WHERE clauses using <, >, <=, >=, = or IN
   320    320   # operators.
   321    321   #
   322    322   do_test collate4-2.1.0 {
   323    323     execsql {
          324  +    PRAGMA automatic_index=OFF;
   324    325       CREATE TABLE collate4t1(a COLLATE NOCASE);
   325    326       CREATE TABLE collate4t2(b COLLATE TEXT);
   326    327   
   327    328       INSERT INTO collate4t1 VALUES('a');
   328    329       INSERT INTO collate4t1 VALUES('A');
   329    330       INSERT INTO collate4t1 VALUES('b');
   330    331       INSERT INTO collate4t1 VALUES('B');
................................................................................
   422    423       INSERT INTO collate4t1 VALUES('1', '1', '0');
   423    424       INSERT INTO collate4t1 VALUES('1', '1', '1');
   424    425       insert into collate4t2 SELECT * FROM collate4t1;
   425    426     }
   426    427   } {}
   427    428   do_test collate4-2.2.1 {
   428    429     count {
   429         -    SELECT * FROM collate4t2 NATURAL JOIN collate4t1;
          430  +    SELECT * FROM collate4t2 NOT INDEXED NATURAL JOIN collate4t1 NOT INDEXED;
   430    431     }
   431    432   } {0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 63}
   432    433   do_test collate4-2.2.1b {
   433    434     execsql {
   434    435       CREATE INDEX collate4i1 ON collate4t1(a, b, c);
   435    436     }
   436    437     count {