susumu.yata
null+****@clear*****
Wed Jun 11 09:13:45 JST 2014
susumu.yata 2014-06-11 09:13:45 +0900 (Wed, 11 Jun 2014) New Revision: 15298c3b4cde064ff640968cbd509593991d989e https://github.com/groonga/grnxx/commit/15298c3b4cde064ff640968cbd509593991d989e Message: Update the new interface candidate. Added files: new-interface/merger.hpp new-interface/row-set.hpp Modified files: new-interface/cursor.hpp new-interface/db.hpp new-interface/expression-builder.hpp new-interface/expression.hpp new-interface/sorter-builder.hpp new-interface/sorter.hpp new-interface/table.hpp Modified: new-interface/cursor.hpp (+14 -7) =================================================================== --- new-interface/cursor.hpp 2014-06-09 12:39:16 +0900 (3b30c70) +++ new-interface/cursor.hpp 2014-06-11 09:13:45 +0900 (fed7bb0) @@ -10,14 +10,21 @@ class Cursor { Cursor(); virtual ~Cursor(); - // カーソルの位置を進めて移動量を返す. - // 途中で終端に到達したときは,そこで移動を停止し,それまでの移動量を返す. - virtual int64_t seek(int64_t count) = 0; + // カーソルの位置を最大で count 進める. + // 成功すれば移動量を返す. + // 失敗したときは *error にその内容を格納し, -1 を返す. + // + // 途中で終端に到達したときは count より小さい値を返す. + virtual int64_t seek(Error *error, int64_t count) = 0; - // カーソルの位置を進めて移動量を返す. - // 途中で終端に到達したときは,そこで移動を停止し,それまでの移動量を返す. - // 移動中に取得した行 ID は *row_ids に格納する. - virtual int64_t read(int64_t count, RowID *row_ids) = 0; + // カーソルの位置を最大で count 進める. + // 成功すれば移動量を返す. + // 失敗したときは *error にその内容を格納し, -1 を返す. + // + // カーソルの移動中に取得した行は *row_set の末尾に追加する. + // + // 途中で終端に到達したときは count より小さい値を返す. + virtual int64_t read(Error *error, int64_t count, RowSet *row_set) = 0; }; } // namespace grnxx Modified: new-interface/db.hpp (+2 -1) =================================================================== --- new-interface/db.hpp 2014-06-09 12:39:16 +0900 (3eacb10) +++ new-interface/db.hpp 2014-06-11 09:13:45 +0900 (eed85f3) @@ -113,7 +113,8 @@ class DB { // - 指定された名前のファイルに対するアクセス権限がない. // - 作業領域が確保できない. // - ディスクの空き容量が足りない. - virtual bool save(Error *error, const char *path, + virtual bool save(Error *error, + const char *path, const DBOptions &options) const = 0; }; Modified: new-interface/expression-builder.hpp (+8 -5) =================================================================== --- new-interface/expression-builder.hpp 2014-06-09 12:39:16 +0900 (a816e09) +++ new-interface/expression-builder.hpp 2014-06-11 09:13:45 +0900 (6aad343) @@ -43,10 +43,11 @@ class ExpressionBuilder { // - 演算子と引数が対応していない. // - 演算子が求める引数の型・数と実際の引数の型・数が異なる. // - リソースを確保できない. - virtual ExpressionNode *create_operator_node(Error *error, - OperatorType operator_type, - int64_t num_args, - ExpressionNode **args) = 0; + virtual ExpressionNode *create_operator_node( + Error *error, + OperatorType operator_type, + int64_t num_args, + ExpressionNode * const *args) = 0; // すべてのノードを破棄する. virtual void clear(); @@ -57,7 +58,9 @@ class ExpressionBuilder { // // 失敗する状況としては,以下のようなものが挙げられる. // - リソースを確保できない. - virtual std::unique_ptr<Expression> create_expression(Error *error) const; + virtual std::unique_ptr<Expression> create_expression( + Error *error, + const ExpressionOptions &options) const; }; } // namespace grnxx Modified: new-interface/expression.hpp (+17 -22) =================================================================== --- new-interface/expression.hpp 2014-06-09 12:39:16 +0900 (1569681) +++ new-interface/expression.hpp 2014-06-11 09:13:45 +0900 (485cdbf) @@ -17,8 +17,6 @@ class Expression { // 評価結果の型を取得する. virtual DataType data_type() const = 0; - // TODO: 行の一覧とスコアの受け渡し方を決める. - // 行の一覧をフィルタにかける. // 成功すればフィルタにかけて残った行数を返す. // 失敗したときは *error にその内容を格納し, -1 を返す. @@ -26,6 +24,9 @@ class Expression { // 評価結果が真になる行のみを残し,前方に詰めて隙間をなくす. // フィルタにかける前後で順序関係は維持される. // + // 先頭の offset 件はそのままにする. + // 返り値はフィルタをかけて残った行数から offset を引いたものになる. + // // 有効でない行 ID を渡したときの動作は未定義である. // // 失敗する状況としては,以下のようなものが挙げられる. @@ -36,16 +37,18 @@ class Expression { // - NaN が発生する. // - TODO: これらの取り扱いについては検討の余地がある. virtual int64_t filter(Error *error, - int64_t num_row_ids, - RowID *row_ids, - double *scores) = 0; + RowSet *row_set, + int64_t offset) = 0; // スコアを調整する. // 成功すれば true を返す. // 失敗したときは *error にその内容を格納し, false を返す. // - // 評価結果を *scores に格納する. - // 式において _score を指定することにより, scores を入力として使うこともできる. + // 評価結果を *row_set に格納する. + // 式の構築において _score を指定することにより, + // 既存のスコアを入力として使うこともできる. + // + // 先頭の offset 件はそのままにする. // // 有効でない行 ID を渡したときの動作は未定義である. // @@ -57,33 +60,25 @@ class Expression { // - NaN が発生する. // - TODO: これらの取り扱いについては検討の余地がある. virtual bool adjust(Error *error, - int64_t num_row_ids, - RowID *row_ids, - double *scores) = 0; + RowSet *row_set, + int64_t offset) = 0; // 行の一覧に対する評価結果を取得する. // 成功すれば true を返す. // 失敗したときは *error にその内容を格納し, false を返す. // - // TODO: 汎用型を配列にするのは効率が悪いため,ほかの方法が望ましい. - // 専用の型を用意することも含めて検討したい. - // - // TODO: 整列などにも使うことを考えれば,ネイティブな型を返すインタフェースが欲しい. - // 少なくとも内部インタフェースとして用意する必要がある. - // - // 有効でない行 ID を渡したときの動作は未定義である. - // // 失敗する状況としては,以下のようなものが挙げられる. // - 演算において例外が発生する. // - オーバーフローやアンダーフローが発生する. // - ゼロによる除算が発生する. // - NaN が発生する. // - TODO: これらの取り扱いについては検討の余地がある. + // - リソースが確保できない. virtual bool evaluate(Error *error, - int64_t num_row_ids, - const RowID *row_ids, - const double *scores, - Datum *values) = 0; + const RowSet &row_set, + int64_t offset, + int64_t limit, + Data *values) = 0; }; } // namespace grnxx Added: new-interface/merger.hpp (+48 -0) 100644 =================================================================== --- /dev/null +++ new-interface/merger.hpp 2014-06-11 09:13:45 +0900 (66f2fe8) @@ -0,0 +1,48 @@ +#ifndef GRNXX_MERGER_HPP +#define GRNXX_MERGER_HPP + +#include "grnxx/types.hpp" + +namespace grnxx { + +enum MergeStatus { + MERGE_CONTINUE, + MERGE_FINISH +}; + +class Merger { + public: + Merger(); + virtual ~Merger(); + + // 所属するテーブルを取得する. + virtual Table *table() const = 0; + + // 行の一覧を合成する. + // 成功すれば出力された行数を返す. + // 失敗したときは *error にその内容を格納し, -1 を返す. + // + // 入力がまだ残っているときは MERGE_CONTINUE, + // 入力がもう残っていないときは MERGE_FINISH を指定する. + // + // lhs_row_set, rhs_row_set を入力として, + // 合成した結果を result_row_set に出力する. + // 合成に使用された行は lhs_row_set, rhs_row_set から取り除かれる. + // そのため,空になった方の入力に行を補充することで合成を継続できる. + // + // 入力は行 ID 昇順もしくは降順になっているものとする. + // また,入力はそれぞれ重複を含まないものとする. + // + // 失敗する状況としては,以下のようなものが挙げられる. + // - スコアが合成によって不正な値になる. + // - リソースが確保できない. + virtual int64_t merge(Error *error, + RowSet *lhs_row_set, + RowSet *rhs_row_set, + RowSet *result_row_set, + MergeStatus status) const = 0; +}; + +} // namespace grnxx + +#endif // GRNXX_MERGER_HPP Added: new-interface/row-set.hpp (+50 -0) 100644 =================================================================== --- /dev/null +++ new-interface/row-set.hpp 2014-06-11 09:13:45 +0900 (6e2aa02) @@ -0,0 +1,50 @@ +#ifndef GRNXX_ROW_SET_HPP +#define GRNXX_ROW_SET_HPP + +#include "grnxx/types.hpp" + +namespace grnxx { + +class RowSet { + public: + RowSet(); + ~RowSet(); + + // 所属するテーブルを取得する. + Table *table() const; + + // 行 ID を取得する. + RowID get_row_id(Int64 i) const; + // スコアを取得する. + double get_score(Int64 i) const; + + // スコアを正規化する. + // 成功すれば true を返す. + // 失敗したときは *error にその内容を格納し, false を返す. + // + // TODO: 具体的な正規化方法を決める. + // 最大値ですべてのスコアを除算するというのが簡単そうである. + // 正規化後の最大値を指定できると便利かもしれない. + // ほかにも何か必要な正規化があるかどうか. + // + // 失敗する状況としては,以下のようなものが挙げられる. + // - 最大値が 0.0, negative, infinity である. + bool normalize(Error *error, const NormalizeOptions &options); + + // TODO: Sorter を使うより RowSet::sort() の方が良い? + + // 整列する. + // 成功すれば true を返す. + // 失敗したときは *error にその内容を格納し, false を返す. + // + // TODO: 整列条件の指定方法を決める. + // + // 失敗する状況としては,以下のようなものが挙げられる. + // - リソースが足りない. + // - 演算において例外が発生する. + bool sort(Error *error, const SortConditions &conditions); +}; + +} // namespace grnxx + +#endif // GRNXX_ROW_SET_HPP Modified: new-interface/sorter-builder.hpp (+5 -3) =================================================================== --- new-interface/sorter-builder.hpp 2014-06-09 12:39:16 +0900 (beb2b83) +++ new-interface/sorter-builder.hpp 2014-06-11 09:13:45 +0900 (d9e1f1d) @@ -29,7 +29,7 @@ class Sorter { // - 式の評価結果が大小関係を持たない型になる. // - リソースを確保できない. virtual bool add_precondition(Error *error, - const Expression *expression, + const Expression &expression, SortOrder order) const = 0; // 整列条件を追加する. @@ -43,7 +43,7 @@ class Sorter { // - 式の評価結果が大小関係を持たない型になる. // - リソースを確保できない. virtual bool add_condition(Error *error, - const Expression *expression, + const Expression &expression, SortOrder order) const = 0; // すべての条件を破棄する. @@ -55,7 +55,9 @@ class Sorter { // // 失敗する状況としては,以下のようなものが挙げられる. // - リソースを確保できない. - virtual std::unique_ptr<Sorter> create_sorter(Error *error) const; + virtual std::unique_ptr<Sorter> create_sorter( + Error *error, + const SorterOptions &options) const; }; } // namespace grnxx Modified: new-interface/sorter.hpp (+3 -2) =================================================================== --- new-interface/sorter.hpp 2014-06-09 12:39:16 +0900 (f000bef) +++ new-interface/sorter.hpp 2014-06-11 09:13:45 +0900 (5356c53) @@ -24,8 +24,9 @@ class Sorter { // - 演算において例外が発生する. // - リソースを確保できない. virtual bool sort(Error *error, - int64_t num_row_ids, RowID *row_ids, - int64_t offset, int64_t limit); + RowSet *row_set, + int64_t offset, + int64_t limit); }; } // namespace grnxx Modified: new-interface/table.hpp (+44 -48) =================================================================== --- new-interface/table.hpp 2014-06-09 12:39:16 +0900 (cc2504c) +++ new-interface/table.hpp 2014-06-11 09:13:45 +0900 (b0cb6ce) @@ -139,11 +139,6 @@ class Table { // ただし,頻繁に削除すると隙間だらけになって効率が落ちる. // オプションとしてはよさそう. // - // TODO: 将来的な検討案. - // 削除によって行 ID に空きができたとき,前方へと詰めるという案がある. - // ただし,参照されているテーブルについては参照元の修正が必要になる. - // また,行 ID に特別な意味を持たせている場合は問題になる. - // // 失敗する状況としては,以下のようなものが挙げられる. // - 指定された ID が行 ID の最小値より小さいか最大値 + 1 より大きい. // - キーカラムが存在しないとき @@ -239,17 +234,13 @@ class Table { // 自動で delete されて困るときは release() で生のポインタを取り出す必要がある. // // TODO: 将来的な検討案. - // 簡易なものでかまわないので,クエリ文字列をパースして式を構築してくれる - // インタフェースがあれば何かと便利かもしれない. - // テスト用と考えれば,最適化などは一切せず, - // 真っ正直にやってくれるのがベスト. + // クエリ文字列をパースして式を構築するインタフェースが欲しい. + // テストやデバッグに使うのであれば,最適化などは必要ない. // // 失敗する状況としては,以下のようなものが挙げられる. - // - オプションが不正である. // - リソースが確保できない. virtual std::unique_ptr<Expression> create_expression_builder( - Error *error, - const ExpressionOptions &options) const = 0; + Error *error) const = 0; // 整列器を構築するためのオブジェクトを作成する. // 成功すれば有効なオブジェクトへのポインタを返す. @@ -266,15 +257,9 @@ class Table { // 自動で delete されて困るときは release() で生のポインタを取り出す必要がある. // // 失敗する状況としては,以下のようなものが挙げられる. - // - オプションが不正である. // - リソースが確保できない. virtual std::unique_ptr<Sorter> create_sorter_builder( - Error *error, - const SorterOptions &options) const = 0; - - // TODO: 分類器については,条件をひとつしか受け付けないのであれば, - // create_grouper() が条件を受け取るようにした方がすっきりする. - // Expression, Sorter にあわせて GrouperBuilder を用意する手もある. + Error *error) const = 0; // 分類器を作成する. // 成功すれば有効なオブジェクトへのポインタを返す. @@ -312,45 +297,56 @@ class Table { // - リソースが確保できない. virtual std::unique_ptr<Grouper> create_grouper( Error *error, + Expression *expression, const GrouperOptions &options) const = 0; - // TODO: 検索結果の型を決める. - // - // 行 ID の配列とスコアの配列に分けるのと, - // 行 ID とスコアをメンバとする構造体の配列にする案がある. + // 行の一覧を逐次マージするためのオブジェクトを作成する. + // 成功すれば有効なオブジェクトへのポインタを返す. + // 失敗したときは *error にその内容を格納し, nullptr を返す. // - // 前者はスコアを必要としないクエリを無駄なく処理できるのが魅力です. - // その代わり,フィルタをかけるにせよ整列をするにせよグループ化をするにせよ, - // スコアがある状況では効率がそれなりに悪くなることが予想されます. + // 行の一覧は行 ID 順になっているものとする. + // 昇順と降順については,どちらかをオプションで選択できるものとする. // - // 後者は,スコアが不要なときに無駄なメモリ消費が発生したり, - // キャッシュの効率が少し低下したりすることが予想されます. + // 返り値は std::unique_ptr なので自動的に delete される. + // 自動で delete されて困るときは release() で生のポインタを取り出す必要がある. // - // 正直なところ,後者の方が良いのではないかという気がしてきました. - // 一度,簡単なプログラムでも作って試してみた方がよいだろうと思います. + // マージの種類としては,以下のようなものが挙げられる. + // - AND: 両方に含まれるものを残す. + // - OR: どちらかに含まれるものを残す. + // - XOR: 一方には含まれていて,もう一方には含まれていないものを残す. + // - SUB: 一つ目の入力には含まれていて,二つ目の入力には含まれていないものを残す. // - // 前者を採用するのであれば,行 ID の配列とスコアの配列が個別にサイズを - // 持つような実装は避けたい.しかし,オブジェクトとしては分かれているのに - // 取り扱いが不可分になるのは厄介である. + // スコアの合成方法としては,以下のようなものが使われそうである. + // - 単純に加算したり乗算したりする. + // - 乗算は必要ないかもしれない. + // - 重みを乗せて加算する. + // - これは Adjuster でも対応できる. + // - スコアを正規化する. + // - たとえば,最大値が 1.0 になるように修正する. + // - すべてのスコアが分かっている状況でなければ適用できないため, + // 逐次マージでは使えない. // - // どちらでも大丈夫なインタフェースを用意したい. + // 失敗する状況としては,以下のようなものが挙げられる. + // - オプションが不正である. + // - リソースが確保できない. + virtual std::unique_ptr<Merger> create_merger( + Error *error, + const MergerOptions &options) const = 0; - // TODO: 検索結果のマージ方法を検討する. - // - // 全文検索や全走査を使えば行 ID 順となるが,ほかの索引を使ったときは - // 別の順序になるかもしれないため,そういうケースへの対策が必要である. - // 行 ID 順についても,昇順と降順があることに注意が必要である. + // 行の一覧を一括でマージする. + // 成功すれば true を返す. + // 失敗したときは *error にその内容を格納し, false を返す. // - // マージの種類としては,以下のようなものが挙げられる. - // - どちらかに含まれるものを残す. - // - 両方に含まれるものを残す. - // - 片方に含まれていて,もう片方には含まれていないものを残す. - // - XOR と SUBTRACT で区別できる. + // マージの種類やスコアの合成方法は逐次マージと同様になる. // - // スコアの合成方法としては,以下のようなものが使われそうである. - // - 単純に加算したり乗算したりする. - // - 双方を正規化(最大値を 1.0 にするなど)してから加算する. - // - スコアを正規化するインタフェースがあれば,単純な加算にできる. + // 失敗する状況としては,以下のようなものが挙げられる. + // - オプションが不正である. + // - リソースが確保できない. + virtual bool merge(Error *error, + RowSet *lhs, + RowSet *rhs, + RowSet *output, + const MergerOptions &options); protected: Table(); -------------- next part -------------- HTML����������������������������... Télécharger