Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
DBのindex(B-tree周り) に触れてみよう
Search
NearMeの技術発表資料です
PRO
May 21, 2024
Programming
0
40
DBのindex(B-tree周り) に触れてみよう
indexに関するイントロダクションです。今回は詳細については触れていませんが、B-treeを例に、indexとはどのようなものかについて触れています。
NearMeの技術発表資料です
PRO
May 21, 2024
Tweet
Share
More Decks by NearMeの技術発表資料です
See All by NearMeの技術発表資料です
Architecture Decision Record (ADR)
nearme_tech
PRO
0
8
遺伝的アルゴリズムを実装する
nearme_tech
PRO
1
15
Fractional Derivative!
nearme_tech
PRO
1
14
GitHub Projectsにおける チケットの ステータス更新自動化について
nearme_tech
PRO
1
25
2つの曲線を比較する方法ってあるの? 〜フレシェ距離を試してみた〜 with Python
nearme_tech
PRO
1
97
Constrained K-means Clustering (クラスタサイズの制限をしたK-means法) を調べてみた
nearme_tech
PRO
1
41
VRPの近傍操作SWAP*について調べてみた
nearme_tech
PRO
1
75
新人エンジニアが読んでためになった本
nearme_tech
PRO
2
37
Object–relational mapping and query builder battle 1: Intro to Prisma
nearme_tech
PRO
1
44
Other Decks in Programming
See All in Programming
iOSの隠されたAPIを解明し、開発効率を向上させる方法/iOSDC24
noppefoxwolf
2
120
ウォンテッドリーにおけるモバイルアプリ開発 / iOSDC Japan 2024 Sponsor Session
kubode
0
220
【TID2024】模擬講義:プログラマと一緒にゲームをデザインしてみよう!
akatsukigames_tech
0
380
What we keep in mind when migrating from Serverless Framework to AWS CDK and AWS SAM
kasacchiful
1
130
Amebaチョイス立ち上げの裏側 ~依存システムとの闘い~
daichi_igarashi
0
220
Polars を Kaggle コンペで使ってみた(LMSYS Chatbot Arena)
kohecchi
1
360
1人で挑むSwiftコンパイラ 〜型システム入門編〜
s_shimotori
0
310
仮想ファイルシステムを導入して開発環境のストレージ課題を解消する
segadevtech
2
390
長期運用プロダクトの開発速度を維持し続けるためのリファクタリング実践例
wataruss
8
2.5k
健康第一!MetricKitで始めるアプリの健康診断 / App Health Checkups Starting with MetricKit
nekowen
4
790
Mergeable Libraryで 高速なアプリ起動を実現しよう!
giginet
PRO
1
1.8k
Modular Monolith Go Server with GraphQL Federation + gRPC
110y
1
550
Featured
See All Featured
Testing 201, or: Great Expectations
jmmastey
35
6.9k
Faster Mobile Websites
deanohume
304
30k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
27
8.9k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
27
1.6k
For a Future-Friendly Web
brad_frost
173
9.3k
[RailsConf 2023] Rails as a piece of cake
palkan
44
4.6k
GitHub's CSS Performance
jonrohan
1029
450k
A better future with KSS
kneath
235
17k
Why Our Code Smells
bkeepers
PRO
333
56k
GraphQLとの向き合い方2022年版
quramy
43
13k
The Straight Up "How To Draw Better" Workshop
denniskardys
230
130k
Robots, Beer and Maslow
schacon
PRO
157
8.1k
Transcript
0 DBのindex(B-tree周り) に触れてみよう 2024-05-17 第90回NearMe技術勉強会 Kaito Asahi
1 indexに関して • indexの役割について ◦ クエリの高速化 ◦ 検索の最適化 ◦ ソートの高速化
◦ ユニーク性の保証 …
2 indexに関して • indexの役割について ◦ クエリの高速化 ◦ 検索の最適化 ◦ ソートの高速化
◦ ユニーク性の保証 … どういう仕組みなんだ...?
3 ☕少し脱線 〜SQLは⾮⼿続き型の⾔語〜 • SQLの命令の例 SELECT name, age FROM users
WHERE age >= 20; → 何が欲しいのかを命令するSQL文 → どのようにとってきて欲しいのかは命令していない!!(非手続き型) ∴ 効率の良い DB設計が求められる 💨👍 • どこにどのような 情報があるのか?(インデックス ) • どのように データを取ることが最適か?(統計情報)
4 indexの種類について(MySQL) • B-tree ◦ 最も一般的 なインデックスタイプ ◦ 等価検索および範囲検索に有効 •
HASH ◦ メモリーベースのストレージエンジン で使用される ◦ 等価検索に有効 • FULLTEXT ◦ テキスト検索用 に最適化されている • SPATIAL ◦ 地理データなどの空間的なデータ に最適化されている
5 indexの種類について(MySQL) • B-tree(今日はこれを中心) ◦ 最も一般的 なインデックスタイプ ◦ 等価検索および範囲検索に有効 •
HASH ◦ メモリーベースのストレージエンジン で使用される ◦ 等価検索に有効 • FULLTEXT ◦ テキスト検索用 に最適化されている • SPATIAL ◦ 地理データなどの空間的なデータ に最適化されている
6 ハンズオン(まずは触れてみる) • B-tree 1. MySQLのDocker imageをpullする $ docker pull
mysql 2. コンテナを起動する(rootアカウントのパスワード:root) $ docker run --name test-mysql -e MYSQL_ROOT_PASSWORD=root -d mysql:latest
7 ハンズオン(まずは触れてみる) • B-tree 3. スライド33枚目にあるPythonファイルで、sqlファイルを取得し、これをローカルからコンテナ 内に入 れる $ docker
cp employees_data.sql test-mysql:/ 4. コンテナに入る $ docker exec -it test-mysql sh
8 ハンズオン(まずは触れてみる) • B-tree 5. mysqlにログインする(パスワード:root) sh-5.1# mysql -u root
-p 6. DBを作成する(ここでは、test_db) mysql> CREATE DATABASE test_db; mysql> USE test_db; 7. employeesテーブルを作成する mysql> CREATE TABLE employees ( id INT AUTO_INCREMENT PRIMARY KEY, name VARCHAR(50), department VARCHAR(50), salary INT );
9 ハンズオン(まずは触れてみる) • B-tree 8. 一旦ログアウト(exit)し、10万レコードのデータを挿入する sh-5.1# mysql -u root
-p test_db < employees_data.sql 9. もう一度ログインし、id <= 100の範囲でデータをとってみる mysql> USE test_db; mysql> SELECT * FROM employees WHERE id <= 100 ORDER BY id;
10 ハンズオン(まずは触れてみる) • B-tree(コスト⽐較する) A. インデックスを適⽤していないとき mysql> EXPLAIN SELECT *
FROM employees WHERE department = 'Engineering'; +----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | 1 | SIMPLE | employees | NULL | ALL | NULL | NULL | NULL | NULL | 99904 | 10.00 | Using where | +----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+ 1 row in set, 1 warning (0.00 sec)
11 ハンズオン(まずは触れてみる) • B-tree(コスト⽐較する) B. インデックスを適⽤するとき mysql> CREATE INDEX idx_department
ON employees(department); +----+-------------+-----------+------------+------+----------------+----------------+---------+-------+-------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-----------+------------+------+----------------+----------------+---------+-------+-------+----------+-------+ | 1 | SIMPLE | employees | NULL | ref | idx_department | idx_department | 203 | const | 40024 | 100.00 | NULL | +----+-------------+-----------+------------+------+----------------+----------------+---------+-------+-------+----------+-------+ 1 row in set, 1 warning (0.01 sec) mysql> EXPLAIN SELECT * FROM employees WHERE department = 'Engineering';
12 ハンズオン(まずは触れてみる) • B-tree(コスト⽐較する) ⾒⽐べると... +----+-------------+-----------+------------+------+----------------+----------------+---------+-------+-------+----------+-------+ | id | select_type
| table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-----------+------------+------+----------------+----------------+---------+-------+-------+----------+-------+ | 1 | SIMPLE | employees | NULL | ref | idx_department | idx_department | 203 | const | 40024 | 100.00 | NULL | +----+-------------+-----------+------------+------+----------------+----------------+---------+-------+-------+----------+-------+ 1 row in set, 1 warning (0.01 sec) +----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+ | 1 | SIMPLE | employees | NULL | ALL | NULL | NULL | NULL | NULL | 99904 | 10.00 | Using where | +----+-------------+-----------+------------+------+---------------+------+---------+------+-------+----------+-------------+ 1 row in set, 1 warning (0.00 sec) 処理する行数の推定値は 半減以下 インデックスが適用 されている
13
14 B-treeインデックスの仕組み • B-tree ◦ ノードの高さが同じになるような木構造をもつ → 平衡木
◦ 検索、挿入、更新、削除には O(logn) の計算量 ◦ index対象の列はソートされた状態 9 15 4 12 19 2 3 6 8 15 19 ルートノード 中間ノード 葉ノード
15 B-treeインデックスの仕組み • B-tree ◦ ノードの高さが同じになるような木構造をもつ → 平衡木
◦ 検索、挿入、更新、削除には O(logn) の計算量 ◦ index対象の列はソートされた状態 ◦ 等価検索に有効 Ex) 6を検索:9 → 12 → 6を辿れば良い 9 15 4 12 19 2 3 6 8 15 19 ルートノード 中間ノード 葉ノード
16 B-treeインデックスの仕組み • B-tree ◦ ノードの高さが同じになるような木構造をもつ → 平衡木
◦ 検索、挿入、更新、削除には O(logn) の計算量 ◦ index対象の列はソートされた状態 ◦ 等価検索に有効 Ex) 6を検索:9 → 12 → 6を辿れば良い 9 15 4 12 19 2 3 6 8 15 19 ルートノード 中間ノード 葉ノード 各ノードで t 個に分岐されるのであれば、探索範囲は 1/t となるので
17 B-treeインデックスの仕組み • B-tree ◦ ノードの高さが同じになるような木構造をもつ → 平衡木
◦ 検索、挿入、更新、削除には O(logn) の計算量 ◦ index対象の列はソートされた状態 ◦ 等価検索に有効 ◦ 範囲検索に有効 Ex) 6以下の値の検索:9 → 12 → 6より左の値 9 15 4 12 19 2 3 6 8 15 19 ルートノード 中間ノード 葉ノード ソートのおかげ
18 B-treeインデックスの仕組み • B-tree ◦ ノードの高さが同じになるような木構造をもつ → 平衡木
◦ 検索、挿入、更新、削除には O(logn) の計算量 ◦ index対象の列はソートされた状態 ◦ 等価検索に有効 ◦ 範囲検索に有効 ▪ “!=”(否定)には効果を持たない → 左と右どちらに値があるのか不明... 9 15 4 12 19 2 3 6 8 15 19 ルートノード 中間ノード 葉ノード
19 indexは張れば張るほど良いのでは!!!
20 indexは張れば張るほど良いのでは!!!
21 B-treeインデックスを有効にするために • カーディナリティの高い ものに ◦ なるべく値の重複の少ない列に • 大きなテーブル に対して利用
• WHERE句などの選択条件 に使用されている列に
22 B-treeインデックスを有効にするために • カーディナリティの高い ものに ◦ なるべく値の重複の少ない列 に(バリエーションがより豊富な列) 1. カーディナリティが高いもの
a. ユーザーID b. メールアドレス c. シリアルナンバー 2. カーディナリティが低いもの a. 性別 b. 婚姻状況 c. 部署名
23 B-treeインデックスを有効にするために • 大きなテーブル に対して利用 データが n 個の場合... 1. 全検索には
O(n) だけ時間がかかる 2. B-treeインデックスでは、O(logn) だけ時間がかかる → 小さい n では、nとlognにあまり差はない → より大きい n に対しては、 B-treeインデックスはとても有効!!
24 B-treeインデックスを有効にするために • WHERE句などの選択条件 に使用されている列に → ソートされた id での条件(id <
100)→ 主キーであれば、基本的にB-treeが適用される ※ 比較が曖昧なものにはインデックスが有効にならない 1. 否定(<>, !=) 2. OR 3. IS NULL 4. 値に演算を行なっている(id * 3 < 100, SUBSTR(id, 1, 1) = …など)
25 indexに最適なカラムとはどのようなものか? ~IDについて~ • データの挿入 1. 連番やソート可能なindexをもつ場合 1,2,3,...,100 1,2,3,...,40 41,42,43,...80
81,82,83,...,100 1,...10 91,...100 ・・・ 新しい
26 indexに最適なカラムとはどのようなものか? ~IDについて~ • データの挿入 1. 連番やソート可能なindexをもつ場合 1,2,3,...,100 1,2,3,...,40 41,42,43,...80
81,82,83,...,100 1,...10 91,...100 ・・・ 新しい 新しいデータをどの葉ノードに入れるかの チェックは右端だけで済む
27 indexに最適なカラムとはどのようなものか? ~IDについて~ • データの挿入 1. 連番やソート可能なindexをもつ場合 1,2,3,...,100 1,2,3,...,40 41,42,43,...80
81,82,83,...,100 1,...10 91,...100 ・・・ 新しい 新しいデータをどの葉ノードに入れるかの チェックは右端だけで済む しかもキャッシュが あればもっと速い!! 最新のデータをバッファプールに おけばキャッシュヒット率は高くなる
28 indexに最適なカラムとはどのようなものか? ~IDについて~ • データの挿入 2. UUIDなどのランダムな場合 ・・・ 新しい
29 indexに最適なカラムとはどのようなものか? ~IDについて~ • データの挿入 2. UUIDなどのランダムな場合 ・・・ 新しい どこに入れるべきか不明なので、
入れる場所の探索にコストがかかる
30 indexに最適なカラムとはどのようなものか? ~IDについて~ • データの挿入 2. UUIDなどのランダムな場合 ・・・ 新しい どこに入れるべきか不明なので、
入れる場所の探索にコストがかかる キャッシュを利用 できる保証がない ... キャッシュにヒットするかは運ゲー 😇
31 補⾜スライド
32 今回利⽤したsqlファイルの⽣成⽅法 import random # 生成するデータの数 num_records = 100000 #
例として10万レコードを生成 departments = ['Engineering', 'HR', 'Marketing', 'Sales', 'Finance'] names = ['Alice', 'Bob', 'Charlie', 'David', 'Eve', 'Frank', 'Grace', 'Hannah', 'Ivan', 'Julia'] with open('employees_data.sql', 'w') as file: file.write("USE test_db;\n") # 使用するデータベース(test_db)を指定 file.write("INSERT INTO employees (name, department, salary) VALUES\n") # レコードを生成 for i in range(num_records): name = random.choice(names) department = random.choice(departments) salary = random.randint(30000, 120000) # 最後のレコード以外はカンマを付ける if i < num_records - 1: file.write(f"('{name}', '{department}', {salary}),\n") else: file.write(f"('{name}', '{department}', {salary});\n")
33 参考⽂献 • 達人に学ぶDB設計 徹底指南書 ~初級者で終わりたくないあなたへ ◦ https://www.shoeisha.co.jp/book/detail/9784798124704 • 計算量同士の比較と入力サイズによる比較
◦ https://algo-logic.info/complexity-compare/ • MySQLでプライマリキーをUUIDにする前に知っておいて欲しいこと ◦ https://techblog.raccoon.ne.jp/archives/1627262796.html • UUIDとULIDの違いと種類を解説【ULID=ソート可能なUUID?】 ◦ https://giginc.co.jp/blog/giglab/uuid-ulid • ソート可能なUUID互換のulidが便利そう ◦ https://qiita.com/kai_kou/items/b4ac2d316920e08ac75a • MySQLバッファプールについて ◦ https://dev.mysql.com/doc/refman/8.0/ja/innodb-buffer-pool.html • 参照の局所性 ◦ https://ja.wikipedia.org/wiki/%E5%8F%82%E7%85%A7%E3%81%AE%E5%B1%80%E6%89 %80%E6%80%A7
34 Thank you