Android教程網
  1. 首頁
  2. Android 技術
  3. Android 手機
  4. Android 系統教程
  5. Android 游戲
 Android教程網 >> Android技術 >> Android開發 >> 關於android開發 >> 高並發低基數多字段任意組合查詢的優化

高並發低基數多字段任意組合查詢的優化

編輯:關於android開發

高並發低基數多字段任意組合查詢的優化


1.問題

首先解釋一下這個標題裡出現的"低基數多字段任意組合查詢"指什麼東西。這裡是指滿足下面幾個條件的查詢:
1. 檢索條件中涉及多個字段條件的組合
2. 這些字段的組合是不確定的
3. 每個單獨字段的選擇性都不好

這種類型的查詢的使用場景很多,比如電商的商品展示頁面。用戶會輸入各種不同查詢條件組合:品類,供應商,品牌,促銷,價格等等...,最後往往還要對結果進行排序和分頁。

這類問題令人頭疼的地方在於:
1. 記錄數量眾多,如果進行全表掃描性能低下無法滿足高並發訪問的要求。
2. 查詢條件涉及的任何單個字段的選擇性都很低,不能通過單字段索引解決查詢效率問題。
3. 如果建立普通的Btree多字段索引,由於用戶的輸入條件組合太多,可能要建成百上千個索引,這不現實也很難維護。

2.方案

對這類問題我想到的解決方案有2種

2.1bitmap索引

bitmap的特點是存儲key以及所有取值等於這個key的行集的bitmap,對於涉及多個key的組合查詢,只需把這些key對應的bitmap做與或運算即可。由於bitmap的size很小,bit與或運算的效率也很高,所以bitmap非常適合做這類查詢。
bitmap索引也有缺點,更新一條記錄就會鎖住整個表,不適合並發寫比較多的場景。另外一個問題是,常見的關系數據庫中支持bitmap索引的似乎只有Oracle一家,而我們很多時候我們想用開源數據庫。

2.2 倒排索引

倒排索引和bitmap有相似之處,存儲的是key和取值等於這個key的行集,行集可能是list也可能是tree或其它存儲形式。對於多個key的組合查詢,把這些key的結果做集合運算即可。
倒排索引一般用於全文檢索,但很多系統也用它支持結構化數據的搜索,比如Elasticsearch。Elasticsearch支持JSON文檔的快速搜索,支持復合查詢,排序,聚合,分布式部署等很多不錯的特性。但是考慮下面幾個因素,我們更希望在關系數據庫裡找方案。
-不需要使用搜索引擎為模糊匹配提供的高級特性,實際上我們需要是精確匹配或者簡單的模糊匹配。
-數據量還沒有大到需要建一個分布式搜索集群。
-原始數據本來就在關系數據庫裡,不想煩心數據同步的問題。
-已經基於關系數據庫的接口開發了應用,不想推倒重來。
-已經掌握了關系數據庫的運維管理,對於全新的系統不知道還要踩多少坑。
-考慮到Java和C效能差異,關系數據庫內建方案的性能未必輸與專業的搜索引擎。

3.PostgreSQL的解法

如果把解決方案的范圍限定在開源關系數據庫,答案可能只有一個,就是PostgreSQL的gin索引。
PostgreSQL的gin索引就是倒排索引,它不僅被用於全文檢索還可以用在常規的數據類型上,比如int,varchar。
對於多維查詢我們可以這樣建索引:
1. 對所有等值條件涉及的低基數字段,建立唯一一個多字段gin索引
2. 對選擇性比較好的等值查詢或范圍查詢涉及的字段,另外建btree索引

可能有同學會有疑問,同樣是多字段索引,為什麼gin的多字段索引只要建一個就可以了,而btree的多字段索引卻要考慮各種查詢組合建若干個。這是由於gin多字段索引中的每個字段是等價的,不存在前導字段的說法,所以只要建一個唯一的gin多字段索引就可以覆蓋所有的查詢組合;而btree多字段索引則不同,如果查詢條件中不包含suoyi前導字段,是無法利用索引的。

多字段gin索引的內部存儲的每個鍵是(column number,key datum)這樣的形式,所以可以區分不同的字段而不致混淆。存儲的值是匹配key的所有記錄的ctid集合。這個集合在記錄數比較多的情況下采用btree的形式存儲,並且經過了壓縮,所以gin索引占用的存儲空間很小,大約只有等價的btree索引的二十分之一,這也從另一方面提升了性能。

