SAP HANA でツリー構造のデータを扱いたかった話

# はじめに
SAP HANA でツリー構造のデータを取り扱いたかったので少し調べてみました。

# 一般的な持ち方
一般的に、RDBMSでツリー構造を表現する場合は２つの方法があり、
２つの方法としては、`隣接リスト` か、`サブセット` があります。

## 隣接リスト
隣接リストでは、親ノード情報を参照するために必要な情報を保持して階層構造を再現します。
おそらくツリー構造を再現したいとなった場合に最初に考える方法で
テーブル設計としては以下のような構造になります。

| node_id | parent_node_id | name |
|------:|------------------:|:------------------:|
| 1 | NULL | 親 |
| 2 | 1 | 子１ |
| 3 | 1 | 子２ |
| 4 | 1 | 子3 |
| 5 | 2 | 孫1-1 |
| 6 | 2 | 孫1-2 |
| 7 | 3 | 孫2-1 |
| 8 | 3 | 孫2-2 |
| 9 | 4 | 孫3-1 |

### メリット
- 直感的なデータ構造
- 追加削除が容易

### デメリット
- 階層データを取得する場合には、再帰的な取得が必要でSQLが複雑 または 単発のSQLでは取得できない


## サブセット

階層構造を範囲で指定します。
親要素が一番大きく、子、孫はそれぞれの範囲の中に含まれているような表し方です。

<img width="1029" alt="スクリーンショット 2020-05-31 22.02.15.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/303235/a1b5dff7-739b-acb8-6338-4b1dd73b8ce2.png">


テーブル設計としては以下のような構造になります。

| node_id | first_node | last_node |name |
|------:|------------------:|------------------:|:------------------:|
| 1 | 1 | 9 | 親 |
| 2 | 2 | 4 | 子１ |
| 3 | 3 | 3 | 孫1-1 |
| 4 | 4 | 4 | 孫1-2 |
| 5 | 5 | 7 | 子２ |
| 6 | 6 | 6 | 孫2-1 |
| 7 | 7 | 7 | 孫2-2 |
| 8 | 8 | 9 | 子3 |
| 9 | 9 | 9 | 孫3-1 |


### メリット
- 階層構造取得するために、必ずしも再起的な取得が必要ではない
- 指定した要素配下を一度に取得できる

### デメリット
- 順番に並んでいることが前提なため、要素の追加・削除に弱い

# SAP HANAではどうなるの？
SAP HANA では、 `HIERARCHY Function` というSQL Functionが実装されており
隣接リスト 構造で階層構造を保持していても、再帰的なアプローチなしにデータ取得できる仕組みが準備されています。

以下のような隣接リストでデータを構築していた場合を例に`HIERARCHY Function` を紹介したいと思います。

## `HIERARCHY Function` を使用したサンプル
### データ
| parent | id | type | order | amount |
|------:|------:|------:|------:|------:|
| null | A1 | a | 1 | 50 |
| A1 | B1 | b | 1 | 120 |
| A1 | B2 | c | 2 | 90 |
| B1 | C1 | a | 1 | 40 |
| B1 | C2 | b | 2 | 60 |
| B2 | C3 | c | 3 | 75 |
| B2 | C4 | a | 4 | 30 |
| C3 | D1 | b | 1 | 10 |
| C3 | D2 | c | 2 | 25 |
| C4 | D3 | a | 3 | 30 |
| null | A2 | b | 2 | 80 |
| A2 | B3 | c | 3 | 45 |
| A2 | C4 | a | 4 | 30 |


### `HIERARCHY Function` を使用したSQL

```SQL
SELECT hierarchy_rank AS rank,  
    hierarchy_tree_size AS tree_size,
    hierarchy_parent_rank AS parent_rank,
    hierarchy_level AS level,
    hierarchy_is_cycle AS is_cycle,
    hierarchy_is_orphan AS is_orphan,
    node_id,
    parent_id,
    type 
 FROM HIERARCHY ( 
 SOURCE ( SELECT id AS node_id, parent AS parent_id, type
             FROM t_demo
             ORDER BY order )
 CACHE FORCE )
 ORDER BY hierarchy_rank;
```

### 取得結果
| RANK | TREE_SIZE | PARENT_RANK | LEVEL | IS_CYCLE | IS_ORPHAN | NODE_ID | PARENT_ID | TYPE |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | 10 | 0 | 1 | 0 | 0 | A1 | ? | a |
| 2 | 3 | 1 | 2 | 0 | 0 | B1 | A1 | b |
| 3 | 1 | 2 | 3 | 0 | 0 | C1 | B1 | a |
| 4 | 1 | 2 | 3 | 0 | 0 | C2 | B1 | b |
| 5 | 6 | 1 | 2 | 0 | 0 | B2 | A1 | c |
| 6 | 3 | 5 | 3 | 0 | 0 | C3 | B2 | c |
| 7 | 1 | 6 | 4 | 0 | 0 | D1 | C3 | b |
| 8 | 1 | 6 | 4 | 0 | 0 | D2 | C3 | c |
| 9 | 2 | 5 | 3 | 0 | 0 | C4 | B2 | a |
| 10 | 1 | 9 | 4 | 0 | 0 | D3 | C4 | a |
| 11 | 4 | 0 | 1 | 0 | 0 | A2 | ? | b |
| 12 | 1 | 11 | 2 | 0 | 0 | B3 | A2 | c |
| 13 | 2 | 11 | 2 | 0 | 0 | C4 | A2 | a |
| 14 | 1 | 13 | 3 | 0 | 0 | D3 | C4 | a |

## 使い方
### 構造データの参照範囲
```SQL
 SOURCE ( SELECT id AS node_id, parent AS parent_id, type
             FROM t_demo
             ORDER BY order )
```
SQL の SOURCE 部分で指定します。
データ取得時には条件があり、自分自身のノードIDを `node_id`、親要素のノードIDを `parent_id` として名前をつけて取得する必要があります。

### HIERARCHY Function を使用したときに取得可能になる値
HIERARCHY Function を使用すると以下の要素が取得可能になり、
取得した要素を組み合わせることで階層情報となります。

| 取得可能な値 | 意味 |
|---|---|
| hierarchy_rank        | 連続した要素番号 |
| hierarchy_tree_size   | 自身の配下に存在する子要素数 |
| hierarchy_parent_rank | 親要素の要素番号 |
| hierarchy_level       | 自身が何回層目に所属しているか |
| hierarchy_is_cycle    | 循環しているか |
| hierarchy_is_orphan   | 孤立しているか |

# 最後に
SAP HANA では、ツリー構造を扱いたい場合には `隣接リスト`を前提に設計すれば良くなります。
HIERARCHY Function には、他にも種類があるので、興味を持たれた方は リファレンスをご参照ください。

## 引用先
[SAP HANA SQL and System Views Reference](https://help.sap.com/viewer/4fe29514fd584807ac9f2a04f6754767/2.0.02/en-US/fc59f81a5c494f399cc2ff70b9c3b4c9.html)