性能優化技巧 - 查找

日常生活中，我們會遇到各種各樣的數據，小到公司通訊錄，大到互聯網用戶行為分析。在進行數據分析處理的過程中，查詢是必不可少的環節，如何更加高效地進行數據查詢。

SPL為用戶提供了強大的索引機制以及針對不同場景中各對象的查詢函數，善加運用，可以顯著提高查詢性能。

1?鍵值查找

1.1?序表

我們先建立一個份“通話記錄”的模擬數據，通過這份數據，來比較一下不同查詢函數對序表查詢性能的影響。建立模擬數據的代碼如下：

代碼1.1.1

其中部分數據如下：

圖1.1.1

對序表進行查詢，通常我們會想到使用A.select()函數。我們來看一下使用該函數的效果：

代碼1.1.2

查詢耗時為80毫秒。

對序表的鍵值進行查詢時，可以利用A.find()函數進行查詢。示例代碼如下：

代碼1.1.3

查詢耗時為1毫秒。

這是因為在集算器的序表中，可以指定某個或某些字段作為主鍵，基于主鍵的查找可以使用專門的函數。比如代碼1.1.3中A5的find函數，不僅能簡化書寫，更能有效地提高計算性能。

當鍵值較多時，我們使用函數A.find@k ()進行批量鍵值查找。示例代碼如下：

代碼1.1.4

要注意的是，在使用A.find()函數時，需事先建立主鍵，否則會報“缺少主鍵”的錯誤。

利用主鍵值查找的函數，可以有效地提升計算性能，是由于在序表中為主鍵建立索引表。在代碼1.1.4中，未建立索引時，平均查詢時間在1400毫秒左右；建立索引后，查詢平均耗時不到1毫秒。

序表中的數據量越大，需要查找的次數越多，對效率的提升就越明顯。

當查詢條件對應多個鍵時，示例代碼如下：

代碼1.1.5

switch/join函數同樣需要根據主鍵值在序表中查找記錄，使用時會對維表自動建立索引。若在多線程fork函數之前沒有對相應維表建立索引，就會在每個線程中都自動為該維表建立一個索引，執行過程中會消耗更多內存，這樣有可能會造成內存溢出，如圖1.1.1.2，要注意避免，較好的處理方式可以參考圖?1.1.3。

圖?1.1.2 fork中的每個線程都自動建立了索引導致內存溢出

圖?1.1.3 fork執行前，先對維表建立索引

?

1.2?集文件

對有序的集文件進行查找，可以使用f.iselect()函數實現二分查找，該函數也支持批量查找，下面是個基于集文件使用f.iselect()批量查找的例子：

代碼1.2.1

代碼1.2.1，建立集文件voiceBill@z.btx。顯然，Subscriber是有序的。

代碼1.2.2

代碼1.2.2，因為f.iselect()是個二分查找函數，所以需要注意代碼中的A2作為查詢序列，與集文件的編號一樣，都需要有序。還要注意，這里的選項@b不是二分法的意思，而是讀取通過f.export()函數導出的集文件。該集文件導出時，注意需要使用選項@z，否則在使用f.iselect ()對集文件進行查詢時會報錯。

假設數據總量為N，使用二分法進行查找的時間復雜度為logN（以 2 為底），當數據量越大，性能提升也就越明顯。

?

1.3?組表

組表也有類似序表的T.find()和T.find@k()函數，可以高效地實現鍵值查找。適合于在大維表中找出少量記錄的場景。我們來看這樣一個例子：

代碼1.3.1

代碼1.3.1，建立組表文件voiceBill.ctx，其中Subscriber是該組表的維。

代碼1.3.2

代碼1.3.2，對組表使用cs.select()函數進行查詢，耗時為：13855毫秒。

代碼1.3.3

代碼1.3.3，對組表使用T.find()函數進行查詢，耗時為：77毫秒。

對比可見：對于有維的組表，可以使用類似序表的T.find()函數，進行單個或者批量鍵值的查詢，其查詢效率遠高于從篩選后的游標中取數。

2 索引查找

組表上可以建立三種索引，每種索引針對的情況也不同，分別為：

1、? hash索引，適合單值查找，比如枚舉類型；

2、? 排序索引，適合區間查找，比如數字、日期、時間類型；

3、? 全文索引，用于模糊查詢，比如字符串類型。

下面我們來建立一個組表，使其數據類型覆蓋以上三種索引，如下：

代碼2.1

代碼2.1建立的組表，前十條記錄如下：

圖2.1

代碼2.2

代碼2.2，根據每列數據類型的特點，建立不同類型的索引。建立好的索引和組表文件如圖2.2：

圖2.2

集算器能自動識別條件找到合適的索引，等值和區間都可以，like(“A*”)式的也支持。我們來看下效果：

等值查找

代碼2.3

代碼2.4

代碼2.3是沒有省略索引名稱的寫法，代碼2.4是省略索引名稱的寫法。兩者時間消耗基本相同，都是100毫秒左右。

