/ Check-in [a7645d29]
Login

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

Overview
Comment:Enhance the ANALYZE command so that it gathers statistics in the sqlite_stat1 table even for tables that are empty or have no indices.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: a7645d293801da64a7579737d0a8b48117af2e2c
User & Date: drh 2010-09-25 22:32:56
Context
2010-09-27
18:14
Simplifications to the expression code generator. Remove about 80 lines of older and obsolete code. check-in: 53f5cfe1 user: drh tags: trunk
2010-09-25
22:32
Enhance the ANALYZE command so that it gathers statistics in the sqlite_stat1 table even for tables that are empty or have no indices. check-in: a7645d29 user: drh tags: trunk
17:29
Add new file e_createtable.test. check-in: 20e16fef user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/analyze.c.

110
111
112
113
114
115
116

117
118
119
120
121
122
123
...
128
129
130
131
132
133
134
135
136







137
138
139
140
141
142
143
...
146
147
148
149
150
151
152

153
154
155
156
157
158
159
...
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
...
298
299
300
301
302
303
304
305
306



307
308
309
310
311
312
313
314
315
316
317
318
319






















320
321
322
323
324
325
326
327
328
329
330
331
332
333
...
449
450
451
452
453
454
455
456

457



458
459
460
461

462
463
464
465
466
467
468
469
470
471
472
473
474
475






476
477
478
479
480
481
482


483
484
485
486
487
488
489
...
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
  Index *pIdx;                 /* An index to being analyzed */
  int iIdxCur;                 /* Cursor open on index being analyzed */
  Vdbe *v;                     /* The virtual machine being built up */
  int i;                       /* Loop counter */
  int topOfLoop;               /* The top of the loop */
  int endOfLoop;               /* The end of the loop */
  int addr;                    /* The address of an instruction */

  int iDb;                     /* Index of database containing pTab */
  int regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regSampleno = iMem++;    /* Register containing next sample number */
  int regCol = iMem++;         /* Content of a column analyzed table */
  int regRec = iMem++;         /* Register holding completed record */
  int regTemp = iMem++;        /* Temporary use register */
................................................................................
  int regSamplerecno = iMem++; /* Index of next sample to record */
  int regRecno = iMem++;       /* Current sample index */
  int regLast = iMem++;        /* Index of last sample to record */
  int regFirst = iMem++;       /* Index of first sample to record */
#endif

  v = sqlite3GetVdbe(pParse);
  if( v==0 || NEVER(pTab==0) || pTab->pIndex==0 ){
    /* Do no analysis for tables that have no indices */







    return;
  }
  assert( sqlite3BtreeHoldsAllMutexes(db) );
  iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
  assert( iDb>=0 );
#ifndef SQLITE_OMIT_AUTHORIZATION
  if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
................................................................................
  }
#endif

  /* Establish a read-lock on the table at the shared-cache level. */
  sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

  iIdxCur = pParse->nTab++;

  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    int nCol = pIdx->nColumn;
    KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);

    if( iMem+1+(nCol*2)>pParse->nMem ){
      pParse->nMem = iMem+1+(nCol*2);
    }
................................................................................

    /* Open a cursor to the index to be analyzed. */
    assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
    sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
        (char *)pKey, P4_KEYINFO_HANDOFF);
    VdbeComment((v, "%s", pIdx->zName));

    /* Populate the registers containing the table and index names. */
    if( pTab->pIndex==pIdx ){
      sqlite3VdbeAddOp4(v, OP_String8, 0, regTabname, 0, pTab->zName, 0);
    }
    sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);

#ifdef SQLITE_ENABLE_STAT2

    /* If this iteration of the loop is generating code to analyze the
    ** first index in the pTab->pIndex list, then register regLast has
    ** not been populated. In this case populate it now.  */
................................................................................
    **
    **        I = (K+D-1)/D
    **
    ** If K==0 then no entry is made into the sqlite_stat1 table.  
    ** If K>0 then it is always the case the D>0 so division by zero
    ** is never possible.
    */
    addr = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);
    sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regSampleno);



    for(i=0; i<nCol; i++){
      sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
      sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);
      sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
      sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);
      sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
    }
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);






















    sqlite3VdbeJumpHere(v, addr);
  }
}

