[發(fā)明專利]一種Gaia系統(tǒng)中的多表連接優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202011267934.3
• 申請(qǐng)日: 2020-11-13
• 公開（公告）號(hào): CN112256705B
• 公開（公告）日: 2022-11-01
• 發(fā)明（設(shè)計(jì)）人: 宗楓博;王國仁;趙宇海;鄭軍
• 申請(qǐng)（專利權(quán)）人: 北京理工大學(xué);東北大學(xué)
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22
• 代理公司: 北京理工大學(xué)專利中心 11120
• 代理人: 劉西云;李微微

本發(fā)明提供一種Gaia系統(tǒng)中的多表連接優(yōu)化方法，為了盡可能減少全局中間連接表體積進(jìn)而降低I/O代價(jià)，本發(fā)明設(shè)計(jì)了一個(gè)連接索引結(jié)構(gòu)，結(jié)合動(dòng)態(tài)規(guī)劃算法在優(yōu)化連接順序的同時(shí)對(duì)每個(gè)連接表的等值連接關(guān)系進(jìn)行優(yōu)化，同時(shí)針對(duì)連接計(jì)算代價(jià)和I/O代價(jià)進(jìn)行了優(yōu)化，有效地減少了多連接任務(wù)的運(yùn)算時(shí)間和中間數(shù)據(jù)的傳輸量；也就是說，本發(fā)明設(shè)計(jì)了一種描述連接表中列關(guān)系的索引結(jié)構(gòu)，此索引結(jié)構(gòu)可以快速找到兩個(gè)表的連接關(guān)系及每一列是否冗余列。

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

本發(fā)明屬于分布式大數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及一種Gaia系統(tǒng)中的多表連接優(yōu)化方法。

背景技術(shù)

多連接優(yōu)化的研究起源于傳統(tǒng)數(shù)據(jù)庫中多表查詢操作的優(yōu)化，傳統(tǒng)的數(shù)據(jù)庫查詢操作分為三個(gè)步驟：將用戶的查詢語句解析和翻譯為連接樹，優(yōu)化，執(zhí)行查詢。優(yōu)化步驟中包括通過重構(gòu)連接表達(dá)式在連接結(jié)果等價(jià)的條件下減小連接代價(jià)，當(dāng)連接樹存在n個(gè)連接關(guān)系時(shí)，則存在n！個(gè)等價(jià)的左深樹和(2n-2)！/(n-1)！個(gè)等價(jià)的稠密樹，多連接優(yōu)化問題已經(jīng)被多類算法研究過。它是經(jīng)典組合旅行商問題的推廣——在完全圖中尋找最短哈密頓圖。旅行商問題研究最多的組合優(yōu)化問題之一，已有幾十種算法被提出，這些算法大多直接適用于多連接優(yōu)化。主要包括確定性算法，隨機(jī)化算法，基因算法和混合算法。

確定性算法通過完全遍歷或在解空間中應(yīng)用一些啟發(fā)式剪枝方法，來執(zhí)行解空間的確定性搜索，如IBM的System R中使用的動(dòng)態(tài)規(guī)劃算法，這個(gè)算法被幾乎現(xiàn)有的所有商用RDBMS系統(tǒng)使用，該算法通過動(dòng)態(tài)剪枝解空間來進(jìn)行完全遍歷，通過迭代已有的連接關(guān)系并盡可能剪枝一些次優(yōu)解來構(gòu)造所有備選連接樹，從而保證了動(dòng)態(tài)規(guī)劃算法在解空間中找到最優(yōu)解。隨機(jī)化算法通過預(yù)定義的變換規(guī)則在解空間內(nèi)隨即移動(dòng)，不斷尋找代價(jià)更低的點(diǎn)，當(dāng)點(diǎn)不再移動(dòng)的次數(shù)達(dá)到預(yù)定義的迭代次數(shù)閾值時(shí)，則認(rèn)為當(dāng)前的解為較優(yōu)的解。如模擬退火算法(Simulated Annealing Algorithm)，它允許當(dāng)前點(diǎn)向代價(jià)更高的點(diǎn)移動(dòng)，從而降低了算法陷入局部最優(yōu)解的概率，此算法同時(shí)可以加入一個(gè)算法參數(shù)來定義在給定時(shí)間點(diǎn)繼續(xù)搜索的可能性，并和當(dāng)前點(diǎn)與目標(biāo)點(diǎn)的代價(jià)比例共同決定點(diǎn)移動(dòng)的概率。

基因算法通過模擬生物的進(jìn)化過程來尋找最優(yōu)解，通過將一個(gè)初始群體(解集合)中的個(gè)體(解)隨機(jī)交叉(crossover)和變異(mutation)產(chǎn)生下一代群體，將適應(yīng)度最高(通過代價(jià)函數(shù)定義)的部分個(gè)體保留，并重復(fù)交叉和變異的過程產(chǎn)生下一代群體，當(dāng)?shù)螖?shù)達(dá)到預(yù)定義的閾值或者群體適應(yīng)度已接近飽和，繼續(xù)進(jìn)化無法再顯著提高適應(yīng)度(通過閾值定義)時(shí)停止迭代過程。如PostgreSQL中的Genetic Query Optimizer，它只考慮了左深樹的情況，實(shí)現(xiàn)了精英選擇算子(Elitist selection operato)，對(duì)于群體中的最優(yōu)解，只進(jìn)行交叉而不進(jìn)行變異，防止群體中的最優(yōu)個(gè)體在迭代到下一代時(shí)發(fā)生丟失，從而導(dǎo)致算法難以收斂到全局最優(yōu)解。

混合算法混合了以上兩種及以上的優(yōu)化策略，比如巡回模擬退火算法(TouredSimulated Annealing)，該算法首先通過確定性算法確定幾個(gè)初始點(diǎn)，然后對(duì)每個(gè)初始點(diǎn)進(jìn)行模擬退火算法。

以上算法為主要基于傳統(tǒng)關(guān)系數(shù)據(jù)庫理論的多連接優(yōu)化，優(yōu)化的最小粒度為表，而在本文所提出的多表連接優(yōu)化方法中優(yōu)化的最小粒度為列，在傳統(tǒng)數(shù)據(jù)庫甚至一些節(jié)點(diǎn)數(shù)不高的分布式數(shù)據(jù)庫中，連接表的列數(shù)，或者說連接表的體積對(duì)I/O并不會(huì)造成顯著影響，而連接表的行數(shù)，即連接表的元組數(shù)會(huì)對(duì)計(jì)算量產(chǎn)生很大影響，因此這些傳統(tǒng)的多連接優(yōu)化算法主要注重于對(duì)連接元組數(shù)進(jìn)行優(yōu)化以提高計(jì)算效率。隨著MapReduce框架在大數(shù)據(jù)處理中的廣泛應(yīng)用，一個(gè)任務(wù)的計(jì)算節(jié)點(diǎn)可能達(dá)到成百上千個(gè)，那么節(jié)點(diǎn)間I/O帶來的影響不再可以忽視。

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

為解決上述問題，本發(fā)明提供一種Gaia系統(tǒng)中的多表連接優(yōu)化方法，可以在優(yōu)化算法中同時(shí)考慮計(jì)算和I/O的代價(jià)，并以動(dòng)態(tài)規(guī)劃算法為例，在動(dòng)態(tài)規(guī)劃算法的基礎(chǔ)上同時(shí)實(shí)現(xiàn)對(duì)計(jì)算和I/O的優(yōu)化。

一種Gaia系統(tǒng)中的多表連接優(yōu)化方法，包括以下步驟：