/ Check-in [73a7f010]
Login

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

Overview
Comment:Fix further issues in schemalint.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | schemalint
Files: files | file ages | folders
SHA1: 73a7f010937828c5195a198604f976e8458cef73
User & Date: dan 2016-02-16 18:37:37
Context
2016-02-17
20:06
Schemalint changes: Avoid creating candidate indexes if a compatible index exists. Do not quote identifiers that do not require it. check-in: cf0f7eeb user: dan tags: schemalint
2016-02-16
18:37
Fix further issues in schemalint. check-in: 73a7f010 user: dan tags: schemalint
2016-02-15
20:12
Progress towards integrating schemalint into the shell tool. Some cases work now. check-in: 58d4cf26 user: dan tags: schemalint
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/shell_indexes.c.

21
22
23
24
25
26
27
28

29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


45


46



47

















48
49
50
51
52
53
54
55
56
57
58
59
60
..
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
142
143
144
145
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
...
472
473
474
475
476
477
478




































479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
...
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
...
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
...
696
697
698
699
700
701
702

703

704
705
706
707
708
709
710
...
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
...
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
...
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846


847
848
849
850
851
852










853
854


























855





856
857
858
859
860
861
862
...
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907

908
909
910

911
912
913
914
915

916
917
918
919
920
921

922



923
924

925
926
927
928
929
930
931
932
933
934
935

936
937
938
939
940
941
typedef struct IdxColumn IdxColumn;
typedef struct IdxTable IdxTable;

/*
** A single constraint. Equivalent to either "col = ?" or "col < ?".
**
** pLink:
**   ... todo ...

*/
struct IdxConstraint {
  char *zColl;                    /* Collation sequence */
  int bRange;                     /* True for range, false for eq */
  int iCol;                       /* Constrained table column */
  i64 depmask;                    /* Dependency mask */
  IdxConstraint *pNext;           /* Next constraint in pEq or pRange list */
  IdxConstraint *pLink;           /* See above */
};

/*
** A WHERE clause. Made up of IdxConstraint objects. Example WHERE clause:
**
**   a=? AND b=? AND (c=? OR d=?) AND (e=? OR f=?)
**
** The above


**


**



**

















*/
struct IdxWhere {
  IdxConstraint *pEq;             /* List of == constraints */
  IdxConstraint *pRange;          /* List of < constraints */
  IdxWhere *pOr;                  /* List of OR constraints */

  IdxWhere *pNextOr;              /* Next in OR constraints of same IdxWhere */
  IdxWhere *pSibling;             /* Next branch in single OR constraint */
  IdxWhere *pParent;              /* Parent object (or NULL) */
};

/*
** A single scan of a single table.
................................................................................
  int iPk;
};
struct IdxTable {
  int nCol;
  IdxColumn *aCol;
};


typedef struct PragmaTable PragmaTable;
typedef struct PragmaCursor PragmaCursor;

struct PragmaTable {
  sqlite3_vtab base;
  sqlite3 *db;
};

struct PragmaCursor {
  sqlite3_vtab_cursor base;
  sqlite3_stmt *pStmt;
  i64 iRowid;
};

/*
** Connect to or create a pragma virtual table.
*/
static int pragmaConnect(
  sqlite3 *db,
  void *pAux,
  int argc, const char *const*argv,
  sqlite3_vtab **ppVtab,
  char **pzErr
){
  const char *zSchema = 
    "CREATE TABLE a(tbl HIDDEN, cid, name, type, isnotnull, dflt_value, pk)";
  PragmaTable *pTab = 0;
  int rc = SQLITE_OK;

  rc = sqlite3_declare_vtab(db, zSchema);
  if( rc==SQLITE_OK ){
    pTab = (PragmaTable *)sqlite3_malloc64(sizeof(PragmaTable));
    if( pTab==0 ) rc = SQLITE_NOMEM;
  }else{
    *pzErr = sqlite3_mprintf("%s", sqlite3_errmsg(db));
  }

  assert( rc==SQLITE_OK || pTab==0 );
  if( rc==SQLITE_OK ){
    memset(pTab, 0, sizeof(PragmaTable));
    pTab->db = db;
  }

  *ppVtab = (sqlite3_vtab*)pTab;
  return rc;
}