/*
** Generate code that will cause the most recent index analysis to
** be laoded into internal hash tables where is can be used.
*/
static void loadAnalysis(Parse *pParse, int iDb){
  Vdbe *v = sqlite3GetVdbe(pParse);
  if( v ){
    sqlite3VdbeAddOp1(v, OP_LoadAnalysis, iDb);
  }
}
................................................................................
  const char *zDatabase;
};

/*
** This callback is invoked once for each index when reading the
** sqlite_stat1 table.  
**
**     argv[0] = name of the index

**     argv[1] = results of analysis - on integer for each column



*/
static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
  analysisInfo *pInfo = (analysisInfo*)pData;
  Index *pIndex;

  int i, c;
  unsigned int v;
  const char *z;

  assert( argc==2 );
  UNUSED_PARAMETER2(NotUsed, argc);

  if( argv==0 || argv[0]==0 || argv[1]==0 ){
    return 0;
  }
  pIndex = sqlite3FindIndex(pInfo->db, argv[0], pInfo->zDatabase);
  if( pIndex==0 ){
    return 0;
  }






  z = argv[1];
  for(i=0; *z && i<=pIndex->nColumn; i++){
    v = 0;
    while( (c=z[0])>='0' && c<='9' ){
      v = v*10 + c - '0';
      z++;
    }


    pIndex->aiRowEst[i] = v;
    if( *z==' ' ) z++;
  }
  return 0;
}

/*
................................................................................
  sInfo.zDatabase = db->aDb[iDb].zName;
  if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
    return SQLITE_ERROR;
  }

  /* Load new statistics out of the sqlite_stat1 table */
  zSql = sqlite3MPrintf(db, 
      "SELECT idx, stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
    sqlite3DbFree(db, zSql);
  }








>







 







|
|
>
>
>
>
>
>
>







 







>







 







|
<
<
<







 







<

>
>
>













>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>






|







 







|
>
|
>
>
>




>
|



|


|


|
|


>
>
>
>
>
>
|
|





>
>







 







|







110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
...
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
...
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
...
169
170
171
172
173
174
175
176



177
178
179
180
181
182
183
...
304
305
306
307
308
309
310

311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
...
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
...
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
  Index *pIdx;                 /* An index to being analyzed */
  int iIdxCur;                 /* Cursor open on index being analyzed */
  Vdbe *v;                     /* The virtual machine being built up */
  int i;                       /* Loop counter */
  int topOfLoop;               /* The top of the loop */
  int endOfLoop;               /* The end of the loop */
  int addr;                    /* The address of an instruction */
  int jZeroRows = 0;           /* Jump from here if number of rows is zero */
  int iDb;                     /* Index of database containing pTab */
  int regTabname = iMem++;     /* Register containing table name */
  int regIdxname = iMem++;     /* Register containing index name */
  int regSampleno = iMem++;    /* Register containing next sample number */
  int regCol = iMem++;         /* Content of a column analyzed table */
  int regRec = iMem++;         /* Register holding completed record */
  int regTemp = iMem++;        /* Temporary use register */
................................................................................
  int regSamplerecno = iMem++; /* Index of next sample to record */
  int regRecno = iMem++;       /* Current sample index */
  int regLast = iMem++;        /* Index of last sample to record */
  int regFirst = iMem++;       /* Index of first sample to record */
#endif

  v = sqlite3GetVdbe(pParse);
  if( v==0 || NEVER(pTab==0) ){
    return;
  }
  if( pTab->pSelect ){
    /* Do not gather statistics on views */
    return;
  }
  if( memcmp(pTab->zName, "sqlite_", 7)==0 ){
    /* Do not gather statistics on system tables */
    return;
  }
  assert( sqlite3BtreeHoldsAllMutexes(db) );
  iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
  assert( iDb>=0 );
#ifndef SQLITE_OMIT_AUTHORIZATION
  if( sqlite3AuthCheck(pParse, SQLITE_ANALYZE, pTab->zName, 0,
................................................................................
  }
#endif

  /* Establish a read-lock on the table at the shared-cache level. */
  sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);

  iIdxCur = pParse->nTab++;
  sqlite3VdbeAddOp4(v, OP_String8, 0, regTabname, 0, pTab->zName, 0);
  for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
    int nCol = pIdx->nColumn;
    KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIdx);

    if( iMem+1+(nCol*2)>pParse->nMem ){
      pParse->nMem = iMem+1+(nCol*2);
    }
