DEIM Forum 2023 2a-1-4

近似的問合せ処理におけるシノプシス構築の高速化
倪天嘉†杉浦 健人†

石川 佳治†

陸可鏡†† 東海国立大学機構名古屋大学大学院情報学研究科 〒 464–8603 愛知県名古屋市千種区不老町
Email: {ni, lu}@db.is.i.nagoya-u.ac.jp, {sugiura, ishikawa}@i.nagoya-u.ac.jp
あらまし 巨大なデータに基づく問合せを効率的に実行するための技術として，近似的問合せ処理（approximate query

processing, AQP）がよく使われている．AQP ではシノプシス（synopsis）を用いた効率的な問合せ処理が行われる．シノプシスとは，対象となるデータをコンパクトに集約したデータを指す一般的な概念であり，さまざまなアプローチがある．近年提案された BAQ（bounded approximate query processing）は元テーブルの適切な部分集合をシノプシス
として保存し，近似誤差がユーザの指定した閾値以下であることを保証する近似的問合せ処理フレームワークである．
しかし，BAQ では処理対象となる各数値属性に対してデータをソートする必要があり，数値属性を多数含むようなテーブルのシノプシス構築には時間がかかる．本稿では最小化シノプシスの構築の高速化に焦点を当て既存研究 BAQを改善し，シノプシスの定義とアルゴリズムを検討する．
キーワード 近似的問合せ処理，問合せ処理，集計計算．
は改善の余地がある．BAQ± にシノプシスの構築は BAQ と同

1 はじめに巨大なデータに基づく問合せを効率的に実行するための技術として，近似的問合せ処理（approximate query processing, AQP）
がよく使われている [1–3]．AQP ではシノプシス（synopsis）を用いた効率的な問合せ処理が行われる．シノプシスとは，対象となるデータをコンパクトに集約したデータを指す一般的な概念であり，さまざまなアプローチがある [4–6]．スキャンが一定時間に完了できない大規模なデータベースを対象として，AQP
は分析問合せの結果の精度と問合せ処理の待ち時間の間のトレードオフを提供する．

2019 年に Li ら [7] は，一部のデータをシノプシスとして保様に，部分シノプシスの構築と統合シノプシスへの統合の 2 手
順に分けられる．部分シノプシスの構築はワークロードの各問合せを対応するため，ワークロードの問合せ数が増えるほど構築時間が増大する．加えて，統合シノプシスへの計算では元テーブルと各部分シノプシスを複数回スキャンする必要がある
ため，最小化のシノプシスの構築高速化が問題になる．本稿では以上の問題を解決するために，BAQ を元にしてシノプシス構
築の高速化に焦点を当て BAQ± の改善アイデアおよび評価実験について述べる．

2 BAQ±

存する近似的問合せ処理フレームワーク（BAQ）を提案した．

BAQ± は BAQ に基づいて厳密な誤差保証がある高効率な近BAQ では，ユーザが設定する誤差の閾値と典型的なワークロー

似的問合せ処理手法を提案した．BAQ± では高精度高効率な近ドを示す問合せ集合を用いてオフライン処理でデータベース

似的問合せ処理を目標として，数値属性のバケット生成手法とからシノプシスを生成し，そのシノプシスを使用して効率的に

オンラインの近似処理手法を改善した．2. 3 節では数値属性のオンライン問合せに回答する．他の要約データを使用するアプ

バケット分割および 2. 4 節ではオンラインでの問合せ処理につローチ（サンプリング，分位数など [4, 8]）と比べて，BAQ は一いてそれぞれ述べる．

般的な集計関数（COUNT，SUM，AVG，MIN，MAX）に対して効率的に誤差を保証できる特徴がある．元々提案された BAQには正の数値データしか扱えないなどの問題点があったため，
著者らはそれらの問題を改善した BAQ± を先行研究として提案した [9]．BAQ± では BAQ を元にしてシノプシスの構成要素であるバケット（数値属性の値をグループ化したもの）の生成
手法を改善し，正負両方を含む数値属性においても誤差保証を提供すると共に，バケット自体の生成数を減少させることで最終的なシノプシスのサイズも削減した．これにより，元の BAQに比べより多様な近似問合せに対応するだけでなく，オンラインの近似処理においても実行時間の削減を実現した．
しかし，BAQ± において誤差保証およびオンラインの問合せ
処理時間の問題を改善したが，シノプシスの構築時間について

2. 1 対象問合せ
BAQ± では以下の演算を用いた OLAP 問合せを想定する．
•

