こんにちは、青山です。

> 柳町です。
> 私が、やりたいのは論理ソートです。
> 丁寧な説明ありがとうございました。

いや、たぶん勘違いされている、というか、
たぶん物理とか論理という言葉の意味の解釈そのものが
大きくずれていると思います。

# ＫＫ＠ＩＢさんの説明にも問題がいろいろあるような・・。


まず最初に、ハードディスクのアクセス方法についての理解が必要です。

ハードディスクを走査するには２つのアクセス方法があります。
・シーケンシャルアクセス
・ランダムアクセス

大量データを検索する場合、シーケンシャルアクセスでは
一回だけディスクを走査すればよいので、効率が良いです。

一方、ピンポイントでデータにアクセスしたい場合は、
シーケンシャルアクセスでデータを全件見ながらデータを探すのは
効率が悪いので、ランダムアクセスで直接データに一発で
アクセスする方が効率がよいです。
(そのため、データ格納方式は、キーを使うとすぐにデータの
 格納位置がわかるような仕組みになっています)

検索するデータ数がある程度多い場合では、ランダムアクセスは
逆に効率が悪くなり、シーケンシャルアクセスの方が効率が良くなります。
# これはまあ直感的にわかる話とは思いますが・・。

また、1個または数個のデータにアクセスしたい場合には常に
ランダムアクセスの方が効率がよいのかというと、必ずしもそうではなく、
行数に比べてキー値の種類が少ない列(=カーディナリティが低い列)
については、検索結果データの絶対数とディスク上の分布によって、
どちらの方法が速いのかが変わってきます。

---------------------

次に、データの格納方法についての理解が必要です。
詳細はここでは説明しませんが、Bツリー(B-Tree, B木)についての
知識が話の前提となるので調べてみてください。

まず、ディスクにデータを格納する場合の格納の仕方についてですが、
物理的にソートされた状態で格納されている方が何かと都合がよいわけです。
しかしデフォルトではデータをINSERT順のまま物理的に格納してしまうので、
それではあんまりうれしくありません。

そこで、例えばInnoDBの場合は、PRIMARY KEYを指定すると、それが
物理的な格納順を決めるキーとして使われ、データの挿入順に関わらず
データが格納された時点でPRIMARY KEYの順番に従ってなるべく物理的に
ソートされた状態となるように並べられます。
なお、ソートアルゴリズムとしてはRDBMSでは一般にBツリーもしくは
その改良版が使われます。

# 実際にはDBファイルのファイルシステム上でのフラグメント化や
# レコードの挿入や削除によるBツリーのリーフの組み替えによる
# 領域の取得や解放が発生するので、厳密に物理的に並べるのは
# 困難ですが、近似的に「ほぼ物理的に並んでいる」という考え方で
# 通常は大きな問題はないと思います。

例えばPRIMARY KEYを使ってデータを1件検索する場合は、
Bツリーを走査する動作を一度だけ行えばよいわけですから、
PRIMAEY KEYが最も高速に検索することができるキーである理由が
理解できると思います。

また、全件検索する場合でも、Bツリーのリーフを順に読めばそのまま
PRIMARY KEYの順になっているので、シーケンシャルアクセスをすれば
PRIMARY KEYでソート済みデータが得られることになります。

以上簡単にまとめると、
・PRIMARY KEYに関しては、論理ソート順と物理ソート順は(ほぼ)同じ
と言うことが出来ます。


一方、PRIMARY KEYではない単なるインデックスの場合は、
データ本体とは別のBツリー上にソートされた状態で格納されます。

このとき、データ本体(正確にはクラスタードインデックスという)に
ついては、すでにPRIMARY KEYの並びでソートされてしまっているわけ
ですから、それ以外のインデックスに対応するような並びには全く
なっていません。

つまり、
・PRIMARY KEY以外のインデックスに関しては、論理ソート順と
  物理ソート順は全く違う
ということが出来ます。

インデックスを使ってデータにアクセス手順についてですが、
・まずインデックスが格納されたBツリーにアクセスしてデータ本体の
  格納位置を取得
・データ本体の格納位置にランダムアクセスしてデータを取得
と、２回のディスク走査が必要になります。
つまりPRIMARY KEYよりも明らかに効率が悪いわけです。

このため、検索件数がある程度多い場合は、インデックスを使わずに
シーケンシャルアクセス(FULL SCAN)する方が速かったりします。

このため、通常のインデックスを張った列データを検索キーにして
大量に検索をかける場合、ORDER BYなどを指定してしまうと
インデックスを使って毎回ランダムアクセスせざるを得ないような
状況になってしまうので、上記の内容からすると、かなり重たい
処理になる可能性があることがわかると思います。

このため、テーブル定義を考える場合は、まず使うであろうSQL文を
ある程度考えておき、また検索時に指定するキーと検索対象行数、
カーディナリティ、それにソートの有無、その他いろいろを考えながら、
最適な定義を求めていく必要があります。


------------------

上記のことからわかると思いますが、

ＫＫ＠ＩＢ さん:
> order by の場合、データレコードを実際に並べ替えず、
> そのレコードを指すインデックスをソートするのが一般的だと私は
> 理解しています。

とありますが、インデックスを使う場合は、最初からソートされているので
後からソートしたりはしません。

> インデックスも実際にはＨＤＤなどに入っているわけですが、
> サイズが小さければ、メモリに全部を読み込んだりできてしまうかも
> しれません。

RDBMSの種類にもよりますが、インデックスデータのサイズが小さければ
メモリにキャッシュされることはよくあるはずです。
また、MySQLの場合は、Bツリーインデックスから勝手にハッシュインデックスを
作成してキャッシュしておいたりもします。


> ところが、上述したように、特定の順番で、早く取り出す、などの目的で、
> 実際にレコードをそういう順序で並べたい
> ケースがあり、そういうときに、実際にレコードを
> 様々な、その状況にあった手段で並べ直します。

文脈からすると「実際に」というのは物理的な並びを指しているのだと
思いますが、MySQLが勝手に全レコードを物理的に後から並べ替えたり
することは決してありません。

MySQLの現在の機能では、物理的に並べ替えたい場合は、一旦データを
ダンプしてからテーブルを削除し、再度テーブルを作り直す必要が
あるようです。
# Oracleとかだと運用しながらテーブル再構築する機能があったりします。


-- 
Hirokazu Aoyama <aoyama@xxxxxxxxxx>