Contando valores de campo únicos en ClickHouse / Sudo Null IT News
¡Hola Habr! Hay varias tareas en TI, muchas de las cuales se resuelven algorítmica o condicionalmente mediante soluciones arquitectónicas. Entre la variedad de problemas, también son interesantes los problemas resueltos mediante métodos estadísticos.
Una de esas tareas es aproximar el número de valores únicos en un campo de tabla (o cardinalidad). Parecería que el beneficio práctico de calcular rápidamente el número de valores únicos de un campo sin una gran cantidad de memoria es pequeño, pero esto permite, por ejemplo, construir una consulta SQL óptima con este campo desde el punto de vista del rendimiento. , o para usar este campo en la interfaz de usuario (por ejemplo, un elemento con desplazamiento infinito o un elemento con una búsqueda de un número significativo de valores únicos, en lugar de mostrar una lista finita), etc. El problema se puede resolver eficazmente en un DBMS con las herramientas adecuadas, por lo que se considerará ClickHouse.
¿Está interesado en resolver el problema de calcular la cantidad de valores de columna únicos en ClickHouse? Bienvenido 🙂
Supongamos que hay mil millones de registros en una tabla y desea calcular aproximadamente la cantidad de valores únicos para una columna. Dado que el valor aproximado es satisfactorio, está claro que no querría guardar todos los valores únicos de la columna, porque Esto desperdiciará mucha memoria. Parece un problema resuelto mediante métodos estadísticos.
Para ilustrar las capacidades de los métodos estadísticos, es interesante recordar, por ejemplo, los estándares GOST e ISO relacionados con el control de calidad selectivo.
Sin entrar en detalles de la formulación hipótesis estadísticaelección criterio estadístico y definiciones intervalo de confianza teniendo en cuenta errores de primer y segundo tipome gustaría dar brevemente un ejemplo de GOST para un problema similar, de modo que quede claro qué solución le gustaría obtener en el problema original de estimación aproximada del número de valores únicos en un campo.
Entonces, en el ejemplo de GOST Apéndice D.1 Control de proveedores Se realiza un control de calidad aleatorio de un lote de 2120 relojes. Sin entrar en detalles, para el control por parte del proveedor basta comprobar la calidad por atributo en una muestra de n=239 relojes (de todo el lote de 2120 piezas), y para aceptar el lote es necesario que el número de relojes con desviaciones no supera A=3 con una probabilidad de aceptación P =0.9503 y nivel de discrepancias qa=0,6%. Es decir, con A=3 unidades de relojes con desviaciones en una muestra de n=239 relojes de un lote de 2120 piezas, con probabilidad P=0,9503 podemos decir que en todo el lote el número de relojes defectuosos será qa=0,6%. Por cierto, en el ejemplo. Apéndice D.2 Control del consumidor del lote 2120, basta comprobar n=73 unidades con número de aceptación A=4 para decidir si aceptar o devolver un lote de relojes con un nivel de discrepancias qb=8,0% y probabilidad de al menos 1-β=0,80. Estos ejemplos muestran que incluso con muestras pequeñas, varias veces más pequeñas que el lote en estudio, es posible resolver con éxito problemas importantes (en este caso, control de calidad) con una precisión y probabilidades determinadas.
De hecho, incluso si no lo pensamos, los métodos estadísticos se utilizan en la producción y venta de todos los bienes del mundo debido a su eficiencia, por lo tanto, volviendo a la tarea original de contar aproximadamente el número de valores únicos, Me gustaría obtener resultados de forma similar, es decir, e. con probabilidad e intervalo de confianza (o, por ejemplo, error relativo).
Parece que en la tarea de calcular el número aproximado de elementos únicos en ClickHouse, tiene sentido utilizar la condición MUESTRAtomar, por ejemplo, el 10% de las filas de una tabla usando SQL de la forma FROM table SAMPLE 0.1, estimar el valor observado de algún criterio estadístico, determinar el intervalo de confianza para una probabilidad dada usando el valor teórico del criterio, etc. .
Afortunadamente, la función ya ha implementado una determinación aproximada del número de valores únicos en ClickHouse. uniqTheta. Vale la pena señalar que ClickHouse tiene otras funciones para contar valores únicos, por ejemplo, único, uniqHLL12Pero uniqTheta Da resultados desde el punto de vista del enfoque estadístico. Por ejemplo, para un tamaño de tabla de 4096 con un nivel de confianza de 0,95, el error relativo es 3,125%, que se proporciona en documentación Y tabla teorica errores, lo cual es alentador y habla de un enfoque estadístico para resolver el problema. Además, a medida que aumenta el tamaño de la tabla, el error relativo sólo disminuye, como se puede ver en tablas de erroreslo que confirma una vez más que para obtener un resultado relativamente preciso no es necesario revisar los mil millones de registros de la tabla.
Debajo del capó, uniqTheta usa KVM (o kth Valor Mínimo).
Puede ver que se utiliza una función hash que devuelve una distribución uniforme de Uniform Random Hash de 0 a 1. Se calculará para todos los valores del campo de la tabla. Los valores hash resultantes se ordenan. A continuación, obtenemos una estimación del número de valores únicos a través de la distancia de 0 a k valores hash (también se da un ejemplo para k=3 y distancia d=0,195; corresponde a la figura):
El error relativo se puede tomar de tablas de errores por número de líneas (Conf: K) y error (#Std Dev: 2).
La documentación también describe los costes de memoria de uniqTheta (41 kilobytes).
Se utilizan bocetos 4096(2^12) de 64 bits. El tamaño del estado es de aproximadamente 41 KB.
Por tanto, utilizando uniqTheta podemos determinar aproximadamente el número de valores únicos. Si es necesario, según el número total de registros de la tabla, verifique tabla de errorescuál será la probabilidad de confianza y el error.
Me gustaría señalar que en el marco de este artículo es difícil recomendar definitivamente tal o cual función de ClickHouse, el artículo tiene carácter de revisión y la efectividad de tal o cual función se prueba para cada caso específico, por ejemplo, utilizando un punto de referencia.
Espero que la inmersión en los enfoques estadísticos haya sido interesante, buena suerte con el procesamiento de Big Data 🙂
