order_byメソッドとOrderedViewクラスの実装

Koherent_DB

実装の楽なlimitメソッドから書こうかと思いましたが、order_byメソッドなくしてlimitメソッドは使い物にならないので、先にorder_byメソッドの実装について書きます。

order_byメソッドではSQLのORDER BYのように検索結果をソートして取得するためのメソッドです。ここではソートを実現するorder_byメソッドと、order_byメソッドの戻り値の型となるOrderedViewクラスの実装について書きます。

例で使用するテーブル

これまで同様、次のようなテーブルがあるものとして話を進めます。

members: メンバーを格納したテーブル
member_id family_name first_name age sex group_id
1011 中田 祐輔 22 0 1
1234 山下 沙希 17 1 2
1999 宮川 崇 18 0 2
2112 石田 菜々 21 1 1
2345 山崎 千佳 19 1 1
PerlShellKoherent::DBでのテーブルの取得

次のようにして、$membersがTableオブジェクトを事前に保持しているものとします。

my $members = $database->table('members');

order_byメソッドの使い方

SELECTのAPI(2) 様々なSELECT文への対応に書いたように、

SELECT * FROM members ORDER BY age;

のようにデータをソートして参照するには、order_byメソッドを用いて下のように書きます。

my $result = $members->order_by(sub{
    my ($row1, $row2) = @_;
    $row1->{'age'} <=> $row2->{'age'}
});

order_byメソッドに渡しているのは比較サブルーチンです。比較サブルーチンは二つの行の大小関係を定義します。二つの行$row1、$row2を引数にとり、$row1が$row2より小さい場合に負の数を、$row1と$row2が等しい場合に0を、$row1が$row2より大きい場合に正の数を返します。order_byメソッドの戻り値は、比較サブルーチンを用いてソート済データを返すViewオブジェクトです。比較サブルーチンを用いることで、複数のフィールドをキーとするソートや、より複雑な計算結果によるソートなどをPerlを用いて柔軟に記述することができます。これは、whereメソッドに条件サブルーチンを渡すのと同じ考え方です。

フィールド値を文字列としてソートする場合に限り、次のようにソートキーとなるフィールド名を渡してorder_byメソッドを呼ぶこともできます。

$result = $members->order_by('family_name');

第2引数を渡すとそれを降順でソートするかどうかのフラグ（真の場合は降順ソート、偽の場合は昇順ソート）と認識し、ソートの昇順・降順を指定できるようにします。

$result = $members->order_by('family_name', 1);

第2引数を省略した場合はPerlの仕様上undefとして受け取るため、降順フラグが偽となり昇順ソートが行われます。第1引数に比較サブルーチンを渡した場合でも第2引数を利用できますが、降順フラグで昇順ソートを指定するよりも比較サブルーチン中で正負を逆転することでそれを実現した方が高速に動作します*1。

使用頻度が高いと思うので、数値としてのソート専用のメソッドを用意することも検討していますが現段階では保留します*2。

order_byメソッドの実装

次にorder_byメソッドの実装について考えます。

whereメソッドが条件にマッチする行だけを返すConditionedViewクラスを返したように*3、order_byメソッドもソート済のビューを表すViewクラス（を継承したクラス）を返します。このViewクラスをOrderedViewクラスとします。

order_byメソッドは比較サブルーチンをOrderedViewクラスに渡して処理を丸投げするだけですが、第1引数にフィールド名を渡した場合はorder_byメソッドの内部で比較サブルーチンを作成する必要があります（OrderedViewクラスの内部で対処することもできますが、order_byメソッドの中で対処した方がプログラムが簡潔になります）。また、降順フラグが真の場合にはソート順を逆転させるために比較サブルーチンをサブルーチンでラップして戻り値の正負を逆転させます。

コードにすると次のようになります。order_byメソッドに関係ない部分は省略しています。

package Koherent::DB::View;

# 省略

use Koherent::DB::OrderedView;

# 省略

