Postgresql多線程hashjoin(inner join)

pg hashjoin 節點大致步驟:
1、分塊與分桶。對一個表hash時,確定塊數和桶數量。(一塊被劃分為10個元組的桶)確定分塊號與分桶號是由hashvalue決定的。
2、執行:

  • 1、順序獲取S表中所有元組,對每一條元組Hash,獲取塊號和桶號,塊號為0,放入內存桶中。
    否則放入S表建立的臨時文件中。
    標記內存中塊號curbatch = 0
  • 2、從表R中獲取元組,進行Hash,獲取元組塊號和桶號。
    當塊號 = 當前內存塊號,直接掃描對應桶,尋找滿足條件的元組并進行連接。
    否則放入為表R建立的臨時文件中(每個塊都有一個)
    一直執行,直到R掃描完畢。
  • 3、從S表中,塊號為curbatch+1對應的臨時文件中讀取所有存儲的元組,將其hash到對應桶內,curbatch++。
  • 4、從R表塊中,塊號為curbatch對應臨時文件讀取所有存儲元組,并計算桶號,并掃描桶中S,尋找滿足連接條件的tuple。

build hash table

pg11,buildhashtable階段:
1、每個worker并行掃描部分inner_table。
2、在共享內存中并行build一個hash表
3、每個worker并行地掃描outer_table,并行執行join probe操作
需要注意的是,在join之前,需要通過barrier機制,先完成自己build操作的線程需要等待hashtable被完整build后才能進入下一步的probe狀態。

multipleBatch的probe與hash

1、并行掃描inner_table,屬于batch0的tuple在內存中構建一個shared hash table;不屬于這個batch的寫入對應batch的inner tuple文件中
2、并行掃描outer_table,寫入對應batch的outer_tuple文件。
3、并行地對batch0執行join
4、某些workers先完成batch0地join后,分別領取后續batch的join任務。

狀態機

對于正在處理某個batch的worker來說
1、若沒有build完成,且有其他worker加入進來,則一起并行build hash table,在join之前必須barrier同步
2、若build完成,無需barrier
3、在barrier相關的module中,每個worker加入執行attach時,barrier中維護計數,在需要等待的地方判斷計數是否歸零。
在這里插入圖片描述

參考

https://zhuanlan.zhihu.com/p/112003245

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/376994.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/376994.shtml
英文地址,請注明出處:http://en.pswp.cn/news/376994.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

iframe實現局部刷新和回調--開篇

今天做項目遇到一個問題。就是提交表單的時候,驗證用戶名是否存在和驗證碼是否正確。 當驗證碼或者用戶名存在的時候。在后臺彈窗提示。可頁面原本file里面符合要求的值刷新沒了。用戶體驗不好。因為用ifream刷新技術已不是什么新鮮技術。所以網上有大把的資料可參考…

Java文件類boolean setExecutable(boolean exec_file,boolean owner_access)方法,帶示例

