Zero-Cost NDV Estimation from Columnar File Metadata

Este artículo presenta un método de costo cero para estimar el número de valores distintos (NDV) en archivos de formato columnar utilizando únicamente metadatos existentes, combinando la inversión de la ecuación de almacenamiento codificado por diccionario y un modelo de recolector de cupones para optimizar consultas y la asignación de memoria sin acceder a los datos ni requerir almacenamiento adicional.

Lo esencial

Imagina que tienes una biblioteca gigante llena de libros (tus datos) organizados en estanterías (archivos de datos). Quieres saber cuántas palabras únicas hay en total en toda la biblioteca para planificar cómo organizar una fiesta de lectura, pero no tienes tiempo ni permiso para abrir ni un solo libro. Solo puedes mirar las etiquetas en las esquinas de las estanterías.

Normalmente, para saber cuántas palabras únicas hay, tendrías que leer todo el contenido, lo cual es lento y costoso. Este paper propone un "truco de magia" para adivinar ese número sin abrir ni una sola página, usando solo la información que ya está escrita en las etiquetas de los archivos.

Aquí te explico cómo funciona, usando analogías sencillas:

El Problema: La Etiqueta "Contar Distintos" está Vacía

En el mundo de los datos (formatos como Parquet), a veces hay una etiqueta que dice "Número de valores únicos". Pero, como contar exactamente es muy difícil y lento, la mayoría de las veces esa etiqueta está en blanco. Los creadores de los archivos no la llenan.

El autor se preguntó: "¿Qué otra información tengo en estas etiquetas que pueda usarse para adivinar?" Y encontró dos pistas ocultas.

---

Pista 1: El Tamaño de la "Lista de Vocabulario" (Inversión del Diccionario)

Imagina que en cada estantería hay un pequeño diccionario con las palabras que aparecen en esa sección.

• Si la estantería tiene 1000 páginas, pero solo usa 5 palabras diferentes, el diccionario es pequeño y las páginas son cortas (porque solo guardan números que apuntan al diccionario).
• Si usa 900 palabras diferentes, el diccionario es enorme y las páginas son más largas.

La Magia: El archivo guarda el tamaño total de este diccionario y de las páginas.
El autor dice: "Si sé cuánto pesa el diccionario y cuántas páginas hay, puedo hacer una ecuación matemática al revés para deducir cuántas palabras únicas hay".

• Cuándo funciona: Cuando las palabras están mezcladas de forma uniforme en todas las estanterías (como una ensalada bien revuelta).
• El truco: Es como adivinar cuántas personas hay en una fiesta solo midiendo el peso de la bolsa de globos que todos tienen, sin contar a nadie.

Pista 2: Los "Extremos" de cada Estantería (La Colección de Cupones)

Cada estantería tiene una etiqueta que dice: "Aquí la palabra más pequeña es 'A' y la más grande es 'Z'".
Si tienes 50 estanterías, tienes 50 pares de "A" y "Z".

La Magia:

• Si los datos están ordenados (como un diccionario real), la estantería 1 tendrá de la A a la F, la 2 de la G a la L, etc. Al mirar los extremos, verás muchas letras diferentes.
• Si los datos están mezclados, la estantería 1 podría tener de la A a la Z, y la estantería 2 también de la A a la Z. Los extremos se repetirán mucho.

El autor usa un modelo matemático famoso llamado "El problema del coleccionista de cupones". Imagina que cada estantería te da un "cupón" (su palabra más pequeña y su más grande).

• Si ves muchos cupones diferentes, significa que hay muchas palabras únicas en total.
• Si ves los mismos cupones una y otra vez, significa que hay pocas palabras únicas.

Cuándo funciona: Cuando los datos están ordenados o divididos por temas (como un diccionario o archivos separados por año). Aquí, la Pista 1 falla, pero la Pista 2 es perfecta.

---

El Árbitro Inteligente: ¿Cuál pista usar?