COUNT，MIN，MAX，SUM，および AVG での集約•

一つ以上のカテゴリ属性に対する =，≠ と集約計算•

一つ以上の数値属性に対する =，≠，>，>= ，<，および<= を用いた条件での選択と集約計算• グルーピング
2. 2 相 対 誤 差
BAQ± では，BAQ と同様に与えられた問合せに対し，集約結果の真値と近似値との誤差 𝑒𝑟𝑟 として相対誤差を用いる．2 つの値 𝑥, 𝑦 ∈ 𝑅 の相対誤差を以下の式で定める．

表 1 入力テーブル “product”

ID nameO

条件を部分的に満たすバケット

条件を満たさないバケット

条件を満たすバケット
図 1 バケットの分類（1000 < price < 2000 の場合）

𝑒𝑟𝑟 (𝑥, 𝑦) =|
 |𝑥−𝑦

𝜖

 𝑥−𝑦
 𝑥

category

revenue
1,330

price

2,000

1,000

(𝑥 = 0)(1)

1jacket clothes

2

shirt

clothes998

3jacket clothes

3,120

4

pant

1,320

5

jacket clothes

1,370

6

fork

1,000

7

jacket clothes

1,304

8

shirt

1,002

clothes
kitchenware
clothes(otherwise)
表 2 BAQ± で 𝜋2 = {name, revenue} のシノプシス.

ただし，𝑥 を真値，𝑦 を近似値とし，𝜖 ∈ 𝑅 を非常に小さな正の値とする．

2. 3 数値属性のバケット分割
BAQ± では，BAQ と同様にユーザがワークロードとなる問合せの集合を用意することが想定されており，与えられた問合せ
集合の情報を使用してシノプシスを構築する．各問合せが問合

namerevenue (min., max., mean) SF

pant(1,320, 1,320, 1,320)

1

fork

(1,000, 1,000, 1,000)

1jacket (1,300, 1,370, 1,333)

3

jacket (3,120, 3,120, 3,120)

1

shirt

2

(998, 1,002, 1,000)

せの列集約 (QCS) 𝑞 に変換されて，この QCS を基に各問合せに対応した部分シノプシス 𝑆𝑖 が構築される．なお，他の QCS

属性の選択がある問合せの場合，数値属性に関する各バケッの部分集合となるようなものについては，上位集合となる QCS

トは条件を満たす，部分的に条件を満たすおよび条件を満たから生成されたシノプシスによって問合せへの回答が可能となさないの 3 通りに分けられる．図 1 で，属性 “price” と条件るため，部分シノプシスの生成は行われない．QCS 𝑞 がカテゴ

1000 < price < 2000 の例で説明する．問合せの結果として，

リー属性のみを持つ場合，BAQ± では BAQ と同様にテーブル

条件を満たす場合と部分的に条件を満たす場合の結果を返す．

内のタプルを 𝑞 に含まれるカテゴリ属性でグループ化すること

BAQ では部分的に条件を満たすバケット内のタプルが一様分布によって構築される．QCS 𝑞 が数値属性を含む場合，BAQ± でに従って存在することを仮定しているため，実際には厳密な誤はバケット 𝑏 について，式 (2) が満たされるようにする．

差範囲を保証できない．BAQ に解決されない厳密な誤差範囲を

𝑒𝑟𝑟 (min 𝑏, 𝑏) <= 𝛿 ∧ 𝑒𝑟𝑟 (max 𝑏, 𝑏) <=𝛿

提供するために，提案手法では一様分布の仮定を置かず，条件(2)

まず，QCS 𝑞 にカテゴリ属性がある場合，テーブル 𝑇 のタプ
ルをカテゴリ属性でグループ化する．次に，各グループの数値
属性の値を昇順にソートする．ソートされた値を式 (2) を満たすバケット 𝑏 ⊆ 𝑅 に割り当てる。表 1 で，𝑞 2 = {name, revenue}
および 𝛿 = 0.05 を例として説明する．BAQ では{1,300, 1,320,

1,370}を jacket グループにまとめることはできないが，BAQ±
では以下のように式 (2) を満たすために単一のバケットとして生成できる．

を部分的に満たすバケットが持ちうる誤差の最大値からシノプ
シスのみで問合せに回答可能か判定し，誤差を保証できない場
合のみ元テーブルを使用する．数値属性 𝐴 に対する選択問合せ
では，条件を完全に満たすバケットについては，以下の関数で結果を返す．この場合，誤差は発生しない．

•

COUNT(∗) → SUM(SF)

