マージの順序に関する仕様を検討する

[s-yata]

概要

レコードの一覧（二系統）をマージするとき，出力の順序をどうするかについて検討します．
現状で考えているのは，二系統のどちらかを継承する，もしくは指定なしというものです．

重要なのは，入出力の順序によって効率的な実装が変わることです．

たとえば，入力の順序が同じであれば，先頭から順に比較しながら進めるのが良さそうです．
出力の順序については，自然と入力の順序が維持されるので問題ありません．

入力の順序が異なる場合，どちらか一方を出力として選択するか，指定なしにするかとなります．
指定なしであれば，ハッシュ表に入れて出して終わりというのでも構わないでしょう．
ただ， offset, limit の指定があるときは，両方を少しずつ処理して，必要に応じて途中で終了するという選択肢が検討に入ります（※）．

※ マージの方法によります． OR であれば片方ずつ進めた方が楽そうですが， AND であれば両方を少しずつ進めることで全体を処理せずに済むかもしれません．

どちらか一方の順序を維持したいときは，維持しなくてよい方をハッシュ表にしてから，維持したい方をハッシュ表に通すという実装が考えられます（※）．
offset, limit の指定があるときについては，上で述べたような工夫をした方が時間を短縮できるかもしれません．

※ OR だと無理です．

とりあえず， AND のときは順序選択ができると便利な気がしてきました．
一方で， OR のときは厳しいように思います．

それから，効率については入力に依存します．
入力のどちらか一方がすごく長い，あるいは短いケースなどをあらかじめ検出できれば良いのですが…．