sqlite3 where结构中的查询重写，选取适合的索引

index 结构体内容

一个index结果里面，有好多统计数据
每个索引结构中存放这key的统计信息，所谓统计直方图，是放在index结果体中

struct Index {
  char *zName;     /* Name of this index */
  int *aiColumn;   /* Which columns are used by this index.  1st is 0 */
  tRowcnt *aiRowEst; /* Result of ANALYZE: Est. rows selected by each column */
  Table *pTable;   /* The SQL table being indexed */
  char *zColAff;   /* String defining the affinity of each column */
  Index *pNext;    /* The next index associated with the same table */
  Schema *pSchema; /* Schema containing this index */
  u8 *aSortOrder;  /* Array of size Index.nColumn. True==DESC, False==ASC */
  char **azColl;   /* Array of collation sequence names for index */
  int nColumn;     /* Number of columns in the table used by this index */
  int tnum;        /* Page containing root of this index in database file */
  u8 onError;      /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
  u8 autoIndex;    /* True if is automatically created (ex: by UNIQUE) */
  u8 bUnordered;   /* Use this index for == or IN queries only */
#ifdef SQLITE_ENABLE_STAT3
  int nSample;             /* Number of elements in aSample[] 主要信息*/
  tRowcnt avgEq;           /* Average nEq value for key values not in aSample */
  IndexSample *aSample;    /* Samples of the left-most key */
#endif
};

/**/

在这个结构体，indexsample中结构体定义如下

struct IndexSample {
  union {
    char *z;        /* Value if eType is SQLITE_TEXT or SQLITE_BLOB */
    double r;       /* Value if eType is SQLITE_FLOAT */
    i64 i;          /* Value if eType is SQLITE_INTEGER */
  } u;
  u8 eType;         /* SQLITE_NULL, SQLITE_INTEGER ... etc. */
  int nByte;        /* Size in byte of text or blob. */
  tRowcnt nEq;      /* Est. number of rows where the key equals this sample */
  tRowcnt nLt;      /* Est. number of rows where key is less than this sample */
  tRowcnt nDLt;     /* Est. number of distinct keys less than this sample */
};

存放着，最左边的元素。其中统计信息有，跟这个值相等的个数，比他小的值的个数，比它小的不同的值的个数
其中，下进行rang个数估算的时候，有用到index里面的值，跟他相等的，和比它小的，在where.c 的约第2734行，whereRangeScanEst 结构里

whereEquascanEst 结构体中任然存在这样的结构

whereInScanEst 结构也应用了这个结构，分别统计等于，再相加，所有的在where条件中的查询优化，最重要的就是访问index结构中

代价评估，x = value value出现在数据直方图中，

这统计直方图的存放形式就是用结构体给表示出来。
whereCost这个代码，是存放查询计划的地方
WherePlan 是存放查询计划的地方，供外面的函数进行调用。存放有策略，估计的行数使用的索引结构等，方便下一步查询的时候使用

where语句优化

大量采用虚拟表达式(virtual term)这种形式，在一个真实的where条件后，再加一个等价的条件，然后在代价估算的时候，逐一判断累计代价，最后选择出最合适的代价估算方案。

or语句优化

优化部位，在sql语句中where子句部分

WHERE  (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
                 ^^^^^^^^^^^^^^^^^^^^

采取的优化策略

1. 把where中 多个or条件转化为in条件。

   x = expr1 OR expr2 = x OR x = expr3------>
   x IN (expr1,expr2,expr3)

2. 第二中情况。如果在子查询条件中，有例如"=", "<", "<=", ">", ">=", "IS NULL", "IN".这样的条件，就扫描索引，累加代价估算。否则就不优化
   步骤

3. or语句分解

4. 找出可以满足case 1，或者case2的项

5. 做出相应的标记，方便后面进行代价估算，查找出最佳的代价

改成左表达式

运用左深树，更省内存。左深树的改写，所有的类似于 xxx = A的这种表达式，都会被转化为A = xxx这种形式

多列索引使用规则

如果有一个类似于这样的多列索引创建

CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);

在多列索引中，有时候，这些索引会被用到，而有时候并不会被用到

WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'

这样的子句，在 abcd列上的索引会被用到。

WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'

这样的子句，只有在abc列上的索引会被用到，因为c列是>号

WHERE a=5 AND b IN (1,2,3) AND d='hello'

如果这样的where子句，之后ab列上的索引会被用到，因为中间有c列被跳过

between规则改写

在范围查询中a BETWEEN b AND c会改写成 (a BETWEEN b AND c) AND (a>=b) AND (a<=c)这样的，就可以通过利用索引结构中 的一些统计数据来完成优化，同事，由于后面的规则是附加上去的。如果可以优化就采用优化后的结构，那就直接跳过where子句中的between条件。

同样的原理

x LIKE 'abc%'会被转化为x>='abc' AND x<'abd' AND x LIKE 'abc%'、X is not NULL 转为 x>NULL通过这些逻辑重写。完成课堂上所讲的代数优化工作。

distinct 是否能被转化

如果where 子句中，有col = x 在x 上的distinct，这种distinct就可以被取消。如果，该列，有unique，就把它distinct设置成冗余。这同样也是一种代数优化方式
找出可以利用的index信息。做上相应的标记。通过循环查找表中的index，进行优化匹配。

索引，能否在orderby 中优化

如果，列不在，from子句中的最左边的列，那么，这个索引，在orderby 中就没有用，这是因为，sqlite在使用多表连接的时候使用的是简单嵌套循环连接。如果索引列在from不是最左边的列。在进行连接的时候，就会顺序会被打乱
如果，有== 约束，对应条件的索引就设置成失效。在没有索引能够正常使用的情况下，就采用用主键的索引（没有orderby 的项目用在表的连接上）

如果所有的orderby项，列条件都能被index覆盖，那么这个index就能被索引

为建立虚表计算出最合适的索引（where.c 2330）

在 两个表，进行join的时候，会执行多次在虚表建立过程中，为了保证高效，可能会用到多列索引
在where中range扫描估计，（在有索引的情况下）单侧不等式，被估计为1/4 双侧不等式被估计为1/16 代码在where.c 第2713行左右
在选择最佳的执行计划的时候，会参考代价估算如果代价估算。其中如果估算代价小于扫描所有行数的时候才会可能被采纳到。

总结：

在整个sqlite系统中，我们子啊课堂上学习到的一些优化算法，例如逻辑优化，和物理优化，选择合适的索引等，在实际的程序实现的时候都即依赖上一层sql解析器中传过来来的具体的sql结构，也依赖下层数据存储的信息，例如是否有索引，有哪些索引，在数据列中比当前数据还要小的数据有多少？还有课堂上老师在讲查询估算的时候的估算方法，所有的信息都是用相应的结构体存放在特定的结构中。很多时候，所有的结构体都不会是单一存在的，结构体会嵌套结构体。每个结构体中会存放相应的信息。

在看sqlite源码过程中，我体会到了一个课本上的优化方法，是如何转化为实际的数据库产品。作者通过设计一些列巧妙的结构体，精心读写相应的结构体。比如统计直方图的设计方式就很是精巧的结构体来实现的。在index结构体中，嵌套indexsample结构体，在indexsample中存放一些统计信息，并精心维护。

另外sqlite是用c语言编写的一个数据库。在c语言这个面向过程的语言中，进行精巧的设计结构，和函数保证系统设计的运行效率。

通过这门课程我最大的感受就是，每一个想法，点子，和锁需要用到的信息，都需要用精巧的设计和定义才能完成。