巨大天体カタログと任意天体カタログとのポジションマッチアップ
山内 千里
宇宙航空研究開発機構 宇宙科学研究所

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.1/40

今日のお話し• 天体カタログとは• 天体カタログのデータ公開サービスとは• 今回の開発に至るまでの経緯• マッチアップの手法• PostgreSQL-8.4 を使った実装の基本• PostgreSQL-8.4 を使った大規模カタログ対応• まとめ

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.2/40

▼

天体カタログとは（1）
天体カタログの目的• 新天体 (超新星・彗星・小惑星等) の捜索• 地上観測・衛星観測での位置較正・等級の較正• データ解析による天文学研究における利用

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.3/40

▼

天体カタログとは（2）
一般的な天体カタログ• プライマリキー・座標 (経度, 緯度; 浮動小数点値)・等級などをカラムに持ち，1 行 1 天体
• カタログにより，位置精度がかなり異なる• 大規模カタログでは，「天体名」のカラムは無い
2 つ以上のカタログで同一天体の情報を得たい場合，位置精度を考慮して座標値が近いものを，自分で選ぶ必要がある→ データ解析ではこの “マッチアップ” の需要が高い

Sloan Digital Sky Survey の例
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.4/40

▼

天体カタログとは（2）
一般的な天体カタログ• プライマリキー・座標 (経度, 緯度; 浮動小数点値)・等級などをカラムに持ち，1 行 1 天体
• カタログにより，位置精度がかなり異なる• 大規模カタログでは，「天体名」のカラムは無い
2 つ以上のカタログで同一天体の情報を得たい場合，位置精度を考慮して座標値が近いものを，自分で選ぶ必要がある→ データ解析ではこの “マッチアップ” の需要が高い

Sloan Digital Sky Survey の例

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.5/40

▼

天体カタログとは（3）天体カタログはどのようにして作られる?
• 主役はサーベイ観測による天体カタログ- 観測プロジェクトが望遠鏡を長時間独占し，広い天域を掃きながら同一条件で写真を撮りまくる．
- それらの写真を専用のプログラムで解析し，星・銀河などを自動検出してカタログ化する．

SDSS サイトから引用
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.6/40

▼

天体カタログとは（4）天体カタログのデータ規模• USNO-B1.0 (アメリカ海軍天文台; 約 10 億天体)

過去の観測による多数の乾板をスキャンして作られた• 2MASS 点源カタログ (米国の複数の研究機関; 約 4.7 億天体)

地上望遠鏡による近赤外天体カタログ• 「あかり」中間赤外全天カタログ (JAXA; 約 87 万天体)衛星による国産初の全天サーベイ天体カタログ▼• 小規模なカタログは無数にある

天体カタログ用のデータ公開サービス• 天文学者が容易に活用できるように，特に大規模カタログでは専用の WebDB が作られる事が多い
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.7/40

天体カタログのデータ公開サービスとは（1）RDBMS に天体カタログを登録し，WebDB を開発して公開するのが一般的．次のようなサービスが求められる．
• ポジション (経度・緯度) による高速検索- Radial Search
1 つの経度・緯度から 半径 r 以内 の天体を検索- Rectangular Search
経度・緯度の範囲 (矩形領域) で天体を検索- Cross-ID(マッチアップ・クロスマッチ)

任意の天体カタログやユーザが用意したカタログのポジションすべてについて Radial Search を行ない，その結果を返す• 様々な条件による検索・結合・統計情報の取得• 画像や，他サイトへの動的リンクの提供
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.8/40

天体カタログのデータ公開サービスとは（1）Radial Search

Rectangular Search

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.9/40

▼

天体カタログのデータ公開サービスとは（2）Radial Search のページ遷移の例 — 検索条件入力ページ

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.10/40

▼

天体カタログのデータ公開サービスとは（3）Radial Search のページ遷移の例 — 結果ページ

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.11/40

▼

天体カタログのデータ公開サービスとは（4）Radial Search のページ遷移の例 — 画像確認ページ

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.12/40

▼

天体カタログのデータ公開サービスとは（5）
開発者視点での，天体カタログ WebDB の特殊性
• 各テーブルは Read Only である

最高の検索速度を狙う事ができる• RDBMS のテーブルには，読み取られて困る情報がない- “SELECT” から始まるユーザ SQL ステートメントの受付- テーブル・ビュー・ストアド関数の仕様公開- 想定外のアクセスが行なわれないように，セキュリティ設定が必要

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.13/40

▼

天体カタログのデータ公開サービスとは（6）SQL ステートメント入力ページ例

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.14/40

▼