................................................................................

    /* Open a cursor to the index to be analyzed. */
    assert( iDb==sqlite3SchemaToIndex(db, pIdx->pSchema) );
    sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIdx->tnum, iDb,
        (char *)pKey, P4_KEYINFO_HANDOFF);
    VdbeComment((v, "%s", pIdx->zName));

    /* Populate the register containing the index name. */



    sqlite3VdbeAddOp4(v, OP_String8, 0, regIdxname, 0, pIdx->zName, 0);

#ifdef SQLITE_ENABLE_STAT2

    /* If this iteration of the loop is generating code to analyze the
    ** first index in the pTab->pIndex list, then register regLast has
    ** not been populated. In this case populate it now.  */
................................................................................
    **
    **        I = (K+D-1)/D
    **
    ** If K==0 then no entry is made into the sqlite_stat1 table.  
    ** If K>0 then it is always the case the D>0 so division by zero
    ** is never possible.
    */

    sqlite3VdbeAddOp2(v, OP_SCopy, iMem, regSampleno);
    if( jZeroRows==0 ){
      jZeroRows = sqlite3VdbeAddOp1(v, OP_IfNot, iMem);
    }
    for(i=0; i<nCol; i++){
      sqlite3VdbeAddOp4(v, OP_String8, 0, regTemp, 0, " ", 0);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
      sqlite3VdbeAddOp3(v, OP_Add, iMem, iMem+i+1, regTemp);
      sqlite3VdbeAddOp2(v, OP_AddImm, regTemp, -1);
      sqlite3VdbeAddOp3(v, OP_Divide, iMem+i+1, regTemp, regTemp);
      sqlite3VdbeAddOp1(v, OP_ToInt, regTemp);
      sqlite3VdbeAddOp3(v, OP_Concat, regTemp, regSampleno, regSampleno);
    }
    sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
    sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
    sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
    sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
  }

  /* If the table has no indices, create a single sqlite_stat1 entry
  ** containing NULL as the index name and the row count as the content.
  */
  if( pTab->pIndex==0 ){
    sqlite3VdbeAddOp3(v, OP_OpenRead, iIdxCur, pTab->tnum, iDb);
    VdbeComment((v, "%s", pTab->zName));
    sqlite3VdbeAddOp2(v, OP_Count, iIdxCur, regSampleno);
    sqlite3VdbeAddOp1(v, OP_Close, iIdxCur);
  }else{
    assert( jZeroRows>0 );
    addr = sqlite3VdbeAddOp0(v, OP_Goto);
    sqlite3VdbeJumpHere(v, jZeroRows);
  }
  sqlite3VdbeAddOp2(v, OP_Null, 0, regIdxname);
  sqlite3VdbeAddOp4(v, OP_MakeRecord, regTabname, 3, regRec, "aaa", 0);
  sqlite3VdbeAddOp2(v, OP_NewRowid, iStatCur, regRowid);
  sqlite3VdbeAddOp3(v, OP_Insert, iStatCur, regRec, regRowid);
  sqlite3VdbeChangeP5(v, OPFLAG_APPEND);
  if( pParse->nMem<regRec ) pParse->nMem = regRec;
  if( jZeroRows ){
    sqlite3VdbeJumpHere(v, addr);
  }
}

/*
** Generate code that will cause the most recent index analysis to
** be loaded into internal hash tables where is can be used.
*/
static void loadAnalysis(Parse *pParse, int iDb){
  Vdbe *v = sqlite3GetVdbe(pParse);
  if( v ){
    sqlite3VdbeAddOp1(v, OP_LoadAnalysis, iDb);
  }
}
................................................................................
  const char *zDatabase;
};

