MapReduce中迭代查詢的最優化是怎樣的

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

MapReduce中迭代查詢的最優化

摘要：

          提出術語OptIQ：在分布式環境中迭代查詢的一種查詢優化的方法。（全自動化的）

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

           物化視圖和增量視圖評估

           作用：減少了不同迭代過程中的重復計算

1. INTRODUCTION

            幾種新的技術：

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

          OptIQ：為辨別迭代查詢中出現的重復計算提出了一個總體框架，應用了在傳統數據庫領域中的物化視圖和增量試圖評估和編譯器領域中的程序分析和轉換的技術。

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

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

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

包括三部分

         Local table 保存當前的迭代中的數據  存在本地磁盤中 let語句

           Global table 保存上一次迭代的數據 存在分布式文件系統。set語句

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

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

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

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

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

Group-by操作重組元組和計算聚集函數

PageRank：

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

Src當前節點  Dest 目的節點   Score相當于PR值  count表示節點的出度

K-means：

兩個表

Point數據點，Centro聚集的中心點

定義的語句

3、查詢優化：

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

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

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

          為了進行物化視圖-------表分解

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

         為了進行自動的增量--------增量表（delta table）

         根據收斂條件減少元組數目。

         OptIQ概述圖

          如何物化視圖

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

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

如PageRank

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

            子查詢的提升（在上面的基礎上繼續優化）如利用分解的表在形成另外一個可以物化的表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（循環不變量）

物化視圖最后優化的語句

     Automatic incrementalization

          1、跟新操作Update operations

           Update操作執行的頻率大于Insert和delete操作

           2、檢測增量表Detecting delta tables

             3、得到增量查詢Deriving incremental queries

        剛開始比較常規的語句

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

        set T = q(T ⊕ ΔT )

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

         Dscore是score表的一個增量表

            研究聚集函數中的增量計算，能夠很大程度的提高性能

                 Sum函數

           Count函數和sum函數有相同的分布規律，average函數可以分解為count函數和sum函數

     Max和min函數

加了incrementalization之后的語句：

實驗

Hadoop和spark上使用OptIQ

PageRank

反應時間和迭代次數減少

K-means

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

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

空間換時間

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

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