天体カタログのデータ公開サービスとは（7）
開発者視点での，天体カタログ WebDB の特殊性
• 素人でも SQL ステートメントが書ける配慮が必要- 文字列・数値の変換や特別なアルゴリズムによる検索は，あらかじめストアド関数に実装→ RDBMS 製品は，ストアド関数の機能が強力である事
特に，複数の行を返すストアド関数が必須→ OSS では PostgreSQL がベスト!
- 検索結果と同時に，SQL ステートメントを表示- ドキュメントの充実• WebAPI も公開- wget 等でのアクセスも想定- コマンドラインでのインタフェースも開発し，公開
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.15/40

今回の開発に至るまでの経緯（1）• JAXA の「あかり」衛星全天サーベイによる日本初の 2 つの赤外線天体カタログ (合計約 130 万天体) が作成され，2010 年 3 月末に一般に公開

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.16/40

今回の開発に至るまでの経緯（2）• 「あかり」カタログ専用の WebDB の開発を担当する事になり，上記公開に合わせて開発・リリース• 「あかり」カタログと 2MASS カタログ (約 4.7 億天体を含む近赤外カタログ) とのマッチアップや，2MASS カタロ
グの高速検索の要望が複数の天文学者から寄せられる

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.17/40

▼

マッチアップの手法（1）
復習 … マッチアップとは?

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.18/40

▼

マッチアップの手法（2）
基本的な考え方• 2 つの天体リストのそれぞれの座標値について，2 つの座標間の角度 r が一定値以下の場合に，同一天体の候補とし，最も小さい r のものを「アタリ」とする．
• 天体リスト A，天体リスト B，それぞれの天球上での位置を直交座標系 (xAn , yAn , zAn )，(xBm , yBm , zBm ) で表わすと，2 つの天体間の角度r は，次の式で求まる．
´³r = acos2−{(xBm −xAn )2 +(yBm −yAn )2 +(zBm −zAn )2 }2

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.19/40

▼

マッチアップの手法（3）マッチアップの手法いろいろ• 総当たりで r を計算

巨大カタログでは現実的でない．
• 天球の分割 + 分割した領域ごとに総当たり

分割した領域の「端」付近の天体の扱いが面倒• Plane Sweep

緯度方向に，リスト A，リスト B を徐々に同時に掃きな
がら r の計算を最小限にする方法．現在，ベストと言われる方法だが，RDBMS 向きではない．
• Multiple Radial Search (今日のお話はコレ)「Radial Search」の検索をチューニングする
RDBMS 向け．
だけなので，システム全体をコンパクトに実装でき，SQL により柔軟な応用が可能 ←ユーザにとって重要
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.20/40

▼PostgreSQL-8.4 を使った実装の基本（1）Multiple Radial Search によるマッチアップのステートメント▼SELECT A.*, B.*-- 天体リスト A と天体リスト B とを結合
FROM(SELECT *-- 天体リスト A をFROM objlist A
ORDER BY dec-- 緯度の順でソート) AJOINobjlist B B
ON-- 検索半径 0.25 で最も近いものを自作関数で検索
fBGetNearestObjIDEq(A.ra, A.dec, 0.25) = B.objid;
Radial Search を行なう fBGetNearestObjIDEq() を最適化せよ!
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.21/40

▼

PostgreSQL-8.4 を使った実装の基本（2）高速 Radial Search のアルゴリズム• 天球分割による方法 — 天文業界での標準- 何らかの手法で天球を非常に細かく分割- 分割したそれぞれの領域に unique な「天域 ID」を付与

SDSS SkyServerから引用
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.22/40

▼

PostgreSQL-8.4 を使った実装の基本（3）高速 Radial Search のアルゴリズム• 天球分割による方法 (つづき)- 天体リストのテーブルに「天域 ID」のためのカラムを追加し，値の登録を行ない，インデックスを作成- 検索する時は，必要とする領域を取りこぼさないように「天域 ID」を計算して求め，「天域 ID」でインデックス・スキャンした後，r を求めて厳密な条件を満たすものだけ取り出す．
- 「天域 ID」の計算にやや時間がかかるため，小さい検索領域での多数の検索は苦手である．
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.23/40

▼

PostgreSQL-8.4 を使った実装の基本（4）高速 Radial Search のアルゴリズム• 直交座標系 (xyz ) を利用する方法 — 今回の方法- 天体リストのテーブルに，直交座標系での位置のためのカラムを追加し，値を登録- xyz の組み合わせで，複合インデックスを作成

CREATE INDEX objlist xyz ON objlist (cx,cy,cz);

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.24/40

▼PostgreSQL-8.4 を使った実装の基本（5）高速 Radial Search のアルゴリズム• 直交座標系 (xyz ) を利用する方法 (つづき)- サーチ半径 R の時，サーチポジションを中心とする一辺2R の立方体の中にある天体を，インデックス・スキャンで取り出し「候補」とする．
- 上記「候補」の天体すべてについて，検索位置からの角度
region for radial search(radius = R)を求め，条件を満たすものczのみ取り出す．
2R- インデックス・スキャン
2R
2Rまでの計算がほとんど無cube for index−scanof (cx,cy,cz)
く，小さいサーチ半径でcycxは効率的
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.25/40