/*
** This callback is invoked once for each index when reading the
** sqlite_stat1 table.  
**
**     argv[0] = name of the table
**     argv[1] = name of the index (might be NULL)
**     argv[2] = results of analysis - on integer for each column
**
** Entries for which argv[1]==NULL simply record the number of rows in
** the table.
*/
static int analysisLoader(void *pData, int argc, char **argv, char **NotUsed){
  analysisInfo *pInfo = (analysisInfo*)pData;
  Index *pIndex;
  Table *pTable;
  int i, c, n;
  unsigned int v;
  const char *z;

  assert( argc==3 );
  UNUSED_PARAMETER2(NotUsed, argc);

  if( argv==0 || argv[0]==0 || argv[2]==0 ){
    return 0;
  }
  pTable = sqlite3FindTable(pInfo->db, argv[0], pInfo->zDatabase);
  if( pTable==0 ){
    return 0;
  }
  if( argv[1] ){
    pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
  }else{
    pIndex = 0;
  }
  n = pIndex ? pIndex->nColumn : 0;
  z = argv[2];
  for(i=0; *z && i<=n; i++){
    v = 0;
    while( (c=z[0])>='0' && c<='9' ){
      v = v*10 + c - '0';
      z++;
    }
    if( i==0 ) pTable->nRowEst = v;
    if( pIndex==0 ) break;
    pIndex->aiRowEst[i] = v;
    if( *z==' ' ) z++;
  }
  return 0;
}

/*
................................................................................
  sInfo.zDatabase = db->aDb[iDb].zName;
  if( sqlite3FindTable(db, "sqlite_stat1", sInfo.zDatabase)==0 ){
    return SQLITE_ERROR;
  }

  /* Load new statistics out of the sqlite_stat1 table */
  zSql = sqlite3MPrintf(db, 
      "SELECT tbl, idx, stat FROM %Q.sqlite_stat1", sInfo.zDatabase);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_exec(db, zSql, analysisLoader, &sInfo, 0);
    sqlite3DbFree(db, zSql);
  }

Changes to src/build.c.

798
799
800
801
802
803
804

805
806
807
808
809
810
811
....
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
    pParse->nErr++;
    goto begin_table_error;
  }
  pTable->zName = zName;
  pTable->iPKey = -1;
  pTable->pSchema = db->aDb[iDb].pSchema;
  pTable->nRef = 1;

  assert( pParse->pNewTable==0 );
  pParse->pNewTable = pTable;

  /* If this is the magic sqlite_sequence table used by autoincrement,
  ** then record a pointer to this table in the main database structure
  ** so that INSERT can find the table easily.
  */
................................................................................
** Apart from that, we have little to go on besides intuition as to
** how aiRowEst[] should be initialized.  The numbers generated here
** are based on typical values found in actual indices.
*/
void sqlite3DefaultRowEst(Index *pIdx){
  unsigned *a = pIdx->aiRowEst;
  int i;
  assert( a!=0 );
  a[0] = 1000000;
  for(i=pIdx->nColumn; i>=5; i--){
    a[i] = 5;
  }
  while( i>=1 ){
    a[i] = 11 - i;
    i--;
  }
  if( pIdx->onError!=OE_None ){
    a[pIdx->nColumn] = 1;
  }
}

/*







>







 







|
|
|
|
|
|
|
|







798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
....
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
    pParse->nErr++;
    goto begin_table_error;
  }
  pTable->zName = zName;
  pTable->iPKey = -1;
  pTable->pSchema = db->aDb[iDb].pSchema;
  pTable->nRef = 1;
  pTable->nRowEst = 1000000;
  assert( pParse->pNewTable==0 );
  pParse->pNewTable = pTable;

  /* If this is the magic sqlite_sequence table used by autoincrement,
  ** then record a pointer to this table in the main database structure
  ** so that INSERT can find the table easily.
  */
................................................................................
** Apart from that, we have little to go on besides intuition as to
** how aiRowEst[] should be initialized.  The numbers generated here
** are based on typical values found in actual indices.
*/
void sqlite3DefaultRowEst(Index *pIdx){
  unsigned *a = pIdx->aiRowEst;
  int i;
  unsigned n;
  assert( a!=0 );
  a[0] = pIdx->pTable->nRowEst;
  if( a[0]<10 ) a[0] = 10;
  n = 10;
  for(i=1; i<=pIdx->nColumn; i++){
    a[i] = n;
    if( n>5 ) n--;
  }
  if( pIdx->onError!=OE_None ){
    a[pIdx->nColumn] = 1;
  }
}