sub order_by{
    my $self = shift;

    # 比較サブルーチン
    my $compare = shift;

    # 降順フラグ
    my $desc = shift;

    if(ref $compare ne 'CODE'){
        # $compareにフィールド名が渡された場合は、
        # そのフィールドをソートキーとしてソートを行う。

        my $field_name = $compare;

        # $compareでサブルーチンが渡された場合にように
        # 戻り値を正負逆転させるサブルーチンでラップすると
        # そのサブルーチン呼び出しのためのオーバーヘッドが発生するため、
        # 降順の際には初めから正負反転した結果を返すサブルーチンを作成する。
        if($desc){
            # 文字列降順にソートするための比較サブルーチン
            $compare = sub{
                my ($row1, $row2) = @_;
                -($row1->{$field_name} cmp $row2->{$field_name});
            };
        }else{
            # 文字列昇順にソートするための比較サブルーチン
            $compare = sub{
                my ($row1, $row2) = @_;
                $row1->{$field_name} cmp $row2->{$field_name};
            };
        }
    }elsif($desc){
        # $compareでサブルーチンが渡され、かつ$descが真の場合は、
        # ソート順を逆転させるために$compareの戻り値の正負を逆転する。

        my $original_compare = $compare;
        $compare = sub{$original_compare->(@_) * -1} if $desc;
    }

    # order_byメソッドを呼び出したViewを元にソート済データを返す
    # OrderedViewクラスのインスタンスを返す。
    Koherent::DB::OrderedView->new($self, $compare);
}

# 省略

OrderedViewクラスの実装

OrderedViewクラスでもiteratorメソッドの実装が重要となります。

ConditionedViewクラスの場合には、ConditionedViewクラスとセットでConditionedViewIteratorクラスを実装しました。OrderedViewクラスに対してもOrderedViewIteratorクラスを考えてもいいのですが、ここでは少し発想を広げてみます。

ソートの処理はストレージ上ではなくメモリ上で行う予定です。テーブルが巨大になると全データをメモリ上に乗せることはできなくなってしまうかもしれません。しかし、ソートは時間計算量がO(n log n)である比較的重い処理*4です。そもそもメモリ上に乗らないような件数のデータをストレージ上でソートしようとすると、処理が重すぎて終わらないのではないかと思います。それほど大量のデータをソートするにはインデックスを用いるのが普通です。PerlShellKoherent::DBではインデックスを用いたソートにはorder_byメソッドとは別のメソッドを利用するため、order_byメソッドでは全件をメモリ上に乗せても問題がない程度の件数を想定し、メモリ上でソートを行おうと思います。

メモリ上でソートを行うのであれば、OrderedViewクラスのiteratorメソッドが呼び出された際の処理は次のようになります。

  1. order_byメソッドの呼び出し元Viewオブジェクトからイテレータを取得する。
  2. 取得したイテレータを介して全件データを取得する（ソートのために配列に格納する）。
  3. 取得した全件データを比較サブルーチンを用いてソートする。
  4. ソート済の全件データを格納した配列をOrderedViewクラス用のイテレータに渡す。

このように考えると、OrderedViewクラス用のイテレータは配列に格納された各行のデータを先頭から順に返すだけでよいことになります。

そのようなイテレータをOrderedViewIteratorクラスとしても良いですが、配列で各行を保持し順に読み出すという処理はより汎用的なものとしてライブラリ化しておくと便利そうです。そこで、配列で行を保持するクラスをArrayViewクラス、ArrayViewクラスからデータを読み出すクラスをArrayViewIteratorクラスとして実装します。

ソート自体は、当初はperlのsort関数を使うことを考えていました。しかし、パッケージ越しのソートサブルーチンがうまく働かないに書いたようにパッケージ越しにソートサブルーチンを渡してソートを行うとうまく動作しなかったため、独自にソートの処理を実装することにしました。このソートはKoherent::PerlShellDB::Util::qsortとして定義しています*5。qsortサブルーチンは第1引数にソート対象の配列を、第2引数にその配列の要素に対する比較サブルーチンをとります。qsortサブルーチンのアルゴリズムにはクイックソートを用いています*6。