SUM( 𝐴) → SUM(mean( 𝐴) · SF)
SUM( 𝐴)• AVG( 𝐴) →COUNT(∗)
各集約関数について 1 つ以上の数値属性に対する選択・グルー•

ピングを含む問合せについては， [9] の分析により，以上の提𝑏 ' 1333

案手法は BAQ より小さい誤差となる．

𝑒𝑟𝑟 (min 𝑏, 𝑏) ' 𝑒𝑟𝑟 (1300, 1333) ' 0.025

一方で，部分的に条件を満たすバケットについて誤差保証の𝑒𝑟𝑟 (max 𝑏, 𝑏) ' 𝑒𝑟𝑟 (1370, 1333) ' 0.027

条件を満たす場合以下の関数で結果を返す． [10] において，各集約関数について部分的に条件を満たすバケットの集約値を計

最終的に表 2 のシノプシスを構築する．

BAQ と比較して，BAQ± ではバケットの対応するデータの範算しやすい近似値で返した際の誤差がしきい値以内となる条件
について検討する．

囲はより大きくなる．加えて，BAQ± では 2 つの数値属性に対•する選択やグルーピングを含む問合せをサポートする．なお，

SUM( 𝐴) → (SUM(mean( 𝐴) · SF))/2
SUM( 𝐴)
AVG( 𝐴) → ()/2
COUNT(∗)
例として，表 3 のシノプシスについて以下の問合せがある．

負の値に対するバケットも同様の方法で生成し，値がゼロのタ
プルが存在する場合はゼロのみのバケットも追加で生成する．

2. 4 問合せ処理
BAQ± では，主にシノプシスを用いて結果を計算する．数値••

COUNT(∗) → SUM(SF)/2

表 3 BAQ± で統合シノプシス.

namecategory

revenue (min., max., mean)

SF1

SF2

jacketclothes(1,300, 1,370, 1,333)

5

3

shirt

clothes(998, 1,002, 1,000)

22jacketclothes(3,120, 3,120, 3,120)

0

1

pant

clothes(1,320, 1,320, 1,320)

0

1

fork

kitchenware(1,000, 1,000, 1,000)

1

1

ID: 0

ID: −1−𝜖(1 + 𝛿)

ID: 2

ID: 1

-𝜖 0 𝜖𝜖(1 + 𝛿)𝜖 1 + 𝛿 2 temperature

図 2 バケットの再定義
表 4 改善アイデアで 𝑞 のシノプシス

SELECT name, SUM(revenue)

namecategory

revenue.ID SF

FROM productshirt

clothes142

2

WHERE revenue > 1300

fork

kitchenware 142

1

GROUP BY namejacket clothes

148

2“shirt” と “fork” グループは条件を満たさない．“pant” グループpantclothes148

1

は条件を満たすバケットのみがあるので，以下の関数で 1,320

jacket clothes

149

1

jacket clothes

1651の結果を得る．

•

SUM(revenue) → SUM(mean · SF2 ).

“jacket” グループには条件を満たすバケットと部分的に条件をいてバケットは相対誤差が閾値 𝛿 未満となる値の集合であり，満たすバケットがあるので，BAQ± はシノプシスを使用してそ言い換えれば最小値と最大値の相対誤差が 𝛿 未満となるよう

れぞれ計算を行う．条件を満たすバケットは 3,120，部分的に条な値の集合である．つまり最小値の値が決定した時点でそのバ件を満たすバケットは 3,999 の集計結果がある．結果は誤差保

ケットの最大値も決まるため，BAQ ではバケット生成の起点と証条件を満たす場合，BAQ± は部分的に条件を満たすバケット

してある数値属性の最小値を求め，そこから昇順に値を処理すについて以下の関数で計算し，合計値 5,120 を “jacket” グルーることでバケットを生成する．

プの結果として返す．

•

SUM(revenue) → SUM(mean · SF2 )/2.

このようなソート処理を除くために，提案手法では各数値
属性 𝐴𝑖 に対して最小単位 𝜖 𝑖 を導入する．つまり，バケット生
成の起点を入力データに応じて動的に決定するのではなく，最3 シノプシスの再定義による構築高速化
本章ではシノプシス構築を高速化するためにまずシノプシスの定義自体を見直し，新たな定義に応じた構築アルゴリズムを提案する．

