第4回　データ処理の方法

はじめに

前回までは、（⁠並列）データ処理の説明をするために必要な言葉の定義や整理をしてきました。いよいよこれからは、データ処理自体について触れていきます。今回は、アプリケーション開発者の視点から見るデータ処理にはどのようなものがあり、その観点において、Hadoopがどのようなものであるか、また、Hadoopがどのようにデータ処理を構築しているかについて、その概要を説明します。

手続き型言語によるデータ処理と宣言型言語によるデータ処理

データ処理は、データ処理を行うアプリケーション開発者（ユーザ）の視点から見ると、

手続き型言語によるデータ処理
宣言型言語によるデータ処理

の2つに大別することができます。

手続き型言語によるデータ処理は、ユーザがプログラミング言語等を用いて行うデータ処理です。たとえば、CやPerlなどを用いて行うデータ処理や、汎用機においてCOBOLなどを用いた集計処理などがこれに該当します。一方、宣言型言語によるデータ処理は、ユーザが宣言型言語を用いて行うデータ処理です。たとえば、関係データベースシステム（RDBMS）におけるSQLを用いたデータ処理がこれに該当します[1]⁠。

これらの違いを少し概念的に表現すると、手続き型言語によるデータ処理においては、ユーザがどのように（How）データ処理を行うかを記述するのに対し、宣言型言語によるデータ処理においては、ユーザはどのような（What）データ処理を行うかを記述します。すなわち、宣言型言語によるデータ処理においては、ユーザは当該データ処理をどのように行うかは記述しません。たとえば、

"SELECT * FROM table WHERE attribute > 10"

のようなSQLにおいては、ユーザはtableにおいてattributeが10より大きいレコードを取り出すことを（データ処理系に）指示していますが、当該レコードを取り出すために、tableを全スキャンして取り出すか、もしくは、attributeの索引を用いてtableにアクセスするか、などの方法については指示していません。

実行プラン（実行計画）

データ処理においては、データ処理プログラムを実行プラン（実行計画）と呼びます。手続き型言語を用いる場合は、ユーザがプログラム言語を用いてデータ処理のプログラムを作成するので、実行プランはユーザにより明示的に作成されます。一方、宣言型言語を用いる場合は、実行プランは処理系によってSQLなどの宣言型言語からユーザに暗黙的に作成されます。つまり、処理系が宣言を解釈して何らかの方法で実行プランを作成します。

近年のデータ処理においては、都度、手続き型言語によりデータ処理プログラムを開発するのは必ずしも容易ではないため、DWHを始めとし、宣言的言語をインターフェースとして用いるデータ処理系が広く普及しつつあります。しかしながら、宣言的言語は必ずしもすべての処理を（効率的に）記述できるわけではありません。たとえば、SQLはチューリング完全[2]ではありませんので、本質的には、記述できない処理があります。また、SQLなどから常に効率的な実行プランを導出することは必ずしも容易ではなく、場合によっては、非効率な実行プランが導出されて実行される場合もあります。このことから、ユーザにある程度の手続きを記述させつつ、当該手続きを実行する大枠のプランは処理系が規定するような、フレームワーク型のデータ処理系も普及しつつあります。本連載における主題の1つであるHadoopは、当該データ処理系に該当するものであると考えられます。すなわち、Hadoopにおけるデータ処理は実行プランの作成の観点からすると、手続き型言語によるデータ処理と宣言型言語によるデータ処理の中間的なものであるとみることができます。

Hadoopの動作原理を理解するためには、Hadoopにおけるデータ処理において、どのように実行プランが作成されるかを理解する必要があります。手続き型言語によるデータ処理においては、基本的にはユーザがすべての処理を記述するため、実行プランの観点からは特にこれ以上述べることはありません。しかしながら、宣言型言語によるデータ処理において、どのように実行プランを作成するか、または、どのように複数の計算機で並列にデータ処理を行う実行プランを作成するかなどは、並列型の関係データベースシステム（並列関係データベースシステム、並列データベースシステム）における技術に基づいており、当該技術を丁寧に理解する必要があります。加えて、近年注目を集めている並列データ処理系であるClouderaのImpalaやFacebookによって開発されているPrestoなども宣言的言語（SQL）をユーザインターフェースとして用いるデータ処理系であるため、これらの動作原理の理解においても当該技術の理解は必須です。よって、以降の数回は、並列データベースにおける技術について見ていくこととします。まずは、宣言型言語によるデータ処理における実行プランをもう少し深掘りしていきます。

