ここではDoqueDBのオプティマイザーの動作について説明します。 オプティマイザーの動作の概要を知ることは、アプリケーション開発においてスキーマ定義やSQL文を考える上で役立ちます。
DoqueDBのデータベースは、表ごとにレコードファイルと索引ファイルなどから構成されます。 これらのファイルは、単体ではinsert、getのような単純な操作のみを提供しています。 オプティマイザーは、SQL文で指示されたデータ操作や問い合わせ操作を、各ファイルに対する操作の組み合わせに変換します。
一般に、あるSQL文を実行するためのファイル操作の組み合わせは複数あることがほとんどです。
以下ではこの組み合わせかたをアクセスプランまたは単にプランと呼ぶことにします。
オプティマイザーの処理では、考えられるアクセスプランから、できるだけ速く処理できるプランを選択することがポイントになります。
アプリケーション開発者が、与えた問い合わせがどのようなアクセスプランで処理されるかを知る方法は2つあります。
confファイルで指定するパラメーターに以下を追加します。
Plan_TraceOptimizationOutput <文字列>
パラメーターの値は文字列で、ログを出力するファイル名を指定します。
以下のパラメーターを加えると、アクセスプランの前に与えたSQL文を確認できます。
Statement_KeepSQLStatement "true" Server_PrintSQLStatement <文字列> Server_PrintParameter <文字列>
パラメーターの値にはPlan_TraceOptimizationOutputと同じファイル名を指定すると便利です。 パラメーターを変更した後は、DoqueDBを再起動しないと有効になりません。
EXPLAIN文によりクライアントからアクセスプランを確認できます。 EXPLAIN文は以下のように問い合わせのSQL文の前にEXPLAIN句を挿入することで使用します。
SQL> explain hint 'file' select * from TBL;
{Plan}
{retrieve TBL
sequential scan on RCD_TBL}
hint 'file'をつけると索引ファイルの使用状況が確認できます。
また、デフォルトではEXPLAIN文では問い合わせ自体を実行しません。問い合わせも実行させたいときはEXECUTE句をつけます。
SQL> explain execute hint 'file' select * from TBL;
この場合、最初のResultSetとしてアクセスプランが、次のResultSetとして問い合わせ結果が得られます。
以下の説明では、EXPLAIN文の実行結果でアクセスプランを例示します。
DoqueDBのオプティマイザーでは、主に以下のような観点で選択を行います。
以下でそれぞれの観点でどのようにアクセスプランが生成されるかについて少し説明します。
ここでは1つの表に対する問い合わせを考えます。
WHERE句は、一般に比較演算や文字列検索演算などの述語がAND、OR、NOTで結合された形式になります。 オプティマイザーは以下のようにしてWHERE句を処理する索引を決めます。
索引と結び付けられない述語が含まれる場合は、索引からの結果と組み合わせて最終結果を作ります。
以下で、AND、OR、NOTの処理について、例を挙げながら説明していきます。
例1：
select * from TBL where id > 10 and id < 20
idにはB木索引がついているものとします。
B木索引は比較演算のANDをまとめて処理できるので、索引ファイルをスキャンして、レコードファイルからすべての列値を取得する、というプランになります。
SQL>explain hint 'file' select * from TBL where id > 10 and id < 20;
{Plan}
{retrieve TBL
index scan on BTR_TBL_IDXid for
(TBL.id > 10 and TBL.id < 20)}
例2：
select * from TBL where id > 10 and text contains 'abc'
idにはB木索引が、textには全文索引がついているものとします。
それぞれの索引から得た結果をintersectし、レコードファイルから列値を取得する、というプランになります。
SQL>explain hint 'file' select * from TBL where id > 10 and text contains 'abc';
{Plan}
{retrieve TBL
intersect files
index scan on BTR_TBL_IDXid for
TBL.id > 10
index scan on FTS_TBL_IDXtext for
TBL.text contains abc}
例3：
select * from TBL where id > 10 and flag = 1
idにはB木索引がついていますが、flagにはついていないものとします。
索引から結果を得たらレコードファイルから列値を取得し、flagに関する条件に合致するもののみ結果に出力します。
SQL>explain hint 'file' select * from TBL where id > 10 and flag = 1;
{Plan}
{retrieve TBL
check predicate
TBL.flag = 1
index scan on BTR_TBL_IDXid for
TBL.id > 10}
例1：
select * from TBL where id > 10 or id < 20
idにはB木索引がついているものとします。
B木索引は比較演算のORをまとめて処理できるので、索引ファイルをスキャンして、レコードファイルからすべての列値を取得する、というプランになります。
SQL>explain hint 'file' select * from TBL where id < 10 or id > 20;
{Plan}
{retrieve TBL
index scan on BTR_TBL_IDXid for
(TBL.id < 10 or TBL.id > 20)}
例2：
select * from TBL where id > 10 or text contains 'abc'
idにはB木索引が、textには全文索引がついているものとします。
それぞれの索引から得た結果をunionし、レコードファイルから列値を取得する、というプランになります。
SQL>explain hint 'file' select * from TBL where id > 10 or text contains 'abc';
{Plan}
{retrieve TBL
union files
index scan on BTR_TBL_IDXid for
TBL.id > 10
index scan on FTS_TBL_IDXtext for
TBL.text contains abc}
select * from TBL where id > 10 or flag = 1
idにはB木索引がついていますが、flagにはついていないものとします。
この場合、まず索引ファイルから条件を満たすレコードのROWIDの集合を得ます。
次に、レコードファイルから1件ずつ取得し、上記ROWIDの集合に含まれるか検査します。
含まれなかった場合、索引が使えない条件を調べます。
このように、ORのオペランドに索引と結び付けられない述語がある場合、全件取得の必要があるため、すべて索引で処理できる場合に比べて効率が悪くなります。
LIMIT指定などで取得レコード数が制限できる場合は別ですが、ORのオペランドに来る条件はできるだけ索引が使えるものにするようにしましょう。
SQL>explain hint 'file' select * from TBL where id > 10 or flag = 1;
{Plan}
{retrieve TBL
check predicate
((check existence
index scan on BTR_TBL_IDXid for
TBL.id > 10)
or TBL.flag = 1)
sequential scan on RCD_TBL}
例1：
select * from TBL where id < 10 and not id = 2
idにはB木索引がついているものとします。
B木索引は比較演算との組み合わせの場合に限り、!=の処理ができるので、索引ファイルをスキャンして、レコードファイルからすべての列値を取得する、というプランになります。
SQL>explain hint 'file' select * from TBL where id < 10 and not id = 2;
{Plan}
{retrieve TBL
index scan on BTR_TBL_IDXid for
(TBL.id != 2 and TBL.id < 10)}
例2：
select * from TBL where id > 10 and not text contains 'abc'
idにはB木索引が、textには全文索引がついているものとします。
まず全文索引の結果をROWIDの集合として得ておきます。
次に、B木索引から得た結果のそれぞれについてROWIDが上記ROWIDの集合に含まれていないか調べ、含まれていないときのみレコードファイルから列値を取得する、というプランになります。
SQL>explain hint 'file' select * from TBL where id > 10 and not text contains 'abc';
{Plan}
{retrieve TBL
check predicate
(check nonexistence
index scan on FTS_TBL_IDXtext for
TBL.text contains abc)
index scan on BTR_TBL_IDXid for
TBL.id > 10}
例3：
select * from TBL where flag = 1 and not id = 10
idにはB木索引がついていますが、flagにはついていないものとします。
B木索引は単独で現れる!=は処理できないので、すべての検索述語で索引が使えないことになります。
つまり、レコードファイルから取得した1件ごとに条件を判定します。
SQL>explain hint 'file' select * from TBL where flag = 1 and not id = 10;
{Plan}
{retrieve TBL
check predicate
(TBL.id != 10 and TBL.flag = 1)
sequential scan on RCD_TBL}
例1：
select * from TBL where id < 10 or not id = 2
idにはB木索引がついているものとします。
ORの後の!=は、単独で現れるものと同じくB木索引では処理できません。
したがって、ORの例3と同様のアクセスプランになります。
SQL>explain hint 'file' select * from TL where id < 10 or not id = 2;
{Plan}
{retrieve TBL
check predicate
((check existence
index scan on BTR_TBL_IDXid for
TBL.id < 10)
or TBL.id != 2)
sequential scan on RCD_doc}
例2：
select * from TBL where id > 10 or not text contains 'abc'
idにはB木索引が、textには全文索引がついているものとします。
まずB木索引と全文索引のそれぞれの結果をROWIDの集合として得ておきます。
次にレコードファイルから1件ずつ取得し、ROWIDがB木索引から得られたROWIDの集合に含まれ、全文索引から得られたROWIDの集合に含まれない場合に結果とする、というプランになります。
SQL>explain hint 'file' select * from TBL where id > 10 or not text contains 'abc';
{Plan}
{retrieve TBL
check predicate
((check existence
index scan on BTR_TBL_IDXid for
TBL.id > 10)
or (check nonexistence
index scan on FTS_TBL_IDXtext for
TBL.text contains abc))
sequential scan on RCD_TBL}
例3：
select * from TBL where flag = 1 or not text contains 'abc'
textには全文索引がついていますが、flagにはついていないものとします。
まず全文索引から条件を満たすレコードのROWIDの集合を得ます。
次にレコードファイルから1件ずつ取得し、ROWIDが上記集合に含まれていなければ結果とし、含まれていればflag=1の条件を判定します。
SQL>explain hint 'file' select * from TBL where flag = 1 or not text contains 'abc';
{Plan}
{retrieve TBL
check predicate
((check nonexistence
index scan on FTS_TBL_IDXtext for
TBL.text contains abc)
and TBL.flag = 1)
sequential scan on RCD_TBL}
ここでは二つ以上の表を結合する問い合わせを考えます。
DoqueDBでは表の結合にあたってIndexed Join(索引を用いた結合)とNested Loop Join(索引を用いない結合)を用います。
結合される表が2つの場合、Indexed Joinが可能ならIndexed Joinが採用されます。 Indexed Joinでは、索引への入力となる件数が処理時間に大きく影響します。
たとえば、以下のように10万件入った表と10件入った表の結合を作る場合を考えます。
select * from TBL_100K, TBL_10 where TBL_100K.x = TBL_10.id
ここで、xおよびidにはどちらもB木索引がついているものとします。
このとき、結合順序としてはTBL_100K→TBL_10と、TBL_10→TBL_100Kの2種類があります。 10万件の表から先にスキャンする場合、TBL_10.idについている索引に対して10万回検索操作を実行することになります。 一方、10件の表から先にスキャンする場合、TBL_100K.xについている索引に対して10回だけ検索操作を実行することになります。
B木索引をたどるのにかかる時間は、簡単にいうと件数のlogにほぼ比例するので、1回の検索操作についていえば前者は後者の5倍速いはずです。 しかし、実行回数が1万倍多いので、結果として2000倍も遅い計算になります。 つまり、索引が使える場合は件数の少ない表から先にスキャンするのがいいといえます。
DoqueDBのオプティマイザーは、それぞれの表に指定されている条件から結果件数を推定し、索引に対する検索操作が小さくなる順序でアクセスプランを作ります。
結合される表が3つ以上になると、もう少し複雑になります。
たとえば、以下のように10万件、10件、20件の表を結合する問い合わせを考えます。
select * from TBL_100K, TBL_10, TBL_20
where TBL_100K.x = TBL_10.id and TBL_100K.y = TBL_20.id
TBL_20のid列にも索引がついているものとします。
このとき、結合順序としてはTBL_100K→TBL_10→TBL_20、TBL_100K→TBL_20→TBL_10、 TBL_10→TBL_100K→TBL_20、TBL_10→TBL_20→TBL_100K、 TBL_20→TBL_100K→TBL_10、TBL_20→TBL_10→TBL_100Kの6通りがあります。
DoqueDBのオプティマイザーは、中間結果をできるだけ小さくしようとします。 また、Indexed Joinが使える結合があればそれを先に処理しようとします。 中間結果を小さくするという観点ではTBL_10→TBL_20→TBL_100Kが一番よいのですが、最初の結合が直積になるため採用されません。この例では、TBL_10→TBL_100K→TBL_20が採用されます。
実は、直積を単純に避けるという方法は、場合によっては最適な順序を見落とすことになっています。 この例でも、10件と10万件の結合結果件数が多い場合、10件と20件の直積を作ってから10万件の表とIndexed Joinしたほうが速いことがあります。 今後見直しが行われるかもしれません。
問い合わせでORDER BYが指定されている場合を考えます。
この場合、指定された1つまたは複数の列に対して、昇順あるいは降順にソートされた結果を返す必要があります。 単純な実装では、すべての結果を溜めてからソートしたものを返すという実装になります。 しかし、特にLIMITが同時に指定されている場合など、たとえば10件の結果を得るために10万件をソートすることになりかねず、効率が悪くなる可能性があります。
ORDER BYに指定された列に索引が定義されている場合、索引によってこの処理を高速に実行できることがあります。 ただし、WHERE句の条件により十分に件数が絞られることが推定される場合は、単純な実装が選択されます。 あくまでもアクセスプランの選択肢に加わるだけです。
以下で適用可能な例を見ていきます。
ORDER BYで指定された列にB木索引が定義されている場合、さらに以下のいずれかの条件を満たすと、索引を使ったORDER BY処理ができます。
例として以下のスキーマを用います。
create table TBL (
f_key int,
f_not_null int not null,
f_nullable int,
f_allrows int,
f_comb0 int,
f_comb1 int,
f_text ntext,
primary key(f_key)
);
create index IDX_f_not_null on TBL(f_not_null); -- not null制約つきの列に索引
create index IDX_f_nullable on TBL(f_nullable); -- not null制約のない列に索引
create all rows index IDX_f_allrows on TBL(f_allrows); -- all rows索引の定義
create index IDX_f_comb on TBL(f_comb0, f_comb1); -- 複合索引の定義
create fulltext index IDX_f_text on TBL(f_text); -- 全文索引の定義
それぞれのプランは以下のようになります。
SQL> explain select * from TBL order by f_not_null;
{Plan}
{retrieve TBL
sequential scan on BTR_IDX_f_not_null for
order by f_not_null asc}
SQL> select * from TBL order by f_key desc;
{Plan}
{retrieve TBL
sequential scan on BTR_TBL_$$PrimaryKey for
order by f_key desc}
SQL> select * from TBL where f_nullable > 10 order by f_nullable;
{Plan}
{retrieve TBL
index scan on BTR_IDX_f_nullable for
TBL.f_nullable > 10,
order by f_nullable asc}
SQL> select * from TBL order by f_allrows;
{Plan}
{retrieve TBL
sequential scan on BTR_IDX_f_allrows for
order by f_allrows asc}
SQL> select * from TBL where f_comb0 = 100 order by f_comb1;
{Plan}
{retrieve TBL
index scan on BTR_IDX_f_comb for
TBL.f_comb0 = 100,
order by f_comb1 asc}
ORDER BYで指定された列が2つ以上あり、そのすべてが同じ複合索引のキーである場合、さらに以下の条件をすべて満たすと、索引を使ったORDER BY処理ができます。
例：
SQL> explain hint 'file' select * from TBL where f_comb0 > 100 order by f_comb0, f_comb1;
{Plan}
{retrieve TBL
index scan on BTR_IDX_f_comb for
TBL.f_comb0 > 100,
order by f_comb0 asc, f_comb1 asc}
ORDER BYで指定されたキーが全文検索のスコア値(score(data)など)の場合、常に索引を使った処理が候補になります。
例：
SQL> select * from TBL where f_text contains 'keyword' order by score(f_text) desc;
{Plan}
{retrieve TBL
index scan on FTS_IDX_f_text for
TBL.f_text contains keyword,
order by score(f_text) desc}
ORDER BYに2つ以上のキーが指定されていて、その一部だけに索引がついている場合、さらに以下の条件をすべて満たすと、索引によってソート対象の件数を絞ることができます。
この場合、以下の手順でソートが実行されます。
このようにすることで、LIMIT値を少し超える件数まで取得したところでソート可能になり、単純な実装に比べて高速に処理できるようになります。
例：
SQL> select * from TBL order by f_not_null, f_nullable, f_allrows limit 10;
{Plan}
{limit 10
<-- sort order by TBL.f_not_null asc, TBL.f_nullable asc, TBL.f_allrows asc limit
<-- retrieve TBL
sequential scan on BTR_IDX_f_not_null for
order by f_not_null asc}
この例ではf_not_nullについている索引の順に取得し、10件目まで取得したときのf_not_nullの値を記録し、11件目以降でf_not_nullの値が変わったら取得をやめ、f_not_null,f_nullable,f_allrowsをキーとしたソートを実施します。
特殊なケースにおける問い合わせの変換について説明します。
EXISTSを用いた副問い合わせは、結合に変換することで最適な結合順序を探索することができます。 副問い合わせ内の表が結合順序の最後以外に現れた場合、結果はFROM句に並べられた表のROWIDの組み合わせについてDISTINCTを取る必要があります。
例として以下のスキーマを用います。
create table TBL0 (
f_key int,
f_link_TBL1 int,
f_text ntext,
primary key(f_key)
);
create index IDX_f_link_TBL1 on TBL0(f_link_TBL1);
create table TBL1 (
g_key int,
g_text ntext,
primary key(g_key)
);
ここで、以下のSQL文を実行します。
select * from TBL0 where
exists (select * from TBL1 where f_link_TBL1 = g_key);
TBL0の件数が少ない場合は、そのままEXISTSの処理を行うことができます。
SQL> select * from TBL0 where
exists (select * from TBL1 where f_link_TBL1 = g_key);
{Plan}
{exists join
<-- retrieve TBL0
sequential scan on RCD_TBL0
<-- retrieve TBL1
index fetch on BTR_TBL1_$$PrimaryKey for
TBL0.f_link_TBL1 = TBL1.g_key}
TBL0の件数が多くなると、TBL1→TBL0の順に結合し、DISTINCTを取ったほうが速くなります。
SQL> explain hint 'file' select * from TBL0 where
exists (select * from TBL1 where f_link_TBL1 = g_key);
{Plan}
{distinct TBL0.ROWID
<-- index join
<-- retrieve TBL1
sequential scan on BTR_TBL1_$$PrimaryKey
<-- retrieve TBL0
index fetch on BTR_IDX_f_link_TBL1 for
TBL0.f_link_TBL1 = TBL1.g_key}
NOTを用いた条件は、同等のNOTを用いない述語に変換できることがあります。 変換を試みられるのは以下の述語です。
例として前述のスキーマを用います。
SQL> explain hint 'file' select * from TBL0 where not f_key < 10;
{Plan}
{retrieve TBL0
index scan on BTR_TBL0_$$PrimaryKey for
TBL0.f_key >= 10}
SQL> explain hint 'file' select * from TBL0 where not (f_key < 10 and f_key > 0);
{Plan}
{retrieve TBL0
index scan on BTR_TBL0_$$PrimaryKey for
(TBL0.f_key >= 10 or TBL0.f_key <= 0)}
SQL> explain hint 'file' select * from TBL0 where not (f_key < 10 or f_link_TBL1 > 100);
{Plan}
{retrieve TBL0
intersect files
index scan on BTR_TBL0_$$PrimaryKey for
TBL0.f_key >= 10
index scan on BTR_IDX_f_link_TBL1 for
TBL0.f_link_TBL1 <= 100}
SQL> explain hint 'file' select * from TBL0 where not (f_key < 10 or f_text not like '%x%');
{Plan}
{retrieve TBL0
check predicate
TBL0.f_text like %x%
index scan on BTR_TBL0_$$PrimaryKey for
TBL0.f_key >= 10}
ORのオペランドにある述語が2つ以上の表にまたがる場合、そのまま評価しようとするといずれかの表を全件取得する必要が生じます。 ORのオペランドのそれぞれを適用した結果を合成した結果を用いることで、より効率的な結合処理ができる可能性があります。
例として以下のスキーマを用います。
create table TBL2 (
f_key int,
f_text ntext,
primary key(f_key)
);
create fulltext index IDX_TBL2_text on TBL2(f_text);
create table TBL3 (
g_key int,
g_text ntext,
primary key(g_key)
);
create fulltext index IDX_TBL3_text on TBL3(g_text);
例1：別々の表に対する全文検索のOR
SQL> explain hint 'file' select * from TBL2, TBL3 where f_key = g_key
and (f_text contains 'key' or g_text contains 'word');
{Plan}
{union
<-- index join
<-- retrieve TBL2
index scan on FTS_IDX_TBL2_text for
TBL2.f_text contains key
<-- retrieve TBL3
index fetch on BTR_TBL3_$$PrimaryKey for
TBL2.f_key = TBL3.g_key
<-- index join
<-- retrieve TBL3
index scan on FTS_IDX_TBL3_text for
TBL3.g_text contains word
<-- retrieve TBL2
index fetch on BTR_TBL2_$$PrimaryKey for
TBL2.f_key = TBL3.g_key}
例2：普通の条件とEXISTSのOR
普通の検索とEXISTSの結合になります。
SQL> explain hint 'file' select * from TBL2 where f_text contains 'key' or
exists (select * from TBL3 where f_key = g_key and g_text contains 'word');
{Plan}
{union
<-- retrieve TBL2
index scan on FTS_IDX_TBL2_text for
TBL2.f_text contains key
<-- distinct TBL2.ROWID
<-- index join
<-- retrieve TBL3
index scan on FTS_IDX_TBL3_text for
TBL3.g_text contains word
<-- retrieve TBL2
index fetch on BTR_TBL2_$$PrimaryKey for
TBL2.f_key = TBL3.g_key}
Copyright (c) 2023 Ricoh Company, Ltd. All rights reserved.