/*

Changes to src/sqliteInt.h.

1248
1249
1250
1251
1252
1253
1254

1255
1256
1257
1258
1259
1260
1261
struct Table {
  char *zName;         /* Name of the table or view */
  int iPKey;           /* If not negative, use aCol[iPKey] as the primary key */
  int nCol;            /* Number of columns in this table */
  Column *aCol;        /* Information about each column */
  Index *pIndex;       /* List of SQL indexes on this table. */
  int tnum;            /* Root BTree node for this table (see note above) */

  Select *pSelect;     /* NULL for tables.  Points to definition if a view. */
  u16 nRef;            /* Number of pointers to this Table */
  u8 tabFlags;         /* Mask of TF_* values */
  u8 keyConf;          /* What to do in case of uniqueness conflict on iPKey */
  FKey *pFKey;         /* Linked list of all foreign keys in this table */
  char *zColAff;       /* String defining the affinity of each column */
#ifndef SQLITE_OMIT_CHECK







>







1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
struct Table {
  char *zName;         /* Name of the table or view */
  int iPKey;           /* If not negative, use aCol[iPKey] as the primary key */
  int nCol;            /* Number of columns in this table */
  Column *aCol;        /* Information about each column */
  Index *pIndex;       /* List of SQL indexes on this table. */
  int tnum;            /* Root BTree node for this table (see note above) */
  unsigned nRowEst;    /* Estimated rows in table - from sqlite_stat1 table */
  Select *pSelect;     /* NULL for tables.  Points to definition if a view. */
  u16 nRef;            /* Number of pointers to this Table */
  u8 tabFlags;         /* Mask of TF_* values */
  u8 keyConf;          /* What to do in case of uniqueness conflict on iPKey */
  FKey *pFKey;         /* Linked list of all foreign keys in this table */
  char *zColAff;       /* String defining the affinity of each column */
#ifndef SQLITE_OMIT_CHECK

Changes to src/where.c.

1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
....
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518


2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
....
4099
4100
4101
4102
4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
  if( pSrc->notIndexed ){
    /* The NOT INDEXED clause appears in the SQL. */
    return;
  }

  assert( pParse->nQueryLoop >= (double)1 );
  pTable = pSrc->pTab;
  nTableRow = pTable->pIndex ? pTable->pIndex->aiRowEst[0] : 1000000;
  logN = estLog(nTableRow);
  costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
  if( costTempIdx>=pCost->rCost ){
    /* The cost of creating the transient table would be greater than
    ** doing the full table scan */
    return;
  }
................................................................................
    /* There is no INDEXED BY clause.  Create a fake Index object to
    ** represent the primary key */
    Index *pFirst;                /* Any other index on the table */
    memset(&sPk, 0, sizeof(Index));
    sPk.nColumn = 1;
    sPk.aiColumn = &aiColumnPk;
    sPk.aiRowEst = aiRowEstPk;
    aiRowEstPk[1] = 1;
    sPk.onError = OE_Replace;
    sPk.pTable = pSrc->pTab;


    pFirst = pSrc->pTab->pIndex;
    if( pSrc->notIndexed==0 ){
      sPk.pNext = pFirst;
    }
    /* The aiRowEstPk[0] is an estimate of the total number of rows in the
    ** table.  Get this information from the ANALYZE information if it is
    ** available.  If not available, assume the table 1 million rows in size.
    */
    if( pFirst ){
      assert( pFirst->aiRowEst!=0 ); /* Allocated together with pFirst */
      aiRowEstPk[0] = pFirst->aiRowEst[0];
    }else{
      aiRowEstPk[0] = 1000000;
    }
    pProbe = &sPk;
    wsFlagMask = ~(
        WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
    );
    eqTermMask = WO_EQ|WO_IN;
    pIdx = 0;
  }