/*
** Disconnect from or destroy a pragma virtual table.
*/
static int pragmaDisconnect(sqlite3_vtab *pVtab){
  sqlite3_free(pVtab);
  return SQLITE_OK;
}

/*
** xBestIndex method for pragma virtual tables.
*/
static int pragmaBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){
  int i;

  pIdxInfo->estimatedCost = 1.0e6;  /* Initial cost estimate */

  /* Look for a valid tbl=? constraint. */
  for(i=0; i<pIdxInfo->nConstraint; i++){
    if( pIdxInfo->aConstraint[i].usable==0 ) continue;
    if( pIdxInfo->aConstraint[i].op!=SQLITE_INDEX_CONSTRAINT_EQ ) continue;
    if( pIdxInfo->aConstraint[i].iColumn!=0 ) continue;
    pIdxInfo->idxNum = 1;
    pIdxInfo->estimatedCost = 1.0;
    pIdxInfo->aConstraintUsage[i].argvIndex = 1;
    pIdxInfo->aConstraintUsage[i].omit = 1;
    break;
  }
  if( i==pIdxInfo->nConstraint ){
    tab->zErrMsg = sqlite3_mprintf("missing required tbl=? constraint");
    return SQLITE_ERROR;
  }
  return SQLITE_OK;
}

/*
** Open a new pragma cursor.
*/
static int pragmaOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
  PragmaCursor *pCsr;

  pCsr = (PragmaCursor*)sqlite3_malloc64(sizeof(PragmaCursor));
  if( pCsr==0 ){
    return SQLITE_NOMEM;
  }else{
    memset(pCsr, 0, sizeof(PragmaCursor));
    pCsr->base.pVtab = pVTab;
  }

  *ppCursor = (sqlite3_vtab_cursor*)pCsr;
  return SQLITE_OK;
}

static int pragmaClose(sqlite3_vtab_cursor *pCursor){
  PragmaCursor *pCsr = (PragmaCursor*)pCursor;
  sqlite3_finalize(pCsr->pStmt);
  sqlite3_free(pCsr);
  return SQLITE_OK;
}

/*
** Move a statvfs cursor to the next entry in the file.
*/
static int pragmaNext(sqlite3_vtab_cursor *pCursor){
  PragmaCursor *pCsr = (PragmaCursor*)pCursor;
  int rc = SQLITE_OK;

  if( sqlite3_step(pCsr->pStmt)!=SQLITE_ROW ){
    rc = sqlite3_finalize(pCsr->pStmt);
    pCsr->pStmt = 0;
  }
  pCsr->iRowid++;
  return rc;
}

static int pragmaEof(sqlite3_vtab_cursor *pCursor){
  PragmaCursor *pCsr = (PragmaCursor*)pCursor;
  return pCsr->pStmt==0;
}

static int pragmaFilter(
  sqlite3_vtab_cursor *pCursor, 
  int idxNum, const char *idxStr,
  int argc, sqlite3_value **argv
){
  PragmaCursor *pCsr = (PragmaCursor*)pCursor;
  PragmaTable *pTab = (PragmaTable*)(pCursor->pVtab);
  char *zSql;
  const char *zTbl;
  int rc = SQLITE_OK;

  if( pCsr->pStmt ){
    sqlite3_finalize(pCsr->pStmt);
    pCsr->pStmt = 0;
  }
  pCsr->iRowid = 0;

  assert( argc==1 );
  zTbl = (const char*)sqlite3_value_text(argv[0]);
  zSql = sqlite3_mprintf("PRAGMA table_info(%Q)", zTbl);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = sqlite3_prepare_v2(pTab->db, zSql, -1, &pCsr->pStmt, 0);
  }
  if( rc ) return rc;
  return pragmaNext(pCursor);;
}

/*
** xColumn method.
*/
static int pragmaColumn(
  sqlite3_vtab_cursor *pCursor, 
  sqlite3_context *ctx, 
  int iCol
){
  PragmaCursor *pCsr = (PragmaCursor *)pCursor;
  if( iCol>0 ){
    sqlite3_result_value(ctx, sqlite3_column_value(pCsr->pStmt, iCol-1));
  }
  return SQLITE_OK;
}

static int pragmaRowid(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
  PragmaCursor *pCsr = (PragmaCursor *)pCursor;
  *pRowid = pCsr->iRowid;
  return SQLITE_OK;
}