對於多維查詢涉及的多個字段,包含在多字段gin索引中的字段,由gin索引做ctid的集合歸並(取並集或交集),然後得到的ctid集合和其它索引得到的ctid集合再做BitmapAnd或BitmapOr歸並。gin索引內部的ctid集合歸並效率遠高於索引間的ctid集合歸並,而且gin索引對低基數字段的優化更好,所以充分利用gin索引的特性比為每個字段單獨建一個btree索引再通過BitmapAnd或BitmapOr歸並結果集效率高的多。


4.一個真實的案例

4.1 原始查詢

下面這個SQL是某系統中一個真實SQL的簡化版。

  1. SELECT CASE WHEN gpppur.GB_BEGINDATE <= '2016-02-29 14:36:00' AND gpppur.GB_ENDDATE > '2016-02-29 14:36:00' THEN 1
  2. WHEN gpppur.PREVIEW_BEGINDT <= '2016-02-29 14:36:00' AND gpppur.PREVIEW_ENDDT > '2016-02-29 14:36:00' THEN 2
  3. ELSE 3 END AS flag,
  4. gpppur.*
  5. FROM T_MPS_INFO gpppur
  6. WHERE gpppur.ATTRACT_TP = 0
  7. AND gpppur.COLUMN_ID = 1
  8. AND gpppur.FIELD2 = 1
  9. AND gpppur.STATUS = 1
  10. ORDER BY flag ASC,gpppur.PC_SORT_NUM ASC,gpppur.GB_BEGINDATE DESC
  11. LIMIT 0,45
用的是MySQL數據庫,總數據量是60w,其中建有FIELD2+STATUS的多字段索引。
查詢條件涉及的4個字段的值分布情況如下:

  1. postgres=# select ATTRACT_TP,count(*) from T_MPS_INFO group by ATTRACT_TP;
  2. attract_tp | count
  3. ------------+--------
  4. | 16196
  5. 6 | 251
  6. 2 | 50
  7. 1 | 3692
  8. 3 | 143
  9. 10 | 314
  10. 4 | 214
  11. 5 | 194333
  12. 9 | 326485
  13. 7 | 1029
  14. 0 | 6458
  15. (11 rows)

  16. postgres=# select COLUMN_ID,count(*) from T_MPS_INFO group by COLUMN_ID;
  17. column_id | count
  18. ------------+--------
  19. | 2557
  20. 285 | 20
  21. 120 | 194
  22. 351 | 2
  23. 337 | 79
  24. 227 | 26
  25. 311 | 9
  26. 347 | 2
  27. 228 | 21
  28. 318 | 1
  29. 314 | 9
  30. 54 | 10
  31. 133 | 27
  32. 2147483647 | 1
  33. 336 | 1056
  34. 364 | 1
  35. 131 | 10
  36. 243 | 5
  37. 115 | 393
  38. 61 | 73
  39. 226 | 40
  40. 196 | 16
  41. 350 | 5
  42. 373 | 72
  43. 377 | 2
  44. 260 | 4
  45. 184 | 181
  46. 363 | 1
  47. 341 | 392
  48. 64 | 1
  49. 344 | 199271
  50. 235 | 17
  51. 294 | 755
  52. 352 | 3
  53. 368 | 1
  54. 225 | 1
  55. 199 | 8
  56. 374 | 2
  57. 248 | 8
  58. 84 | 1
  59. 362 | 1
  60. 361 | 331979
  61. 319 | 7
  62. 244 | 65
  63. 125 | 2
  64. 130 | 1
  65. 272 | 65
  66. 66 | 2
  67. 240 | 2
  68. 775 | 1
  69. 253 | 49
  70. 60 | 45
  71. 121 | 5
  72. 257 | 3
  73. 365 | 1
  74. 0 | 1
  75. 217 | 5
  76. 270 | 1
  77. 122 | 39
  78. 56 | 49
  79. 355 | 5
  80. 161 | 1
  81. 329 | 1
  82. 222 | 9
  83. 261 | 275
  84. 2 | 3816
  85. 57 | 19
  86. 307 | 4
  87. 310 | 8
  88. 97 | 37
  89. 202 | 20
  90. 203 | 3
  91. 85 | 1
  92. 375 | 641
  93. 58 | 98
  94. 1 | 6479
  95. 59 | 114
  96. 185 | 7
  97. 338 | 10
  98. 379 | 17
  99. (80 rows)

  100. postgres=# select FIELD2,count(*) from T_MPS_INFO group by FIELD2;
  101. field2 | count
  102. --------+--------
  103. | 2297
  104. 6 | 469
  105. 2 | 320
  106. 1 | 11452
  107. 3 | 286
  108. 10 | 394
  109. 4 | 291
  110. 5 | 200497
  111. 9 | 331979
  112. 0 | 2
  113. 7 | 1178
  114. (11 rows)

  115. postgres=# select STATUS,count(*) from T_MPS_INFO group by STATUS;
  116. status | count
  117. --------+--------
  118. | 2297
  119. 0 | 15002
  120. 3 | 5
  121. 4 | 1
  122. 1 | 531829
  123. 2 | 31
  124. (6 rows)