文件類boolean setExecutable(boolean exec_file,boolean owner_access) (File Class boolean setExecutable(boolean exec_file , boolean owner_access)) This method is available in package java.io.File.setExecutable(boolean exec_file , boolean owner_acc…

OLTP 系統和 OLAP 系統的核心設計思想

關于 OLTP 系統和 OLAP 系統的核心設計思想 數據存儲系統的關于查詢的典型操作: -- 第一種需求: 根據 key(1) 找 value(name,age), 單點查詢 select name, age from student where id 1; stu…

虛擬機

vt-x 虛擬技術的硬盤支持。想像成“硬解碼”的東東。不是裝虛擬機必須的,但有它效果會好些。 vt-x檢測工具:securable.exe 下載地址:http://pan.baidu.com/s/1kTBOvzD Hardware Virtualization選項: no [CPU和BIOS都不支持VT] loc…

算法(轉)

歡迎自薦和推薦鏈接。 算法 優秀博客推薦:各種數據結構與算法知識入門經典(不斷更新)基本算法 貪心算法:貪心算法 作者:獨酌逸醉 貪心算法精講 作者:3522021224 遞歸和分治:遞歸與分治策略 …

sjf調度算法_如何通過靜態方法預測SJF調度中未來過程的突發時間?

sjf調度算法In SJF Scheduling, CPU is assigned to the process having the smallest burst time but it can not be implemented practically, because we dont know burst time of the arrived processes in advance. 在SJF Scheduling中 ,將CPU分配給具有最短突…

flask 知識點總結

request對象的常用屬性具體使用方法如下:request.headers, request.headers.get(If-None-Match)request.json, request.json[value] 或 request.json.get(detail_msg, "")request.args, request.args.get(limit, 10)來獲取query parametersrequest.form, request.for…

Postgresql中的hybrid hash join(無狀態機講解)

hybrid hash join hybrid hash join是基于grace hash join 的優化。 在postgresql中的grace hash join 是這樣做的:inner table太大不能一次性全部放到內存中,pg會把inner table 和outer table按照join的key分成多個分區,每個分區(有一個inn…

末日中的黎明

哈哈, 今天是2012-12-21,傳說中的世界末日,不過現在看來,一切都是空的。。。 在這個容易記憶的日子里,我的博客開通了。他將伴隨我以后的學習開發,期望我能充分利用博客,幫我養成常總結、常記筆…

使用numpy.tanh()打印矢量/矩陣元素的雙曲正切值 使用Python的線性代數

Prerequisite: 先決條件: Defining a Vector 定義向量 Defining a Matrix 定義矩陣 Numpy is the library of function that helps to construct or manipulate matrices and vectors. The function numpy.tanh(x) is a function used for generating a matrix / v…

Mahout kmeans聚類

Mahout K-means聚類 一、Kmeans 聚類原理 K-means算法是最為經典的基于劃分的聚類方法,是十大經典數據挖掘算法之一。K-means算法的基本思想是:以空間中k個點為中心進行聚類,對最靠近他們的對象歸類。通過迭代的方法,逐次更新各聚…

Web項目中獲取SpringBean——在非Spring組件中獲取SpringBean

最近在做項目的時候我發現一個問題:Spring的IOC容器不能在Web中被引用(或者說不能被任意地引用)。我們在配置文件中讓Spring自動裝配,但并沒有留住ApplicationContext的實例。我們如果希望在我們的項目中任何位置都能拿到同一個ApplicationContext來獲取…

postgresql對于HashJoin算法的Data skew優化與MCV處理

Data skew 很好理解,即數據傾斜。現實中的數據很多都不是正態分布的,譬如城市人口,東部沿海一個市的人口與西部地區一個市地區的人口相比,東部城市人口會多好幾倍。 postgresql的skew的優化核心思想是"避免磁盤IO"。 優…

JavaScript | 創建對象并通過JavaScript函數在表中顯示其內容

In this example, we created an object named employee with id, name, gender, city, and salary and assigned and displaying the values in the table using JavaScript function. 在此示例中,我們創建了一個名為employee的對象,其對象為id &#x…

基于socket的簡單文件傳輸系統

【實驗目的及要求】 在 Uinx/Linux/Windows 環境下通過 socket 方式實現一個基于 Client/Server 文件傳輸程序。 【實驗原理和步驟】 1. 確定傳輸模式:通過 socket 方式實現一個基于 Client/Server 或 P2P 模式的文件傳輸程序。 2. 如果選擇的是 Client/Server 模式的文件傳輸…

《GPU高性能編程-CUDA實戰》中例子頭文件使用

《GPU高性能編程-CUDA實戰(CUDA By Example)》中例子中使用的一些頭文件是CUDA中和C中本身沒有的,需要先下載這本書的源碼,可以在:https://developer.nvidia.com/content/cuda-example-introduction-general-purpose-g…

mcq 隊列_人工智能| AI解決問題| 才能問題解答(MCQ)| 套裝1

mcq 隊列1) Which of the following definitions correctly defines the State-space in an AI system? A state space can be defined as the collection of all the problem statesA state space is a state which exists in environment which is in outer spaceA state sp…

Postgresql的HashJoin狀態機流程圖整理

狀態機 可以放大觀看。 HashJoinState Hash Join運行期狀態結構體 typedef struct HashJoinState {JoinState js; /* 基類;its first field is NodeTag */ExprState *hashclauses;//hash連接條件List *hj_OuterHashKeys; /* 外表條件鏈表;list of …

Ajax和Jsonp實踐

之前一直使用jQuery的ajax方法,導致自己對瀏覽器原生的XMLHttpRequest對象不是很熟悉,于是決定自己寫下,以下是個人寫的deom,發表一下,聊表紀念。 Ajax 和 jsonp 的javascript 實現: /*! * ajax.js * …

得到前i-1個數中比A[i]小的最大值,使用set,然后二分查找

題目 有一個長度為 n 的序列 A&#xff0c;A[i] 表示序列中第 i 個數(1<i<n)。她定義序列中第 i 個數的 prev[i] 值 為前 i-1 個數中比 A[i] 小的最大的值&#xff0c;即滿足 1<j<i 且 A[j]<A[i] 中最大的 A[j]&#xff0c;若不存在這樣的數&#xff0c;則 pre…