ヒストグラムの概要

ヒストグラムは、列の統計情報の特殊なタイプであり、データを一連の順序付けられたバケットに格納することで、その列のデータ分布特性を記述します。オプティマイザーはヒストグラムに基づいて、より正確な行数を推定することができます。

デフォルトでは、オプティマイザーは列のデータが均等に分布していると仮定し、その特性に基づいて行数を推定します。しかし、実際のシナリオでは、ほとんどのテーブルのデータ分布は均一ではありません。このような場合には、ヒストグラムを使用する必要があります。

OceanBaseデータベースのオプティマイザーでは、列のヒストグラム情報はビュー ALL_TAB_HISTOGRAMS、DBA_TAB_HISTOGRAMS、および USER_TAB_HISTOGRAMS に格納され、以下の情報を含みます：

• ヒストグラムの基本情報（tenant_id、table_id、partition_id、column_id を含む）

• ヒストグラムの統計情報タイプ（情報レベルは GLOBAL、PARTITION、SUBPARTITION に分類される）

• ヒストグラム内の各バケットに累積されたデータ量（現在のバケットとそれ以前のバケットの合計を含む）

• ヒストグラム内の各バケットにおける最大値

• ヒストグラム内の各バケットにおける最大値の頻度

ヒストグラムの種類

OceanBaseデータベースのオプティマイザーは、頻度ヒストグラム、Topkヒストグラム、および混合ヒストグラムの3種類のヒストグラムをサポートしています。

頻度ヒストグラムでは、異なる列値がヒストグラムの個々のバケットに対応します。指定されたバケット数は、列のNDV値以上である必要があります。

Topkヒストグラムは頻度ヒストグラムの変種であり、Lossy Countingアルゴリズムに基づいています。一部のデータ特徴を取得することで全体のデータ分布を推定し、記録されたデータ数と総データ数の比率が 1-(1/bucket_size) 以上である必要があります。

混合ヒストグラムは、指定されたデータ量を収集してヒストグラムを構築するもので、頻度ヒストグラムとTopkヒストグラムの機能を補完します。

頻度ヒストグラム

頻度ヒストグラムでは、異なる列値がヒストグラムの個々のバケットに対応します。各値には専用のバケットが割り当てられているため、一部のバケットには多くの値が含まれ、他のバケットには少ない値しか含まれない場合があります。頻度ヒストグラムの例えとして、硬貨を分類することが挙げられます。例えば、ある財布に0.1元、0.2元、0.5元、1元の4種類の異なる額面の硬貨が合計20枚入っているとします。分類に従って、すべての0.1元の硬貨を最初のバケットに、すべての0.2元の硬貨を2番目のバケットに、すべての0.5元の硬貨を3番目のバケットに、すべての1元の硬貨を4番目のバケットに入れます。これにより、以下のような頻度ヒストグラムが得られます。頻度ヒストグラムの特性を総合すると、指定されたバケット数は列のNDV値以上である必要があります。

Topkヒストグラム

Topkヒストグラムは頻度ヒストグラムの変種です。指定したバケット数がすべてのNDVを収容するには不十分な場合、Topkヒストグラムの使用が検討されます。Topkヒストグラムは本質的に頻度が低いデータを無視し、主に頻度が高いデータの分布を考慮します。例えば、ある財布に0.1元、0.2元、0.5元、1元の4種類の異なる額面の硬貨が合計100枚入っているとします。そのうち0.1元の硬貨はわずか1枚しかありません。同時に、硬貨を収容するためのバケットは3つしかありません。この場合、0.1元の硬貨を無視し、残りの3種類の硬貨の分布のみを考慮することができます。これにより、以下のようなTopkヒストグラムが得られます。

Topkヒストグラムは、一部のデータ特徴を取得して全体のデータ分布を推定するため、誤差が大きくなりすぎないようにするためには、Topkヒストグラムが記録したデータ数と総データ数の比率が 1–(1/bucket_size) 以上である必要があります。例えば、上記のシナリオで、指定したバケット数が3つ、硬貨の合計数が100枚の場合、Topkヒストグラムが99枚を記録していれば、明らかに 99/100 > 2/3 となり、要件を満たしています。現在、OceanBaseデータベースのオプティマイザーは主にLossy Countingアルゴリズムを用いてTopkヒストグラムを実装しています。

ハイブリッドヒストグラム

データ量が非常に多い大規模テーブルのシナリオでは、指定されたヒストグラムのバケット数がNDV値を下回り、同時にTopkヒストグラムも最小データ比率を満たせない場合があります。このような場合、データ分布の特徴をより均等に記述するためのヒストグラムが必要となり、ハイブリッドヒストグラムが導入されました。ハイブリッドヒストグラムは、指定されたデータ量を収集してヒストグラムを構築します。頻度ヒストグラムやTopkヒストグラムとは異なり、1つのバケットに複数の異なるValue値を含めることができます。収集したデータ量をバケット数で分割し、各区間内のすべてのデータを対応するバケットに配置することで、より少ないバケット数でより大量のデータ分布を記述できます。バケット内の最大Value値をendpoint_valueとし、endpoint_repeat_cntという新しいフィールドを追加してendpoint_valueの頻度を記録します。

例えば、同じく100枚のコインがある場合：0.1元が10枚、0.2元が10枚、0.5元が15枚、1元が15枚、2元が25枚、5元が10枚、10元が15枚です。これにより計算されるTopkヒストグラムのデータカバー率は(25+15+15+15)/100=0.7ですが、Topkデータカバー率の最小しきい値は1-1/N =3/4=0.75であり、このしきい値に達していないためTopkヒストグラムの条件を満たしません。そこで、指定バケット数を4に設定した場合（バケット数が列のNDV値を下回り、頻度ヒストグラムの条件を満たさないため）、構築されるハイブリッドヒストグラムは以下のとおりです。

ヒストグラムの選択戦略

OceanBaseデータベースのオプティマイザーは、列から情報を収集してヒストグラムを形成する際、バケット数がオプティマイザーのパフォーマンスに与える影響（バケット数が多すぎると検索パフォーマンスとデータストレージに負の影響を及ぼす）を考慮します。そのため、一般的には列のNDV値がヒストグラムのバケット数（bucket_size）以下であることが望ましく、デフォルト値は254です。

1. 指定列上の異なる値のNDV（Number of Distinct Values）数が254以下の場合、頻度ヒストグラムを使用します。

2. 254を超える場合、TopKヒストグラムを優先的に使用します。具体的な方法は、列の情報を統計した後、バケットに対応する頻度の高い順に並べ替え、番号が254を超えるバケットを除外します。ただし、これら254個のバケットで統計されたデータ量が総データ量に占める割合が1 - (1/bucket_size)以上であることを保証する必要があります。デフォルト値は99.6%です。

3. 2の条件を満たさない場合、ハイブリッドヒストグラムを使用します。バケットを再定義することで、各バケットがより多くのデータを記述できるようにし、同時にバケットの定義を詳細に記述するための新しい値を導入します。これには、バケットのエンドポイント値（endpoint_value）とエンドポイント値の頻度（endpoint_repeat_cnt）が含まれます。