數據庫查詢性能優化之利器—索引（一）

最近在做基于Android的公交查詢系統的過程中，遇到一個很棘手的問題：換乘算法效率低。在直達查詢和一次換乘查詢的時候，問題體現的還不是很明顯，能夠在1s之內查詢出乘車方案，而當進行二次查詢的時候，基本要等一兩分鐘才能查詢出換乘方案，這對于公交查詢系統是絕對無法容忍的。于是找了大量的關于公交換乘算法方面的論文和資料進行研究，發現大多治標不治本，沒有從根本上解決公交換乘算法效率低下的問題。公交換乘算法主要有以下三種思路：

　　1)基于數據庫的查詢；

　　2)采用Dijkstra或者Floyd算法或者改進的Dijkstra算法；

　　3)基于矩陣的運算；

　　由于在做這個系統之前就想過這個問題，是采用Dijkstra算法、矩陣運算還是基于數據庫的查詢。仔細分析之后還是選擇了基于數據庫的查詢，因為對于大中型城市的公交網絡，Dijkstra算法和矩陣運算根本不適用，尤其還是基于Android系統的公交查詢系統(離線查詢系統)，舉個例子，像成都市的公交網絡系統有將近500條公交線路，5000個公交站點，如果采用矩陣運算或者Dijkstra算法的話，就只是直達矩陣就得有5000*5000=25000000個數據，若數據采用int類型保存，則該矩陣得占用25000000*4/(1024*1024*8)=12M的內存空間，這個數據對于移動設備來說想而知，是不可取的辦法。因此最后采用了基于數據庫查詢的方案。

　　在我的數據庫中有兩張表：cnbusw(線路表),cnbus(站點線路表)

???? cnbusw的字段：

???? id：線路編號，busw：線路名稱，shijian：起始站和起始時間描述；

???? cnbus的字段：

　　zhan:站點名，xid：對應的線路編號，pm：在該線路中的位置，kind：線路類型(去程or返程or環形路線)

　　后來發現在進行一次換乘查詢的時候需要直達站點信息，因此添加了一個視圖direct

　　direct的字段：

　　start：起始站，end：終點站，route：對應的線路編號，stopcount：兩站之間的站點數

　　在數據庫中進行測試了一下：

　　1)直達方案的話，直接在direct中進行查詢：

　　　比如下面一條sql查詢語句:

select?*?from?direct?where?start='磨子橋'?and?end='春熙路南口'

　　?? 查詢耗時：119.05ms

　　2)一次換乘查詢方案，通過direct的自連接進行查詢：

　　?? 比如下面一條sql查詢語句：

select?s1.start?as?start,s1.route?as?route1,s1.end?as?zhuan,s2.route?as?route2,
s2.end?as?end,s1.stopcount?as?count1,s2.stopcount?as?count2,(s1.stopcount+s2.stopcount)?
as?stopcount?from?direct?s1,direct?s2?where?s1.start='崔家店'?and?s2.end='磨子橋'?and?s1.end=s2.start?and?s1.route!=s2.route?order?by?(s1.stopcount+s2.stopcount)

　　?? 查詢耗時：415.32ms

　　上述查詢時間都在能夠接受的范圍之內，然后我很自然地按照上面的思路寫出了三次換乘的sql查詢語句，結果在查詢時發現等了一分鐘還沒等出結果，并且sqlite可視化管理工具界面卡死了，這個很明顯地告訴我二次換乘直接使用這樣的sql語句是絕對不可行的，于是我想了一些辦法，比如：兩次換乘相當于是A->B->C->D，那么先查詢經過站點D的線路中站點序號比D小的站點集合U，然后就相當于查詢A到U集合中所有站點的一次換乘查詢，這樣就方便了，但是用sql語句查詢了一下，一般U集合的大小都在400左右，然后要進行400次一次換乘查詢，耗時400ms*400=160000ms=160s，怎么也得2分多鐘，顯然不可取。在陷入了這樣的僵局之后，想了很久沒想到辦法，因為數據庫里面的數據量很大，簡單地對sql語句進行改進無法解決根本性問題。只有從數據庫本身著手，于是想到了索引，以前上數據庫課程的時候，老師提到過索引對于大量數據查詢的時候效率提升的很明顯，于是就嘗試了一下，發現查詢耗時一下減少了很多。在建立索引的過程中，原本想在視圖上建立索引，發現似乎sqlite不支持在視圖上創建索引，于是刪除了direct視圖，建立了direct直達表，在建立索引的時候，考慮是建立多列索引還是單列索引，分析一次換乘查詢發現要將start，end，route這三列同時作為查詢條件，并且要對stopcount進行排序，因此選擇創建多列索引：

create?index?directindex?on?direct(start,end,route,stopcount)

　　在創建索引之后，重新將上面的一次換乘查詢語句執行了一次，耗時：5.59ms，查詢速度提升了將近80倍，然后又將直達查詢語句執行了一次，耗時0.49ms，也明顯提升了不少。然后按照一次換乘的思路寫出了二次換乘的sql語句進行執行，

select?s1.start?as?start,s1.xid?as?route1,s1.end?as?zhuan1,s2.xid?as?route2?,
s2.end?as?zhuan2,s3.xid?as?route3,s3.end?as?end,s1.stopcount,s2.stopcount,s3.stopcount,
(s1.stopcount+s2.stopcount+s3.stopcount)?from?direct?s1,direct?s2,direct?s3?where?s1.start='川大路黃河路口'?and?s3.end='春熙路南口'?and?s1.end=s2.start?and?s2.end=s3.start?
and?s1.xid!=s2.xid?and?s2.xid!=s3.xid?order?by?s1.stopcount+s2.stopcount+s3.stopcount

　　耗時411.15ms，很好地解決查詢效率低下的問題，從這里可以看出，在數據量很大的情況，建立索引和沒有索引的區別簡直是天壤之別，適當地建立索引能夠使查詢速度提升很大，關于索引的相關問題準備在后面進行進一步學習和研究。

?