宣言型言語によるデータ処理における実行プラン

宣言型言語によるデータ処理における実行プランには、多くの場合、論理実行プランと物理実行プランの2つの実行プランがあります。論理実行プランは、図1（a）に示すような、データ処理の内容および手順が抽象的に表現されたプランです。たとえば、SQLを構文解析して得られる関係代数表現は当該実行プランの1つです。一方、物理実行プランは、データ処理の内容および手順が具体的に表現されているプランです。たとえば、図1（b）に示すような、データをどのような形で読み取り（データをスキャンするか、もしくは、インデックスを用いてアクセスするか⁠）⁠、また、どのようなアルゴリズムで複数のデータを結合するか、加えて、どのように複数の計算機を用いて並列にデータ処理を行うか、ということを表したものが当該実行プランの1つです。

関係データベースシステムなどのデータ処理系においては、SQLなどの宣言が論理実行プランに変換され、論理実行プランが物理実行プランに変換され、物理実行プランが実際に計算機で実行されます。この際、論理実行プランは関係代数演算子の組み合わせにより構成され、物理実行プランはTableScanやHashJoinなどの事前に定義された処理オペレータ（オペレータ）の組み合わせにより構成されます。

論理実行プランや物理実行プランの構成においては、関係代数演算子やオペレータの並べ方により、そのデータ処理の性能や効率は大きく左右される可能性があるため、当該演算子やオペレータをどのように並べるかという問題があります。任意の並び順を考慮するとすると、考慮すべきパターン数は膨大になり、特に演算子やオペレータの数が多い場合には、現実的な時間では最適な並び順を導出することは難しいと考えられます。このことから、演算子およびオペレータを並べる形に制限を設けることにより、考慮すべき並び順の数を削減する取り組みが見られ、たとえば、木（ツリー）の形態に限定することが行われています。

考慮すべき並び順の数を削減しつつ、可能な限り効率的な実行プランを見つけるべく、図2に示すようなLeft-Deep Tree型、Bushy Tree型、Right-Deep Tree型を始めとし、これまでさまざまな木の形態が考案されてきました。これらの具体的な違いについては、また後の回で触れていく予定ですが、たとえば、複数の表を結合する場合においては、木の形態によって表の結合順序が異なることがあります。Left-Deep Tree型においては、2つの表を結合し、その結果と次の表を結合する、というように処理が進みます。これに対し、Bushy Tree型においては2つの表を結合し、またほかの2つの表を結合し、2つの結果を結合する、というように処理が進みます[3]⁠。後の回でまたくわしく説明する予定ですが、HadoopのSQL処理系であるHive[4]の実行プランにおいては、map()関数を実行するオペレータとreduce()関数を実行するオペレータをLeft-Deep Tree型で接続します。

なお、関係データベース等のデータ処理系において、どのような木の形態を用いてどのような順番でオペレータを接続するかを決定することを、問い合わせ最適化と呼びます。問い合わせ最適化についても、後の回でかんたんに触れる予定です。

おわりに

今回は、データ処理には手続き型言語によるデータ処理と宣言型言語によるデータ処理があり、Hadoopなどのデータ処理系は、実行プラン作成の観点においては、それらの中間的なものであると考えられることを述べました。また、宣言型言語によるデータ処理を詳細に見ていく準備として、当該データ処理における実行プランの作成の流れをかんたんに説明しました。次回は、宣言型言語によるデータ処理において、どのように実行プランを並列化するかについて、その概要を説明していきます。