Los índices de árbol B son perfectos cuando sus datos están distribuidos uniformemente . No son realmente útiles, cuando tienes datos sesgados . Más adelante explicaré por qué este es el caso, pero primero aprendamos cómo detectar "sesgo"
¿Qué es el sesgo?
Un sesgo es un término de las estadísticas cuando una distribución normal no es simétrica. El ejemplo dado en Wikipedia muestra una distribución como esta:
En RDBMS, a veces usamos el término sesgo coloquialmente para significar lo mismo que una distribución no uniforme, es decir, una distribución normal también estaría sesgada. Simplemente queremos decir que algunos valores aparecen más a menudo que otros. Por lo tanto, pondré el término "sesgar" entre comillas dobles en este artículo. Si bien las estadísticas de su RDBMS contienen esta información una vez que se calculan, también podemos detectar dichos "sesgos" manualmente en consultas ad-hoc utilizando percentiles que se definen en el estándar SQL y se admiten en una variedad de bases de datos, como funciones agregadas ordinarias, que incluyen:
- Oracle
- PostgreSQL
- SQL Server (lamentablemente, solo como funciones de ventana)
Distribución uniforme
Veamos los valores de FILM_ID en la base de datos de Sakila ]:
SELECCIONAR percentile_disc (0.0) WITHIN GROUP (ORDENAR POR film_id) COMO "0%", percentile_disc (0.1) DENTRO DE GRUPO (ORDEN POR film_id) COMO "10%", percentile_disc (0.2) DENTRO DE GRUPO (ORDEN POR film_id) COMO "20%", percentile_disc (0.3) DENTRO DE GRUPO (ORDEN POR film_id) COMO "30%", percentile_disc (0.4) DENTRO DE GRUPO (ORDEN POR film_id) COMO "40%", percentile_disc (0.5) DENTRO DE GRUPO (ORDEN POR film_id) COMO "50%", percentile_disc (0.6) EN GRUPO (ORDEN POR film_id) COMO "60%", percentile_disc (0.7) DENTRO DE GRUPO (ORDEN POR film_id) COMO "70%", percentile_disc (0.8) EN GRUPO (ORDEN POR film_id) COMO "80%", percentile_disc (0.9) EN GRUPO (ORDEN POR film_id) COMO "90%", percentile_disc (1.0) DENTRO DE GRUPO (ORDEN POR film_id) COMO "100%" De la película
¿Qué estamos calculando aquí? Estamos tratando de encontrar 11 valores diferentes para los que podemos decir que:
- 0% de los film_ids son más bajos que el valor "0%"
- El 10% de los film_ids son más bajos que el valor "10%"
- …
O en otras palabras:
- 0% es el valor MIN (film_id)
- 50% es el valor MEDIANO (film_id)
- 100% es el valor MAX (film_id) [19659015] El resultado muestra una distribución sorprendentemente uniforme:
0% | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% | --- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | - ---- | 1 | 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 | 1000 |
Podemos trazar esto en Microsoft Excel o alguna otra herramienta para obtener esta bonita curva:
Esto no es sorprendente, ya que las ID son solo valores consecutivos, que es una propiedad deseada de las claves sustitutas.
”Distribución
Es una historia diferente cuando observamos la distribución de montos en la tabla de pagos:
SELECCIONE percentile_disc (0.0) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "0%", percentile_disc (0.1) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "10%", percentile_disc (0.2) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "20%", percentile_disc (0.3) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "30%", percentile_disc (0.4) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "40%", percentile_disc (0.5) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "50%", percentile_disc (0.6) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "60%", percentile_disc (0.7) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "70%", percentile_disc (0.8) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "80%", percentile_disc (0.9) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "90%", percentile_disc (1.0) DENTRO DEL GRUPO (ORDEN POR cantidad) COMO "100%" DESDE el pago;
Ahora estamos obteniendo:
0% | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | - --- | ----- | ----- 0.00 | 0.99 | 1.99 | 2.99 | 2.99 | 3.99 | 4.99 | 4.99 | 5.99 | 6.99 | 11.99
Esto parece … "sesgado", aunque claramente el sesgo se debe principalmente al hecho de que se generan estos datos. Cuando trazamos lo anterior, obtenemos:
La pendiente es menos pronunciada al comienzo de esta curva, lo que esencialmente significa que existen más valores en el extremo inferior del rango que en el extremo superior. Podemos validar esto con otra consulta:
SELECCIONE la cantidad, cuente (*) DESDE ( SELECCIONAR trunc (cantidad) AS cantidad DE PAGO ) t GRUPO POR CANTIDAD ORDEN POR cantidad;
… que produce:
cantidad | recuento | ------- | ------ | 0 | 3003 | 1 | 641 | 2 | 3542 | 3 | 1117 | 4 | 3789 | 5 | 1306 | 6 | 1119 | 7 | 675 | 8 | 486 | 9 | 257 | 10 | 104 | 11 | 10 |
Trazado:
Al trazar esto, podemos ver que hay más cantidades en la mitad inferior del rango que en la mitad superior, lo que lleva a que los percentiles se vuelvan más lentos.
Correlaciones
Esta técnica puede También se aplicará para detectar correlaciones en los datos. Podemos, por ejemplo, tratar de encontrar los percentiles de la longitud de las películas y agrupar los conjuntos de datos por clasificación. Estoy usando una función de GRUPO AJUSTES, la función ROLLUP () para calcular el total general también. Simplemente revise la consulta y sus resultados, y verá:
SELECCIONE clasificación, contar(*), percentile_disc (0.0) DENTRO DE GRUPO (ORDEN POR longitud) COMO "0%", percentile_disc (0.1) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "10%", percentile_disc (0.2) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "20%", percentile_disc (0.3) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "30%", percentile_disc (0.4) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "40%", percentile_disc (0.5) DENTRO DE GRUPO (ORDEN POR longitud) COMO "50%", percentile_disc (0.6) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "60%", percentile_disc (0.7) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "70%", percentile_disc (0.8) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "80%", percentile_disc (0.9) DENTRO DEL GRUPO (ORDEN POR longitud) COMO "90%", percentile_disc (1.0) DENTRO DE GRUPO (ORDEN POR longitud) COMO "100%" De la película GRUPO POR ROLLUP (calificación);
Esto produce:
calificación | conteo | 0% | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | 100% | ------- | ------ | --- | ---- | ---- | ---- | ---- | ---- | ---- | - --- | ---- | ---- | ----- | G | 178 | 47 | 57 | 67 | 80 | 93 | 107 | 121 | 138 | 156 | 176 | 185 | PG | 194 | 46 | 58 | 72 | 85 | 99 | 113 | 122 | 137 | 151 | 168 | 185 | PG-13 | 223 | 46 | 61 | 76 | 92 | 110 | 125 | 138 | 150 | 162 | 176 | 185 | R | 195 | 49 | 68 | 82 | 90 | 104 | 115 | 129 | 145 | 160 | 173 | 185 | NC-17 | 210 | 46 | 58 | 74 | 84 | 97 | 112 | 125 | 138 | 153 | 174 | 184 | | 1000 | 46 | 60 | 74 | 86 | 102 | 114 | 128 | 142 | 156 | 173 | 185 |Por lo tanto, la cláusula GROUP BY
produjo una fila por clasificación y una columna de total general adicional en la parte inferior. Para fines de ilustración, he agregado la columnaCOUNT (*)para mostrar cuántas películas hay en cada grupo. Las 5 primeras filas suman 1000, que es nuevamente el total general en la parte inferior.Grafiquemos los percentiles ahora como líneas y gráficos de barras:
Podemos "ver" que no hay una fuerte correlación entre los dos puntos de datos. Ambos conjuntos de datos están casi distribuidos uniformemente, independientemente de la clasificación, con la excepción de PG-13, que está ligeramente inclinado hacia longitudes de película más largas.
Nuevamente, esto no es muy interesante ya que el conjunto de datos se generó , probablemente usando alguna aleatoriedad para evitar una distribución perfectamente uniforme. En escenarios del mundo real, los datos anteriores habrían sido más "sesgados".
¿Cómo ayuda esto con el rendimiento?
Un índice de árbol equilibrado es muy útil cuando los datos se distribuyen de manera bastante uniforme, porque en ese caso, puede ayuda para acceder a puntos de datos o rangos de datos en O (log (N)) tiempo . Esta es una propiedad bastante útil para consultas que buscan valores de ID de película, por ejemplo,
SELECCIONAR * De la película DONDE film_id = 1
Al acceder a datos "sesgados", algunos valores son más iguales que otros. Esto significa que, por ejemplo, si buscamos importes en la tabla de pagos, estas dos consultas no son las mismas:
- Se devolvieron muchas filas (3644) SELECCIONE * DESDE el pago DONDE la cantidad ENTRE 0 y 2; - Pocas filas devueltas (361) SELECCIONE * DESDE el pago DONDE la cantidad ENTRE 9 y 11;
Un índice en la columna de cantidad podría haber sido útil para la segunda consulta, pero tal vez no para la primera.
Hay varias cosas que podemos hacer para asegurarnos de que el uso óptimo del índice se aplique para todo tipo de consultas . En el caso de datos distribuidos uniformemente, generalmente no tenemos que hacer nada como desarrolladores de SQL. En el caso de conjuntos de datos "sesgados", puede valer la pena pensar en:
- Usar estadísticas de histograma
- Indicar el optimizador (en Oracle o SQL Server)
- Evitar variables de enlace (solo en casos extremos)
Conclusión
No todos los conjuntos de datos son iguales. A menudo son "sesgados". Por "sesgado", en SQL, no nos referimos al significado estadístico de una distribución normal que está sesgada asimétricamente. Queremos decir que una distribución no es uniforme, por lo que incluso una distribución normal está "sesgada". Cuando lo es, entonces algunos valores aparecen mucho más a menudo que otros. Algunos ejemplos son:
Distribución uniforme
- Claves sustitutas generadas a partir de secuencias (consecutivas)
- Claves sustitutas generadas a partir de UUIDs (aleatorias)
- Claves foráneas en relaciones de uno a uno
Slight "Skew"
Posiblemente significativo "skew"
Esto realmente depende del conjunto de datos real, pero espera un "skew" significativo en estos tipos de datos
- Claves foráneas en muchas relaciones (por ejemplo, algunos clientes tienen más Activos que otros)
- Valores numéricos (p. ej. cantidad)
- Códigos y otros valores discretos (p. ej., clasificación de películas, códigos de liquidación de pagos, etc.)
Este artículo muestra cómo podemos usar funciones agregadas de SQL simples, incluidas Los percentiles, para calcular y visualizar tal "sesgo".
No comments:
Post a Comment