................................................................................
    **   
    **   CREATE TABLE t1(a, b); 
    **   CREATE TABLE t2(c, d);
    **   SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
    **
    ** The best strategy is to iterate through table t1 first. However it
    ** is not possible to determine this with a simple greedy algorithm.
    ** However, since the cost of a linear scan through table t2 is the same 
    ** as the cost of a linear scan through table t1, a simple greedy 
    ** algorithm may choose to use t2 for the outer loop, which is a much
    ** costlier approach.
    */
    nUnconstrained = 0;
    notIndexed = 0;
    for(isOptimal=(iFrom<nTabList-1); isOptimal>=0; isOptimal--){







|







 







<


>
>




<
<
<
<
<
<
<
<
<
<







 







|







1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
....
2509
2510
2511
2512
2513
2514
2515

2516
2517
2518
2519
2520
2521
2522
2523










2524
2525
2526
2527
2528
2529
2530
....
4090
4091
4092
4093
4094
4095
4096
4097
4098
4099
4100
4101
4102
4103
4104
  if( pSrc->notIndexed ){
    /* The NOT INDEXED clause appears in the SQL. */
    return;
  }

  assert( pParse->nQueryLoop >= (double)1 );
  pTable = pSrc->pTab;
  nTableRow = pTable->nRowEst;
  logN = estLog(nTableRow);
  costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
  if( costTempIdx>=pCost->rCost ){
    /* The cost of creating the transient table would be greater than
    ** doing the full table scan */
    return;
  }
................................................................................
    /* There is no INDEXED BY clause.  Create a fake Index object to
    ** represent the primary key */
    Index *pFirst;                /* Any other index on the table */
    memset(&sPk, 0, sizeof(Index));
    sPk.nColumn = 1;
    sPk.aiColumn = &aiColumnPk;
    sPk.aiRowEst = aiRowEstPk;

    sPk.onError = OE_Replace;
    sPk.pTable = pSrc->pTab;
    aiRowEstPk[0] = pSrc->pTab->nRowEst;
    aiRowEstPk[1] = 1;
    pFirst = pSrc->pTab->pIndex;
    if( pSrc->notIndexed==0 ){
      sPk.pNext = pFirst;
    }










    pProbe = &sPk;
    wsFlagMask = ~(
        WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
    );
    eqTermMask = WO_EQ|WO_IN;
    pIdx = 0;
  }
