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à)評(píng)估，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)化策略

1. 把where中 多個(gè)or條件轉(zhuǎn)化為in條件。

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

2. 第二中情況。如果在子查詢條件中，有例如"=", "<", "<=", ">", ">=", "IS NULL", "IN".這樣的條件，就掃描索引，累加代價(jià)估算。否則就不優(yōu)化
   步驟

3. or語句分解

4. 找出可以滿足case 1，或者case2的項(xiàng)

5. 做出相應(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)閏列是>號(hào)

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)?，sqlite在使用多表連接的時(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ì)和定義才能完成。