以上を踏まえてOrderedViewクラスを実装すると次のようになります。なお、Viewオブジェクトからの全件取得のためにrowsメソッドを使用しています。rowsメソッドはViewオブジェクトが自身のイテレータを介して全件を取得し、配列リファレンスとして返すというメソッドです。

package Koherent::DB::OrderedView;

# 省略

use base qw(Koherent::DB::View);
use Koherent::DB::ArrayView;
use Koherent::DB::Util qw(qsort);

sub new{
    my ($class, $view, $compare) = @_;

    my $self = $class->SUPER::new;
    $self->{'view'} = $view;
    $self->{'compare'} = $compare;

    $self;
}

sub iterator{
    my $self = shift;

    # order_byメソッド呼び出し下Viewオブジェクトから全件を取得
    my $rows = $self->{'view'}->rows;

    my $compare = $self->{'compare'};

    # 全件データをソート
    qsort($rows, $compare);

    # ソート結果を格納したArrayViewオブジェクトを生成しイテレータを取得
    Koherent::DB::ArrayView->new($rows)->iterator;
}

# 省略

package Koherent::DB::View;
# 省略

sub iterator{
    # 抽象メソッドのためオーバーライドが必要
    croak "iterator is an abstract method. Override it.";
}

sub rows{
    my $self = shift;
    my $rows = [];

    my $iterator = $self->iterator;

    # イテレータを用いて全件を取得
    while(my $row = $iterator->next){
        push @{$rows}, $row;
    }

    $rows;
}

# 省略

ArrayViewクラスの実装

ArrayViewクラスは配列として行データを保持し、それにアクセスするためのイテレータをiteratorメソッドで提供します。

実装上難しい部分はないため、下記にコードのみを示します。ArrayViewクラスではupdateメソッド等の更新系メソッドはサポートしません。このため、コンストラクタに与えた配列を直接操作しない限り、生成時のデータを保持し続けることになります。

package Koherent::DB::ArrayView;

# 省略

use base qw(Koherent::DB::View);
use Koherent::DB::ArrayViewIterator;

sub new{
    my $class = shift;
    my $rows = shift;

    # 引数を省略した際に、
    # 空のArrayViewオブジェクトを生成するため
    $rows = [] unless defined($rows);

    # $rowsが配列リファレンスでなければ
    # ArrayViewIteratorがエラーを起こすため
    croak 'ROWS must be an array reference.'
        unless UNIVERSAL::isa($rows, 'ARRAY');

    my $self = $class->SUPER::new;
    $self->{'rows'} =  $rows;

    $self;
}

sub iterator{
    my $self = shift;
    Koherent::DB::ArrayViewIterator->new($self);
}

# 省略

ArrayViewIteratorクラスの実装

ArrayViewIteratorクラスはArrayViewクラスの保持する配列の各要素に順番にアクセスし返します。順番にアクセスするためには、現在何番目の要素を指しているかを記録しておかなければなりません。下記コードでは、$pointerという変数に現在指している要素番号を格納しています。

package Koherent::DB::ArrayViewIterator;

# 省略

use base qw(Koherent::DB::ViewIterator);

sub new{
    my ($class, $array_view) = @_;

    my $self = {
        array_view => $array_view,
        # 現在何番目の要素を指しているかを表すポインタ
        pointer => 0, # 最初の要素を指すため初期値は0
    };

    bless $self, $class;
}

sub next{
    my $self = shift;

    my $pointer = $self->{'pointer'};

    my $row;

    # ポインタの指す要素（行）のデータを取得
    $row = $self->{'array_view'}->{'rows'}->[$pointer];

    # ポインタを一つ進めて記録
    $self->{'pointer'} = $pointer + 1;

    $row;
}

# 省略

まとめ

SQLのORDER BYに相当するorder_byメソッドを実装しました。

order_byメソッドには比較サブルーチンを与えることで、単純なフィールドによるソートに留まらない複雑なソート条件を記述できるようにしました。また、第2引数である降順フラグに真を渡すことで、比較サブルーチンの結果を反転し結果を降順で得られるように実装しました。またショートカットとして、比較サブルーチンの代わりにフィールド名を渡すことで、フィールド値を文字列として評価しソートを行えるようにしました。