BAQ± と BAQ におけるシノプシス構築は部分シノプシスの小単位を起点とすることでバケット分割を静的に行う．例として，図 2 にこのバケット分割の概略図を示す．まず最小単位として 𝜖 𝑖 を持つ数値属性 𝐴𝑖 に対し，絶対値が最小単位未満の値（ |𝑎 𝑖 | < 𝜖 𝑖 ）を ID 0 のバケットとしてまとめる．次に，正の値を含むバケットを以下の式によって ID 𝑗 にまとめる．

[𝜖𝑖 (1 + 𝛿) 𝑗−1 , 𝜖 𝑖 (1 + 𝛿) 𝑗 )構築と統合シノプシスへの統合の 2 手順に分けられるが，特に部分シノプシスの構築がボトルネックとなる．部分シノプシスの構築は各ワークロード問合せに対して必要となるため，ワー(3)

同様に負の値を含むバケットは ID − 𝑗 としてまとめる．

(−𝜖 𝑖 (1 + 𝛿) 𝑗 , −𝜖 𝑖 (1 + 𝛿) 𝑗−1 ]クロードとなる問合せが増えるほど処理時間が増大する．特に，(4)全ての QCS がカテゴリ属性しか含まない場合は元テーブルを一度走査するだけで部分シノプシスを構築できるが，数値属性

この分割において最小単位は式 (1) における 𝜖 に対応し，言いを含む場合はソート処理のために複数回の走査が必要となる．

換えればゼロとみなせる閾値を表す．本研究では各最小単位は

数値属性のソート処理はカテゴリ属性の各グループ，数値属性

ユーザによって指定されることを想定するが，背景知識に基づが複数含まれる場合は各バケットについても行う必要があるた

き最小単位を決定するのは困難でないと考えられるため，そのめ，多数のソート処理が必要となる．

負荷は問題にならないと考える．

この問題を解決するために，3. 1 節では数値属性のバケット

このバケット分割の利点として，ある数値属性の値 𝑎 𝑖 ∈ 𝐴𝑖

化を再定義することでソート処理を排除する手法を提案する．

から対応するバケット ID を以下の式で求められる点が挙げら

更に，3. 2 節と 3. 3 節では再定義したバケットに基づくシノプ

れる．

シスの構築手法およびシノプシスの最小化についてそれぞれ述べる．

3. 1 バケットの再定義
|𝑎 𝑖 |
𝑗 = sgn 𝑎 𝑖 log1+ 𝛿𝜖𝑖(5)なお，sgn は与えた値がゼロのときは 0，正負いずれかの場合は対応する符号（+1 or −1）を返す符号関数である．つまり，元BAQ においてソート処理が必要となるのは，バケット生成のテーブルに含まれる各数値属性の値は静的にバケット化されたために各数値属性の最小値が必要となるためである．BAQ にお

ID へ変換でき，後述するようにそれに応じたシノプシスの構築が可能となる．

3. 2 シノプシスの構築改善したバケット定義を用いたシノプシス構築について，ま表 5 ワークロードに {name, category} および {revenue} 属性集合がある場合

ずベースラインとして単純な手法を述べる．このベースライン

namecategory

revenue.ID SF1

では BAQ のようなワークロード問合せを用いず，各数値属性

shirt

clothes142

23の最小単位のみを用いて汎用的なシノプシスを構築する．

fork

kitchenware 148

13

ベースライン手法では元テーブルのタプルを順に走査し，各数値属性の値を上述した方法でバケット ID に変換したものを

SF2

jacket clothes

149

4

1

pant

165

1

1

clothes

レコードとしてシノプシスへ挿入ないし更新する．このとき，挿入時は対応する SF を 1 に設定し，更新時は 1 ずつ加算する

具体的には，アルゴリズム 1 により，ワークロード問合せにことで各レコードの SF を計算する．例えば元テーブルは表 1，

おいて同時に出現しない属性集合を確認する．バケット ID が誤差の閾値は 𝛿 = 0.05，属性 “revenue” の最小単位が 1 である

計算されたデータを 𝑇 とする．残り集合と属性を共通しない

とき，表 4 のシノプシスが構築される．つまり，ベースライン

QCS 集合 𝑞 で構成される 𝑄 およびデータ 𝑇 を入力データとし，

手法ではバケット ID へ変換された数値属性をカテゴリ属性とシノプシス 𝑆 を初期化する（1 行目）．続いて，順番に 𝑇 のタみなすことで，全属性を用いた Group By による集約を行ってプルを各 QCS 𝑞 によるシノプシス 𝑆 へ追加する（2–3 行目）．

いると言える．

シノプシス 𝑆 にレコード 𝑟 の 𝜋𝑞 値がタプル 𝑡 の 𝜋𝑞 値と同じ場

