ジェイウォーク（信号無視）
アンチパターン
カンマ区切り文字列でidを一つのカラムに格納する。
デメリット
- 特定のidを持つレコードだけを抽出する、のような本来簡単なクエリにまで正規表現が必要になる。仮に002というidに紐づけられているレコードを検索する際のWHERE句は1002などを避けるためにfig. 1のようになる
fig. 1
WHERE id ~* ANY(ARRAY['002,%', '%,002,%', '%,002']) OR id = '002';
- VARCHARのような上限のある型を用いてしまうと当然、紐づけられるid数に物理的な上限が生じる。
- idの編集の際に文字列の結合が必要になってしまう
- 区切り文字は決してidとして使われない文字にしなければならない
例外
- 格納されたそれぞれ個別のidを取り出すことはない場合
- カンマ区切りで結合されているというフォーマットに意味がある場合
解決策
- 交差テーブルを作成する
感想
基本的には多対多の関係を一対多で表現しようとすると発生しそう。
こんなこと普通はしないと思っていたが、例えば、投稿に複数のメディアを添付し、そのメディアを他の投稿にも添付できるといった仕様の場合には容易に発生するかもしれない。実際、TwitterのMediaLibraryとTweetComposer(カードを作るところ)におけるカードとメディアの関係はそうなっている。配列型を用いれば基本的な問題は回避できるはずだが、sqliteなどのそもそも配列型をサポートしていないRDSを使用する場合はすぐに手に取れる安直な選択肢になってしまいかねないと思った。
ナイーブな木（素朴な木）
アンチパターン
木構造を表現するために、親のidのみを参照するようにする
デメリット
- 木構造を木構造として扱いにくくなる(ex. ツリー全体の削除、ノードの順序を意識したツリーの構築etc)
例外
- 直近ノードとの関係性が重要な場合
解決策
経路列挙
そのノードまでのルートからのパスをカラムとして格納する。
ただし、パスの存在とノードの存在の整合性を担保できず、パスのメンテナンスはアプリケーション側に依存する。
また、ジェイウォークと同じ弱点を持つ
入れ子集合
全体を包含関係を持った集合として捉えてその両端点をカラムとして格納する
ノードの削除は簡単だが非ルートノードの挿入では、ツリーの再計算が必要になる。
入れ子モデルのよくできた絵
閉包テーブル
実体とは別に、木に上から水を垂らした場合に水滴がかかる可能性のあるノードとその始点となるノードを保存するPathテーブルを別に持って包含関係を表現する。ただ、一般的に木構造は根を上にして表現されるので、重力に逆らうことになる。
Pathテーブルはあくまで実体への参照なので、実体側のidを入れ替えれば要素の交換が容易。また、部分木の付け替えもその始点となるノード以下のPathと始点となるノードまでのPathを一旦削除し、新たに付け加えた部分を考慮して再計算すれば可能。
閉包テーブルのよくできた絵
RECURSIVE修飾子の利用
再帰的(ドキュメントに従えば反復的)クエリを実行する。
循環参照があった場合、クエリが返ってこなくなる。
安全のためにLIMITを張る場合、仕様とエラーの判断が難しくなる。
WITH RECURSIVE leaf_node(id, parent_node_id) AS (
-- 非再帰的表現（初期条件）
SELECT
leaf_node.id
,leaf_node.parent_node_id
FROM
target_table AS leaf_node
WHERE
id = {leaf_nodeのid} -- 検索の始点となるノードのid
UNION ALL
-- 再帰的表現
SELECT
t_parent.id
,t_parent.parent_node_id
FROM
target_table AS t_parent INNER JOIN leaf_node AS t_leaf ON
t_parent.id = t_leaf.parent_node_id
)
SELECT
id
,parent_node_id
FROM
leaf_node
;
感想
経路列挙は、idカラムにUUID型やBIGINT型など使用される文字に制限のある型を使用し、pathカラムにPostgreSQLのTEXTのような制限なし可変長文字列を使用すれば出来そうだが、非リーフノードの挿入/削除が面倒で致命的。
入れ子集合は、ツリーの高さと部分木の数に現実的な上限を設けて、端点として保存する値を整数ではなく小数にしてしまえば使えなくはなさそうだが、端点という物理的な値を比較するクエリは全体像を把握していないと理解が難しい。それに物理的な値で話をするのは好きではない。できるだけ論理的な値で考えたい。
閉包テーブルは部分木の付け替えやノード自体の入れ替えが容易という魅力はあるが、直近のノードの検索というあくまで直鎖だけを考えればいい場面でも木構造を意識させられるのが冗長に思えてならない。
RECURSIVE修飾子は中では最も実用的だと思った。ただ、何かのバグで生じる影響が無限ループとなってしまうとリスクが大きいようにも思える。単なるSELECTであっても、ロックを取らなければ他のクエリが実行できないという状況はあり得る。この場合の影響範囲は大きくなる。これを回避するためにLIMITを付けることになれば、やはり仕様が絡んでくる。
postgresqlにはJSON型やJSONB型が存在するので、木構造をそのままJSONとして保存してしまえばいいかもしれない。イメージは投稿に対するコメントにコメントがついたFacebookページ投稿をFacebookのGraphApiで取得した際のレスポンス。commentsというキーに紐づいたバリュー自体がJSONになっていて、その中にcommentsというキーが存在するという構造になっている。fig. 2はRubyでその構造を再現した際のコード。このままだと直鎖になる。あくまでイメージ。
ただ、この場合親子関係だけを簡単に抜き出せるようにするには隣接リストモデルとの併用になるが、これはパスという情報の二重管理以外の何物でもなくて、またRDSの恩恵も受けられず、データ不整合のリスクがつきまとう。Twitterのスレッド投稿には、ルートノードのステータスidをidとして持ったスレッドという概念が内部的に存在するようだが、どうやって実現しているのか気になる。
隣接リストモデルにRECURSIVE修飾子付きのクエリを使うのが現実的かと思う。
fig. 2
def make_comment_json(reply_flag: false)
{
id: make_post_fbid,
message: Faker::Lorem.sentence,
from: {
name: Faker::Name.name
},
created_time: Time.now,
like_count: random_int,
comments: if reply_flag
{
data: [
make_comment_json
]
}
end
}
end
プアマンズ・サーチエンジン（貧者のサーチエンジン）
アンチパターン
キーワード検索のためにLIKE述語のようなパターンマッチ述語を使用する
デメリット
- 一般的なインデックスの恩恵を受けられなくなり、テーブルスキャンを行うことになる
- 意図しない結果が返ってくることがある
例外
使用頻度の低いクエリなど、最適化にかかるコストのほうが大きい場合
解決策
TSVECTOR型等の適切なツールを用いる
感想
目的のキーワードを%で挟んでLIKE述語を使うのが一般的だと思っていたので目を引いた。
ただ、TSVECTOR型はそもそも分かち書きする言語向けの機能のようで、そのまま日本語には適用できなさそう。
PGroongaというPostgreSqlの拡張機能もあるが、そこまでしなければいけないようなパフォーマンスの問題が発生する、もしくは、しそうになるまでは%とLIKEでよさそう。