MapReduce中迭代查詢的最優(yōu)化是怎樣的

本篇文章為大家展示了 MapReduce中迭代查詢的最優(yōu)化是怎樣的，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

MapReduce中迭代查詢的最優(yōu)化

摘要：

          提出術(shù)語OptIQ：在分布式環(huán)境中迭代查詢的一種查詢優(yōu)化的方法。（全自動化的）

          用到的方法：view materialization and incremental view evaluation.

           物化視圖和增量視圖評估

           作用：減少了不同迭代過程中的重復(fù)計(jì)算

1. INTRODUCTION

            幾種新的技術(shù)：

          Spark     Haloop     REX  查詢優(yōu)化都不是自動化和框架化的，需要程序員指出那些數(shù)據(jù)需要重用以及手動的指定那些數(shù)據(jù)如何存儲。

          OptIQ：為辨別迭代查詢中出現(xiàn)的重復(fù)計(jì)算提出了一個總體框架，應(yīng)用了在傳統(tǒng)數(shù)據(jù)庫領(lǐng)域中的物化視圖和增量試圖評估和編譯器領(lǐng)域中的程序分析和轉(zhuǎn)換的技術(shù)。

           流程：1、把迭代查詢分為變和不變的視圖，并且不變的視圖將會用到下次的迭代過程中去。

2、通過跳過評估那些收斂的元組來增量化變化的視圖。

2、為迭代查詢定義SQL語句

包括三部分

         Local table 保存當(dāng)前的迭代中的數(shù)據(jù)  存在本地磁盤中 let語句

           Global table 保存上一次迭代的數(shù)據(jù) 存在分布式文件系統(tǒng)。set語句

        判斷是否收斂時跟新表中（update table）的所有的元組都要進(jìn)行比較。

               R和S是輸入表，schema（R）表示R表的屬性，T（list）表示T表中有一個list屬性，表示一個命題公式。

      投影操作（projection）投影輸入表中特殊的屬性集

        選擇操作（selection）選擇滿足輸入表中滿足的元組

       連接操作（join）提取兩個輸入表的叉積滿足^2的元組

Group-by操作重組元組和計(jì)算聚集函數(shù)

PageRank：

三個表，定義的查詢語句如下

Src當(dāng)前節(jié)點(diǎn)  Dest 目的節(jié)點(diǎn)   Score相當(dāng)于PR值  count表示節(jié)點(diǎn)的出度

K-means：

兩個表

Point數(shù)據(jù)點(diǎn)，Centro聚集的中心點(diǎn)

定義的語句

3、查詢優(yōu)化：

          view materialization and incremental view evaluation.（物化視圖和增量視圖評估）

        物化視圖重用了未修改屬性子查詢的結(jié)果

        增量視圖評估重用了未修改元組的結(jié)果

          為了進(jìn)行物化視圖-------表分解

          把表分解成變和不變的視圖，重復(fù)使用不變的視圖。

         為了進(jìn)行自動的增量--------增量表（delta table）

         根據(jù)收斂條件減少元組數(shù)目。

         OptIQ概述圖

          如何物化視圖

1、把update table 分解成變和不變的視圖，重寫迭代查詢語句，把update table 用變化的視圖表示(變和不變的視圖有一個相同的視圖，最后可以用來進(jìn)行join操作)

2、物化查詢過程中不變的視圖，重寫和簡化迭代過程重要使用的不變視圖

如PageRank

              將Graph（src，dest，score）分解成 VI（src，score）和IT（src，dest）

            子查詢的提升（在上面的基礎(chǔ)上繼續(xù)優(yōu)化）如利用分解的表在形成另外一個可以物化的表IT_count

          IT_Count = select IT.src,IT.dest,Count.count

           from IT, Count

          where IT.src = Count.src.

               VT表和score表可以相互替換

                loop invariant code motion（循環(huán)不變量）

物化視圖最后優(yōu)化的語句

     Automatic incrementalization

          1、跟新操作Update operations

           Update操作執(zhí)行的頻率大于Insert和delete操作

           2、檢測增量表Detecting delta tables

             3、得到增量查詢Deriving incremental queries

        剛開始比較常規(guī)的語句

       T是update table，q(T)相當(dāng)于查詢語句，φ(ΔT )是收斂條件

        set T = q(T ⊕ ΔT )

      假設(shè)：q(T ⊕ ΔT) = q(T) ? q(ΔT ).

         Dscore是score表的一個增量表

            研究聚集函數(shù)中的增量計(jì)算，能夠很大程度的提高性能

                 Sum函數(shù)

           Count函數(shù)和sum函數(shù)有相同的分布規(guī)律，average函數(shù)可以分解為count函數(shù)和sum函數(shù)

     Max和min函數(shù)

加了incrementalization之后的語句：

實(shí)驗(yàn)

Hadoop和spark上使用OptIQ

PageRank

反應(yīng)時間和迭代次數(shù)減少

K-means

View并沒有增加效率，優(yōu)化過程中磁盤讀寫增加了。

物化視圖： 物化視圖（Meterialized View）提供了強(qiáng)大的功能，可以用于預(yù)先計(jì)算，并且保存表連接或者表聚集等耗時比較多的操作的結(jié)果，這樣子，在執(zhí)行查詢的時候，就可以避免這些耗時的操作，從而快速的得到結(jié)果。

空間換時間

如何能夠保證IO開銷，即消耗空間換取的時間能不能抵消掉讀磁盤產(chǎn)生的IO開銷。

上述內(nèi)容就是 MapReduce中迭代查詢的最優(yōu)化是怎樣的，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注億速云行業(yè)資訊頻道。