static int registerPragmaVtabs(sqlite3 *db){
  static sqlite3_module pragma_module = {
    0,                            /* iVersion */
    pragmaConnect,                /* xCreate */
    pragmaConnect,                /* xConnect */
    pragmaBestIndex,              /* xBestIndex */
    pragmaDisconnect,             /* xDisconnect */
    pragmaDisconnect,             /* xDestroy */
    pragmaOpen,                   /* xOpen - open a cursor */
    pragmaClose,                  /* xClose - close a cursor */
    pragmaFilter,                 /* xFilter - configure scan constraints */
    pragmaNext,                   /* xNext - advance a cursor */
    pragmaEof,                    /* xEof - check for end of scan */
    pragmaColumn,                 /* xColumn - read data */
    pragmaRowid,                  /* xRowid - read data */
    0,                            /* xUpdate */
    0,                            /* xBegin */
    0,                            /* xSync */
    0,                            /* xCommit */
    0,                            /* xRollback */
    0,                            /* xFindMethod */
    0,                            /* xRename */
  };
  return sqlite3_create_module(db, "pragma_table_info", &pragma_module, 0);
}

/*
** Allocate and return nByte bytes of zeroed memory using sqlite3_malloc(). 
** If the allocation fails, set *pRc to SQLITE_NOMEM and return NULL.
*/
static void *idxMalloc(int *pRc, int nByte){
  void *pRet;
  assert( *pRc==SQLITE_OK );
................................................................................
      zRet = 0;
    }
    *pRc = rc;
  }

  return zRet;
}





































static int idxGetTableInfo(
  sqlite3 *db,
  IdxScan *pScan,
  char **pzErrmsg
){
  const char *zSql = "SELECT name, pk FROM pragma_table_info(?)";
  sqlite3_stmt *p1 = 0;
  int nCol = 0;
  int nByte = sizeof(IdxTable);
  IdxTable *pNew = 0;
  int rc, rc2;
  char *pCsr;

  rc = sqlite3_prepare_v2(db, zSql, -1, &p1, 0);
  if( rc!=SQLITE_OK ){
    idxDatabaseError(db, pzErrmsg);
    return rc;
  }
  sqlite3_bind_text(p1, 1, pScan->zTable, -1, SQLITE_TRANSIENT);
  while( SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = sqlite3_column_text(p1, 0);
    nByte += 1 + strlen(zCol);
    rc = sqlite3_table_column_metadata(
        db, "main", pScan->zTable, zCol, 0, &zCol, 0, 0, 0
    );
    nByte += 1 + strlen(zCol);
    nCol++;
  }
  rc2 = sqlite3_reset(p1);
  if( rc==SQLITE_OK ) rc = rc2;

................................................................................
    pNew->aCol = (IdxColumn*)&pNew[1];
    pNew->nCol = nCol;
    pCsr = (char*)&pNew->aCol[nCol];
  }

  nCol = 0;
  while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = sqlite3_column_text(p1, 0);
    int nCopy = strlen(zCol) + 1;
    pNew->aCol[nCol].zName = pCsr;
    pNew->aCol[nCol].iPk = sqlite3_column_int(p1, 1);
    memcpy(pCsr, zCol, nCopy);
    pCsr += nCopy;

    rc = sqlite3_table_column_metadata(
        db, "main", pScan->zTable, zCol, 0, &zCol, 0, 0, 0
    );
    if( rc==SQLITE_OK ){
      nCopy = strlen(zCol) + 1;
      pNew->aCol[nCol].zColl = pCsr;
      memcpy(pCsr, zCol, nCopy);
      pCsr += nCopy;
    }
................................................................................
      }else{
        zCreate = sqlite3_mprintf("CREATE TABLE %Q(%s)", pIter->zTable, zCols);
      }
      if( zCreate==0 ) rc = SQLITE_NOMEM;
    }

    if( rc==SQLITE_OK ){
#if 1
      printf("/* %s */\n", zCreate);
#endif
      rc = sqlite3_exec(dbm, zCreate, 0, 0, pzErrmsg);
    }
    sqlite3_free(zCols);
    sqlite3_free(zPk);
    sqlite3_free(zCreate);
