こんにちは！アルダグラムでエンジニアをしている森下霞です
ancestry は、Rails アプリケーションで階層データを簡単に管理するためのジェムです。このジェムを使用することで、ツリー構造を持つデータを1つのデータベースカラムを使って表現できます。
ancestry を使用し親子関係を持つデータを簡単に保存し、ルートノード、子ノード、ツリーなど、階層を取得することができるのに便利なメソッドが用意してあります。
ただ、データ量が増えて処理が複雑になるとデメリットもあります。本稿では、その解決アイデアを述べたいと思います。
テストデータ生成
まずは、例用テーブルを用意します。例で MySQL を使用します。
CREATE TABLE a_table_with_ancestry_relations (
id INT PRIMARY KEY NOT NULL AUTO_INCREMENT,
ancestry varchar(255) DEFAULT NULL
);
CREATE INDEX index_on_ancestry ON a_table_with_ancestry_relations (ancestry);
ActiveRecord モデルを作成し、６階層のツリーデータを生成します。
class ATableWithAncestryRelations < ApplicationRecord
-- ancestry を使用
has_ancestry
end
# root レコードになる1000件
ATableWithAncestryRelations.insert_all((1..1000).map { { ancestry: nil } })
# root レコードの子孫を５階層で追加
(0..4).each do |depth|
# 親案件になるレコードを取得
current_level_records =
ATableWithAncestryRelations.
where("COALESCE(1 + LENGTH(ancestry) - LENGTH(REPLACE(ancestry, '/', '')), 0) = ?", depth)
current_level_records.in_batches(of: 10_000) do |batch|
records_to_insert = []
batch.each do |parent_record|
if depth == 0
# 深さ0の子供は親のIDを参照するだけ
records_to_insert += (1..3).map { { ancestry: parent_record.id } }
else
# 深さ0以降のレベルは親の ancestry に追加される
new_ancestry = "#{parent_record.ancestry}/#{parent_record.id}"
records_to_insert += (1..3).map { { ancestry: new_ancestry } }
end
end
ATableWithAncestryRelations.insert_all(records_to_insert)
end
end
レコード数確認。深さは COALESCE(1 + LENGTH(ancestry) - LENGTH(REPLACE(ancestry, '/', '')), 0) で計算できます。
mysql> SELECT COUNT(*) FROM a_table_with_ancestry_relations;
+----------+
| count(*) |
+----------+
| 364000 |
+----------+
mysql> SELECT COALESCE(1 + LENGTH(ancestry) - LENGTH(REPLACE(ancestry, '/', '')), 0),
COUNT(*)
FROM a_table_with_ancestry_relations
GROUP BY COALESCE(1 + LENGTH(ancestry) - LENGTH(REPLACE(ancestry, '/', '')), 0);
+------------------------------------------------------------------------+----------+
| COALESCE(1 + LENGTH(ancestry) - LENGTH(REPLACE(ancestry, '/', '')), 0) | COUNT(*) |
+------------------------------------------------------------------------+----------+
| 0 | 1000 |
| 1 | 3000 |
| 2 | 9000 |
| 3 | 27000 |
| 4 | 81000 |
| 5 | 243000 |
+------------------------------------------------------------------------+----------+
リレーションも用意します。
CREATE TABLE attributes_for_ancestry_relations (
id INT PRIMARY KEY NOT NULL AUTO_INCREMENT,
name VARCHAR(255) NOT NULL,
ancestry_relation_id INT,
FOREIGN KEY (ancestry_relation_id) REFERENCES a_table_with_ancestry_relations(id) ON DELETE CASCADE
);
-- 各 ancestry レコードに一つのレコードを作成
INSERT INTO attributes_for_ancestry_relations (name, ancestry_relation_id)
SELECT
-- ランダムな文字列。例：ce07a965e6
SUBSTRING(MD5(RAND()), 1, 10),
id
FROM a_table_with_ancestry_relations;
モデル定義。
class AttributesForAncestryRelations < ApplicationRecord
end
# 前作った ATableWithAncestryRelations にリレーションを追加
class ATableWithAncestryRelations < ApplicationRecord
has_ancestry
has_one :attributes_for_ancestry_relation,
class_name: 'AttributesForAncestryRelations',
foreign_key: 'ancestry_relation_id'
end
ancestry メソッドのパフォーマンス
ancestry のデメリットを示す2つの遅いまたはメモリ上に重いケースを紹介します。
レコードリストで has_children? メソッド
リストで各行ごとに子レコードの有無を表したい時に、has_children? メソッドが使えます。そのパフォーマンスは以下になります。
# 一番最後に追加された100件の root レコードリスト
time = Benchmark.realtime do
ATableWithAncestryRelations.
where(ancestry: nil).
order(id: :desc).
limit(100).
each { |record| p record.has_children? }
end
0.10920141699898522
メモリ消費。
report = MemoryProfiler.report {
ATableWithAncestryRelations.
where(ancestry: nil).
order(id: :desc).
limit(100).
each { |record| p record.has_children? }
}
report.pretty_print(detailed_report: false)
Total allocated: 1867296 bytes (19397 objects)
Total retained: 13422 bytes (130 objects)
以下のようなクエリが100回に実行されます。
ATableWithAncestryRelations Exists? (0.5ms) SELECT 1 AS one
FROM `a_table_with_ancestry_relations`
WHERE `a_table_with_ancestry_relations`.`ancestry` = '5596884'
LIMIT 1
実行時間は長くないが、N+1 が起こるのでメモリ消費が結構あります。
リレーションで検索
ancestry レコードリストのツリーで名前で検索を実施します。ancestry の subtree メソッドはスコープではないので、以下のようにまず全部のツリーを取得し、そのあと名前で検索します。
time = Benchmark.realtime do
relation_ids = ATableWithAncestryRelations.
where(ancestry: nil).
order(id: :desc).
limit(100).
flat_map(&:subtree_ids)
names = AttributesForAncestryRelations.
where(ancestry_relation_id: relation_ids).
where("attributes_for_ancestry_relations.name LIKE 'c%'")
p names
end
1.8685909179912414
report = MemoryProfiler.report {
relation_ids = ATableWithAncestryRelations.
where(ancestry: nil).
order(id: :desc).
limit(100).
flat_map(&:subtree_ids)
names = AttributesForAncestryRelations.
where(ancestry_relation_id: relation_ids).
where("attributes_for_ancestry_relations.name LIKE 'c%'")
p names
}
report.pretty_print(detailed_report: false)
Total allocated: 9554351 bytes (97319 objects)
Total retained: 301452 bytes (88 objects)
以下のクエリが100回に実行されます。
ATableWithAncestryRelations Load (9.5ms) SELECT `a_table_with_ancestry_relations`.*
FROM `a_table_with_ancestry_relations`
WHERE ((`a_table_with_ancestry_relations`.`ancestry` LIKE '5596968/%'
OR `a_table_with_ancestry_relations`.`ancestry` = '5596968')
OR `a_table_with_ancestry_relations`.`id` = 5596968)
名前の取得は以下のクエリで行われます。
SELECT `attributes_for_ancestry_relations`.*
FROM `attributes_for_ancestry_relations`
WHERE `attributes_for_ancestry_relations`.`ancestry_relation_id` IN (
5599966,
5599967,
5599968,
....
-- 合計36400のIDリスト
);
データベース内で処理が行えないので、ruby に多量なデータを取得し、IN句にIDを大量に入れます。IN句が多いクエリは遅くなりやすいので、仕様は推奨されません。
参考：https://zenn.dev/nasu/articles/410bdb9739cd35
ancestry メソッドの改善
N+1 の解消
まず、#has_children? の N+1 をなくす方法を考えましょう。
一般的に、N+1 をなくすのに eager loading が使われます。
参考：https://guides.rubyonrails.org/active_record_querying.html#n-1-queries-problem
ただ、ancestry で eager loading が用意してありません。この課題は2011年から指摘されているものの、現在も解決されていません。
そうしたら、自分で eager loading を作ってみましょう。すぐ結論出しますが、ATableWithAncestryRelations モデルに以下のクエリを用意します。このコードで ancestry の #has_children? の代わりにクエリ結果に has_children 属性を追加します。
children_query = ATableWithAncestryRelations.from('a_table_with_ancestry_relations AS children').where(
<<~SQL.squish,
children.ancestry =
CASE
WHEN a_table_with_ancestry_relations.ancestry IS NULL
THEN CAST(a_table_with_ancestry_relations.id AS CHAR)
ELSE CONCAT(a_table_with_ancestry_relations.ancestry, '/', a_table_with_ancestry_relations.id)
END
SQL
)
result = ATableWithAncestryRelations.
where(ancestry: nil).
order(id: :desc).
limit(100).
select("a_table_with_ancestry_relations.*, (#{children_query.arel.exists.to_sql}) AS has_children")
時間。
time = Benchmark.realtime do
result.each { |record| p record.has_children }
end
0.0716110409994144
メモリ。
report = MemoryProfiler.report {
result.each { |record| p record.has_children }
}
report.pretty_print(detailed_report: false)
Total allocated: 152305 bytes (1741 objects)
Total retained: 2334 bytes (10 objects)
時間は通常のメソッドより1.5倍早く、メモリ消費はおよそ12倍に軽くなりました。😌
subtree で JOIN
リレーションで検索の際に、関連のテーブルを JOIN できれば ruby の処理やメモリ使いが軽くなるので、JOIN 方法を検討してみました。
まずは、このクエリができました。
time = Benchmark.realtime do
# ここで他の条件でレコードが絞ると想定して、例のためただ100レコードをサンプルしました
ids = ATableWithAncestryRelations.
where(ancestry: nil).
order(id: :desc).
limit(100).
pluck(:id)
joins_sql = <<-SQL.squish
INNER JOIN a_table_with_ancestry_relations AS children ON (
children.ancestry = CASE
WHEN a_table_with_ancestry_relations.ancestry IS NULL
THEN CAST(a_table_with_ancestry_relations.id AS CHAR)
ELSE
CONCAT(a_table_with_ancestry_relations.ancestry, '/', a_table_with_ancestry_relations.id)
END
)
SQL
# Build the query using ActiveRecord
result = ATableWithAncestryRelations.
joins(Arel.sql(joins_sql)).
joins(:attributes_for_ancestry_relation).
where(id: ids).
where('attributes_for_ancestry_relations.name LIKE ?', 'c%')
p result
end
0.05521804100135341
メモリ確認。
report = MemoryProfiler.report {
# ここは上記のコード
}
report.pretty_print(detailed_report: false)
Total allocated: 83131 bytes (898 objects)
Total retained: 1908 bytes (13 objects)
実行されたクエリ。
ATableWithAncestryRelations Load (11.5ms)
SELECT `a_table_with_ancestry_relations`.*
FROM `a_table_with_ancestry_relations`
INNER JOIN a_table_with_ancestry_relations AS children ON (
children.ancestry = CASE
WHEN a_table_with_ancestry_relations.ancestry IS NULL THEN CAST(a_table_with_ancestry_relations.id AS CHAR)
ELSE CONCAT(a_table_with_ancestry_relations.ancestry, '/', a_table_with_ancestry_relations.id)
END)
INNER JOIN attributes_for_ancestry_relations AS a ON a.ancestry_relation_id = children.id
WHERE
-- 本来、ここで他の絞る条件
`a_table_with_ancestry_relations`.`id` IN (5596968, 5596967, 5596966, 5596965, 5596964, 5596963, 5596962, 5596961, 5596960, 5596959, 5596958, 5596957, 5596956, 5596955, 5596954, 5596953, 5596952, 5596951, 5596950, 5596949, 5596948, 5596947, 5596946, 5596945, 5596944, 5596943, 5596942, 5596941, 5596940, 5596939, 5596938, 5596937, 5596936, 5596935, 5596934, 5596933, 5596932, 5596931, 5596930, 5596929, 5596928, 5596927, 5596926, 5596925, 5596924, 5596923, 5596922, 5596921, 5596920, 5596919, 5596918, 5596917, 5596916, 5596915, 5596914, 5596913, 5596912, 5596911, 5596910, 5596909, 5596908, 5596907, 5596906, 5596905, 5596904, 5596903, 5596902, 5596901, 5596900, 5596899, 5596898, 5596897, 5596896, 5596895, 5596894, 5596893, 5596892, 5596891, 5596890, 5596889, 5596888, 5596887, 5596886, 5596885, 5596884, 5596883, 5596882, 5596881, 5596880, 5596879, 5596878, 5596877, 5596876, 5596875, 5596874, 5596873, 5596872, 5596871, 5596870, 5596869)
-- 関連テーブルの条件
AND (a.name LIKE 'c%')
以下のようにスコープも定義できます。
class ATableWithAncestryRelations < ApplicationRecord
has_ancestry
has_one :attributes_for_ancestry_relation,
class_name: 'AttributesForAncestryRelations',
foreign_key: 'ancestry_relation_id'
scope :with_subtree, -> {
joins(
<<-SQL.squish
INNER JOIN a_table_with_ancestry_relations AS children ON (
children.ancestry = CASE
WHEN a_table_with_ancestry_relations.ancestry IS NULL
THEN CAST(a_table_with_ancestry_relations.id AS CHAR)
ELSE CONCAT(a_table_with_ancestry_relations.ancestry, '/', a_table_with_ancestry_relations.id)
END
)
SQL
)
}
end
スコープを使用します。
time = Benchmark.realtime do
# ここで他の条件でレコードが絞ると想定して、例のためただ100レコードをサンプルしました
ids = ATableWithAncestryRelations.
where(ancestry: nil).
order(id: :desc).
limit(100).
pluck(:id)
result = ATableWithAncestryRelations.
with_subtree.
joins(:attributes_for_ancestry_relation).
where(id: ids).
where('attributes_for_ancestry_relations.name LIKE ?', 'c%')
p result
end
0.04731141700176522
総括
ancestry ジェムでまだ上がっている eager loading 課題に対していくつかアイデアを述べました。どなたかに役に立てばととても幸いです。
また、ツリー構造のライブラリを選定する時にもご参考になればと思います。
もっとアルダグラムエンジニア組織を知りたい人、ぜひ下記の情報をチェックしてみてください！
株式会社アルダグラムのTech Blogです。 世界中のノンデスクワーク業界における現場の生産性アップを実現する現場DXサービス「KANNA」を開発しています。 採用情報はこちら herp.careers/v1/aldagram0508/
Discussion