プライマリーキー(primary key)はシーケンシャルな値で良いと思うよ

を読んでの感想です。「シーケンスナンバーをPKにする」以外の項目については言及しませんが、言及しないことは正当性や妥当性を保証していることにはならないです。

InnoDB(MySQL)を想定してます。が、原理は割と一般的なので他のDBでも適用できることが多いと思います。

追記:一般的とは分散でないような"普通の"RDBMSを想定してましたが、分散システム(distributed systemないしreplicated system)のような場合では話が違います。

なぜシーケンシャルな値がよいか

端的にいうと書き込み操作時にバッファープール(baffuer pool)に読み混む必要のあるページが少なくて済むからです。その結果書き込み操作時にバッファープールにページが存在する可能性が高くレイテンシー的に有利になる可能性が高いです。

バッファープール、ページ、btreeなど具体的にイメージできない人にとっては難しいとは思いますが、軽く説明しておきます。多くのRDBMSはディスクIOの遅さをカバーするため直接ファイルを読み書きするわけではなく、必ずバッファープールに読み出してから操作を行います。これはwrite時もread時も同じです。ページというのはざっくり言ってバッファープールに読み混む単位であり、btreeのノードもページ上で表現されています。だからバッファープール上にページが存在しない場合、一旦ディスクから読み混まなくてはならないため操作に時間がかかるようになります*1。

InnoDBではレコードはプライマリーキーをキーとしてbtreeを構築してますので、ざっくり言ってinsert=btree上のノードを辿って適切なページにデータをおくということです。

バッファープールはメモリ上に構築されています。メモリはディスクに比べたら容量は少ないので、すべてのページをバッファープールに載せることはいずれ難しくなります。こうなるとバッファープール上に読み混まれたページは何かしらのポリシーによって入れ換えが行われ、不要なページはバッファープール上から追い出され必要なページが読み込まれます。InnoDBの場合はそのポリシーはLRU(の亜種)です。重要なことはbtree全部をバッファープールに乗せられない場合使用頻度の高いページはバッファープールに載っている可能性が高く、使用頻度が低いページは追い出されている可能性が高いということです。時間的局所性(temporal locality)といわれる性質です。

以上を踏まえてシーケンシャルな値かランダムな値どちらが良いかを考えると、ランダムな値の場合ランダムですので原理的にすべてのノードがバッファープール上に必要になります。すべてのページの使用頻度が同じくらいなので局所性がない状態です。どのページも同じ確率でバッファープールから追い出されていきます。すると書き込みの際、必要なページの内のどれかはバッファープールにない状態が普通になりますから、ディスクとのIOが必要になる可能性が高いのでレイテンシ的に不利になります。

シーケンシャルな値の場合は書き込みに必要なノードは1経路のみですから全体をバッファプール上に保持しておく必要はなく、ページがバッファープール上に存在することが大いに期待できます。書き込みと同時にページ全体(に近い範囲)を読み混むようなselect文が走っている環境であっても置き換えポリシーはLRUですので定期的な書き込みがあればバッファープールにのっていることが期待できます。

ページのラッチ(latch)

ページへの操作は競合状態を避けるためラッチ処理が行われます。同時実行制御です。InnoDBの場合MTR(mini transaction)という名前になっています*2。ですから1ページに複数の書き込み操作を同時に行う場合は実質的に1つずつしか実行されないので、異なる複数のページに書き込みを行い同時に実行できる場合と比べて確かに遅くなります。

話はそれますが結構一般的な問題ではあることから各RDBMS最適化の実装が入っています。

つまり局所的には件の記事に書かれている説明は正しいですが、実際的にはバッファープールが載っているかどうかの方が支配的であるため一見正しそうに見えて多くの場合ではバッファープールの事情を優先した方がパフォーマンス的には有利になるでしょう。

場合による

(自分の経験した)典型的なユースケースの場合、シーケンシャルな値の方が良いと思ってますが、すべては場合によります。「ページのラッチの差が重要である」かつ「データ量は多くないのでバッファープールにページがのりきる」という場面もありえないわけでもないです。そういうユースケースやテーブル設計は想像できますし想像できると言うことはありうるということでしょう*3。またアプリケーションの事情は常に正*4だと思っているので、アプリケーションの事情でプライマリーキーを選択しなければならない場合もあるかと思います。特に歴史的経緯があるならばなおさらです。遅いことがプロダクトの価値を毀損していないのであれば、DB的には正しくなくても周りとの一貫性を優先した方がプロダクト全体に良い影響があることはざらにあります。

べき集べからず集というのは「もっとも効果的にテクノロジーを使うために知らなければならない全体の20%」*5だと思っているので、べき集べからず集に対してアーキテクチャを説明して「議論は単純化はできない、場合による」と言ったところで求められているものとは違うわけで、あんまり効果的ではないと思っています。なので本心では「場合による」が正しいと思ってますが、あえて言い切るのであれば、「プライマリーキーはシーケンシャルな値を使え」です。