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分成多個分區,每個分區(有一個inner table子部分也有一個outer table的子部分)保存在disk上。再對每個分區用普通的hash join。每個分區稱為一個batch,通過join key計算出hash value,然后計算出對應的batchNo與BucketNo:計算公式如下:

bucketNo = hash value % nbuckets;
batchNo = (hash value / nbuckets) % nbatch;
//nbuckets為buckets的個數,nbacth為batch的個數。

大致上和mysql差不多,不過mysql并沒有分buckets。
判斷是否需要多個batch的邏輯如下:
若 inner table的size + buckets的開銷 < work_mem,使用單個batch。否則使用多個batch:

plan_rows:預估的inner table的行數
plan_width:預估的inner table的列數
NTUP_PER_BUCKET:單個buckets的tuple數據
Work_mem:為hashjoin分配的內存配額

hybrid hash join的優化在于:對于第一個batch不必寫入disk,從而避免第一個batch的磁盤IO
在這里插入圖片描述
具體過程如下:
1、首先對inner table進行分區/分batch,計算batchNo:
如果該tuple屬于batch0,則加入內存中的hashtable中;
否則寫入batchNo對應的disk file中。
總結就是batch0不用寫如磁盤(當然也有例外,在下文會提到)
2、對outer table進行分區/分batch,計算batchNo:
如果tuple屬于batch0,那么用key去內存hashtable尋找(equal_range or find),匹配則輸出,否則繼續讀下一行probe tuple。
否則寫入batchNo對應的disk file中。
3、outer table掃描完畢,batch0也處理完了。
開始按照No處理下一個batchx:
加載batchx的inner table到內存,build hash table
掃描batchx的outer table,進行probe。
batchx處理完,處理batchx+1,直到所有batch都處理完畢。

現在還有一個問題:如果分割后的batch0仍然太大,不能一次性放到內存中,怎么辦?
postgresql的做法是將batch個數翻倍,從原本的n變為2n。重新掃描batch0的tuples,根據nbatch = 2n,重新計算所屬的batch。如果重新計算后的batcth仍然屬于batch0,就保留在內存中,否則從內存中拿出,寫入到tuple對應的新batch中。
(此時batch0的后半部分數據被分配到batchn上)
在這里插入圖片描述
注意,此時不會移動磁盤中batch file中已有的tuple,當處理到該batch的時候會處理。
還記得上文提到的hybrid hash join的取模操作嗎?這個操作保證了,batch數目翻倍后,tuple所屬的batch只會向后擴展。
剛剛說的只是batch0,當我們繼續處理batch_i的時候,可能還是會遇到這個問題。那么就繼續將nbatch數目翻倍吧!
當然tuple所屬的batchNo也會變化。

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

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

相關文章

末日中的黎明

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

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

Prerequisite: 先決條件&#xff1a; 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算法是最為經典的基于劃分的聚類方法&#xff0c;是十大經典數據挖掘算法之一。K-means算法的基本思想是&#xff1a;以空間中k個點為中心進行聚類&#xff0c;對最靠近他們的對象歸類。通過迭代的方法&#xff0c;逐次更新各聚…

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

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

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

Data skew 很好理解&#xff0c;即數據傾斜。現實中的數據很多都不是正態分布的&#xff0c;譬如城市人口&#xff0c;東部沿海一個市的人口與西部地區一個市地區的人口相比&#xff0c;東部城市人口會多好幾倍。 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. 在此示例中&#xff0c;我們創建了一個名為employee的對象&#xff0c;其對象為id &#x…

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

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

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

《GPU高性能編程-CUDA實戰&#xff08;CUDA By Example&#xff09;》中例子中使用的一些頭文件是CUDA中和C中本身沒有的&#xff0c;需要先下載這本書的源碼&#xff0c;可以在&#xff1a;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方法&#xff0c;導致自己對瀏覽器原生的XMLHttpRequest對象不是很熟悉&#xff0c;于是決定自己寫下&#xff0c;以下是個人寫的deom&#xff0c;發表一下&#xff0c;聊表紀念。 Ajax 和 jsonp 的javascript 實現&#xff1a; /*! * 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…

學習語言貴在堅持

學習語言貴在堅持 轉自&#xff1a;http://zhidao.baidu.com/link?urlr2W_TfnRwipvCDLrhZkATQxdrfghXFpZhkLxqH1oUapLOr8jXW4tScbyOKRLEPVGCx0dUfIr-30n9XV75pWYfK給大家介紹幾本書和別處COPY來的學習C50個觀點 《Thinking In C》&#xff1a;《C編程思想》&#xff1b; 《The…

stl vector 函數_在C ++ STL中使用vector :: begin()和vector :: end()函數打印矢量的所有元素...

stl vector 函數打印向量的所有元素 (Printing all elements of a vector) To print all elements of a vector, we can use two functions 1) vector::begin() and vector::end() functions. 要打印矢量的所有元素&#xff0c;我們可以使用兩個函數&#xff1a;1) vector :: b…

JqueryUI入門

Jquery UI 是一套開源免費的、基于Jquery的插件&#xff0c;在這里記錄下Jquery UI 的初步使用。 第一、下載安裝 下載Jquery,官網&#xff1a;http://jquery.com;  下載Jquery UI&#xff0c;官網&#xff1a;http://jqueryui.com/ Jquery的部署就不說了&#xff0c;說下Jqu…

gp的分布、分區策略(概述)

對于大規模并行處理數據庫來說&#xff0c;一般由單master與多segment組成。 那么數據表的單行會被分配到一個或多個segment上&#xff0c;此時需要想一想分布策略 分布 在gp6中&#xff0c;共有三個策略&#xff1a; 哈希分布 隨機分布 復制分布 哈希分布 就是對分布鍵進行…

[ Java4Android ] Java基本概念

視頻來自&#xff1a;http://www.marschen.com/ 1.什么是環境變量 2.JDK里面有些什么&#xff1f; 3.什么是JRE&#xff1f; 什么是環境變量&#xff1f; 1.環境變量通常是指在操作系統當中&#xff0c;用來指定操作系統運行時需要的一些參數; 2.環境變量通常為一系列的鍵值對&…

_thread_in_vm_Java Thread類的靜態void sleep(long time_in_ms,int time_in_ns)方法,帶示例

_thread_in_vm線程類靜態無效睡眠(long time_in_ms&#xff0c;int time_in_ns) (Thread Class static void sleep(long time_in_ms, int time_in_ns)) This method is available in package java.lang.Thread.sleep(long time_in_ms, int time_in_ns). 軟件包java.lang.Thread…

大規模web服務開發技術(轉)

前段時間趁空把《大規模web服務開發技術》這本書看完了&#xff0c;今天用一下午時間重新翻了一遍&#xff0c;把其中的要點記了下來&#xff0c;權當復習和備忘。由于自己對數據壓縮、全文檢索等還算比較熟&#xff0c;所以筆記內容主要涉及前5章內容&#xff0c;后面的零星記…

IO多路復用的三種機制Select,Poll,Epoll

IO多路復用的本質是通過系統內核緩沖IO數據讓單個進程可以監視多個文件描述符&#xff0c;一旦某個進程描述符就緒(讀/寫就緒)&#xff0c;就能夠通知程序進行相應的讀寫操作。 select poll epoll都是Linux提供的IO復用方式&#xff0c;它們本質上都是同步IO&#xff0c;因為它…