................................................................................
      zIdx = sqlite3_mprintf("CREATE INDEX IF NOT EXISTS "
          "'%q_idx_%08x' ON %Q(%s)", pScan->zTable, h, pScan->zTable, zCols
      );
      if( !zIdx ){
        rc = SQLITE_NOMEM;
      }else{
        rc = sqlite3_exec(dbm, zIdx, 0, 0, 0);

        printf("/* %s */\n", zIdx);

      }
    }

    sqlite3_free(zIdx);
    sqlite3_free(zCols);
  }
  return rc;
................................................................................
      }
    }
  }

  return rc;
}

static int idxPrepareStmt(
  sqlite3 *db,                    /* Database handle to compile against */
  const char *zSql,               /* SQL statement to compile */
  sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
  char **pzErrmsg                 /* OUT: sqlite3_malloc()ed error message */
){
  int rc = sqlite3_prepare_v2(db, zSql, -1, ppStmt, 0);
  if( rc!=SQLITE_OK ){
    *ppStmt = 0;
    idxDatabaseError(db, pzErrmsg);
  }
  return rc;
}

/*
** Create candidate indexes in database [dbm] based on the data in 
** linked-list pScan.
*/
static int idxCreateCandidates(
  sqlite3 *dbm,
  IdxScan *pScan,
................................................................................
  char **pzErrmsg
){
  int rc2;
  int rc = SQLITE_OK;
  sqlite3_stmt *pDepmask;         /* Foreach depmask */
  IdxScan *pIter;

  rc = idxPrepareStmt(dbm, "SELECT mask FROM depmask", &pDepmask, pzErrmsg);

  for(pIter=pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    IdxWhere *pWhere = &pIter->where;
    while( SQLITE_ROW==sqlite3_step(pDepmask) && rc==SQLITE_OK ){
      i64 mask = sqlite3_column_int64(pDepmask, 0);
      rc = idxCreateFromWhere(dbm, mask, pIter, pWhere, 0, 0);
      if( rc==SQLITE_OK && pIter->pOrder ){
................................................................................
}

int idxFindIndexes(
  sqlite3 *dbm,                        /* Database handle */
  const char *zSql,                    /* SQL to find indexes for */
  void (*xOut)(void*, const char*),    /* Output callback */
  void *pOutCtx,                       /* Context for xOut() */
  char **pzErrmsg                      /* OUT: Error message (sqlite3_malloc) */
){
  char *zExplain;
  sqlite3_stmt *pExplain;
  int rc;

  zExplain = sqlite3_mprintf("EXPLAIN QUERY PLAN %s", zSql);
  if( zExplain==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = idxPrepareStmt(dbm, zExplain, &pExplain, pzErrmsg);
    sqlite3_free(zExplain);


  }
  if( rc!=SQLITE_OK ) return rc;

  while( sqlite3_step(pExplain)==SQLITE_ROW ){
    int iCol;
    // for(iCol=0; iCol<sqlite3_column_count(pExplain); iCol++){ }










    xOut(pOutCtx, sqlite3_column_text(pExplain, 3));
  }


























  rc = sqlite3_finalize(pExplain);





}

/*
** The xOut callback is invoked to return command output to the user. The
** second argument is always a nul-terminated string. The first argument is
** passed zero if the string contains normal output or non-zero if it is an
** error message.
................................................................................
  char **pzErrmsg                      /* OUT: Error message (sqlite3_malloc) */
){
  int rc = SQLITE_OK;
  sqlite3 *dbm = 0;
  IdxContext ctx;
  sqlite3_stmt *pStmt = 0;        /* Statement compiled from zSql */

  rc = registerPragmaVtabs(db);
  if( rc ) return rc;
  memset(&ctx, 0, sizeof(IdxContext));

  /* Open an in-memory database to work with. The main in-memory 
  ** database schema contains tables similar to those in the users 
  ** database (handle db). The attached in-memory db (aux) contains
  ** application tables used by the code in this file.  */
  rc = sqlite3_open(":memory:", &dbm);
  if( rc==SQLITE_OK ){
    rc = sqlite3_exec(dbm, 
        "ATTACH ':memory:' AS aux;"
        "CREATE TABLE aux.depmask(mask PRIMARY KEY) WITHOUT ROWID;"
        "INSERT INTO aux.depmask VALUES(0);"
        , 0, 0, 0
    );
  }

  /* Prepare an INSERT statement for writing to aux.depmask */
  if( rc==SQLITE_OK ){
    rc = sqlite3_prepare_v2(dbm, 
        "INSERT OR IGNORE INTO depmask SELECT mask | ?1 FROM depmask;", -1,
        &ctx.pInsertMask, 0
    );
  }

  if( rc!=SQLITE_OK ){
    idxDatabaseError(dbm, pzErrmsg);
    goto indexes_out;
  }

  /* Analyze the SELECT statement in zSql. */

  ctx.dbm = dbm;
  sqlite3_db_config(db, SQLITE_DBCONFIG_WHEREINFO, idxWhereInfo, (void*)&ctx);
  rc = sqlite3_prepare(db, zSql, -1, &pStmt, 0);

  sqlite3_db_config(db, SQLITE_DBCONFIG_WHEREINFO, (void*)0, (void*)0);

  if( rc!=SQLITE_OK ){
    idxDatabaseError(db, pzErrmsg);
    goto indexes_out;

  }

  /* Create tables within the main in-memory database. These tables
  ** have the same names, columns and declared types as the tables in
  ** the user database. All constraints except for PRIMARY KEY are
  ** removed. */

  rc = idxCreateTables(db, dbm, ctx.pScan, pzErrmsg);



  if( rc!=SQLITE_OK ){
    goto indexes_out;

  }

  /* Create candidate indexes within the in-memory database file */
  rc = idxCreateCandidates(dbm, ctx.pScan, pzErrmsg);
  if( rc!=SQLITE_OK ){
    goto indexes_out;
  }

  rc = idxFindIndexes(dbm, zSql, xOut, pOutCtx, pzErrmsg);

 indexes_out:

  idxScanFree(ctx.pScan);
  sqlite3_close(dbm);
  return rc;
}









|
>













|

|
>
>

>
>

>
>
>

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





<







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







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






|







|
<
<
<
<
<
|
|


|







 







|


|




|







 







|







 







>

>







 







<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|







 







|

|
|
|

|
<
|
<
|
<
>
>

<

|
|
<
>
>
>
>
>
>
>
>
>
>
|
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>







 







<
<












|





|
|
<



<
<
<
<
<

>
|
|
<
>
|
<
<
<
<
>






>
|
>
>
>
|
<
>



<
|
<
<
<
|
|
<
>






21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

78
79
80
81
82
83
84
...
114
115
116
117
118
119
120











































































































































































































121
122
123
124
125
126
127
...
293
294
295
296
297
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
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
...
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
...
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
...
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
...
628
629
630
631
632
633
634














635
636
637
638
639
640
641
...
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
...
668
669
670
671
672
673
674
675
676
677
678
679
680
681

682

683

684
685
686

687
688
689

690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
...
747
748
749
750
751
752
753


754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773

774
775
776





777
778
779
780

781
782




783
784
785
786
787
788
789
790
791
792
793
794
795

796
797
798
799

800



801
802

803
804
805
806
807
808
809
typedef struct IdxColumn IdxColumn;
typedef struct IdxTable IdxTable;

/*
** A single constraint. Equivalent to either "col = ?" or "col < ?".
**
** pLink:
**   Used to temporarily link IdxConstraint objects into lists while
**   creating candidate indexes.
*/
struct IdxConstraint {
  char *zColl;                    /* Collation sequence */
  int bRange;                     /* True for range, false for eq */
  int iCol;                       /* Constrained table column */
  i64 depmask;                    /* Dependency mask */
  IdxConstraint *pNext;           /* Next constraint in pEq or pRange list */
  IdxConstraint *pLink;           /* See above */
};

/*
** A WHERE clause. Made up of IdxConstraint objects. Example WHERE clause:
**
**   a=? AND b=? AND ((c=? AND d=?) OR e=?) AND (f=? OR g=?) AND h>?
**
** The above is decomposed into 5 AND connected clauses. The first two are
** added to the IdxWhere.pEq linked list, the following two into 
** IdxWhere.pOr and the last into IdxWhere.pRange.
**
** IdxWhere.pEq and IdxWhere.pRange are simple linked lists of IdxConstraint
** objects linked by the IdxConstraint.pNext field.
**
** The list headed at IdxWhere.pOr and linked by IdxWhere.pNextOr contains
** all "OR" terms that belong to the current WHERE clause. In the example
** above, there are two OR terms:
**
**   ((c=? AND d=?) OR e=?)
**   (f=? OR g=?)
**
** Within an OR term, the OR connected sub-expressions are termed siblings.
** These are connected into a linked list by the pSibling pointers. Each OR
** term above consists of two siblings.
**
**   pOr -> (c=? AND d=?) -> pNextOr -> (f=?)
**               |                        |
**            pSibling                 pSibling
**               |                        |
**               V                        V
**             (e=?)                    (g=?)
**
** IdxWhere.pParent is only used while constructing a tree of IdxWhere 
** structures. It is NULL for the root IdxWhere. For all others, the parent
** WHERE clause.
*/
struct IdxWhere {
  IdxConstraint *pEq;             /* List of == constraints */
  IdxConstraint *pRange;          /* List of < constraints */
  IdxWhere *pOr;                  /* List of OR constraints */

  IdxWhere *pNextOr;              /* Next in OR constraints of same IdxWhere */
  IdxWhere *pSibling;             /* Next branch in single OR constraint */
  IdxWhere *pParent;              /* Parent object (or NULL) */
};

/*
** A single scan of a single table.
................................................................................
  int iPk;
};
struct IdxTable {
  int nCol;
  IdxColumn *aCol;
};












































































































































































































/*
** Allocate and return nByte bytes of zeroed memory using sqlite3_malloc(). 
** If the allocation fails, set *pRc to SQLITE_NOMEM and return NULL.
*/
static void *idxMalloc(int *pRc, int nByte){
  void *pRet;
  assert( *pRc==SQLITE_OK );
................................................................................
      zRet = 0;
    }
    *pRc = rc;
  }

  return zRet;
}

