Ogawa::Memoranda

MT::Util::make_unique_basenameは新しいエントリを作るたびに必ず1回呼び出され、そのエントリのbasenameを決定します。このmake_unique_basenameは以下のような手続きからなっています。

sub make_unique_basename {
    my ($entry) = @_;
    my $blog = $entry->blog;
    my $title = $entry->title;
    unless ($title) {
        if (my $text = $entry->text) {
            $title = MT::Util::first_n_words($text, 5);
        }
        $title = 'Post' unless $title;
    }
    my $base = substr(MT::Util::dirify($title), 0, 15);
    $base =~ s/^_+//;
    $base =~ s/_+$//;
    $base = 'post' if $base eq '';
    my $i = 1;
    my $base_copy = $base;
    
    while (MT::Entry->count({ blog_id => $blog->id,
                              basename => $base })) {
        $base = $base_copy . '_' . $i++;
    }
    $base;
}

この手続きをおおまかに説明すると、まずタイトルもしくは本文をdirifyした文字列の最長15文字を取り出します。次にこの文字列をbasenameに持つエントリがないかどうかを、「SELECT COUNT(*) FROM mt_entry WHERE basename=...」の戻り値が、0(=マッチするエントリなし)か、0でないか(=マッチするエントリあり)かによって判定します。

マッチするエントリがあれば、文字列に「_1」を付加して再度SELECT COUNT(*)を実行します。これを「_2」、「_3」、…と繰り返し、マッチするエントリがない状態になったらそれをベースネームとして返します。

例えば、このBlogではタイトルがすべて日本語からなるエントリが400個あります。これらのエントリのbasenameはpost, post_1, post_2, ..., post_399と付けられているわけです。次にすべて日本語からなるタイトルを持つエントリを作ったとすると、401回SELECT COUNT(*)を実行して初めてpost_400というbasenameが付けられるわけです。

少し形式的な書き方をすると、エントリ数をNとすると、一回のインデックススキャン(SELECT COUNT(*))の処理時間は最良でO(1)、平均でO(log N)、一回のmake_unique_basenameはこのシーケンススキャンをO(N)回(※)行います。したがって、エントリを1個追加するのに要する時間はO(N log N)となります。Acceptableかどうかはギリギリというところでしょう。念のためこれはMySQL, PostgreSQLの場合であり、BerkeleyDBではO(N²)になる可能性があります。

どうしてもO(N)にしたければ以下のようなコード(正確な動作はオリジナルと異なります)にすればよいわけですが、普段たいていO(1)で済んでいた英語国民には不幸になります。というかこっちはこっちで重い操作をやっていて、試しに書いてみたというだけのものです。お使いの環境によっては高速化されるとは限りません。

sub make_unique_basename {
    my ($entry) = @_;
    my $blog = $entry->blog;
    my $title = $entry->title;
    unless ($title) {
        if (my $text = $entry->text) {
            if (MT::ConfigMgr->instance->DefaultLanguage eq 'ja') {
                $title = MT::I18N::first_n_text($text, 10);
            } else {
                $title = MT::Util::first_n_words($text, 5);
            }
        }
        $title = 'Post' unless $title;
    }
    my $base = substr(MT::Util::dirify($title), 0, 15);
    $base =~ s/^_+//;
    $base =~ s/_+$//;
    $base = 'post' if $base eq '';
    my @bnames = grep {/^$base(\_[0-9]+)?$/} map {$_->basename}
                        MT::Entry->load({ blog_id => $blog->id });
    return $base unless @bnames;
    my $max = -1;
    foreach my $bname (@bnames) {
        my $bidx = ($bname =~ /$base\_(.*)/) ? $1 : 0;
        $max = $bidx if $max < $bidx;
    }
    return $base . '_' . ++$max;
}

よくある質問とその答え

Q1. 「個別のアーカイブへのリンクに以前の形式(id)を利用」したり、アーカイブファイルの形式を指定すれば、この問題を回避できますか?

A1. できません。エントリを追加した際にmake_unique_basenameが必ず呼ばれてしまいます。回避するとすれば、make_unique_basenameの定義を書き換えるか、プラグインなどで上書きする必要があります。

Q2. そんなに遅くなった気がしないのですが?

A2. ここで述べている問題は「下書き」状態でエントリを保存するのにかかる時間、あるいはエクスポートデータのインポートにかかる時間、に関するものだと考えてもらった方が直感に合っています。make_unique_basenameはそのエントリが「下書き」にしろ「公開」にしろ最初に保存されたときに一回だけ呼び出されるのですから。

もっともエントリの追加と同時に公開+再構築を行う場合などは、make_unique_basenameの処理時間は一般に無視できるかもしれません。なぜなら再構築はテンプレートの解釈やファイルI/Oを伴うもっとずっと重い操作ですから。しかし、再構築の処理オーダーがO(N)であるのなら、いずれmake_unique_basenameの処理オーバーヘッドが顕在化することも予想できます。