................................................................................
    **   
    **   CREATE TABLE t1(a, b); 
    **   CREATE TABLE t2(c, d);
    **   SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
    **
    ** The best strategy is to iterate through table t1 first. However it
    ** is not possible to determine this with a simple greedy algorithm.
    ** Since the cost of a linear scan through table t2 is the same 
    ** as the cost of a linear scan through table t1, a simple greedy 
    ** algorithm may choose to use t2 for the outer loop, which is a much
    ** costlier approach.
    */
    nUnconstrained = 0;
    notIndexed = 0;
    for(isOptimal=(iFrom<nTabList-1); isOptimal>=0; isOptimal--){

Changes to test/analyze.test.

69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
do_test analyze-1.6.3 {
  catchsql {
    CREATE INDEX main.stat1idx ON SQLite_stat1(idx);
  }
} {1 {table sqlite_stat1 may not be indexed}}
do_test analyze-1.7 {
  execsql {
    SELECT * FROM sqlite_stat1
  }
} {}
do_test analyze-1.8 {
  catchsql {
    ANALYZE main
  }
} {0 {}}
do_test analyze-1.9 {
  execsql {
    SELECT * FROM sqlite_stat1
  }
} {}
do_test analyze-1.10 {
  catchsql {
    CREATE TABLE t1(a,b);
    ANALYZE main.t1;
  }
} {0 {}}
do_test analyze-1.11 {
  execsql {
    SELECT * FROM sqlite_stat1
  }
} {}
do_test analyze-1.12 {
  catchsql {
    ANALYZE t1;
  }
} {0 {}}
do_test analyze-1.13 {
  execsql {
    SELECT * FROM sqlite_stat1
  }
} {}

# Create some indices that can be analyzed.  But do not yet add
# data.  Without data in the tables, no analysis is done.
#
do_test analyze-2.1 {
  execsql {
    CREATE INDEX t1i1 ON t1(a);
    ANALYZE main.t1;
    SELECT * FROM sqlite_stat1 ORDER BY idx;
  }
} {}
do_test analyze-2.2 {
  execsql {
    CREATE INDEX t1i2 ON t1(b);
    ANALYZE t1;
    SELECT * FROM sqlite_stat1 ORDER BY idx;
  }
} {}
do_test analyze-2.3 {
  execsql {
    CREATE INDEX t1i3 ON t1(a,b);
    ANALYZE main;
    SELECT * FROM sqlite_stat1 ORDER BY idx;
  }
} {}

# Start adding data to the table.  Verify that the analysis
# is done correctly.
#
do_test analyze-3.1 {
  execsql {
    INSERT INTO t1 VALUES(1,2);







|









|












|









|










|






|






|







69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
do_test analyze-1.6.3 {
  catchsql {
    CREATE INDEX main.stat1idx ON SQLite_stat1(idx);
  }
} {1 {table sqlite_stat1 may not be indexed}}
do_test analyze-1.7 {
  execsql {
    SELECT * FROM sqlite_stat1 WHERE idx NOT NULL
  }
} {}
do_test analyze-1.8 {
  catchsql {
    ANALYZE main
  }
} {0 {}}
do_test analyze-1.9 {
  execsql {
    SELECT * FROM sqlite_stat1 WHERE idx NOT NULL
  }
} {}
do_test analyze-1.10 {
  catchsql {
    CREATE TABLE t1(a,b);
    ANALYZE main.t1;
  }
} {0 {}}
do_test analyze-1.11 {
  execsql {
    SELECT * FROM sqlite_stat1
  }
} {t1 {} 0}
do_test analyze-1.12 {
  catchsql {
    ANALYZE t1;
  }
} {0 {}}
do_test analyze-1.13 {
  execsql {
    SELECT * FROM sqlite_stat1
  }
} {t1 {} 0}

# Create some indices that can be analyzed.  But do not yet add
# data.  Without data in the tables, no analysis is done.
#
do_test analyze-2.1 {
  execsql {
    CREATE INDEX t1i1 ON t1(a);
    ANALYZE main.t1;
    SELECT * FROM sqlite_stat1 ORDER BY idx;
  }
} {t1 {} 0}
do_test analyze-2.2 {
  execsql {
    CREATE INDEX t1i2 ON t1(b);
    ANALYZE t1;
    SELECT * FROM sqlite_stat1 ORDER BY idx;
  }
} {t1 {} 0}
do_test analyze-2.3 {
  execsql {
    CREATE INDEX t1i3 ON t1(a,b);
    ANALYZE main;
    SELECT * FROM sqlite_stat1 ORDER BY idx;
  }
} {t1 {} 0}

# Start adding data to the table.  Verify that the analysis
# is done correctly.
#
do_test analyze-3.1 {
  execsql {
    INSERT INTO t1 VALUES(1,2);

Changes to test/auth.test.

1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
....
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
      CREATE TABLE t4(a,b,c);
      CREATE INDEX t4i1 ON t4(a);
      CREATE INDEX t4i2 ON t4(b,a,c);
      INSERT INTO t4 VALUES(1,2,3);
      ANALYZE;
    }
    set ::authargs
  } {t4 {} main {}}
  do_test auth-1.295 {
    execsql {
      SELECT count(*) FROM sqlite_stat1;
    }
  } 2
  proc auth {code args} {
    if {$code=="SQLITE_ANALYZE"} {
      set ::authargs [concat $::authargs $args]
      return SQLITE_DENY
    }
    return SQLITE_OK
  }
................................................................................
      ANALYZE;
    }
  } {1 {not authorized}}
  do_test auth-1.297 {
    execsql {
      SELECT count(*) FROM sqlite_stat1;
    }
  } 2
} ;# ifcapable analyze


# Authorization for ALTER TABLE ADD COLUMN.
# These tests are omitted if the library
# was built without ALTER TABLE support.
ifcapable {altertable} {







|




|







 







|







1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
....
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
      CREATE TABLE t4(a,b,c);
      CREATE INDEX t4i1 ON t4(a);
      CREATE INDEX t4i2 ON t4(b,a,c);
      INSERT INTO t4 VALUES(1,2,3);
      ANALYZE;
    }
    set ::authargs
  } {t4 {} main {} t2 {} main {}}
  do_test auth-1.295 {
    execsql {
      SELECT count(*) FROM sqlite_stat1;
    }
  } 3
  proc auth {code args} {
    if {$code=="SQLITE_ANALYZE"} {
      set ::authargs [concat $::authargs $args]
      return SQLITE_DENY
    }
    return SQLITE_OK
  }
