鬱白2015-12-06 05:45:11

Oceanbase已做到，基本就是題主的思路，能下壓到各節點的做的儘量下壓，最後匯聚到一點規約，這個設計簡單，問題就是隻能有一個點做規約。曾經還做過一版多輪MapReduce的方案，不過後來好像廢棄了。

更詳細的，坐等SQL組

@曉楚

@茂七

@楊志豐

同學來回答

韓飛2016-03-25 11:11:55

額，我說一下基於map reduce的分散式sql演算法吧……

1。 給入一個sql語句，經過sql planner做出plan，這個plan就是一個DAG圖，每條邊就是一個shuffle-sort的過程，一般aggr、window、join或者直接的sort、distribute by、寫partition這些操作會引入shuffle-sort。

題主在1中的例子壓根不需要shuffle-sort的過程，直接split一下表就可以搞了。

例2，需要再Plan階段做一下謂詞下推，把on條件推上去（當然外連線是不能隨便推的）。

2。 join（等值連線）的分散式演算法主要分為hash-join和merge-sort join。 merge join要求左右表都是有序表，每次在兩邊同時讀相等的等值連線的key到記憶體中（其實在記憶體的只有一邊就可以了）做笛卡爾積。比如 a join b on a。key = b。key。a。key的值是1，2，3 b。key的值是1，3，4，那麼先a。key = 1和所有行和b。key = 1的所有行join，忽略掉a。key = 2，再讀key = 3。這樣就需要左父親的DAG節點（Task）按照a。key shuffle sort，右父親的DAG節點按照b。key shuffle-sort。

易見這種算法理論上可以的無限的橫向拓展，只要保證每個instance上的key都是有序的，且同一個key都在一個instance上。

hash-join要求一個父親是小表，可以全部裝載到記憶體中，並組織成map這樣的資料結構。比如a join b其中a是小表，那麼每個instance都要有一份a的全量資料，b不要求是有序的，隨機分配到每個instance上即可，但是a表要廣播到每個Instance上。對於等值連線，b的每一行都可以在記憶體中查詢具有相等key的全部a，做笛卡爾積即可。對於非等值連線，b的每一行和a的全量做笛卡爾積然後按照on條件過濾即可。

值得注意的是，a left join b ，a不能是小表，因為a不會知道自己有哪些行沒有被匹配到。

楊東東2016-09-30 16:11:43

沒做過，類似的文章倒是看過，有幾個相關問題要回答，

1。 一致性。很大的難題。可以選擇的是在snapshot上做放棄一致性，或者類似MegaStore有一箇中心點做全域性version管理，做分散式事務，或者類似spanner用絕對時間管理版本避免單點，或者根據業務情況定製一個簡化版本。

2。 效能。單機join訪問的是自己的磁碟和記憶體，且能做更好的cache策略，多臺機器就會面臨網路交換資料的問題，分散式join演算法花很大的精力解決這個問題，核心思想是不去遠端讀，比如第一次讀之後就儲存在本地，計算跟著儲存走之類；減少遠端讀次數和資料量，比如一次多讀一點，批次讀取甚至全表資料分發到全部相關節點，資料壓縮，遠端把結果計算好再向上構建（下推執行）；使用更好的硬體，比如更好的網絡卡，全記憶體全快閃記憶體等等；最佳化軟體，比如減少複製，繞過核心協議棧等等；也可以預計算，比如構建索引。

3。 擴充套件性，計算能力不足的時候能否透過簡單加節點解決？sql map的思路是因為mr的擴充套件能力強，那麼將sql變成mr執行之後就具備了mr的擴充套件能力，不過這是願望，能不能做到也得看系統怎麼設計的了

當然如何足夠健壯也是一個很大的話題。

知乎使用者2018-08-21 22:33:10

簡單回答下這個問題：

分散式資料來源的複雜查詢，實現只是最簡單的一層，做好細粒度的資源管控並恰好剛剛可以滿足使用者的rt需求以及實時性需求，才是這個需求的更高層次。

分散式的資料下的sql執行，和單機sql執行並沒有本質的區別

分散式執行引擎才能帶來分散式資料庫以上的執行效率提升

Map reduce，spark，flink能夠提供的抽象API ，同時做到介面抽閒和分散式算力資源分配，是分散式執行引擎的實現選擇這些工具的原因

問題裡的sql + 下推 + 執行 都有成熟的工具來解決，比如calcite，可以做到解析出下推最佳化後的optimized plan，並且還能根據不同的分散式執行引擎來生成相應的物理plan

sql 如何變成執行器：

sql -> Ast -> logicPlan -> Optimized plan -> executable plan

在這裡executable plan可以是 datastream，operator ， beam pipeline，DataStream，對於一個像calcite這樣介面設計優雅的最佳化器來說只是差別在加入一層convert Rule來做相應轉化而已

具體的資料可以參考：

Apache Calcite • Dynamic data management framework

https：//

cloud。google。com/spanne

r/docs/query-execution-plans

： google spanner計劃生成

Flink SQL 解析流程

Sovnlo2021-06-01 08:58:04

Join：

PolarDB-X：分散式資料庫如何實現 Join？

子查詢：

PolarDB-X：子查詢漫談

計算下推：

PolarDB-X：PolarDB-X 中的計算下推