由於這幾個字段的值分布極其不均的,我們構造下面這個lua腳本產生不同的select語句來模擬負載。
qx.lua:

  1. pathtest = string.match(test, "(.*/)") or ""

  2. dofile(pathtest .. "common.lua")

  3. function thread_init(thread_id)
  4. set_vars()
  5. end

  6. function event(thread_id)
  7. local ATTRACT_TP,COLUMN_ID,FIELD2,STATUS
  8. ATTRACT_TP = sb_rand_uniform(0, 10)
  9. COLUMN_ID = sb_rand_uniform(1, 100)
  10. FIELD2 = sb_rand_uniform(0, 10)
  11. STATUS = sb_rand_uniform(0, 4)

  12. rs = db_query("SELECT CASE WHEN gpppur.GB_BEGINDATE <= '2016-02-29 14:36:00' AND gpppur.GB_ENDDATE > '2016-02-29 14:36:00' THEN 1
  13. WHEN gpppur.PREVIEW_BEGINDT <= '2016-02-29 14:36:00' AND gpppur.PREVIEW_ENDDT > '2016-02-29 14:36:00' THEN 2
  14. ELSE 3 END AS flag,
  15. gpppur.*
  16. FROM T_MPS_INFO gpppur
  17. WHERE gpppur.ATTRACT_TP = "..ATTRACT_TP.."
  18. AND gpppur.COLUMN_ID = "..COLUMN_ID.."
  19. AND gpppur.FIELD2 = "..FIELD2.."
  20. AND gpppur.STATUS = "..STATUS.."
  21. ORDER BY flag ASC,gpppur.PC_SORT_NUM ASC,gpppur.GB_BEGINDATE DESC
  22. LIMIT 45")
  23. end

然後用sysbench進行壓測,結果在32並發時測得的qps是64。

  1. [root@rh6375Gt20150507 ~]# sysbench --db-driver=mysql --test=/opt/sysbench-0.5/sysbench/tests/db/qx.lua --mysql-db=test --mysql-user=mysql --mysql-password=mysql --mysql-host=srdsdevapp69 --num-threads=32 --max-time=5 run
  2. sysbench 0.5: multi-threaded system evaluation benchmark
  3. Running the test with following options:
  4. Number of threads: 32
  5. Random number generator seed is 0 and will be ignored
  6. Threads started!
  7. OLTP test statistics:
  8. queries performed:
  9. read: 825
  10. write: 0
  11. other: 0
  12. total: 825
  13. transactions: 0 (0.00 per sec.)
  14. read/write requests: 825 (64.20 per sec.)
  15. other operations: 0 (0.00 per sec.)
  16. ignored errors: 0 (0.00 per sec.)
  17. reconnects: 0 (0.00 per sec.)
  18. General statistics:
  19. total time: 12.8496s
  20. total number of events: 825
  21. total time taken by event execution: 399.6003s
  22. response time:
  23. min: 1.01ms
  24. avg: 484.36ms
  25. max: 12602.74ms
  26. approx. 95 percentile: 222.79ms
  27. Threads fairness:
  28. events (avg/stddev): 25.7812/24.12
  29. execution time (avg/stddev): 12.4875/0.23

4.2 優化後的查詢

對於上面那個特定的SQL雖然我們可以通過建一個包含所有等值查詢條件中4個字段(ATTRACT_TP,COLUMN_ID,FIELD2,STATUS)的組合索引進行優化,但是需要說明的是,這條SQL只是各種查詢組合產生的1000多種不同SQL中的一個,每個SQL涉及的查詢字段的組合是不一樣的,我們不可能為每種組合都單獨建一個多字段索引。
所以我們想到了PostgreSQL的gin索引。為了使用PostgreSQL的gin索引,先把MySQL的表定義,索引和數據原封不動的遷移到PostgreSQL。
在添加gin索引前,先做了一個測試。另人驚訝的是,還沒有開始進行優化,PostgreSQL測出的性能已經是MySQL的5倍(335/64=5)了。

  1. [root@rh6375Gt20150507 ~]# sysbench --db-driver=pgsql --test=/opt/sysbench-0.5/sysbench/tests/db/qx.lua --pgsql-db=postgres --pgsql-user=postgres --pgsql-password=postgres --pgsql-host=srdsdevapp69 --num-threads=32 --max-time=5 run
  2. sysbench 0.5: multi-threaded system evaluation benchmark

  3. Running the test with following options:
  4. Number of threads: 32
  5. Random number generator seed is 0 and will be ignored


  6. Threads

  7. OLTP test statistics:
  8. queries performed:
  9. read: 1948
  10. write: 0
  11. other: 0
  12. total: 1948
  13. transactions: 0 (0.00 per sec.)
  14. read/write requests: 1948 (335.52 per sec.)
  15. other operations: 0 (0.00 per sec.)
  16. ignored errors: 0 (0.00 per sec.)
  17. reconnects: 0 (0.00 per sec.)

  18. General statistics:
  19. total time: 5.8059s
  20. total number of events: 1948
  21. total time taken by event execution: 172.0538s
  22. response time:
  23. min: 0.90ms
  24. avg: 88.32ms
  25. max: 2885.69ms
  26. approx. 95 percentile: 80.01ms

  27. Threads fairness:
  28. events (avg/stddev): 60.8750/27.85
  29. execution time (avg/stddev): 5.3767/0.29

下一步,添加gin索引。

  1. postgres=# create extension btree_gin;
  2. CREATE EXTENSION
  3. postgres=# create index idx3 on t_mps_info using gin(attract_tp, column_id, field2, status);
  4. CREATE INDEX

再進行壓測,測出的qps是5412,是MySQL的85倍(5412/64=85)。

  1. [root@rh6375Gt20150507 ~]# sysbench --db-driver=pgsql --test=/opt/sysbench-0.5/sysbench/tests/db/qx.lua --pgsql-db=postgres --pgsql-user=postgres --pgsql-password=postgres --pgsql-host=srdsdevapp69 --num-threads=32 --max-time=5 run
  2. sysbench 0.5: multi-threaded system evaluation benchmark

  3. Running the test with following options:
  4. Number of threads: 32
  5. Random number generator seed is 0 and will be ignored


  6. Threads

  7. OLTP test statistics:
  8. queries performed:
  9. read: 10000
  10. write: 0
  11. other: 0
  12. total: 10000
  13. transactions: 0 (0.00 per sec.)
  14. read/write requests: 10000 (5412.80 per sec.)
  15. other operations: 0 (0.00 per sec.)
  16. ignored errors: 0 (0.00 per sec.)
  17. reconnects: 0 (0.00 per sec.)

  18. General statistics:
  19. total time: 1.8475s
  20. total number of events: 10000
  21. total time taken by event execution: 58.2706s
  22. response time:
  23. min: 0.95ms
  24. avg: 5.83ms
  25. max: 68.36ms
  26. approx. 95 percentile: 9.42ms

  27. Threads fairness:
  28. events (avg/stddev): 312.5000/47.80
  29. execution time (avg/stddev): 1.8210/0.02

4.3 補充

作為對比,我們又在MySQL上添加了包含attract_tp, column_id, field2和status這4個字段的多字段索引,測出的qps是4000多,仍然不如PostgreSQL。可見業界廣為流傳的MySQL的簡單查詢性能優於PostgreSQL的說法不可信!(對於復雜查詢PostgreSQL的性能大大優於MySQL應該是大家的共識。我例子中的SQL不能算是復雜查詢吧?)


5. 總結

gin索引(還包括類似的gist,spgist索引)是PostgreSQL的一大特色,基於它可以挖掘出很多好玩的用法。對於本文提到的場景,有興趣的同學可以把它和Oracle的bitmap索引以及基於搜索引擎(Elasticsearch,Solr等)的方案做個對比。另外,本人所知有限,如果有其它更好的方案,希望能讓我知道。



  1. 上一頁:
  2. 下一頁:
熱門文章
閱讀排行版
Copyright © Android教程網 All Rights Reserved