El sistema tiene un pequeño "detective" que mira las etiquetas de las estanterías para decidir qué pista es más confiable:

1. ¿Las estanterías se superponen mucho? (¿Todas tienen de la A a la Z?) -> Usa la Pista 1 (Tamaño del diccionario).
2. ¿Las estanterías son diferentes y progresivas? (¿Una tiene A-F, otra G-L?) -> Usa la Pista 2 (Extremos/Cupones).

Al final, el sistema toma la mayor de las dos estimaciones. ¿Por qué? Porque es mejor sobreestimar un poco que quedarse corto. Si una dice 100 y la otra 1000, es muy probable que la realidad esté cerca de 1000.

¿Para qué sirve esto? (La Fiesta de Lectura)

Imagina que eres el organizador de la fiesta (un motor de consulta de datos en una computadora). Necesitas saber cuántos valores únicos hay para:

• Saber cuánta memoria necesitas: Si hay muchas palabras únicas, necesitas más espacio en la mesa para organizarlas.
• Decidir el orden de las tareas: Saber cuántas cosas únicas hay ayuda a decidir qué tarea hacer primero para que la fiesta sea más rápida.

El beneficio: Antes, para saber esto, tenías que abrir los libros (leer los datos), lo cual tomaba mucho tiempo. Ahora, solo miras las etiquetas (metadatos) y tienes una respuesta casi perfecta en una fracción de segundo. Es gratuito (Zero-Cost) y rápido.

Resumen en una frase

El paper nos enseña a leer entre líneas de las etiquetas de los archivos de datos para adivinar cuántas cosas únicas hay dentro, usando dos trucos matemáticos (el tamaño del diccionario y la variedad de los extremos) y un pequeño juez que decide cuál truco usar según cómo estén organizados los datos. Todo esto sin tocar ni un solo dato real.

Resumen técnico

Aquí tienes un resumen técnico detallado del artículo "Zero-Cost NDV Estimation from Columnar File Metadata" en español:

Resumen Técnico: Estimación de NDV sin Costo desde Metadatos de Archivos Columnares

1. El Problema

En los motores de consulta distribuidos y acelerados por GPU (como Theseus de VoltronData), es crucial contar con estimaciones precisas del Número de Valores Distintos (NDV) de una columna para la optimización basada en costos (ordenamiento de joins, pushdown de agregaciones, asignación de memoria).

Sin embargo, en formatos de archivo columnares como Apache Parquet, el campo distinct_count en los metadatos rara vez se llena porque calcular el conteo exacto es costoso y la mayoría de los escritores de datos lo omiten. Las alternativas tradicionales, como el muestreo o el mantenimiento de sketches (ej. HyperLogLog), requieren acceso a los datos o infraestructura adicional en el lado del escritor, lo que contradice el objetivo de la planificación basada únicamente en metadatos.

La pregunta central: ¿Qué información de cardinalidad ya está codificada implícitamente en los metadatos existentes (tamaño de almacenamiento y estadísticas min/max) que pueda ser explotada sin acceder a los datos?

2. Metodología

El artículo propone un método que combina dos señales complementarias extraídas exclusivamente de los metadatos de los archivos Parquet (y generalizable a otros formatos como ORC y F3):

A. Inversión de la Ecuación de Tamaño del Diccionario

• Principio: Las columnas con cardinalidad baja/media utilizan codificación de diccionario. El tamaño total descomprimido ($S$) de un fragmento de columna es la suma del tamaño del diccionario y el tamaño de los índices.
• Ecuación: $S = ndv \times len + (N - nulls) \times \lceil \log_2(ndv) \rceil / 8$.
• Método: Dado que $S$, $N$ (filas), $nulls$ y $len$ (longitud media) son conocidos o estimables, se resuelve la ecuación para $ndv$ utilizando el método numérico Newton-Raphson.
• Limitación: Funciona mejor cuando los valores distintos están bien distribuidos entre los grupos de filas (row groups). Si los datos están ordenados, este método tiende a subestimar el NDV.

