Descending indexing and loose index scan
降序索引和減輕索引掃描
Comments to my previous posts, especially this one by Gokhan inspired me to write a bit about descending indexes and about loose index scan, or what Gokhan calls “better range” support. None of these are actially related to Innodb tables in general - these are features MySQL should get for all storage engines at some point.
在我以前文章的評論中，尤其是 Gokhan 在這個中提到的，激發了我想寫點關於降序索引和減輕索引掃描的東西，或者是 Gokhan 所謂的“改善的范圍”支持。通常這些特性跟 Innodb 表都沒有內在聯系，它們將來在某些時候都能支持各種存儲引擎。
Descending indexes - This is something MySQL does not have at this point, but it was not where for so long at large extent because it is less problem than many people think. First - if index is ascending it does not mean it can’t be scanned in reverse order and it will well be. This is how MySQL will optimize indexed ORDER BY col DESC querIEs for example. Reverse scan could be as fast as forward scan - this is however where storage engines and operating systems come in play. For example certain Operation systems might not do backward read-ahead which may slow it down a bit. Or some storage engines, such as MyISAM (for packed indexes) may have reverse scan being much slower than forward scan.
降序索引 -- 現在 MySQL 還不支持這個功能，不過這比很多人想的那樣，問題少多了。首先，如果索引是順序的並不意味著它不能倒序掃描，實際上它表現得挺好的。這就是為什麼 MySQL 能優化例如 ORDER BY col DESC 查詢的索引。倒序掃描能和正序掃描一樣快，不過這些是由存儲引擎和操作系統來處理的。例如有些操作系統無法倒序讀，這對速度有所降低。或者某些存儲引擎，如 MyISAM (它壓縮了索引) 倒序掃描時比正序掃描來的慢。
So when do you really need Descending indexes ? Most typical case is when you want to order by two colums in different directions: … ORDER BY price ASC, date DESC LIMIT 10 If you have indexed on (price,date) in ascending order you will not be able to optimize this query well - external sort (”filesort”) will be needed. If you would be able to build index on price ASC, date DESC the same query could retrive data in aready sorted order.
那麼什麼時候才真的需要倒序索引呢？很多典型的情況是當你想要對兩個字段作不同方向的排序時：… ORDER BY price ASC, date DESC LIMIT 10。如果已經有了對 (price,date) 的正序索引，則不能較好地優化這個查詢 -- 需要用到外部排序(“filesort”)。如果能建立 price ASC, date DESC 的索引，那麼這個查詢就能按照已經排好的順序取出數據了。
This is however something you can workaround by having something like “reverse_date” column and using it for sort. With MySQL 5.0 you even can use triggers to update it as real date updates so it becomes less ugly. In fact this is for example why you would see “reverse_timestamp” fIEld in Wikipedia table structure.
然而，常見的變通辦法是創建一個“倒序數據”字段，並且利用它來排序。在 MySQL 5.0 中你甚至可以使用觸發器來更新真實的數據使得更合適。這就是為什在 Wikipedia 的表結構中有一個 “reverse_timestamp” 字段的緣故。
Loose index scan - Number of years ago when I just started using MySQL I thought it would have any optimization which could come to my mind. For example if I would have (A>0 and B>6) clause and index (A,B) I expected it would start looking at all values where A>0 instantly jumping to onces have B>6 by using index. It is possibe. So I was shocked and upset to find out it did not. And this optimization is still not implemented. This is very important item to remember when you designing your new applications or porting ones from other databases. Designing the indexes for MySQL you should only make sure querIEs use “=” for all keyparts in the last of index. Only last one is allowed to have “range” clauses, such as >, IN etc. All clauses which follow the range in the index will not use index for their Operation.
減少索引掃描 -- 多年前當我剛開始使用 MySQL 時，我想它也許有些優化方法能讓我記住。例如如果有一個 (A>0 and B>6) 分句和索引 (A,B)，我期望能使用索引來查找所有 A>0 的值，並且能立刻跳轉到 B>6 的記錄上，我想這是可行的。不過令我郁悶的是竟然不支持，並且這種優化方法還未實現。在設計新的應用程序或者移植數據庫時，記住這個特點很重要。設計 MySQL 索引時只需設計保證能讓索引最後的所有索引部分都使用 “=” 查詢。只有最後一個索引部分才支持 “range” 分句、IN 等。所有在范圍索引後面的分句都不會使用到索引。
Let me give one more example KEY (A,B,C) A=5 and B>6 and C=7 In this case index will be used to check A=5 and B>6 cause. C=7 will not be using the index (rows with all C values will be retrIEved from the index) and if this is not the index covered query you might rather shorten your key to KEY(A,B) to keep index smaller.
舉幾個例子吧， 索引 (A,B,CP) 和 A=5 and B>6 and C=7 分句的情況下，索引會檢索 A=5 和 B>6 的條件，C=7 則不會用到索引(所有包含 C 的記錄都會從索引中檢索得到)。這個時候如果任何查詢都無需使用完整的索引的話，就可以縮短索引為 KEY(A,B)，這樣能讓索引變小。
The good news are Loose index scan implementation is finally on a way. In fact it was even implemented in MySQL 5.0, but only for very narrow case of aggregate querIEs.
一個好消息是，減少索引掃描終究會以某種方式實現。MySQL 5.0 中其實已經實現了，不過只適用於少數情況的聚合查詢。
In general complete loose index scan implementation is one of my most wanted features for MySQL optimizer.
P.S If you post querIEs in your comments please also explain which indexes do you have on the table. SHOW CREATE TABLE is the best. Otherwise I can get you wrong.
常規意義上的完全減少索引掃描是我最想要實現的MySQL優化器特性。順便提一下，如果你在我的帖子評論中貼上了查詢語句，請順便說明你的索引情況，最好是貼上 SHOW CREATE TABLE 的結果。
