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)
^^^^^^^^^^^^^^^^^^^^
采取的优化策略
-
把where中 多个or条件转化为in条件。
x = expr1 OR expr2 = x OR x = expr3------>
x IN (expr1,expr2,expr3) 第二中情况。如果在子查询条件中，有例如
"=", "<", "<=", ">", ">=", "IS NULL", "IN".这样的条件，就扫描索引，累加代价估算。否则就不优化
步骤or语句分解
找出可以满足case 1，或者case2的项
做出相应的标记，方便后面进行代价估算，查找出最佳的代价
改成左表达式
运用左深树，更省内存。左深树的改写，所有的类似于 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语言这个面向过程的语言中，进行精巧的设计结构，和函数保证系统设计的运行效率。
通过这门课程我最大的感受就是，每一个想法，点子，和锁需要用到的信息，都需要用精巧的设计和定义才能完成。