▼PostgreSQL-8.4 を使った実装の基本（6）Radial Search の実際の SQL テートメント

SELECT o.*
FROM (SELECT objid,cx,cy,cz,fDistanceArcMinXYZ($1,$2,$3,cx,cy,cz) AS distance
FROM IrcObjAll
WHERE (cx BETWEEN $1 - fArcMin2Rad($4) AND $1 + fArcMin2Rad($4))
AND(cy BETWEEN $2 - fArcMin2Rad($4) AND $2 + fArcMin2Rad($4))
AND(cz BETWEEN $3 - fArcMin2Rad($4) AND $3 + fArcMin2Rad($4))) o
WHERE o.distance <= $4$1，$2，$3 …検索位置 (直交座標系)$4 …検索半径
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.26/40

▼

PostgreSQL-8.4 を使った大規模カタログ対応（1）「浮動小数点値の (x, y, z) に複合インデックス」の限界• 1 つのテーブルで単純に実装できるのは，せいぜい 1000万天体まで

3500
3000
2500
2000
1500
1000
500
002e+07

4e+07

6e+07

8e+07

計測に用いたマシン: DP Opteron 2384(2.7GHz) 32GB メモリ
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.27/40

▼

PostgreSQL-8.4 を使った大規模カタログ対応（2）2MASS カタログ (4.7 億天体) のための戦略• 天体の直交座標系での位置 (x, y, z) 専用のテーブルを作成• テーブルパーティショニング (緯度で分割)• CE を使わず，自作ストアド関数 (PL/pgSQL+C) で子テーブルを選択 (子テーブルが 100 個を越えても高速に動作)• 天体の直交座標系での位置 (x, y, z) を，4 バイト整数でスケーリングして格納→約 20GB
• (x, y, z) を 2 バイトに丸めた値に対して，複合インデック

スを作成 (複合式インデックス) →約 10GB
• SSD を活用

【インデックスの深さを抑え，ディスク I/O を最小化】
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.28/40

2MASS カタログ検索システムのためのテーブル設計

objid (INT4)

objid (INT4)

racxi ( INT4)deccyi ( INT4)

err_majczi ( INT4)}

twomass_xyzi

index

twomasschild tables

err_mintwomass_j2000i

child tables}

err_ang::objid (INT4)
rai ( INT4)
deci ( INT4)

index

▼

PostgreSQL-8.4 を使った大規模カタログ対応（3）

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.29/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（4）巨大テーブルパーティショニングのメリット・デメリット• パーティショニングをする場合○何らかの実装により，特定のカラムについてのみ，検索の高速化が可能．
×プライマリキーでの JOIN は，パーティショニングをしない場合よりも遅くなった．
• パーティショニングをしない場合○プライマリキーでの検索・JOIN は高速．
×unique ではないカラムの検索は苦手．

パーティショニングをする場合・しない場合それぞれのメリットをとる事が重要らしい．

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.30/40

ユーザはどのように使うのか?
fTwomassGetNearbyObjEq()

twomass
objid (INT4)
ra}twomass_xyzi
objid (INT4)cxi ( INT4)
cyi ( INT4)
czi ( INT4)

indexfTwomassGetObjFromRectEq()

child tablesdec
err_min
err_ang::

twomass_j2000i

child tables}

err_maj

objid (INT4)
rai ( INT4)
deci ( INT4)

index

▼

PostgreSQL-8.4 を使った大規模カタログ対応（5）巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.31/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（6）2MASS カタログ検索システムでの検索例• マッチアップ (個数を得る)
SELECT count(fTwomassGetNearestObjIDEq(o.ra,o.dec, 0.1))
FROM ( SELECT * FROM akari irc ORDER BY dec ) o;

• Radial Search(ワンタイムサーチ)
SELECT M.*-- 天体情報をメインテーブルから取得
FROM(-- Radial Search を行なう
SELECT *-- カラム (objid，座標，距離) の表が返るFROM fTwomassGetNearbyObjEq(1.2, 3.4, 10)) F
JOIN Twomass M -- メインテーブル
ONF.objid = M.objid;
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.32/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（7）2MASS カタログのための最適なパーティション数
3700
3600
3500

search radius = 0.1arcmin

3400
3300
3200
search radius = 0.25arcmin

3100
3000
2900
2800
2700

0200

400

600

800

1000 1200 1400 1600

計測に用いたマシン: DP Opteron 2384(2.7GHz) 64GB メモリ
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.33/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（8）普通の PC でのパフォーマンス (マシン起動直後に計測)

