Azure SQL Database で Count Distinct の概算関数が一般プレビュー

2018-07-18

SQL Azure Database で、巨大テーブルのユニーク数の概算を取得するのに役立つ関数「APPROX_COUNT_DISTINCT」の一般プレビューがリリースされました。(紹介Blog

SELECT COUNT(DISTINCT())

使用例としては、一千万行ぐらいのテーブルで、ダッシュボード表示用にCOUNT(DISTINCT())する場合が考えられます。
このケースで重要なは正確な数字ではなく、データ取得までの応答速度です。

「APPROX_COUNT_DISTINCT」は、NULLではないユニークな数の概算を取得する関数です。

「APPROX_COUNT_DISTINCT」は、大きなデータで使用する前提で設計されていて、次のようなケースに最適化されています。

  • 数百万行以上のデータにアクセスする場合
  • 多数の異なる値を持つ列をカウントする場合

この関数は、通常の使用用途では2%以内の精度を維持しつつ、かつどんなに稀な使用例でも悪くても20%以内の精度を維持されるべきだと考えています。

設計ポイント

「APPROX_COUNT_DISTINCT」は、非常に少ないメモリ使用量で算出できるように設計されています。COUNT DISTINCTで、メモリ内にデータが収まりきらずTempDBを使用して算出するケースでは、優位になります。「APPROX_COUNT_DISTINCT」は、基本的にTempDBを使用して算出することはありません。

Q & A

  • 「APPROX_COUNT_DISTINCT」でクエリは高速化しますか?
    • 対象データによります。メモリに最適化しているので、メモリ内に収まりきらない場合には、かなりの応答優位性を発揮します。
    • メモリ内で収まる場合には、あまり差がありません。
  • 精度が2%に収まらない最悪のレアケースでは、どれぐらいの精度になりますか?
    • 20%以内に収まるべきと考えています。
  • 実行プランへの影響は?
    • COUNT(DISTINCT)では、Hash MatchとSort操作がはいります。INDEX SCANは95%程度ですが、「APPROX_COUNT_DISTINCT」では、98%の時間がINDEX SCANです。

 

実装方法

実装に採用されているアルゴリズムについて教えてもらったので追記しておく。
OracleやRedis、Redshifにも同様の関数があって、それらは「HyperLoglog」が使用されているので、Azure SQL Databaseでも恐らくそれだろう。

オリジナル論文は、2007年に公開されている。
なんとなく理解をするのなら、「HyperLoglogでcount distinctを速くする」を参照するとなんとなく理解できたような気ができる。