sqlite3 where結(jié)構(gòu)中的查詢重寫，選取適合的索引
index 結(jié)構(gòu)體內(nèi)容
一個(gè)index結(jié)果里面，有好多統(tǒng)計(jì)數(shù)據(jù)
每個(gè)索引結(jié)構(gòu)中存放這key的統(tǒng)計(jì)信息，所謂統(tǒng)計(jì)直方圖，是放在index結(jié)果體中
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
};
/**/
在這個(gè)結(jié)構(gòu)體凹联，indexsample中結(jié)構(gòu)體定義如下
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 */
};
存放著，最左邊的元素哆档。其中統(tǒng)計(jì)信息有蔽挠，跟這個(gè)值相等的個(gè)數(shù)，比他小的值的個(gè)數(shù)瓜浸，比它小的不同的值的個(gè)數(shù)
其中澳淑，下進(jìn)行rang個(gè)數(shù)估算的時(shí)候，有用到index里面的值插佛，跟他相等的杠巡，和比它小的，在where.c 的約第2734行雇寇，whereRangeScanEst 結(jié)構(gòu)里
whereEquascanEst 結(jié)構(gòu)體中任然存在這樣的結(jié)構(gòu)
whereInScanEst 結(jié)構(gòu)也應(yīng)用了這個(gè)結(jié)構(gòu)氢拥，分別統(tǒng)計(jì)等于，再相加锨侯，所有的在where條件中的查詢優(yōu)化嫩海，最重要的就是訪問index結(jié)構(gòu)中
代價(jià)評估，x = value value出現(xiàn)在數(shù)據(jù)直方圖中识腿，
這統(tǒng)計(jì)直方圖的存放形式就是用結(jié)構(gòu)體給表示出來。
whereCost這個(gè)代碼造壮，是存放查詢計(jì)劃的地方
WherePlan 是存放查詢計(jì)劃的地方渡讼，供外面的函數(shù)進(jìn)行調(diào)用。存放有策略耳璧，估計(jì)的行數(shù)使用的索引結(jié)構(gòu)等成箫，方便下一步查詢的時(shí)候使用
where語句優(yōu)化
大量采用虛擬表達(dá)式(virtual term)這種形式，在一個(gè)真實(shí)的where條件后旨枯，再加一個(gè)等價(jià)的條件蹬昌，然后在代價(jià)估算的時(shí)候，逐一判斷累計(jì)代價(jià)攀隔，最后選擇出最合適的代價(jià)估算方案皂贩。
or語句優(yōu)化
優(yōu)化部位栖榨，在sql語句中where子句部分
WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
^^^^^^^^^^^^^^^^^^^^
采取的優(yōu)化策略
-
把where中 多個(gè)or條件轉(zhuǎn)化為in條件。
x = expr1 OR expr2 = x OR x = expr3------>
x IN (expr1,expr2,expr3) 第二中情況明刷。如果在子查詢條件中婴栽，有例如
"=", "<", "<=", ">", ">=", "IS NULL", "IN".這樣的條件，就掃描索引辈末，累加代價(jià)估算愚争。否則就不優(yōu)化
步驟or語句分解
找出可以滿足case 1，或者case2的項(xiàng)
做出相應(yīng)的標(biāo)記挤聘，方便后面進(jìn)行代價(jià)估算轰枝，查找出最佳的代價(jià)
改成左表達(dá)式
運(yùn)用左深樹，更省內(nèi)存组去。左深樹的改寫鞍陨，所有的類似于 xxx = A的這種表達(dá)式，都會(huì)被轉(zhuǎn)化為A = xxx這種形式
多列索引使用規(guī)則
如果有一個(gè)類似于這樣的多列索引創(chuàng)建
CREATE INDEX idx_ex1 ON ex1(a,b,c,d,e,...,y,z);
在多列索引中添怔，有時(shí)候湾戳，這些索引會(huì)被用到，而有時(shí)候并不會(huì)被用到
WHERE a=5 AND b IN (1,2,3) AND c IS NULL AND d='hello'
這樣的子句广料，在 abcd列上的索引會(huì)被用到砾脑。
WHERE a=5 AND b IN (1,2,3) AND c>12 AND d='hello'
這樣的子句，只有在abc列上的索引會(huì)被用到艾杏，因?yàn)閏列是>號
WHERE a=5 AND b IN (1,2,3) AND d='hello'
如果這樣的where子句韧衣，之后ab列上的索引會(huì)被用到，因?yàn)橹虚g有c列被跳過
between規(guī)則改寫
在范圍查詢中a BETWEEN b AND c會(huì)改寫成 (a BETWEEN b AND c) AND (a>=b) AND (a<=c)這樣的购桑，就可以通過利用索引結(jié)構(gòu)中 的一些統(tǒng)計(jì)數(shù)據(jù)來完成優(yōu)化畅铭，同事，由于后面的規(guī)則是附加上去的勃蜘。如果可以優(yōu)化就采用優(yōu)化后的結(jié)構(gòu)硕噩，那就直接跳過where子句中的between條件。
同樣的原理
x LIKE 'abc%'會(huì)被轉(zhuǎn)化為x>='abc' AND x<'abd' AND x LIKE 'abc%'缭贡、X is not NULL 轉(zhuǎn)為 x>NULL通過這些邏輯重寫炉擅。完成課堂上所講的代數(shù)優(yōu)化工作。
distinct 是否能被轉(zhuǎn)化
如果where 子句中阳惹，有col = x 在x 上的distinct谍失，這種distinct就可以被取消。如果莹汤，該列快鱼，有unique，就把它distinct設(shè)置成冗余。這同樣也是一種代數(shù)優(yōu)化方式
找出可以利用的index信息抹竹。做上相應(yīng)的標(biāo)記线罕。通過循環(huán)查找表中的index，進(jìn)行優(yōu)化匹配柒莉。
索引闻坚，能否在orderby 中優(yōu)化
如果，列不在兢孝，from子句中的最左邊的列窿凤，那么，這個(gè)索引跨蟹，在orderby 中就沒有用雳殊，這是因?yàn)椋瑂qlite在使用多表連接的時(shí)候使用的是簡單嵌套循環(huán)連接窗轩。如果索引列在from不是最左邊的列夯秃。在進(jìn)行連接的時(shí)候，就會(huì)順序會(huì)被打亂
如果痢艺，有== 約束仓洼，對應(yīng)條件的索引就設(shè)置成失效。在沒有索引能夠正常使用的情況下堤舒，就采用用主鍵的索引（沒有orderby 的項(xiàng)目用在表的連接上）
如果所有的orderby項(xiàng)色建，列條件都能被index覆蓋，那么這個(gè)index就能被索引
為建立虛表計(jì)算出最合適的索引（where.c 2330）
在 兩個(gè)表舌缤，進(jìn)行join的時(shí)候箕戳，會(huì)執(zhí)行多次在虛表建立過程中，為了保證高效国撵，可能會(huì)用到多列索引
在where中range掃描估計(jì)陵吸，（在有索引的情況下）單側(cè)不等式，被估計(jì)為1/4 雙側(cè)不等式被估計(jì)為1/16 代碼在where.c 第2713行左右
在選擇最佳的執(zhí)行計(jì)劃的時(shí)候介牙，會(huì)參考代價(jià)估算如果代價(jià)估算壮虫。其中如果估算代價(jià)小于掃描所有行數(shù)的時(shí)候才會(huì)可能被采納到。
總結(jié)：
在整個(gè)sqlite系統(tǒng)中环础，我們子啊課堂上學(xué)習(xí)到的一些優(yōu)化算法囚似，例如邏輯優(yōu)化，和物理優(yōu)化喳整，選擇合適的索引等谆构，在實(shí)際的程序?qū)崿F(xiàn)的時(shí)候都即依賴上一層sql解析器中傳過來來的具體的sql結(jié)構(gòu)裸扶，也依賴下層數(shù)據(jù)存儲(chǔ)的信息框都，例如是否有索引，有哪些索引，在數(shù)據(jù)列中比當(dāng)前數(shù)據(jù)還要小的數(shù)據(jù)有多少魏保？還有課堂上老師在講查詢估算的時(shí)候的估算方法熬尺，所有的信息都是用相應(yīng)的結(jié)構(gòu)體存放在特定的結(jié)構(gòu)中。很多時(shí)候谓罗，所有的結(jié)構(gòu)體都不會(huì)是單一存在的粱哼，結(jié)構(gòu)體會(huì)嵌套結(jié)構(gòu)體。每個(gè)結(jié)構(gòu)體中會(huì)存放相應(yīng)的信息檩咱。
在看sqlite源碼過程中揭措，我體會(huì)到了一個(gè)課本上的優(yōu)化方法，是如何轉(zhuǎn)化為實(shí)際的數(shù)據(jù)庫產(chǎn)品刻蚯。作者通過設(shè)計(jì)一些列巧妙的結(jié)構(gòu)體绊含，精心讀寫相應(yīng)的結(jié)構(gòu)體。比如統(tǒng)計(jì)直方圖的設(shè)計(jì)方式就很是精巧的結(jié)構(gòu)體來實(shí)現(xiàn)的炊汹。在index結(jié)構(gòu)體中躬充，嵌套indexsample結(jié)構(gòu)體，在indexsample中存放一些統(tǒng)計(jì)信息讨便，并精心維護(hù)充甚。
另外sqlite是用c語言編寫的一個(gè)數(shù)據(jù)庫。在c語言這個(gè)面向過程的語言中霸褒，進(jìn)行精巧的設(shè)計(jì)結(jié)構(gòu)伴找，和函數(shù)保證系統(tǒng)設(shè)計(jì)的運(yùn)行效率。
通過這門課程我最大的感受就是傲霸，每一個(gè)想法疆瑰，點(diǎn)子，和鎖需要用到的信息昙啄，都需要用精巧的設(shè)計(jì)和定義才能完成穆役。