ベースライン手法は単純な手法であるが，構築時間を BAQ合，対応する SF を 1 増加させる（4–6 行目）．共通しない属性

よりも大きく削減できる．構築するシノプシスにおいて全属性，が存在それば，対応する 𝜋𝑞0 を持つレコードの 𝜋𝑞 は NULL のつまりカテゴリ属性および変換されたバケット ID の組合せは

場合 1 つのレコードへ更新する（7–11 行目）．タプル 𝑡 の 𝜋𝑞一意となるため，レコードの挿入ないし更新処理は索引を用い値がシノプシス 𝑆 に存在しない場合，シノプシス 𝑆 に 𝜋𝑞 値とることでレコードの総数 𝑀 に対して 𝑂 (𝑀) で行える．つまり，

𝑆𝐹 = 1 を追加する（12–14 行目）．

元テーブルのタプル数が 𝑁 の場合 𝑂 (𝑁 log 𝑀) でシノプシスを構築できる．

例として，表 1 において，2 つのワークロード問合せに対応
する QCS 𝜋1 = {name, category} と 𝜋2 = {revenue} が与えられ更に，提案手法はシノプシスの維持管理においても優れた性たとする．QCS 𝜋1 と 𝜋2 は共通する属性を持たないため，そ質を持つ．上記の構築処理は単純な集計処理とみなせるため，れぞれに所属する属性が同時に問合せで用いられることはな

分割統治法によって用意に並列化可能である．加えて，BAQ でい．つまり，シノプシス内において各 QCS に対応する列は独は元テーブルの変更（挿入ないし更新）によって最悪の場合シ立に SF を設定できる．具体的には，𝜋1 は{ (shit, clothes), (fork,

ノプシスの再構築が必要となるのに対し，提案手法は差分更新

kitchenware), (jacket, clothes), (pant, clothes) }の組合せ，𝜋2 は{のみで変更に対応できる．これはバケット ID の存在によって142, 148, 149, 165 }についてのみ SF を設定できればよく，それ変更の影響が及ぶレコードを一意に特定できるためであり，変ぞれを跨ぐ組合せについては無視できる．この点に基づき最小更の発生するレコードを更新するのみでシノプシスも元テーブ化することで，シノプシスのレコード数は表 5 まで削減できる．

ルの変更に追従できる．

3. 3 シノプシスの最小化

ただし，異なる 𝜋 のサイズには大きな差があるので，シノプ
シスの最小化問題に最適解を求めるのは非現実的になる．本研
究では誤差を保証できる近似手法について検討している．

上述したベースライン手法は単純かつ高速にシノプシスを構築できる一方，構築されるシノプシスのサイズは BAQ よりも

4 実験および評価大きくなる．ベースライン手法はバケット ID を含む全カテゴ
リ属性の組合せによってシノプシスのレコードを表現するため，本章では，提案手法に関する実装と評価する．BAQ± および属性数が多い場合，構築されるシノプシスは近似処理に用いる

BAQ に対し，生成したシノプシスのサイズおよびオフラインのには大きくなりすぎる恐れがある．また，全属性の組合せを考

シノプシス生成時間の 2 点で比較する．

えることでレコードは細分化されるため，実際の問合せ処理に

4. 1 準おいて不要な集約が発生することも考えられる．
そこで，BAQ± と同様にワークロード問合せの存在を想定し，シノプシスを最小化する手法について提案する．提案手法はBAQ と同様に各 QCS 集合 𝑞 に応じてレコード数 𝑆𝐹𝑞 を設定する．しかし，ワークロード問合せにおいて同時に出現しない属性集合を定義する．提案手法の基本アイデアでは，元テーブルのタプルを順に走査し，シノプシス内で各 QCS に対応する列
を順番に埋める．シノプシスに NULL など空きがあるレコードが存在すればタプルの対応値で更新する．シノプシスのレコー
ドに空きがない場合，新規レコードとして挿入する．

備a ) データセット
本研究では 2 つのデータセットを使用した．1 つ目は 7 列（6つのカテゴリ列と 1 つの数値列）を持つ Kaggle の temperature
データセットである．この 280 万レコードがあるデータセットには，321 個都市の 36 年間の気温の統計が含まれている．2 つ目はよく知られている TPC-H ベンチマークからの scale=1 の900 万のレコードを含むデータセットであり，4. 2 節の実験では 4 列（3 つのカテゴリ列と 1 つの数値列）の orders テーブルを使用する．