static int idxPrepareStmt(
  sqlite3 *db,                    /* Database handle to compile against */
  sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
  char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
  const char *zSql                /* SQL statement to compile */
){
  int rc = sqlite3_prepare_v2(db, zSql, -1, ppStmt, 0);
  if( rc!=SQLITE_OK ){
    *ppStmt = 0;
    idxDatabaseError(db, pzErrmsg);
  }
  return rc;
}

static int idxPrintfPrepareStmt(
  sqlite3 *db,                    /* Database handle to compile against */
  sqlite3_stmt **ppStmt,          /* OUT: Compiled SQL statement */
  char **pzErrmsg,                /* OUT: sqlite3_malloc()ed error message */
  const char *zFmt,               /* printf() format of SQL statement */
  ...                             /* Trailing printf() arguments */
){
  va_list ap;
  int rc;
  char *zSql;
  va_start(ap, zFmt);
  zSql = sqlite3_vmprintf(zFmt, ap);
  if( zSql==0 ){
    rc = SQLITE_NOMEM;
  }else{
    rc = idxPrepareStmt(db, ppStmt, pzErrmsg, zSql);
    sqlite3_free(zSql);
  }
  va_end(ap);
  return rc;
}

static int idxGetTableInfo(
  sqlite3 *db,
  IdxScan *pScan,
  char **pzErrmsg
){
  const char *zTbl = pScan->zTable;
  sqlite3_stmt *p1 = 0;
  int nCol = 0;
  int nByte = sizeof(IdxTable);
  IdxTable *pNew = 0;
  int rc, rc2;
  char *pCsr;

  rc = idxPrintfPrepareStmt(db, &p1, pzErrmsg, "PRAGMA table_info=%Q", zTbl);





  while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = sqlite3_column_text(p1, 1);
    nByte += 1 + strlen(zCol);
    rc = sqlite3_table_column_metadata(
        db, "main", zTbl, zCol, 0, &zCol, 0, 0, 0
    );
    nByte += 1 + strlen(zCol);
    nCol++;
  }
  rc2 = sqlite3_reset(p1);
  if( rc==SQLITE_OK ) rc = rc2;

