2006-06-23  ウィスパー3―その1―

ウィスパー3は，ウィスパー2の上位層に位置するアプリケーションです。ウィスパー3の肝は「表の集合演算」と「字句と構文の解析」です。まだ要求仕様と実装仕様のどちらも，はっきりしていません。

表の集合演算

ウィスパー3で定義している集合演算の種類はみっつです。各々，演算子として「+（和）」「*（積）」「-（差）」を使うことにします。例えば以下のように集合A，B，Cがあるとします。

A = { a, b, c, d, e, f }
B = { a, c, d, f }
C = { f }

このとき「A * B - C」は{ a,c,d }です。

（注意：上の例はあくまで考え方を説明するためのものであって，実際にABCやabcdefが出てくるわけではありません。以後もそうです。）

何をやりたいのかというと， SQLのSELECT文で抽出したレコードに対して集合演算したいのです。いったいどうすればよいのでしょうか。

テンポラリテーブルを使った方法

最初に実験したのは，すべて2項演算にしてしまうことでした。A * B - CだったらA * B → Zとして，まずZを求めます。つぎにZ - Cを計算して解を得ます。原理上どんなに長い式でも扱えますし，1回計算するごとに式が短くなるので，数学的に扱いやすいと思いました。以下は擬似コードです。

Clear() ;
Calculate( A ) ;
Calculate( B, 'AND' ) ;
Calculate( C, 'EXCEPT' ) ;
Result() ;

（偶然にも命令文の並びは，電子式卓上計算機を操作する手順と似ています。）

2項演算の結果Zは，どこかに残しておかなければいけません。前の計算結果を知らなければ，つぎの計算ができないからです。テンポラリテーブルを作って，途中の計算結果を格納することにしてみたのだが，この方法には問題がありました。

式が長くなると演算回数も増えるので，目に見えて遅くなってしまいました。レコードが数万件のとき，5項の演算で遅い感じがして，15項を超えると使い物にならないという気がしました。要求仕様では，現実的な速さで最大15項の演算ができなければいけません。どうやら考え方が「素直」というだけでは，役に立たないようです。

なぜ遅くなるのでしょうか。項数が増えるとテンポラリテーブルの作成と破棄を何度も繰り返してしまうのと，途中計算のために使いもしないレコードを保持しなければいけないのが原因だと思いました。テンポラリテーブルは1回の演算で使い捨てるので，インデックスとの相性が悪そうなのも気になりました（正確にはインデックスをつけたときの性能を調べていないので不明）。

差の演算回数を1回にした方法

テンポラリテーブルをなるべく使わないで計算する方法を考えたいと思います。以下の案はこれから実験します。

• SELECT文のWHERE句に，複数個のAND演算子とOR演算子を埋め込む
• テンポラリテーブルの出番を1回にする
• 差の演算回数を1回にする

ひとつ目は，例えば「SELECT … WHERE p = α OR p = β AND p = γ AND p = δ」のように，和と積を多項演算してしまいます。

残りのふたつは，同じことを言っています。この方法では，差の演算回数が1回しかありません。仮に「A + B - C - D」という式があったら，変形して「(A + B) - (C + D)」としてしまうのです。

さて何の気なしに「式を変形して」なんて言ってしまいました。コンピュータの世界でこれをするには，まず文字列を字句解析して「演算子」「シンボル（演算されるもの）」に分けなければいけません。つぎに字句の並びを決められた構文に当てはめて，「式」として解釈させなければいけません。簡単にできそうな気もしますが，難しい気もします。

何やらこの先とんでもない罠が待ち構えていそうです。