Input: 𝑇 , 𝑄// 元テーブル 𝑇 と 𝑇 の QCS

Output: 𝑆// 最小化されるシノプシス

1

𝑆←∅

2

foreach 𝑡 ∈ 𝑇 do

3

Synopsis size [KB]

Algorithm 1: GenerateSynopsis(𝑇, 𝑄)

300

提案手法

200

BAQ±(greedy)

100

BAQ(greedy)

00.05

foreach 𝑞 ∈ 𝑄 do// シノプシスに 𝑇 の QCS を確認
if ∃𝑟 ∈ 𝑆, 𝜋𝑞 (𝑟 ) = 𝜋𝑞 (𝑡) then5

𝑟 の 𝑆𝐹𝑞 を 1 増やす

6continue

4. 2. 1 シノプシスサイズ// 次の QCS// 他のシノプシスに存在しない QCS を確認
7

foreach 𝑞0 ∈ 𝑄 \ 𝑞 do// |𝑞 ∩ 𝑞0 | の降順で QCS を確認

8

if ∃𝑟 ∈ 𝑆, ( 𝜋𝑞∩𝑞0 (𝑟 ) = 𝜋𝑞∩𝑞0 (𝑡)∧ ∀𝑎 ∈ 𝜋𝑞\𝑞0 (𝑟 ), 𝑎 = 𝑁 𝑈 𝐿𝐿) then9

𝜋𝑞\𝑞0 (𝑡) で 𝑎 ∈ 𝜋𝑞\𝑞0 (𝑟 ) を更新

10

𝑟 の 𝑆𝐹𝑞 を 1 に設定

11

break

提案手法，BAQ± と BAQ で生成したシノプシスのサイズの実験結果を図 3 と図 4 に示す．

2000
1500
1000
500
0
0.05

if 𝑟 ∈ 𝑆, 𝜋𝑞 (𝑟 ) = 𝜋𝑞 (𝑡) then13

𝜋𝑞 (𝑡) で 𝑟 を 𝑆 に挿入

14

𝑟 の 𝑆𝐹𝑞 を 1 に設定

提案手法
BAQ±(greedy)
BAQ(greedy)
BAQ±(scan)
0.1 0.15 0.2 0.25
Error bound: 𝛿BAQ(scan)

図 4 Temperature に関するシノプシスのサイズ// シノプシスに 𝑇 の QCS がない場合タプルを追加
12

BAQ(scan)

図 3 TPC-H に関するシノプシスのサイズ

Synopsis size [KB]4

BAQ±(scan)
0.1 0.15 0.2 0.25
Error bound: 𝛿

既存手法が貪欲的な手法でシノプシスを生成する場合，orders
データについて提案手法のシノプシスのサイズは BAQ± に対して 56–95%，temperature の場合が 81–95%となっている．BAQ
に対して orders データの場合が 50–69%，temperature の場合が66–72%のサイズでシノプシスを構築できる．既存手法がスキャb) 問 合 せンベースの手法でシノプシス構築する場合，orders データを使実験のため，各データセットについて 310 個の問合せを生用するとき提案手法のシノプシスのサイズは BAQ± の 45–60%，

成した．これには，選択条件がない MIN/MAX 問合せ 2 個，

temperature の場合が 71–95%になった．BAQ より orders データ

SUM/AVG 問合せ 2 個，条件がカテゴリ属性のみの COUNT 問を利用するときは 37–45%，temperature のデータで 59–66%の合せ 50 個，MIN/MAX 問合せ 50 個，SUM/AVG 問合せ 50 個，

サイズでシノプシスを生成できる．

選択条件に数値属性を含む COUNT 問合せ 52 個，MIN/MAX

以下の分析が行える．提案手法は，実際の問合せ処理におい

問合せ 52 個，SUM/AVG 問合せ 52 個である．以上の 310 個のて必要な集約のみ考慮してシノプシスを生成する．シノプシス

問合せ集合によりオフラインにシノプシスを生成して，シノプに各 QCS 対応する 𝑝𝑖 の数に最大数を 𝑀 𝜋 とし，提案手法はシスのサイズと生成時間を評価する．加えて，各データについ

各 QCS に対応する列を順番に埋めるため，シノプシス全体のて同時に問合せしない属性集合を設定した．共通しない属性

レコード数は 𝑀 𝜋 である．しかし BAQ± および BAQ では，複集合は orders データについて{ (status, priority, price), (clerk) }，数の部分シノプシスに関して元テーブルのタプルを順に走査しtemperature データについて{(region, city, temperature),(country,

統合シノプシスのレコードとして保存するため，レコード数はyear) }で定義した．各数値属性の 𝜖 を 0.1 とする．