................................................................................
    pNew->aCol = (IdxColumn*)&pNew[1];
    pNew->nCol = nCol;
    pCsr = (char*)&pNew->aCol[nCol];
  }

  nCol = 0;
  while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(p1) ){
    const char *zCol = sqlite3_column_text(p1, 1);
    int nCopy = strlen(zCol) + 1;
    pNew->aCol[nCol].zName = pCsr;
    pNew->aCol[nCol].iPk = sqlite3_column_int(p1, 5);
    memcpy(pCsr, zCol, nCopy);
    pCsr += nCopy;

    rc = sqlite3_table_column_metadata(
        db, "main", zTbl, zCol, 0, &zCol, 0, 0, 0
    );
    if( rc==SQLITE_OK ){
      nCopy = strlen(zCol) + 1;
      pNew->aCol[nCol].zColl = pCsr;
      memcpy(pCsr, zCol, nCopy);
      pCsr += nCopy;
    }
................................................................................
      }else{
        zCreate = sqlite3_mprintf("CREATE TABLE %Q(%s)", pIter->zTable, zCols);
      }
      if( zCreate==0 ) rc = SQLITE_NOMEM;
    }

    if( rc==SQLITE_OK ){
#if 0
      printf("/* %s */\n", zCreate);
#endif
      rc = sqlite3_exec(dbm, zCreate, 0, 0, pzErrmsg);
    }
    sqlite3_free(zCols);
    sqlite3_free(zPk);
    sqlite3_free(zCreate);
