Project Tsurugi
SQL処理の実装
ノーチラス・テクノロジーズ
2020-10NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

Agendan SQL実⾏エンジンの役割
n SQL実⾏エンジンの⽬指すものn 現代的HWにおけるデータ処理の課題
n SQL処理におけるデータ並列
n shuffle処理によるデータ分割
n shuffleにおけるキャッシュの効率的な利⽤
n shuffleはなぜsortベースかn その他

NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

2

SQL実⾏エンジンの役割
n SQLで記述されたデータ処理を実⾏SQL
クライアント処理
結果

サービスフロントエンド
SQL
SQLコンパイラ
実⾏計画

処理
結果

SQL実⾏エンジン
Get/Put
トランザクションエンジン
I/O
データストレージ
RDBMS
NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

3

Tsurugi SQL実⾏エンジンの⽬指すものn SQL処理をインメモリで⾼速に実⾏– 特性の異なるワークロード両⽅に対応
n ⽐較的単純な⼤量のSQL処理

n ⼤規模なデータ処理を⾏う複雑なSQL– SQL内の関係演算⼦を⾼速に並列処理
n inter-/intra-operator paralleln inter-query paralleln 現代的なアーキテクチャのHW性能を活⽤– メニーコア - 数⼗~数百コアを利⽤可能– ⼤容量メモリ - 数TBの記憶領域

NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

4

現代的HWにおけるデータ処理の課題
n 課題– 多数のCPUコアを⼗分に活⽤するためにプログラムとデータを効率よくコアに供給し続ける必要がある– メモリのアクセス速度の進歩は容量やCPUコア数の増加よりも緩やかであり、相対的にボトルネックとなりやすい

n 解決案– データを適切に分割しデータ並列を実現することによってコアを⼗分に活⽤する– メモリキャッシュを適切に利⽤して、メモリ本体へのアクセスを減らす

NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

5

SQL処理におけるデータ並列
n SQL処理は関係演算⼦グラフに沿ったデータフ

ロー処理
n ⼊⼒データを分割することで、関係演算⼦を並列実⾏可能にしたい

Join

NAUTILUS

Join

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

Join

Join

6

SQL処理におけるデータ並列の難しさ
n SQLの関係演算は素直にデータ並列化できない– ⼊⼒を単純に分割しても正しい結果を得られない– 重要な演算⼦の多くはグループ単位で処理を⾏う
n グループを壊さないようにデータを分割する必要がある– 等結合であれば結合に使⽤しているキーで分割– 集約の場合はグループ化キーで分割

NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

7

例︓Joinに対する適切な分割
n 下記のJoinを分割することを考える
XYC1C2A

1B

2C1C3A

10B

20

Join on X.C1 =Y.C1NAUTILUS

C1C2C3A

110B

220Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

8例︓Joinに対する適切な分割
n 等結合キーC1が等しい⾏は同じ分割単位に所属
X

Y

C1C2A

1B

2=

C1C3A

10B

20=

C1C2A

1+

C1C3A

10+

C1C2B

2C1C3B

20「A」の分割「B」の分割Join on X.C1 = Y.C1NAUTILUS

C1C2C3A

110B

220=

C1C2C3A

110+

C1C2C3B

220Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

9

Tsurugi 実⾏エンジンにおけるデータ分割(1/2)
⼤規模メモリを活かし、インメモリでデータを分割
AA

B

B

この操作をshuffleと呼ぶ

Join

NAUTILUS

Join

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

Join

10

Tsurugi 実⾏エンジンにおけるデータ分割(2/2)
n メモリ上のshuffle処理は、多くのコアが同時に⼤量の読み書きを⾏い、メモリアクセスが逼迫しやすい
n そこでメモリキャッシュの活⽤に効果的なアルゴリズムを⽤い、メモリへの直接アクセスを削減する– 複数のコアで同じ領域を同時に扱わない– シーケンシャルアクセスを多⽤しプリフェッチ効率を⾼める(空間局所性)– あるメモリアドレス上のデータを複数回アクセスする場合、その間の処理を最⼩にする (時間局所性)

NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

11

shuffle処理の例(1/3)
A

1E

2C

5B

2C

4A

6A

3F

6B

3B

3C

4C

5A

6E

2F

6B

3B

2C

4C

5E

2F

6A

1A

3A

1A

3NAUTILUS

B

A

26A

1B

3C

4A

3B

2C

5A

6E

2F

6Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

12

shuffle処理の例(2/3)
宛先ごとに分割・ソート宛先に転送ソート済みをマージ

NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

13

shuffle処理の例(3/3)
スレッドは個別のローカル領域で処理を⾏うため
競合しない

転送時のみ
同期NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

14

shuffleにおけるキャッシュの効率的な利⽤(1/2)
n ソートによる処理⽅式

メモリを採⽤– ⼤規模ソートは分割統治⽅式が多い– 時間/空間局所性が⾼く、キャッシュを活かしやすいn C++標準ライブラリのintro sortを利⽤– quick sortの改良版で分割
統治⽅式
NAUTILUS

メモリアクセス

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

時間

15

shuffleにおけるキャッシュの効率的な利⽤(2/2)
n マージ処理は、個々のソート済み領域にシーケンシャルアクセス– キャッシュプリフェッチが活きて効率が良い– 個々のソート済み領域には、別ソケット上のメモリもあるため、キャッシュの活⽤は重要

NAUTILUS

A4...

A1...

A5...

A2...

A9...

A6...

...

...

...

...

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

A1...

A2...

A4...

A5...

A6...

...

...

16

shuffleはなぜsortベースかn hash mapによる分割・マージも可能
n しかしhash mapを現代的HW上で⼤規模データに使⽤すると性能が芳しくない実験結果を複数観察している
n 例︓集約処理を含むshuffleの⽐較(sortベース vs hash mapベース)

NAUTILUS

shuffle+aggregateduration(sec)– 10億レコード– 100パーティション– hash mapはhopscotchを使⽤

400
300

9.9 倍⾼速200
1000

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

sort-based

map-based
17その他
他にも⾼性能処理のために様々な機能を検討中
n shuffleだけに頼らないためのbroadcastによるjoinの仕組み
n shuffle処理の並列化やマルチノードで分散処理
n ⼀連の関係演算⼦群をLLVM等の現代的なコンパイラ機構を⽤いてコード⽣成
n 複数SQLの処理へ適切にリソース配分を⾏う
並列スケジューリング
n ストアドプロシージャの実⾏基盤としても利⽤予定
NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

18

まとめ
n Tsurugiではメニーコア・⼤規模メモリ等の現代的なハードウェアを効率的に活⽤し、SQL処理を⾼速並列化するための実⾏エンジンを開発中
です

NAUTILUS

Copyright © 2020 Nautilus Technologies, Inc. All rights reserved.

19