𝑀 𝜋 より大きい可能性が高い．さらに，誤差の限界を増加させc) 評 価 項 目

ると，各バケット ID の範囲が式 (2) により広くになるため，シ

提案手法と既存手法を 2 つの角度から比較する：（1）シノプノプシスのサイズが減少する．

シスのサイズ，（2）オフラインのシノプシスの生成時間（分）．

4. 2. 2 シノプシス生成時間

評価実験では，提案手法，BAQ± と BAQ をそれぞれ 30 回実行

オフラインにシノプシスを生成する時間について，orders とし，平均値を結果とする．既存手法 BAQ± および BAQ では，

temperature データセットに対する計測結果を図 5 と図 6 に示す．

部分シノプシスの構築時間および統合シノプシスの生成時間の既存研究 BAQ± と BAQ では，スキャンベースの手法および貪
欲的な手法で統合シノプシスを生成し，評価する．

4. 2 誤差上限に対する性能比較
誤差限界 𝛿 を 0.05，0.1，0.15，0.2，0.25 を設定して，提案
手法と BAQ±，BAQ を比較する．

Construction time[minutes]

合計値をオフラインのシノプシスの生成時間とする．加えて，

300

提案手法

200

BAQ±(greedy)

100

BAQ(greedy)00.05

BAQ±(scan)
0.1 0.15 0.2 0.25
Error bound: 𝛿BAQ(scan)

図 5 TPC-H に関するオフラインの生成時間

Construction time[minutes]

800
600
400
200
0
0.05

0.1 0.15 0.2 0.25
Error bound: 𝛿

提案手法と精度の間でトレードオフが実現されるが，いくつかの問題がBAQ±(greedy)

存在する．まず，サンプリングベースの手法には，BAQ [7] とBAQ(greedy)

BAQ± [9] などの厳密な誤差保証がない．加えて，サンプリン

BAQ±(scan)

グベースの手法はロングテールなどの歪んだデータについてパ

BAQ(scan)

フォーマンスが低下になる可能性がある．つまり，事前に対象
データの分布を把握しておくことが必要にある．

図 6 Temperature に関するオフラインの生成時間

貪欲的な手法を使う BAQ± と BAQ について，orders データを6 まとめと今後の課題

使用するとき提案手法は BAQ± に対して 28–33%，temperature

本稿では，近似的問合せ処理におけるシノプシス構築の高速の場合が 49–98%となっている．BAQ より提案手法は orders化に対する改善アイデアを述べた．また，上記のシノプシス

データの場合が最大 28%，temperature が最大 98%の時間で計算の最小化構築アルゴリズムを実装し，2 つのデータセットを用できる．スキャンベースの BAQ± と BAQ について，orders デー

いて評価実験を行った．実験結果により，提案手法は既存手法タを利用するとき提案手法は BAQ± の 39–70%になり，BAQ と

BAQ± よりシノプシスサイズとオフラインのシノプシス構築時ほぼ同じ結果がある．temperature については BAQ± と BAQ よ間において優れていることを示した．今後の課題としては，今り時間がかかる．

回議論した提案手法に基づく誤差とオンラインの問合せ処理のここで簡単な分析をする．提案アルゴリズムはテーブルの各
タプルについて各属性集合 𝜋 によるシノプシスをスキャンする．

効能分析とアルゴリズムの改善について詳細な検討を行う予定
である．

スキャンベースの手法ではテーブルと各シノプシスのスキャン
が 1 回だけ必要なため，構築時間が短い．そのために提案手法

謝

辞でシノプシスの構築時間がスキャンベースの BAQ± と BAQ よ
り長い可能性がある．ただし，実験結果により提案手法で計算するシノプシスのサイズは貪欲的な手法とスキャンベースの既存手法より小さいため，最小化シノプシス構築の高速化の目標を達成できると考えている．

5 関連研究BAQ± [9] と同様に，いくつかの既存の研究は前処理でシノプシスを構築し，そのシノプシスを使用して OLAP 問合せに回答する．ヒストグラム，Wavelets [11] および Sketches [12] 研究は問合せの列集合に基づいてシノプシスを生成し，歪んだデー
タにも高精度に近似計算できる．ただし，以上の手法では，問合せを全部事前に与える必要がある．なお，これらの研究は数値列のみ適用し，問合せごとにシノプシスが構築されるため，多くのストレージも必要になる．
一方，サンプリングに基づく近似的問合せ処理（SAQ）は