................................................................................
      zIdx = sqlite3_mprintf("CREATE INDEX IF NOT EXISTS "
          "'%q_idx_%08x' ON %Q(%s)", pScan->zTable, h, pScan->zTable, zCols
      );
      if( !zIdx ){
        rc = SQLITE_NOMEM;
      }else{
        rc = sqlite3_exec(dbm, zIdx, 0, 0, 0);
#if 0
        printf("/* %s */\n", zIdx);
#endif
      }
    }

    sqlite3_free(zIdx);
    sqlite3_free(zCols);
  }
  return rc;
................................................................................
      }
    }
  }

  return rc;
}















/*
** Create candidate indexes in database [dbm] based on the data in 
** linked-list pScan.
*/
static int idxCreateCandidates(
  sqlite3 *dbm,
  IdxScan *pScan,
................................................................................
  char **pzErrmsg
){
  int rc2;
  int rc = SQLITE_OK;
  sqlite3_stmt *pDepmask;         /* Foreach depmask */
  IdxScan *pIter;

  rc = idxPrepareStmt(dbm, &pDepmask, pzErrmsg, "SELECT mask FROM depmask");

  for(pIter=pScan; pIter && rc==SQLITE_OK; pIter=pIter->pNextScan){
    IdxWhere *pWhere = &pIter->where;
    while( SQLITE_ROW==sqlite3_step(pDepmask) && rc==SQLITE_OK ){
      i64 mask = sqlite3_column_int64(pDepmask, 0);
      rc = idxCreateFromWhere(dbm, mask, pIter, pWhere, 0, 0);
      if( rc==SQLITE_OK && pIter->pOrder ){
................................................................................
}

int idxFindIndexes(
  sqlite3 *dbm,                        /* Database handle */
  const char *zSql,                    /* SQL to find indexes for */
  void (*xOut)(void*, const char*),    /* Output callback */
  void *pOutCtx,                       /* Context for xOut() */
  char **pzErr                         /* OUT: Error message (sqlite3_malloc) */
){
  sqlite3_stmt *pExplain = 0;
  sqlite3_stmt *pSelect = 0;
  int rc, rc2;

  rc = idxPrintfPrepareStmt(dbm, &pExplain, pzErr,"EXPLAIN QUERY PLAN %s",zSql);

  if( rc==SQLITE_OK ){

    rc = idxPrepareStmt(dbm, &pSelect, pzErr, 

        "SELECT sql FROM sqlite_master WHERE name = ?"
    );
  }


  while( rc==SQLITE_OK && sqlite3_step(pExplain)==SQLITE_ROW ){
    int i;

    const char *zDetail = (const char*)sqlite3_column_text(pExplain, 3);
    int nDetail = strlen(zDetail);

    for(i=0; i<nDetail; i++){
      if( memcmp(&zDetail[i], " USING INDEX ", 13)==0 ){
        int nIdx = 0;
        const char *zIdx = &zDetail[i+13];
        while( zIdx[nIdx]!='\0' && zIdx[nIdx]!=' ' ) nIdx++;
        sqlite3_bind_text(pSelect, 1, zIdx, nIdx, SQLITE_STATIC);
        if( SQLITE_ROW==sqlite3_step(pSelect) ){
          xOut(pOutCtx, sqlite3_column_text(pSelect, 0));
        }
        rc = sqlite3_reset(pSelect);
        break;
      }
    }
  }
  rc2 = sqlite3_reset(pExplain);
  if( rc==SQLITE_OK ) rc = rc2;
  if( rc==SQLITE_OK ) xOut(pOutCtx, "");

  while( rc==SQLITE_OK && sqlite3_step(pExplain)==SQLITE_ROW ){
    int iSelectid = sqlite3_column_int(pExplain, 0);
    int iOrder = sqlite3_column_int(pExplain, 1);
    int iFrom = sqlite3_column_int(pExplain, 2);
    const char *zDetail = (const char*)sqlite3_column_text(pExplain, 3);
    char *zOut;

    zOut = sqlite3_mprintf("%d|%d|%d|%s", iSelectid, iOrder, iFrom, zDetail);
    if( zOut==0 ){
      rc = SQLITE_NOMEM;
    }else{
      xOut(pOutCtx, zOut);
      sqlite3_free(zOut);
    }
  }

 find_indexes_out:
  rc2 = sqlite3_finalize(pExplain);
  if( rc==SQLITE_OK ) rc = rc2;
  rc2 = sqlite3_finalize(pSelect);
  if( rc==SQLITE_OK ) rc = rc2;

  return rc;
}

/*
** The xOut callback is invoked to return command output to the user. The
** second argument is always a nul-terminated string. The first argument is
** passed zero if the string contains normal output or non-zero if it is an
** error message.
................................................................................
  char **pzErrmsg                      /* OUT: Error message (sqlite3_malloc) */
){
  int rc = SQLITE_OK;
  sqlite3 *dbm = 0;
  IdxContext ctx;
  sqlite3_stmt *pStmt = 0;        /* Statement compiled from zSql */



  memset(&ctx, 0, sizeof(IdxContext));

  /* Open an in-memory database to work with. The main in-memory 
  ** database schema contains tables similar to those in the users 
  ** database (handle db). The attached in-memory db (aux) contains
  ** application tables used by the code in this file.  */
  rc = sqlite3_open(":memory:", &dbm);
  if( rc==SQLITE_OK ){
    rc = sqlite3_exec(dbm, 
        "ATTACH ':memory:' AS aux;"
        "CREATE TABLE aux.depmask(mask PRIMARY KEY) WITHOUT ROWID;"
        "INSERT INTO aux.depmask VALUES(0);"
        , 0, 0, pzErrmsg
    );
  }

  /* Prepare an INSERT statement for writing to aux.depmask */
  if( rc==SQLITE_OK ){
    rc = idxPrepareStmt(dbm, &ctx.pInsertMask, pzErrmsg,
        "INSERT OR IGNORE INTO depmask SELECT mask | ?1 FROM depmask;"

    );
  }






  /* Analyze the SELECT statement in zSql. */
  if( rc==SQLITE_OK ){
    ctx.dbm = dbm;
    sqlite3_db_config(db, SQLITE_DBCONFIG_WHEREINFO, idxWhereInfo, (void*)&ctx);

    rc = idxPrepareStmt(db, &pStmt, pzErrmsg, zSql);
    sqlite3_db_config(db, SQLITE_DBCONFIG_WHEREINFO, (void*)0, (void*)0);




    sqlite3_finalize(pStmt);
  }

  /* Create tables within the main in-memory database. These tables
  ** have the same names, columns and declared types as the tables in
  ** the user database. All constraints except for PRIMARY KEY are
  ** removed. */
  if( rc==SQLITE_OK ){
    rc = idxCreateTables(db, dbm, ctx.pScan, pzErrmsg);
  }

  /* Create candidate indexes within the in-memory database file */
  if( rc==SQLITE_OK ){

    rc = idxCreateCandidates(dbm, ctx.pScan, pzErrmsg);
  }

  /* Create candidate indexes within the in-memory database file */

  if( rc==SQLITE_OK ){



    rc = idxFindIndexes(dbm, zSql, xOut, pOutCtx, pzErrmsg);
  }


  idxScanFree(ctx.pScan);
  sqlite3_close(dbm);
  return rc;
}