代碼2.5

代碼2.5使用普通游標查詢同樣的記錄，查詢耗時則需要40秒左右。

?

區間查找

代碼2.6

代碼2.6對Subscriber使用排序索引，進行區間查找，查詢耗時是70毫秒左右。

代碼2.7

代碼2.7使用普通游標查詢同樣條件的記錄，查詢耗時則需要40秒左右。

?

模糊查找

代碼2.8

代碼2.8對Company使用全文索引，進行模糊查詢，查詢耗時是1500毫秒左右。

代碼2.9

代碼2.9使用普通游標查詢同樣條件的記錄，查詢耗時則需要40秒左右。

?

當數據規模更大時，例如：

代碼2.10

代碼2.10，建造了10億條結構如圖2.3的組表文件employee.ctx。

圖2.3

代碼2.11

?

代碼2.11中，對大部分列建立了索引。組表與索引的各個文件如圖2.4。

圖2.4

多等值條件項&&時，可以分別為每個字段建立索引。集算器能夠快速在多個索引中用歸并算法計算交集。比如：

代碼2.12

代碼2.12，查詢條件均為等值查詢，A3查出記錄數為324條，耗時31883毫秒。

但區間條件時不能再用歸并計算交集，集算器將只對其中一個條件使用索引，另一個條件使用遍歷計算，效果就會差，比如：

代碼2.13

代碼2.13，查詢條件均為區間條件，A3查出記錄數為389條，耗時70283毫秒。

?

3 索引緩存

組表索引提供了兩級緩存機制，可以用index@2或者index@3預先把索引的索引讀入內存，如果需要重復多次使用索引查找，則可以有效提高性能。

選項@2、@3的意思分別是將索引的第二、三級緩存先加載進內存。經過索引緩存的預處理，第一遍查詢時間也能達到查詢數百次后才能達到的極限值。@2相比@3緩存的內容少，效果相對差一點，但內存占用也更少。使用時需要程序員根據具體場景來權衡@2還是@3。

代碼3.1

代碼3.1，基于代碼2.10建造的組表文件，不使用索引緩存，查詢耗時為31883毫秒。

代碼3.2

代碼3.2使用第三級索引緩存，查詢耗時為5225毫秒。

這里使用的是列存組表，列存采用了數據分塊并壓縮的算法，對于遍歷運算來講，訪問數據量會變小，也就會具有更好的性能。但對于基于索引隨機取數的場景，由于要有額外的解壓過程，而且每次取數都會針對整個分塊，運算復雜度會高很多。因此，從原理上分析，這時候的性能應當會比行存要差。將組表轉為行存后，查詢耗時僅為1592毫秒。

?

索引緩存在并行時可以復用，如下：

代碼3.3

代碼3.3，并行時，A5的每個線程中都可以使用A2、A3中建立的第三級索引緩存，最終查詢耗時為21376毫秒。

?

4 帶值索引

組表的行存和列存形式都支持索引，列存索引查找比行存性能差，返回結果集較少時差異不明顯，大量返回時會有明顯劣勢，在設計存儲方案時要權衡。

代碼4.1