................................................................................
      ANALYZE;
    }
  } {1 {not authorized}}
  do_test auth-1.297 {
    execsql {
      SELECT count(*) FROM sqlite_stat1;
    }
  } 3
} ;# ifcapable analyze


# Authorization for ALTER TABLE ADD COLUMN.
# These tests are omitted if the library
# was built without ALTER TABLE support.
ifcapable {altertable} {

Changes to test/misc4.test.

147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
      insert into b values ('01',1);
      insert into b values ('01',2);
      insert into b values ('+1',3);
      insert into b values ('+1',4);
      
      select a.*, x.*
        from a, (select key,sum(period) from b group by key) as x
        where a.key=x.key;
    }
  } {01 data01 01 3 +1 data+1 +1 7}

  # This test case tests the same property as misc4-4.1, but it is
  # a bit smaller which makes it easier to work with while debugging.
  do_test misc4-4.2 {
    execsql {







|







147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
      insert into b values ('01',1);
      insert into b values ('01',2);
      insert into b values ('+1',3);
      insert into b values ('+1',4);
      
      select a.*, x.*
        from a, (select key,sum(period) from b group by key) as x
        where a.key=x.key order by 1 desc;
    }
  } {01 data01 01 3 +1 data+1 +1 7}

  # This test case tests the same property as misc4-4.1, but it is
  # a bit smaller which makes it easier to work with while debugging.
  do_test misc4-4.2 {
    execsql {

Changes to test/select6.test.

454
455
456
457
458
459
460

461
462
463
464
465
466
467
} ;# ifcapable view

# Ticket #1634
#
do_test select6-9.1 {
  execsql {
    SELECT a.x, b.x FROM t1 AS a, (SELECT x FROM t1 LIMIT 2) AS b

  }
} {1 1 1 2 2 1 2 2 3 1 3 2 4 1 4 2}
do_test select6-9.2 {
  execsql {
    SELECT x FROM (SELECT x FROM t1 LIMIT 2);
  }
} {1 2}







>







454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
} ;# ifcapable view

# Ticket #1634
#
do_test select6-9.1 {
  execsql {
    SELECT a.x, b.x FROM t1 AS a, (SELECT x FROM t1 LIMIT 2) AS b
     ORDER BY 1, 2
  }
} {1 1 1 2 2 1 2 2 3 1 3 2 4 1 4 2}
do_test select6-9.2 {
  execsql {
    SELECT x FROM (SELECT x FROM t1 LIMIT 2);
  }
} {1 2}

Changes to test/tkt3757.test.

31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
  db eval {
     CREATE TABLE t1(x INTEGER, y INTEGER, z TEXT);
     CREATE INDEX t1i1 ON t1(y,z);
     INSERT INTO t1 VALUES(1,2,'three');
     CREATE TABLE t2(a INTEGER, b TEXT);
     INSERT INTO t2 VALUES(2, 'two');
     ANALYZE;
     SELECT * FROM sqlite_stat1;
  }
} {t1 t1i1 {1 1 1}}

# Modify statistics in order to make the optimizer then that:
#
#   (1)  Table T1 has about 250K entries
#   (2)  There are only about 5 distinct values of T1.
#
# Then run a query with "t1.y IN (SELECT ..)" in the WHERE clause.







|

|







31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
  db eval {
     CREATE TABLE t1(x INTEGER, y INTEGER, z TEXT);
     CREATE INDEX t1i1 ON t1(y,z);
     INSERT INTO t1 VALUES(1,2,'three');
     CREATE TABLE t2(a INTEGER, b TEXT);
     INSERT INTO t2 VALUES(2, 'two');
     ANALYZE;
     SELECT * FROM sqlite_stat1 ORDER BY 1, 2;
  }
} {t1 t1i1 {1 1 1} t2 {} 1}

# Modify statistics in order to make the optimizer then that:
#
#   (1)  Table T1 has about 250K entries
#   (2)  There are only about 5 distinct values of T1.
#
# Then run a query with "t1.y IN (SELECT ..)" in the WHERE clause.