AQP に広く研究されている．サンプリングに基づく近似的問合せ処理では，オンラインに問合せの列によるサンプルを抽出し，そのサンプルを使用して結果を推定する．近似結果の精度は抽出されたサンプルに依存するため，結果として良いサンプ
ルを選択するために無作為抽出や層別抽出などの手法が使われている．BlinkDB [13] や VerdictDB [14] 研究では，短くの応答時間を目標としてサンプリングと事前計算を組み合わせて近似的問合せ処理手法を提案する．ただし，BlinkDB と VerdictDBで対応できるのは構造が簡単な問合せのみであり，複雑な述語を含む問合せへの対応は考慮されない．加えて，Ma ら [6, 15]
は機械学習モデルを使用してサンプルを抽出し，高精度な近似的問合せ処理システムを開発する．しかし，Ma らの研究では，

MIN や MAX などの一部の集計関数の近似問題を対応できない．
サンプリングに基づく近似的問合せ処理では，パフォーマンス

本 研 究 の 一 部 は 科 研 費（JP20K19804,

JP21H03555,

JP22H03594）による．
文

献[1] S. Chaudhuri, B. Ding, and S. Kandula, “Approximate query processing: No silver bullet,” in Proc. SIGMOD, pp. 511–519, 2017.
[2] K. Li and G. Li, “Approximate query processing: What is new andwhere to go? A survey on approximate query processing,” Data
Science and Engineering, vol. 3, pp. 379–397, 2018.
[3] B. Mozafari and N. Niu, “A handbook for building an approximate
query engine,” IEEE Data Eng. Bull., vol. 38, no. 3, pp. 3–29, 2015.
[4] B. Walenz, S. Sintos, S. Roy, and J. Yang, “Learning to sample:
Counting with complex queries,” in Proc. VLDB Endowment, vol. 13,
pp. 389–401, 2019.
[5] S. Agarwal, H. Milner, A. Kleiner, A. Talwalkar, M. I. Jordan, S. Madden, B. Mozafari, and I. Stoica, “Knowing When You’re Wrong:
Building fast and reliable approximate query processing systems,” inProc. SIGMOD, pp. 481–492, 2014.
[6] Q. Ma and P. Triantaﬁllou, “DBEST: Revisiting approximate query
processing engines with machine learning models,” in Proc. SIGMOD, pp. 1553–1570, 2019.
[7] K. Li, Y. Zhang, G. Li, W. Tao, and Y. Yan, “Bounded approximate query processing,” IEEE Transactions on Knowledge and Data
Engineering, vol. 31, no. 12, pp. 2262–2276, 2019.
[8] B. Ding, S. Huang, S. Chaudhuri, K. Chakrabarti, and C. Wang,“Sample+Seek: Approximating aggregates with distribution precision guarantee,” in Proc. SIGMOD, pp. 679–694, 2016.
[9] 倪 天嘉, 杉浦 健人, 石川 佳治, 陸 可鏡, “シノプシスの最適化に基づく近似問合せ処理の高効化,” in 第 13 回データ工学と情報マネジメントに関するフォーラム, 2022.
[10] 倪 天嘉, 杉浦 健人, 石川 佳治, 陸 可鏡, “近似的問合せ処理における問合せ高速化のための誤差保証条件の検討,” in 情報処
理学会第 177 回データベースシステム研究会, 2022.
[11] S. Guha and B. Harb, “Wavelet synopsis for data streams: minimizing
non-euclidean error,” in Proc. SIGKDD, pp. 88–97, 2005.
[12] V. Braverman and R. Ostrovsky, “Generalizing the layering methodof indyk and woodruf: recursive sketches for frequency based vectors
on streams,” in Proc. SIGKDD, pp. 58–70, 2013.
[13] S. Agarwal, A. Panda, B. Mozafari, S. Madden, and I. Stoica,“BlinkDB: Queries with bounded errors and bounded response times

on very large data,” in Proc. EuroSys, pp. 29–42, 2013.
[14] Y. Park, B. Mozafari, J. Sorenson, and J. Wang, “VerdictDB: Universalizing approximate query processing,” in Proc. SIGMOD, pp. 1461–
1476, 2018.
[15] Q. Ma, A. M. Shanghooshabad, M. Almasi, M. Kurmanji, P. T. Chaudhuri, B. Ding, and S. Kandula, “Learned approximate query processing: Make it light, accurate and fast,” in Proc. CIDR, pp. 1–11, 2021.