B. Diversidad de Mínimos/Máximos (Modelo del Coleccionista de Cupones)

• Principio: Los metadatos de cada grupo de filas almacenan los valores mínimo y máximo. La diversidad de estos extremos a través de los $n$ grupos de filas actúa como una muestra implícita de la cardinalidad global.
• Modelo: Se aplica el problema del coleccionista de cupones. Si se muestrean $n$ grupos de filas de una población de $NDV$ valores, el número esperado de mínimos (o máximos) distintos observados sigue una distribución específica.
• Método: Se invierte la ecuación del modelo del coleccionista de cupones ($E[m] = NDV \times (1 - e^{-n/NDV})$) para estimar el NDV global basándose en la cuenta de mínimos y máximos distintos observados.
• Fortaleza: Es muy preciso para datos ordenados o particionados, donde cada grupo de filas cubre un rango de valores distinto, algo donde la inversión del diccionario falla.

C. Detector de Distribución y Fusión

• Un detector ligero clasifica la distribución de los datos analizando el solapamiento de rangos y la monotonicidad entre grupos de filas consecutivos.
• Estrategia de Fusión: La estimación final toma el máximo de las dos estimaciones (diccionario y min/max), acotado por el número de filas no nulas y restricciones de tipo de datos (ej. rango entero). Esto mitiga los modos de fallo de cada método individual.

3. Contribuciones Clave

1. Ecuación de Cierre: Derivación de una ecuación cerrada que relaciona el NDV con el tamaño de almacenamiento del diccionario, resoluble numéricamente.
2. Reconocimiento de Estadísticas Implícitas: Identificación de que las estadísticas min/max de los grupos de filas funcionan como sketches de cardinalidad implícitos, recuperables mediante inversión del modelo del coleccionista de cupones.
3. Detector de Distribución: Un clasificador eficiente que decide qué estimador priorizar según la estructura de los datos (bien distribuido vs. ordenado/particionado).
4. Predicción de Memoria por Lotes: Uso del modelo del coleccionista de cupones para predecir el tamaño del diccionario necesario para un lote de datos específico sin leer los datos, crucial para la gestión de memoria en GPU.

4. Resultados y Validación

• Implementación: La técnica se implementó y validó en producción en el motor de consulta Theseus (VoltronData).
• Precisión: En datos reales de Parquet, los errores de estimación fueron típicamente inferiores al 10% para columnas bien distribuidas.
• Robustez: El enfoque híbrido demostró ser robusto frente a diferentes tipos de distribución de datos, corrigiendo las subestimaciones sistemáticas que ocurrían al usar solo la inversión del diccionario en datos ordenados.
• Eficiencia: La complejidad es $O(n)$ en tiempo y $O(1)$ en espacio (donde $n$ es el número de grupos de filas), ya que solo requiere un pase sobre los metadatos.

5. Significado y Aplicaciones

• Optimización de Consultas: Permite a los optimizadores de consultas tomar decisiones informadas sobre pushdown de agregaciones y ordenamiento de joins sin incurrir en el costo de leer los datos.
• Asignación de Memoria en GPU: Facilita la asignación precisa de memoria para kernels de GPU, evitando desbordamientos o subutilización de recursos.
• Generalización: Aunque demostrado en Parquet, el método es aplicable a cualquier formato columnar que utilice codificación de diccionario y estadísticas de partición (como ORC y el formato F3).
• Costo Cero: Elimina la necesidad de escaneos de datos o almacenamiento adicional de sketches, aprovechando únicamente la información que ya existe en los archivos.

Nota sobre el contexto: El artículo menciona que, tras la liquidación de los activos de VoltronData, los datos experimentales detallados se perdieron, y este trabajo reconstruye el enfoque desde la memoria, con planes para reproducir los resultados en benchmarks públicos.