whereメソッド同様に、order_byメソッド、OrderedViewクラスをセットで実装しました。しかし、OrderedViewクラスのデータ参照にはOrderedViewIteratorクラスを用意するのではなく、より汎用的なクラスとしてArrayViewクラスとArrayViewIteratorクラスを用いることにしました。ArrayViewクラスは単純に表データを配列として保持するクラスです。OrderedViewクラスのiteratorメソッドが呼び出された際には、全件データをソートして、それを格納するArrayViewオブジェクトを生成します。iteratorメソッドの戻り値には、そのArrayViewオブジェクトのイテレータを返します。

*1:order_byメソッドの実装で書いたように、降順フラグに真を渡して降順ソートを行う場合は、比較サブルーチンをラップして戻り値の正負を逆転するサブルーチンを挟むため、余分なサブルーチン呼び出しと正負の反転のオーバーヘッドが発生します。

*2:引数で数値・文字列の指定を行う形も検討しましたが、例えば第3引数に数値・文字列のフラグを渡すようにすると、第3引数のフラグが真の場合は昇順の場合でも第2引数の降順フラグを省略できなくなってしまい、やや使いづらいように感じます。数値によるソートを別メソッドで切り出す方法も考えられます。しかし、order_byメソッドは引数によって比較サブルーチンとフィールド名が渡された場合を区別するのに、数値用ソートメソッド（例えばorder_by_number）はフィールド名のみ受け取るというのも気持ち悪いように思います。order_by（比較サブルーチンのみ）、order_by_text（フィールド名のみ受け取り文字列としてソート）、order_by_number（フィールド名のみ受け取り数値としてソート）の三つを用意することもできますが、やや冗長ですし、他のメソッドはすべて引数で挙動をコントロールしているので、order_byだけ複数のメソッドを用意するのも一貫性に欠けます。フィールドの型をTableクラスから引継ぎ自動判別することも考えましたが、selectメソッドで自由に式を埋め込まれた場合（例えばsub{$_[0]->{'age'} - 1}を渡された場合）、その結果が数値なのか文字列なのかを判別することができません。どのような方法をとるのがベストかの判断が難しく、また数値によるソートは比較サブルーチンで実現できるため、現断簡では保留としました。

*3:whereメソッドとConditionedViewクラスの実装参照。

*4:例えば、線形探索はO(n)、二分探索はO(log n)でソートより軽い処理です。ソートの計算量もアルゴリズムによりますが、比較によるソートではO(n log n)より高速なソートが存在しないことが数学的に証明されています（参考文献：定本 Cプログラマのためのアルゴリズムとデータ構造 p.180）。O(n log n)となる比較によるソートアルゴリズムは、クイックソート、マージソート、ヒープソートなどです。なお、比較によらないソートにはビンソートや基数ソートのように、O(n)でソートを行うことができるアルゴリズムも存在します。しかし、比較によらないソートには制約が多く、また処理上の様々なオーバーヘッドから、現実的なパフォーマンスを考えると通常は比較によるソートが使われます。

*5:qsortのqはクイックソートのqです。最初はサブルーチン名をsortにしようとしたのですが、Perlのsort関数と衝突してうまく動作しなかったためsort以外の名前にしました。quick_sortという名前も考えましたが、C言語のqsort関数にちなんでqsortとしました。

*6:クイックソートはデータがソート済である場合に計算量がO(n^2)になってしまうため、左端、中央、右端のデータの中央値をピボットとする方法を用いています。3値の中央値をピボットとする手法でも、巧妙にデータを並べれば計算量がO(n^2)とすることはでき、最大計算量はO(n^2)のままです。しかし、そのような並びが自然に作られることはほぼないと考え、現実的なレベルでの対策として3値の中央値をピボットとする手法を採用しました。より抜本的な対策としては、クイックソートとヒープソートを組み合わせたイントロソートというアルゴリズムが存在します。