7/30 (水)
[PostgreSQL] Parameterized Path についての覚書
PostgreSQL の planner/optimizer の内部で使われる Parameterized Path について覚書を書きておく。 詳細は PostgreSQL ソースコードの src/backend/optimizer/README に記述されている。
PostgreSQL は JOIN 処理に対して Nested Loop、Merge Join、Hash Join の 3 つの処理方式を持っているが、Nested Loop が基本になっている。
今、テーブル A
とテーブル B
というテーブルがあって、A.X = B.Y
という条件で JOIN を掛ける。
SELECT B.Y FROM A, B WHERE A.X = B.Y
一番原始的な処理は nested loop を使って、テーブル A とテーブル B を二重にループし当てはまるものを探すことになる。
for (a : TABLE A) for (b : TABLE B) if (a.X = b.Y) output b.Y
これはナイーブな処理方法で効率がよくない。
もしテーブル A
が小さくてテーブル B
の大きく、かつテーブル B
にカラム Y
を含むようなインデックスがある場合、以下のように最適化できる。
for (a : TABLE A) for (b : INDEX ON B (condition a.X = b.Y)) output b.Y
内側の B のインデックススキャンに条件を足しているが、この条件は外側のループの a によってパラメタライズされている。 このようなアクセスパス(Access Path)を PostgreSQL の用語で Parameterized Path と呼ぶらしい。
EXPLAIN の出力だと以下のようなイメージになる。
NestLoop -> Seq Scan on A -> Index Scan using B_Y_IDX on B Index Condition: B.Y = A.X
Planner/optimizer の中では構造体 Path
の param_info が NULL 出ない場合は parameterized path となる。
typedef struct Path
{
NodeTag type;
NodeTag pathtype; /* tag identifying scan/join method */
RelOptInfo *parent; /* the relation this path can build */
ParamPathInfo *param_info; /* parameterization info, or NULL if none */
/* estimated size/costs for path (see costsize.c for more info) */
double rows; /* estimated number of result tuples */
Cost startup_cost; /* cost expended before fetching any tuples */
Cost total_cost; /* total cost (assuming all tuples fetched) */
List *pathkeys; /* sort ordering of path's output */
/* pathkeys is a List of PathKey nodes; see above */
} Path;
7/26 (土)
[Movie] Godzilla
チネチッタで 3D 吹き替えの『Godzilla』を観て来た。 中盤以降、ムート、ゴジラの3匹が姿を現して以降は怪獣映画の本道という感じで面白い。
追記:7/27
川崎 109 シネマズの IMAX 3D で二度目を観て来た。 吹き替えと字幕でセリフがいくつか異なっている。 ステンツ少将が芹沢博士にゴジラはムトーに勝てるかとたずねるシーンで、吹き替え版では「我々は祈るだけだ」みたいなことを言うが、元は「(ゴジラとムトーを)戦わせてみよう(決着は分からんよ)」のような表現になっている。
[Food] カプリチョーザ@川崎
映画を観た後に銀柳街のプリチョーザに入って夏の冷たいカルボナーラという季節限定メニューを食べたが、望外に美味かった。
7/23 (水)
7/21 (月)
メトロポリタン美術館 古代エジプト展@東京都美術館
メトロポリタン美術館 古代エジプト展 女王と女神を観て来た。 15:00頃に入ったが中はそれほど混雑していなかった。
あまり期待せずに行ったのだが、過去のエジプト展とは趣が異なって面白い。 エジプト新王国期のハトシェプスト女王の遺物が中心で装飾品が多いが一つ一つが華麗な装飾がなされていて見ていて面白い。
ところで今回の展示で関心したのは、展示物の説明が複数個所に貼ってあるという点。 展示物の前だけに貼るとそれを読むために客の足がとまるのだけど、壁とかにも同じ内容が貼ってあるので並列処理できる。 まあ東京都美術館の企画展スペースにかなり「ゆったり」と配置できているので可能な技なのだろうけど。
7/20 (日)
[Android] Bluetooth のオーディオヘッドセットを三度購入
Android 用の Bluetooth のオーディオヘッドセットを初めて購入したのが2011年7月30日。 SONY DRC-BT60P だったのだがミニヘッドフォン端子がグラグラして音がちゃんと出なくなって轟沈。
二台目を購入したのは2012年7月16日。 ロジテックの LBT-AVHP300。 ネクタイピンを大きくしたような形をしたイヤフォン一体型のオーディオヘッドだった。 しかしピンの部分が壊れて、服にクリップすることができなくなった。 電子的には問題ないが、通勤中に使うことができなくなって轟沈。
川崎のヨドバシで涙ながらに三台目を購入。 今度は Sony の SBH50。 どうか壊れてくれるな。
[Movie] プレーン2
チネチッタで「プレーン2」を観る。 「カーズ(Cars)」は DVD で観たけど「プレーン」の1は観ないまま鑑賞。
7/19 (土)
ブラジルフェスティバル 2014 @代々木公園
残念なことに小雨が降る渋谷。 代々木公園で今日と明日にわたってブラジルフェスティバル 2014が開催される。
ブラジル料理の店が並ぶ。 ドネルケバブだのジャンバラヤの店も並ぶ。
BRAZILIAN DAY JAPAN 2013 で食べたブラジルカレーは、小豆ご飯だと思っていたのだが、もしかするとアサイーを使って炊いたご飯だったのかもしれない。
アサイースノーアイスは珍しい。 見た目はチョコっぽいけど、甘くないのがいい。
7/17 (木)
川崎図書館の利用登録
武蔵小杉の川崎市立図書館で利用登録を行った。 武蔵小杉図書館はいつ行っても満員状態なので、本を借りて読むことにしたからだ。
川崎は南武線沿いに並ぶように13の図書館があるようだ。 別に県立図書館もある。
7/14 (月)
[Algorithm] Cuckoo Hashing
Cuckoo Hashing は 2001 年に Rasmus Pagh と Flemming Friche Rodler によって発明されたハッシュアルゴリズム(Wikipedia、元論文)。 ハッシュを検索する時間が一定になりなるのが特徴。 ただしハッシュへの挿入は重い。 データベースやディスクキャッシュの分野で利用されている。
Cuckoo は鳥のカッコウを意味し、カッコウがホオジロなどの巣に自分の卵を産み、それをホオジロの親鳥に孵させる。 その際に、カッコウは元の巣にあったホオジロの卵を捨ててしまう。 Cuckoo Hashing は、このカッコウの習性に似ている。
Cuckoo Hashing では 2 つのハッシュ関数(h1(x)とh2(x))と、2枚のハッシュテーブル(HashTable1、HashTable2)を用いる。 ハッシュテーブルはリンク構造を持たず、同一のハッシュ値の値を一つしか保持できない。
- あるキーkがハッシュテーブルに含まれているかどうかは HashTable1 の h1(k) のエントリと、HashTable2 の h2(k) のエントリを確認する。キーが Cuckoo Hash Table に含まれていればどちらかから見つかる。その二箇所から見つからなければ、キーは Cuckoo Hash Table に含まれていないことになる。
- 新しいキーを挿入する場合、少し複雑である。
- HashTable1 の h1(k) のエントリか HashTable2 の h2(k) のエントリのどちらかに挿入する。 エントリが空ならそのまま登録すればよい。両方が埋まっている場合、どちらに登録するか決める。これはランダムでよい。
- 仮に HashTable1 の h1(k) に挿入することに決めた場合、そこにはすでにエントリが存在している。仮にそれを l とする。 まず l を取り出しておき k を登録する。 その後で l はハッシュの反対側、HashTable2 の h2(l) へ登録する。 このエントリが空なら l を登録して終わりである。しかしそこにも別の値、仮に m があったとする。
- 2. でやったように m を追い出し、反対側のハッシュテーブル HashTable1 の h1(m) へ登録する。 そにも値があった場合は、それを追い出してぐるぐる繰り返す。
ハッシュテーブルの再構築は時間がかかり、これが cuckoo hashing の弱点といわれている。 内部のハッシュテーブルとハッシュ関数のセットを 2 組ではなく、もっと多数枚持つものなどがバリアントが考えられている。
Cuckoo Hashing のネーミングについて
ところで、私は Cuckoo Hashing の動作を見て、これはカッコウというよりメキシコに居る社会性のクモ Oecobius civitas に近いと思った。 Oecobius civitas のことはドーキンスの「利己的な遺伝子」で知った。 ある種の生き物はテリトリーを持つが、先住者のテリトリーに侵入者が入ってきて争いになった場合、個体の戦闘能力が同程度でも侵入者の方が引き下がることが多い。 双方が決着が着くまで戦うより、先住者にアドバンテージを認めて戦闘を終結させる進化的に安定な戦略(ESS)だとされる。 ところが Oecobius civitas はそれとは逆に侵入者にアドバンテージを認めている。
その部分を引用すると、
私は少々早まったようだ。この文を書いたあとで、私はメイナード=スミス教授から、J・W・バージェンスがメキシコ産の社会性のクモ Oecobius civitas の行動にういて次のように書いていることをきいた。
「このクモは何かに妨害されて隠れ場所から追い出されると、岩の上をつっ走り、身を隠すことができる空いた割れ目がみつからないと、同種の別の個体の隠れ場所に逃げ込む。
侵入者がはいってきたときに、そこに先住者のクモがいると、そのクモは侵入者を攻撃しないで逃げ出し、新たに自分の隠れ場所をさがす。
このため、いったん最初のクモが追いだされると、次々と巣の持ち主の入れ替わりがおこり、それが数分も続いて、しばしば、その集団の大部分の個体が自分の住み家からよその家に移らされることになる
(社会性のクモ、サイエンティフィック・アメリカン誌、1976年3月号)
どうだろう。 カッコウの托卵よりも、こちらの方が適していないだろうか?
7/13 (日)
7/12 (火)
太古の哺乳類展@上野国立科学博物館
上野の国立科学博物館で太古の哺乳類展がはじまったので観にいった。 今日が初日だが比較的すいている。
残念ならが今回の展示の全身標本はほとんどレプリカで、実物は歯の化石である。
束柱類という海性哺乳類の全身骨格だがこれはレプリカ。 右端の奴がパレオパラドキシアのはず。
パレオパラドキシアの実物は歯の化石と頭がない全身骨格のみだった。 しょんぼり。
特別展のチケットで常設展も観れるので、久しぶりに地球館を観てくる。 って、もしかして10年ぶりかしらん?(2004年5月9日) これまで観たことのなかた B2〜B3 や屋上を鑑賞する。 B2 は恐竜以外の古代生物、B3 は物理・化学・宇宙関係の展示がある。
B2 はカンブリア紀の化石のオンパレード。
太古の魚類の化石か。
パノクトゥスという南アメリカにいた甲羅を被る哺乳類。
[Food] 東坡@原宿
東京、“激辛”麻婆豆腐 10選の制覇を目指していたことを思い出して、原宿の一角にある東坡という店に行ってみる。 中国家庭料理を謳っていてお爺さんが一人で調理している。
花椒が強いとあったが、唐辛子の辛さも結構強い。
7/9 (水)
[MyWeb] pib を Linux カーネル 3.15 に対応させる
Linux カーネルの 3.14 から 3.15 で include/rdma/
に格納されているデータ構造に変更があり、pib がコンパイル時にエラーを出すようになった。
具体的には struct ib_umem
と struct ib_dma_mapping_ops
のメンバ変数に増減がある。
野良カーネルモジュールなので複数のバージョンに対応させる必要があるが、これは LINUX_VERSION_CODE
で対応している。
#if LINUX_VERSION_CODE >= KERNEL_VERSION(3, 15, 0) #else #endif
あと 3.15 からコンパイラオプションが変更され、浮動小数点を戻り値とする関数が呼び出せなくなった。 これは浮動小数点の割り算なども該当するようだ。
7/6 (日)
ドライヤー
川崎のヨドバシカメラでドライヤーを探すが、どいつもこいつもマイナスイオンだのナノイオンだのを出しやがる。 変なイオンの出ないドライヤーを見つけて購入。
[Movie] マレフェセント
チネチッタで『マレフェセント』(原題:Maleficent)を観る。 四分の三程度の席が埋まっていた。 ディズニーはこのところ『Alice In Wonderland』、『オズ はじまりの戦い』、『ジャックと天空の巨人』など過去のメルヘンの改作した作品を出し続けているが今回は眠れる森の美女である。
ストーリー展開は最初の20分ぐらいで全部読めてしまった。 同じディズニーで似たような脚本が続くのはどうかと…
[Movie] 聖闘士星矢 LEGEND of SANCTUARY
ついでにレイトショーで『聖闘士星矢 LEGEND of SANCTUARY』を観る。 当初想像していたよりは違和感はなく、十二宮の戦闘に入ったあたりでは普通に見られた。 ストーリーはダイジェストなので矢のように飛んでゆくが、シャカとアフロディーテの戦闘を省いたせいで一輝と瞬に見せ場が無くなってもうた。