[發(fā)明專利]基于連接簡(jiǎn)圖的數(shù)據(jù)庫連接基數(shù)估計(jì)方法和系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202210137615.3
• 申請(qǐng)日: 2022-02-15
• 公開（公告）號(hào): CN114625760A
• 公開（公告）日: 2022-06-14
• 發(fā)明（設(shè)計(jì)）人: 楊仝;王飛宇;屠要峰;楊洪章
• 申請(qǐng)（專利權(quán)）人: 北京大學(xué);中興通訊股份有限公司
• 主分類號(hào): G06F16/2453
• 分類號(hào): G06F16/2453;G06F16/25
• 代理公司: 北京君尚知識(shí)產(chǎn)權(quán)代理有限公司 11200
• 代理人: 邱曉鋒

本發(fā)明涉及一種基于連接簡(jiǎn)圖的數(shù)據(jù)庫連接基數(shù)估計(jì)方法和系統(tǒng)。該方法的步驟包括：利用元素過濾器，將數(shù)據(jù)庫表中的元素分為熱元素與冷元素；將熱元素存儲(chǔ)至熱元素表中，將冷元素存儲(chǔ)至冷元素Sketch中；分別計(jì)算兩個(gè)數(shù)據(jù)庫表的熱元素表的連接基數(shù)、冷元素Sketch的連接基數(shù)以及熱元素表和冷元素Sketch的連接基數(shù)，并相加，得到對(duì)該兩個(gè)數(shù)據(jù)庫表的連接基數(shù)的估計(jì)結(jié)果。本發(fā)明通過將熱元素和冷元素分離，可以提高對(duì)數(shù)據(jù)庫連接基數(shù)估計(jì)的精度，且算法的時(shí)間和空間開銷都有所下降；精確的連接基數(shù)估計(jì)，有利于數(shù)據(jù)庫管理系統(tǒng)給出最佳的連接順序，從而提升數(shù)據(jù)庫復(fù)雜查詢的性能。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)庫連接基數(shù)查詢領(lǐng)域，具體為一種利用Join Sketch(連接簡(jiǎn)圖)來快速估計(jì)關(guān)系型數(shù)據(jù)庫中兩張表連接結(jié)果基數(shù)的方法和系統(tǒng)。

背景技術(shù)

關(guān)系型數(shù)據(jù)庫是指采用了關(guān)系模型組織數(shù)據(jù)的數(shù)據(jù)庫，是目前應(yīng)用最廣泛的數(shù)據(jù)庫類型。常見的數(shù)據(jù)庫系統(tǒng)，包括PostgreSQL、MySQL、SQL Server、Oracle在內(nèi)，都是典型的關(guān)系型數(shù)據(jù)庫。在關(guān)系型數(shù)據(jù)庫中，表連接是一類重要的操作，該操作將兩張或多張數(shù)據(jù)表連接起來，形成一張新的數(shù)據(jù)表作為輸出。

數(shù)據(jù)庫的查詢優(yōu)化是關(guān)系型數(shù)據(jù)庫中的一個(gè)重要問題，對(duì)數(shù)據(jù)庫整體的性能有重要的影響。當(dāng)用戶給出一條查詢時(shí)，數(shù)據(jù)庫管理系統(tǒng)需要在多種等價(jià)的查詢方案中選擇查詢開銷最小的方案。為了尋找最佳查詢方案，數(shù)據(jù)庫系統(tǒng)需要對(duì)不同查詢方案產(chǎn)生的開銷進(jìn)行快速準(zhǔn)確的估計(jì)。在眾多影響因素中，連接基數(shù)的大小對(duì)查詢開銷的影響最大。其中連接基數(shù)是指對(duì)兩張數(shù)據(jù)表進(jìn)行連接操作后生成的新數(shù)據(jù)表所包含的記錄的數(shù)量。

目前主流的連接基數(shù)估計(jì)方案包括建立數(shù)據(jù)直方圖、采樣、機(jī)器學(xué)習(xí)模型和Sketch(簡(jiǎn)圖)技術(shù)四種。在這四種方案中，數(shù)據(jù)直方圖需要較多的存儲(chǔ)來獲取較好的精度，采樣方案在面對(duì)偏斜數(shù)據(jù)分布和稀疏數(shù)據(jù)時(shí)性能較差。傳統(tǒng)的基于Sketch的連接基數(shù)估計(jì)算法包括AGMS Sketch和Fast AGMS Sketch。AGMS Sketch能夠較為精確地對(duì)數(shù)據(jù)庫連接基數(shù)進(jìn)行估計(jì)，然而該算法的時(shí)間和空間復(fù)雜度較高；Fast AGMS Sketch是對(duì)AGMS Sketch的改進(jìn)，該算法顯著地提升了速度，但是在精度上又有所損失。目前的算法都無法很好地解決連接基數(shù)估計(jì)的任務(wù)，可能導(dǎo)致數(shù)據(jù)庫無法找到最優(yōu)的連接順序，從而拖累數(shù)據(jù)庫系統(tǒng)的性能。

發(fā)明內(nèi)容

為了克服現(xiàn)有的連接基數(shù)估計(jì)算法速度慢、精度低以及無法很好地應(yīng)對(duì)偏斜數(shù)據(jù)分布的問題，本發(fā)明提供一種基于Sketch的連接基數(shù)估計(jì)方法，該方法基于冷元素與熱元素分離的思想，可以有效地提高偏斜數(shù)據(jù)分布下的連接基數(shù)估計(jì)的精度。

本發(fā)明的目的通過如下的技術(shù)方案來實(shí)現(xiàn)：

一種基于連接簡(jiǎn)圖的數(shù)據(jù)庫連接基數(shù)估計(jì)方法，包括以下步驟：

利用元素過濾器，將數(shù)據(jù)庫表中的元素分為熱元素與冷元素；

將熱元素存儲(chǔ)至熱元素表中，將冷元素存儲(chǔ)至冷元素Sketch中；

分別計(jì)算兩個(gè)數(shù)據(jù)庫表的熱元素表的連接基數(shù)、冷元素Sketch的連接基數(shù)以及熱元素表和冷元素Sketch的連接基數(shù)，并相加，得到對(duì)該兩個(gè)數(shù)據(jù)庫表的連接基數(shù)的估計(jì)結(jié)果。

進(jìn)一步地，所述熱元素表用來存儲(chǔ)熱元素，其每一個(gè)表項(xiàng)由元素指紋和計(jì)數(shù)器兩部分組成，元素指紋是元素的一個(gè)哈希值，計(jì)數(shù)器記錄熱元素出現(xiàn)的頻數(shù)。

進(jìn)一步地，所述元素過濾器包括若干個(gè)桶，每個(gè)桶包括若干個(gè)記錄，每條記錄由元素指紋和計(jì)數(shù)器兩部分組成，元素指紋是元素的一個(gè)哈希值，計(jì)數(shù)器記錄元素出現(xiàn)的頻數(shù)。

進(jìn)一步地，所述冷元素Sketch是CM Sketch，由若干個(gè)計(jì)數(shù)器組成，并且有d個(gè)相互獨(dú)立的哈希函數(shù)，哈希函數(shù)的作用是將一個(gè)元素隨機(jī)映射到CM Sketch的一個(gè)計(jì)數(shù)器內(nèi)。