ゴールデンウィークだからエバラ焼き肉のたれ黄金の味で焼き肉をやるかわりにapache pigと戯れてやるよこの豚野郎 part 3

俺たちのゴールデンウィークはこれからだ!ということで、part2でいい感じになっていなかった、木構造の繰り返し自己結合による経路列挙を解きます。っていうか、日程的なゴールデンウィークを終えてから結構がんばってたのですが、なんかうまくいかなかったので結構ずれ込んでしまいました。

まあ世の中そんなものですかね。


ではまず問題の整理から。


こんな感じのデータがあるとします。木構造ですね。

親子関係だけを持つとすると、下記のようなデータを持つことになると思います。

こいつの経路を列挙したいという問題です。現実の問題としては、Web界隈ならクリックストリームの抽出に対応するし、製造業では部品表逆展開、ワークフローではまんまですが経路の列挙とか。そういう感じのものを解きたいときにつかいたいロジックですね。


では、経路列挙を行うコードを書いていきます。こないだ書いてたコードからはじめて、とりあえず満足できるところまで改善していきます。

上記のデータについての結果の期待値は、下記のような感じです。

(1,2,5,10)
(1,2,5,11)
(1,3,6,12)
(1,3,7,13)
(1,3,7,14)
(1,3,8,)
(1,4,9,15)

まあ、単純に自己結合をleafにたどりつくまでやりつづければいいのですが、pig latinでは制御構造がかけないので繰り返しができません。しょうがないので、展開する段数を決め打ちして実装します。二回結合すればいいので、二回結合します。


こないだ書いてたコードです。

結果が、

(1,2,2,5,5,10)
(1,2,2,5,5,11)
(1,3,3,6,6,12)
(1,3,3,7,7,13)
(1,3,3,7,7,14)
(1,4,4,9,9,15)

なので、1,3,4の経路がとれてないですね。こらあかん。要するに、leafまでの距離は一定でないので、left outer joinしないといけません。


ということで、left outer joinするのですが、スキーマなしのリレーションでは自然結合はできるようですがleft outer joinはできないそうなので、スキーマをつけます。

リレーションの要素について、asで名前と型をつけるとスキーマ付きのデータになります。Hiveと違って、スキーマがあるデータでもないデータでも、Pigは分析することができます。「豚は何でも食べるのよ」というのがPigのコンセプトなので。

これの結果だと、

(1,2,2,5,5,10)
(1,2,2,5,5,11)
(1,3,3,6,6,12)
(1,3,3,7,7,13)
(1,3,3,7,7,14)
(1,3,3,8,,)
(1,4,4,9,9,15)

まあ悪くはないですが、無駄にデータが残ってて嫌な感じです。パフォーマンス観点でもprojectionはしたいです。


ということで、foreach ... generateでprojectionするのですが、自己結合したリレーションのデータに対するprojectionを行う際に、同じリレーションからデータを結合すると、結合したリレーションに対する参照が結合もとのリレーションに対する参照になってしまう感じになっているので、うまく行きません。

要するにバグってる気がしますが、Pigには言語仕様がないので仕様通りかもしれません。しようがないので、いける方法で実装します。同じソースに対して結合しなければ僕の期待通りに動くので、そうします。

結果は、

(1,2,5,10)
(1,2,5,11)
(1,3,6,12)
(1,3,7,13)
(1,3,7,14)
(1,3,8,)
(1,4,9,15)

なので、いい感じです。rootとなるノードが決め打ちになっていますが、個人的には満足です。


以下残課題。まあ結合戦略なのでソースを読んでく感じがいいかなと。
・skew join
・merge join