Fonctions approximatives Oracle 12.2 (#2)

L’objectif de cet article est de tester les nouvelles fonctions d’agrégation approximatives offertes par Oracle 12cR2. On utilisera les données chargées dans le billet précédent.

Avec la version 12.2, la fonction APPROX_COUNT_DISTINCT (introduite en 12.1.0.2) est complétée par APPROX_COUNT_DISTINCT_DETAIL, APPROX_COUNT_DISTINCT_AGG et TO_APPROX_COUNT_DISTINCT qui offrent notamment la possibilité de réaliser des agrégations hiérarchiques.

Cette fonction de comptage s’appuie sur l’algorithme Hyperloglog qui permet d’obtenir des gains de performance impressionnants par rapport à un comptage exact mais au prix d’une précision approximative (erreur de comptage généralement inférieure à 5%).

Dans ce billet, l’idée est d’estimer le nombre de contributeurs à Wikipedia par périodes (mois, année etc…). Le dataset utilisé est relativement volumineux 77 millions de lignes (~4GB).

Ci-dessous, on calcule le nombre de contributeurs distincts sur l’ensemble du dataset (années 2005 à 2016). On emploie d’abord un comptage approximatif puis un comptage exact:

SQL> SELECT banner FROM v$version;

BANNER
--------------------------------------------------------------------------------
Oracle Database 12c Enterprise Edition Release 12.2.0.1.0 - 64bit Production
PL/SQL Release 12.2.0.1.0 - Production
CORE    12.2.0.1.0      Production
TNS for Linux: Version 12.2.0.1.0 - Production
NLSRTL Version 12.2.0.1.0 - Production

SQL> SET TIMING ON
SQL>
SQL> SELECT approx_count_distinct (uname) FROM log_contribs;

APPROX_COUNT_DISTINCT(UNAME)
----------------------------
                    30284800

Elapsed: 00:00:09.16
SQL> SELECT a.name, b.VALUE
  2    FROM v$statname a, v$mystat b
  3   WHERE a.statistic# = b.statistic# AND a.name = 'session pga memory max';

NAME                                                                  VALUE
---------------------------------------------------------------- ----------
session pga memory max                                              4262248

Elapsed: 00:00:00.03
SQL>
SQL> SELECT COUNT (DISTINCT uname) FROM log_contribs;

COUNT(DISTINCTUNAME)
--------------------
            28839444

Elapsed: 00:00:50.40
SQL> SELECT a.name, b.VALUE
  2    FROM v$statname a, v$mystat b
  3   WHERE a.statistic# = b.statistic# AND a.name = 'session pga memory max';

NAME                                                                  VALUE
---------------------------------------------------------------- ----------
session pga memory max                                           1733560680

Elapsed: 00:00:00.03
SQL>

On peut voir que l’erreur d’approximation n’est que de 4.7% (100*(30284800-28839444)/30284800) alors qu’on obtient une diminution de 82% du temps de calcul (100*(50-9)/50).
Encore mieux: le besoin mémoire du comptage approximatif ne représente qu’une portion infinitésimale de celui lié au comptage exact: 4MB contre 1.7GB!

Cette approche est très prometteuse lorsqu’on travaille sur des datasets massifs avec des exigences de précision pouvant s’accommoder d’une erreur de l’ordre de 5%.

Outre le gain de performance pur, Oracle 12.2 permet grâce aux fonctions APPROX_COUNT_DISTINCT_DETAIL & APPROX_COUNT_DISTINCT_AGG de procéder à des agrégations hiérarchiques (le détail d’une agrégation peut être recombiné pour constituer une agrégation plus large).

C’est plus facile à expliquer sur un exemple ; considérons les données suivantes:

CATEGORIE ID
1 1
1 2
1 3
1 4
1 5
2 4
2 5
2 6
2 7
2 8

Les ID 4 et 5 existent à la fois pour les valeurs de CATEGORIE 1 et 2.

Si je souhaite connaitre le nombre d’ID distincts par catégorie, je peux exécuter la requête suivante:

select CATEGORIE, count(distinct ID) cd_ID from T1 group by CATEGORIE;

CATEGORIE cd_ID
1 5
2 5

Maintenant, si je souhaite connaitre le nombre d’ID distinct globalement (c’est à dire, toutes catégories confondues), il se trouve que le résultat ne peut pas être déduit du résultat de la requête précédente. En effet, le nombre de valeurs distinctes globalement (8) ne correspond pas à la somme des valeurs distinctes de chaque catégorie (5+5). Pour obtenir le résultat, cela oblige à l’exécution d’une nouvelle requête:

select count(distinct ID) cd_ID from T1;

 

Ici, le dataset est minuscule mais quand on doit réaliser ce genre d’agrégations à plusieurs niveaux de détail sur des milliards de lignes, la répétition de requêtes s’avère prohibitive.

C’est dans ce genre de contexte que la fonction d’agrégation approximative APPROX_COUNT_DISTINCT_DETAIL prend tout son sens. Elle permet de fournir un résultat d’agrégation intermédiaire (dans un format binaire) « ré-agrégeable » à un niveau moins fin.

 

En reprenant l’exemple précédent, pour connaitre le nombre d’ID distinct par catégorie, on peut stocker le résultat de la requête à l’aide d’une vue matérialisée:

create materialized view MV_CNT_CAT as select CATEGORIE, approx_count_distinct_detail(ID) cd_ID_bin from T1 group by CATEGORIE;

La MView précédente est alors exploitable directement via la fonction TO_APPROX_COUNT_DISTINCT:

select CATEGORIE, to_approx_count_distinct(cd_ID_bin) from MV_CNT_CAT group by CATEGORIE;

Mais, avec APPROX_COUNT_DISTINCT_AGG, on peut aussi procéder à une ré-aggregation pour obtenir le nombre (approché) d’ID toute catégories confondues:

select to_approx_count_distinct(APPROX_COUNT_DISTINCT_AGG(cd_ID_bn)) from MV_CNT_CAT;

On évite ainsi de re-balayer la table source!

 

Faisons un petit essai sur la table LOG_CONTRIBS: je souhaite connaitre le nombre de contributeurs distincts à Wikipedia par mois et par année. Avec un comptage exact j’aurai normalement recours à deux vues matérialisées:

SQL> CREATE MATERIALIZED VIEW MV_CONTRIB_AN_MOIS_EXACT
  2  AS
  3        SELECT EXTRACT (YEAR FROM tmstamp) an,
  4               EXTRACT (MONTH FROM tmstamp) mois,
  5               COUNT (DISTINCT uname)     cd
  6          FROM log_contribs
  7      GROUP BY EXTRACT (YEAR FROM tmstamp), EXTRACT (MONTH FROM tmstamp);

Materialized view created.

Elapsed: 00:01:26.80
SQL>
SQL> CREATE MATERIALIZED VIEW MV_CONTRIB_AN_EXACT
  2  AS
  3        SELECT EXTRACT (YEAR FROM tmstamp) an,
  4               COUNT (DISTINCT uname)     cd
  5          FROM log_contribs
  6      GROUP BY EXTRACT (YEAR FROM tmstamp);

Materialized view created.

Elapsed: 00:01:06.32
SQL>
SQL> BEGIN
  2      DBMS_MVIEW.refresh ('MV_CONTRIB_AN_MOIS_EXACT,MV_CONTRIB_AN_EXACT', 'C');
  3  END;
  4  /

PL/SQL procedure successfully completed.

Elapsed: 00:02:39.87
SQL>

Avec une approche basée sur les fonctions approximatives, on créée une MView au niveau de détail le plus fin en utilisant APPROX_COUNT_DISTINCT_DETAIL:

SQL> CREATE MATERIALIZED VIEW MV_CONTRIB_AN_MOIS_APPROX_DET
  2  AS
  3        SELECT EXTRACT (YEAR FROM tmstamp)        an,
  4               EXTRACT (MONTH FROM tmstamp)       mois,
  5               approx_count_distinct_detail (uname) acdd
  6          FROM log_contribs
  7      GROUP BY EXTRACT (YEAR FROM tmstamp), EXTRACT (MONTH FROM tmstamp);

Materialized view created.

Elapsed: 00:00:52.21
SQL>
SQL> desc MV_CONTRIB_AN_MOIS_APPROX_DET
 Name                                      Null?    Type
 ----------------------------------------- -------- ----------------------------
 AN                                                 NUMBER
 MOIS                                               NUMBER
 ACDD                                               BLOB

SQL>

La MView ainsi construite n’est pas directement utilisable, les infos de comptages sont dans un champ BLOB. En revanche, on peut utiliser cette MView comme source de MViews dépendantes:

SQL> CREATE MATERIALIZED VIEW MV_CONTRIB_AN_MOIS_APPROX
  2  AS
  3      SELECT an, mois, to_approx_count_distinct (acdd) acd
  4        FROM MV_CONTRIB_AN_MOIS_APPROX_DET;

Materialized view created.

Elapsed: 00:00:00.28
SQL>
SQL> CREATE MATERIALIZED VIEW MV_CONTRIB_AN_APPROX
  2  AS
  3        SELECT an,
  4               to_approx_count_distinct (approx_count_distinct_agg (acdd)) acd
  5          FROM MV_CONTRIB_AN_MOIS_APPROX_DET
  6      GROUP BY an;

Materialized view created.

Elapsed: 00:00:00.11
SQL>

La création de ces dernières est extrêmement rapide dans la mesure ou l’essentiel du travail d’agrégation a déjà été réalisé.

Le refresh de l’ensemble est significativement plus rapide que celui des MViews avec comptage exact:

SQL> BEGIN
  2      DBMS_MVIEW.refresh (
  3          'MV_CONTRIB_AN_MOIS_APPROX_DET,MV_CONTRIB_AN_MOIS_APPROX,MV_CONTRIB_AN_APPROX',
  4          'C',
  5          nested   => TRUE);
  6  END;
  7  /

PL/SQL procedure successfully completed.

Elapsed: 00:00:57.34
SQL>

On peut alors s’intéresser à la précision des données approchées. Afin d’obtenir des éléments statistiques sur l’erreur d’approximation, j’utilise ma fonction stat_summary présentée dans un billet précédent:

SQL> set long 10000
SQL> set longc 10000
SQL> set pages 0
SQL> set timing off
SQL> CREATE OR REPLACE VIEW err_approx
  2  AS
  3      SELECT ROUND (100 * (ABS (cd - acd) / cd), 2) pct
  4        FROM MV_CONTRIB_AN_MOIS_APPROX a, MV_CONTRIB_AN_MOIS_EXACT b
  5       WHERE a.an = b.an AND a.mois = b.mois;

View created.

SQL>
SQL> SELECT stat_summary ('err_approx', 'pct') FROM DUAL;

C##RAF.ERR_APPROX [PCT]
----------------------

N: 145
Min/Max: 0/4.56 - Delta: 4.56
Var.: 1.298825 - e.t.: 1.13966

Quantiles
----------------------
     5%: .112
    25%: .55
Mediane: 1.28
    75%: 2.19
    95%: 3.856

Principale(s) modalite(s):
   [1]: .46
   [2]: 1.33
   [3]: .03
   [4]: 1.83
   [5]: .63

Cinq valeurs les plus grandes [Outliers (*) >4.65]:
   [1]: 4.56
   [2]: 4.45
   [3]: 4.4
   [4]: 4.33
   [5]: 4.28

Cinq valeurs les plus petites [Outliers (*) <-1.91]:
   [5]: .04
   [4]: .03
   [3]: .03
   [2]: .03
   [1]: 0
SQL>

L’erreur d’approximation reste systématiquement sous la barre des 5%. On a même 95% des approximations présentant une erreur inférieure à 3.9%

La précision des approximations est encore meilleure pour l’estimation année par année (entre 0.03% et 2.18%):

SQL> set pages 50
SQL>   SELECT a.an, ROUND (100 * (ABS (cd - acd) / cd), 2) pct
  2      FROM MV_CONTRIB_AN_APPROX a, MV_CONTRIB_AN_EXACT b
  3     WHERE a.an = b.an
  4  ORDER BY 2 DESC;

        AN        PCT
---------- ----------
      2010       2.18
      2011       2.16
      2012        1.9
      2013          1
      2014        .79
      2016        .65
      2004         .4
      2007        .35
      2005        .31
      2009        .28
      2008        .26
      2006         .2
      2015        .03

13 rows selected.

SQL>

Dans les situation ou un comptage approximatif est suffisant, l’utilisation de ces fonctions présente de sérieux avantages: gain de performance, faible besoin mémoire, hiérarchie d’agrégation réutilisable. Le paramètre d’initialisation APPROX_FOR_COUNT_DISTINCT permet en outre de convertir automatiquement les appels COUNT(DISTINCT xxx) en APPROX_COUNT_DISTINCT(xxx)!

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

81 + = eighty four