カタログ

サーチ半径

ディスク

経過時間 Radial-Search 回数

AKARI-IRC PSC 0.25arcmin RAID1(HDD×2)

18.2 分

798 回/秒

AKARI-IRC PSC 0.25arcmin

SATA2 SSD

8.2 分

1778 回/秒

AKARI-IRC PSC 0.25arcmin

SATA3 SSD

7.0 分

2078 回/秒

Tycho-2

0.25arcmin

SATA3 SSD

15.9 分

2666 回/秒

Tycho-2

0.1arcmin

SATA3 SSD

15.2 分

2788 回/秒

上記カタログから 2MASS カタログに対しマッチアップした．
AKARI-IRC PSC は約 87 万天体．Tycho-2 は約 250 万天体．
計測に用いたマシン: Core2Quad 3.0GHz 8GB メモリ + Crucial C300 SSD

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.34/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（9）いろんな PC + SSD での結果 (マシン起動直後に計測)
ハードウェア

経過時間 Radial-Search 回数

Q9650 (3GHz) + X48 + U3S6

15.2 分

2788 回/秒

XEON E5540 SMT:OFF (2.53GHz) + X58 + U3S6

17.6 分

2405 回/秒

PhenomII X4 945 (3GHz) + 890GX

18.0 分

2351 回/秒

Tycho-2 カタログ (約 250 万天体) から 2MASS カタログに対しマッチアップ

検索半径は 0.1 arcmin
ディスクインタフェースはすべて SATA3．SSD は Crucial C300 を使用

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.35/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（10）UP XEON E5540 + SSD で，マルチコア&SMT を活用:
1 つの PostgeSQL サーバ上で，N 個同時に SQL ステートメントを実行
プロセス数 N 経過時間 Radial-Search 回数 (平均)117.7 分2395 回/秒

210.8 分3926 回/秒

45.57 分7597 回/秒

83.23 分13094 回/秒

Tycho-2 カタログ (約 250 万天体) から 2MASS カタログに対しマッチアップ

検索半径は 0.1 arcmin
・2 プロセスの場合の SQL ステートメント
SELECT count(fTwomassGetNearestObjIDEq(o.ra, o.dec, 0.1))
FROM ( SELECT * FROM tycho2 WHERE objid % 2 =ORDER BY dec ) o;
0 or 1
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.36/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（11）細かなチューニング• CPU 等の動的クロッキングの停止- インテル系では，BIOS の C1E は必ず無効に (1 割以上改善)．EIST は影響が小さいが，止めた方が改善する事も．
- AMD 系では，BIOS の powernow または OS の cpuspeed を止める (最近は AMD 系でも C1E があるので注意)．
• effective cache size を 1GB 以下に設定
2GB 以上にすると，パフォーマンスが低下• SSD に対する先読み設定
hdparm で 1024 程度にする．これで数パーセント改善• SSD は ext4 でフォーマットext3 や xfs よりも数パーセント改善
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.37/40

▼PostgreSQL-8.4 を使った大規模カタログ対応（12）2MASS Catalog Server Kit の紹介• 誰でも 2MASS カタログの高速検索サーバが構築可能→ google で「"2mass kit"」で検索

巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.38/40

まとめ• 天体カタログは，新天体の捜索，観測での較正，データ解析による研究で使われ，データ解析ではカタログ間でのマッチアップの需要が高い．
• PostgreSQL-8.4 と最近の SSD を活用し，マッチアップにおいて，2MASS カタログ (4.7 億天体) に対して秒間 2000〜 3000 回の位置検索を，普通の PC で可能にするシステムを開発した．
- CE を使わず，自作関数で子テーブルを選べば，約 1000 個のパーティションまでパフォーマンスアップを狙える．
- 直交座標系の位置については，2 バイト整数値に対してインデックスを作成する事で，ディスク I/O を最小化
- 1 台の PC でも，SSD+マルチコア&SMT の活用で 2MASSカタログに対して秒間 10000 回以上の検索が可能
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.39/40

おまけ• 低価格対決 Crucial C300 v.s. Intel X25-M では，SATA-2 イン

タフェースの場合でも，C300 の勝ち．
• SATA-3 インタフェースカードは，PCIe x4 以上のものを買いたい．
• 安価な SATA-3 インタフェースカードとして，ASUS U3S6がある．パフォーマンスは抜群だが，相性問題あり．
○ X38，X58△ X48
× MCP55Pro• 6Gbps SAS カード LSI 9211-4i が C300 との組み合わせで良い結果を得ている．C300 × 3 で RAID0 を組めば，シーケ
ンシャルリード 1GB/秒を軽く越えてくる．
巨大天体カタログと任意天体カタログとのポジションマッチアップ – p.40/40