代碼4.1建立組表文件id_600m.ctx，結構為(#id,data) ，包含6億條記錄，其中：

A1：包含 26 個英文字母和 10 個阿拉伯數字的字符串。

A2、A3：建立結構為 (id,data) 的組表文件，使用列式存儲方式。

A4：循環 6000 次，循環體B4、B5，每次生成 10 萬條對應結構的記錄，并追加到組表文件。

執行后，生成組表文件：id_600m.ctx

?

代碼4.2

代碼4.2為組表id列建立索引。

執行后，生成組表的索引文件：id_600m.ctx__id_idx。

?

列存組表生成時 create() 函數加上 @r 選項，即可變為生成行存組表，其余代碼無異，這里不再舉例，當返回數據量較大時：

?

代碼4.3

代碼4.3中，列存查詢耗時和行存查詢耗時，也就是A5和A9的值分別為205270和82800毫秒。

?

組表支持一種帶值索引，即把查找字段也寫入索引，這樣可以不再訪問原組表即返回結果。但存儲空間會占用較多。

基于代碼4.1的列存組表文件id_600m.ctx。

?

代碼4.4

代碼4.4為組表id列建立索引，在對組表建立索引時，當 index 函數有數據列名參數，如本例 A2 中的 data，就會在建索引時把數據列 data 復制進索引。當有多個數據列時，可以寫為：index(id_idx;id;data1,data2,…)。

因為在索引中做了冗余，索引文件也自然會較大，本文中測試的列存組表和索引冗余后的文件大小為：

?

當數據復制進索引后，實際上讀取時不再訪問原數據文件了。

從 6 億條數據總量中取 1 萬條批量隨機鍵值，完整的測試結果對比：

?

?

5 批量鍵值

組表索引能夠識別出contain式條件，支持批量等值查找。

代碼5.1

代碼5.1建立組表文件id_600m.ctx，結構為(#id,data) ，包含6億條記錄，其中：

A1：包含 26 個英文字母和 10 個阿拉伯數字的字符串。

A2、A3：建立結構為 (id,data) 的組表文件，@r 選項表示使用行式存儲方式。

A4：循環 6000 次，循環體B4、B5，每次生成 10 萬條對應結構的記錄，并追加到組表文件。

執行后，生成組表文件：id_600m.ctx。

?

代碼5.2

代碼5.2為組表id列建立索引。

執行后，生成組表的索引文件：id_600m.ctx__id_idx

代碼5.3

代碼5.3，在組表的 icursor()這個函數中，使用索引 id_idx，以條件 A2.contain(id) 來過濾組表。集算器會自動識別出 A2.contain(id) 這個條件可以使用索引，并會自動將 A2 的內容排序后從前向后查找。

進階使用

使用排序索引多線程查找時，按鍵值排序分組后扔給多個線程去查詢，避免兩個線程中有交叉內容。同時，還可以設計成多個組表，把鍵值能平均分配到多個組表上并行查找。

所謂多線程并行，就是把數據分成 N 份，用 N 個線程查詢。但如果只是隨意地將數據分成 N 份，很可能無法真正地提高性能。因為將要查詢的鍵值集是未知的，所以理論上也無法確保希望查找的數據能夠均勻分布在每一份組表文件中。比較好的處理方式是先觀察鍵值集的特征，從而盡可能地進行數據的均勻拆分。

如果鍵值數據有比較明顯的業務特征，我們可以考慮按照實際業務場景使用日期、部門之類的字段來處理文件拆分。如：將屬于部門 A 的 1000 條記錄均分在 10 個文件中，每個文件就有 100 條記錄。在利用多線程查詢屬于部門 A 的記錄時，每個線程就會從各自對應的文件中取數相應的這 100 條記錄了。

下面我們來看個實際的例子，已有數據文件multi_source.txt的結構如下：

其中 type 和 id 兩個字段作為聯合主鍵確定一條記錄，其中部分數據如下：

?

代碼5.4

代碼5.4詳解：

A1：type 的枚舉值組成的序列。在實際情況中，枚舉列表可能來自文件或者數據庫數據源。。

A2：給枚舉值序列中每個 type 一個 tid。為后續的數字化主鍵合并做準備。

A3~A6：從 multi_source.txt 文件中獲取數據，并按照 A2 中的對應關系，把 type 列的枚舉串變成數字，然后將 type 和 id 進行合并后，生成新的主鍵 nid。

A7：使用循環函數，創建名為“鍵值名 _ 鍵值取 N 的余數 _T.ctx”的組表文件，其結構同為 (#nid,data)。

A8：用循環函數將游標數據分別追加到 N 個原組表上。比如當 N=1 時，拼出的 eval 函數參數為：channel(A4).select(nid%4==0).attach(A7(1).append(~.cursor()))。意思是對游標 A4 創建管道，將管道中記錄按鍵值 nid 取 4 的余數，將余數值等于 0 的記錄過濾出來。attach 是對當前管道的附加運算，表示取和當前余數值對應的原組表，將當前管道中篩選過濾出的記錄，以游標記錄的方式追加到 A7(1)，即第 1 個組表。

A9：循環游標 A6，每次獲取 50 萬條記錄，直至 A6 游標中的數據取完。

執行后，產出 4（這時例子取 N=4）個獨立的組表文件：

?

代碼5.5

代碼5.5，創建索引過程詳解：

A1：列出滿足 nid*T.ctx 的文件名（這里 * 為通配符），這里 @p 選項代表需要返回帶有完整路徑信息的文件名。使用 fork 執行多線程時，需要注意環境中的并行限制數是否設置合理。這里用了 4 個線程，設計器中對應的設置如下：

B1：每個線程為各個組表建立對應的索引文件，最終結果如下：

?

代碼5.6

代碼5.6，查詢過程詳解：

A1：從 keys.txt 獲取查詢鍵值序列，因為只有一列結果，使用 @i 選項，將結果返回成序列：

A2：把 A1 的序列按 4 的余數進行等值分組：

A3、B3~B5：用 fork 函數，按等值分組后的鍵值對各個組表分別并行查詢。這里的 fork 后面分別寫了兩個參數，第一個是循環函數 N.(~-1)，第二個是 A2。在接下來的 B3、B4 中分別使用 A3(2) 和 A3(1) 來獲取 fork 后面這兩個對應順序的參數，B4：對組表文件進行根據 B3 中的鍵值集進行數據篩選，B5：返回游標。由于 A3 中是多個線程返回的游標序列，所以 A6 中需要使用 conjx 對多個游標進行縱向連接。

A6~A7：將多個線程返回的游標進行縱向連接后，導出游標記錄至文本文件，前幾行內容如下。