Natural sort order for PostgreSQL

Natural sort orderPHPではnatsort関数で実現できるソート方法です。
例えばsort関数でソートすると

<?php
$a = ['file1', 'file2,' 'file10'];
sort($a); // => ['file1', 'file10', 'file2']

となるところ、natsort関数では、

<?php
$a = ['file1', 'file2,' 'file10'];
natsort($a); // => ['file1', 'file2', 'file10']

となる。通常文字列ソートすると辞書式順序に従うのだが、ユーザが任意のコンテンツ名に連番付けて整頓するようなサービスでは、Natural orderは有用だ。

PostgreSQLでNatural order

PostgreSQLではどうすんのかなと調べてみたら、標準関数などでは用意がないが、関数を書いた人を見つけた。

gist.github.com

SELECT * FROM files FROM filename;
-- -> filename: file1, file10, file2

SELECT * FROM files FROM naturalsort(filename);
-- -> filename: file1, file2, file10

PHPのnatsort関数と全く同じ結果になるわけではないようだけど、ほとんどこれで十分なのでは。

naturalsort関数の動作する仕組み

まずFROM句を取り出して動きを確認してみる。

SELECT regexp_matches('2file', '0*([0-9]+)|([^0-9]+)', 'g');
regexp_matches
{2,null}
{null,file}

数字とそれ以外に分解して行を作っている。0*で0パティング(01,02,…10,11とか)を無視する。

 SELECT string_agg(convert_to(coalesce(r[2],length(length(r[1])::text)::text || length(r[1])::text || r[1]),'SQL_ASCII'),'\x00')
 FROM regexp_matches('2file', '0*([0-9]+)|([^0-9]+)', 'g') r;
string_agg
112 file

(112,fileの間は\x00
string_aggで、regexp_matchesで出力された複数行を`\x00'で区切った1つの文字列にしている。
集約前に、convert_toの引数で各行に何をしているか、以下のようになる。

regexp_matches convert_to(…)
{2,null} 112
{null,file} file

112とは、length(length('2')) || length('2') || '2' の結果出力される数字だ。数字の桁数を連結している。最終的にはstring_aggで集約した文字列"112 file"がORDER句のソートに使われるわけだが、112という数字を作る意味は何か、数字の例で確認すると分かりやすい。

length(length(text)) length(text) text
1 1 1
1 1 2
1 1 3
1 2 10
1 2 20
1 3 100
1 3 200

textの桁数が変わらないうち(1,2,3,…9)は、上位桁が変わらない。辞書式順序では、単純にtextだけで比較されることになる。
textの桁数が上がる(10,100)と、上位桁であるlength(text)の数が上がる。辞書式順序では、まずlength(text)(textの桁数)で比較され、同じであれば次にtextで比較される。
これで辞書式順序でも意図した大小関係で比較できるわけだ。

textの数を大きくしてみよう。

length(length(text)) length(text) text
1 9 999999999
2 10 1000000000
2 11 10000000000
3 100 1e99
4 1000 1e999
5 10000 1e9999
6 1e5 1e99999
9 1e8 1e99999999
10 1e9 1e999999999

length(text)が2桁以上になればlength(length(text))が上がる。text=1e99999999、length(length(text))=9までは問題なく動作する。text=1e999999999、length(length(text))=10となると、辞書式順序ではlength(length(text))=2より小さいとみなされ、正しく動作しない。が、1e999999999なんて大きな数を扱うことはないのではないか。

普通、辞書式順序で数字をソートする時は、対象の数字の最大桁数を調べて0パティングすると思うが、あらかじめ桁数が分かっていない場合は、制限があることを分かった上でこの手法を使うのは便利そう。

元のGistコードではエラーが発生したのでフォークした。Postgres 8.4(string_aggが無い)で動かす例も追記してある。 gist.github.com