Estimation des valeurs centiles

Snowflake utilise une version améliorée de l’algorithme « t-digest » qui constitue un moyen rapide et discret d’estimer les valeurs centiles approximatives d’un ensemble de données.

Dans ce chapitre :

Vue d’ensemble

Snowflake fournit une version améliorée d’une implémentation des documents sur l’algorithme t-Digest de Dunning et Ertl. Il est implémenté via l’ensemble de fonctions APPROX_PERCENTILE.

Tel que documenté, l’algorithme a une erreur relative constante. Il est à noter que l’algorithme bénéficie d’une prise en charge empirique substantielle, mais aucune preuve rigoureuse de garantie d’exactitude n’est fournie.

Fonctions SQL

Les Fonctions d’agrégation suivants sont prévus pour l’utilisation de t-Digest pour estimer les valeurs centiles :

  • APPROX_PERCENTILE : renvoie une approximation de la valeur centile désirée.

  • APPROX_PERCENTILE_ACCUMULATE : ignore l’étape d’estimation finale et, à la place, retourne l’état intermédiaire t-Digest à la fin d’une agrégation.

  • APPROX_PERCENTILE_COMBINE : combine (c’est-à-dire fusionne) plusieurs états d’entrée en un seul état de sortie.

  • APPROX_PERCENTILE_ESTIMATE : calcule une estimation en centile d’un état t-Digest produit par APPROX_PERCENTILE_ACCUMULATE ou APPROX_PERCENTILE_COMBINE.

Détails de l’implémentation

  • L’estimation utilise un espace constant quelle que soit la taille de l’entrée.

  • L’état t-Digest est indépendant de la valeur centile. Ceci permet de calculer une fois l’état t-Digest, puis d’interroger l’état pour plusieurs valeurs centiles.