Federico Razzoli

Última actualización el 8 de diciembre de 2019

Devolver filas aleatorias en un orden aleatorio desde una base de datos relacional es un problema muy difícil. En este artículo veremos un antipatrón, discutiremos por qué este problema es tan difícil, y examinaremos algunas soluciones imperfectas.

Actualización: Algunos SGBD soportan TABLESAMPLE. No lo mencioné porque hasta hoy sólo conocía la implementación de SQL Server, y no la considero buena para extraer filas aleatorias (ya explicaré por qué). Pero tras una pregunta en Facebook de Daniël van Eeden he investigado un poco, y he descubierto que la implementación de PostgreSQL podría ser mucho más adecuada. Voy a leer más sobre ello y probarlo, y entonces probablemente escribiré un segundo artículo sobre ello. De todos modos, MySQL y MariaDB no soportan TABLESAMPLE.

El camino equivocado: ORDER BY RAND()

Muchos desarrolladores piensan que pueden hacerlo de esta manera:

SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;

Esta es la única consulta que hace exactamente lo esperado. Si la función RAND() es aleatoria de forma fiable, devuelve un conjunto aleatorio de filas, donde cada fila tiene las mismas posibilidades de ser devuelta.

El problema es cómo funciona bajo el capó. Para ordenar los valores aleatorios, uno tiene que crearlos primero. Para crear un valor aleatorio para cada fila de una tabla, un SGBD tiene que leer cada fila. Así que el SGBD hará una operación de dos pasos:

1. Copiar las filas más un valor aleatorio a una tabla temporal, con suerte en memoria;
2. Ordenar las filas en la tabla temporal.

Nótese este detalle: con suerte en memoria. Dependiendo del SGBD, puede haber razones por las que la tabla necesite ser creada en disco. Normalmente, esto ocurre si la tabla es demasiado grande. Las versiones antiguas de MySQL también crean tablas temporales en disco si contienen columnas TEXT o BLOB.

Huelga decir que si la tabla es grande esta es una operación lenta que consume muchos recursos.

¿Por qué los SGBD relacionales no proporcionan una forma incorporada de devolver filas aleatorias?

Las bases de datos relacionales están construidas en torno a una rama de las matemáticas llamada álgebra relacional. Se basa en la lógica, porque trata de predicados verdadero/falso; ans similar a la teoría de conjuntos, aunque una relación es algo más complejo que un conjunto, e incluso verlo como una tabla no es matemáticamente correcto. Este artículo es un buen ejemplo de lo que quiero decir, pero hay argumentos más complejos.

A pesar de que SQL no es una implementación precisa del modelo relacional, su álgebra se utiliza como referencia. Como todas las ramas de las matemáticas, tiene un conjunto bien definido de operaciones. Obtener tuplas al azar de una relación no es definitivamente una de ellas.

Esta respuesta suena demasiado teórica, ¿verdad? ORDER BY y las tablas sin clave primaria también violan las reglas del álgebra relacional, pero SQL las soporta.

Sin embargo, para las bases de datos, la velocidad es vital. Los SGBD relacionales están diseñados para realizar operaciones relacionales muy rápidamente. Obviamente, una estructura de datos diseñada para optimizar ciertas operaciones no está optimizada para otras operaciones. Así, los SGBD relacionales no están optimizados para realizar búsquedas aleatorias.

Debería ser obvio que hacer un bucle sobre las filas para elegir algunas de ellas al azar sería lento. Teóricamente, la lectura de una fila aleatoria utilizando un índice sería tan rápida como encontrar una fila por el valor de la clave primaria. Pero entonces, diferentes filas tendrían diferentes posibilidades de ser elegidas.

La imagen de arriba es del repositorio GitHub de Jeremy Cole, innodb_diagrams. Tarde o temprano debería escribir sobre sus proyectos para analizar las estructuras de datos de InnoDB.

Lo importante aquí es que un índice es un árbol cuyos nodos son páginas de memoria. Los nodos hoja contienen datos reales; los niveles superiores sólo contienen la información necesaria para elegir el camino más corto hacia el nodo hoja deseado. Los detalles no son importantes en este contexto.

El SGBD podría teóricamente elegir una página al azar realizando una serie de decisiones aleatorias: ¿voy a la izquierda o a la derecha? Pero entonces, las páginas hoja contienen un número variable de filas. Incluso podrían estar vacías. Así, diferentes filas tendrían diferentes oportunidades de ser seleccionadas.

El resultado está claramente fuera de los casos de uso previstos por los SGBD; y puede ser lento o erróneo, dependiendo de si se utiliza un índice o no. Los SGBDs han optado acertadamente por no implementar esta característica.

Algunas soluciones

No hay soluciones perfectas. Hay soluciones que pueden ser aceptables pero tienen inconvenientes. Debemos elegir una según el caso.

Elegir aleatoriamente de un rango

Esta solución es aplicable a las tablas que tienen una clave primaria autoincremental. Es la más fácil de implementar, pero una clave primaria «fragmentada» causa problemas.

Consiste en comprobar el id mínimo, el id máximo, y generar un número aleatorio en ese rango:

No es que las consultas con MIN() y MAX() sobre cualquier índice, sin otras cláusulas, sean muy rápidas.

El resultado es una fila realmente aleatoria. Para elegir más de una fila, podemos repetir esta consulta varias veces. Esto nos lleva a dos inconvenientes:

• Si esta operación se realiza a menudo, podríamos ejecutar esta consulta muchas veces.
• No hay garantía de que no se seleccione la misma fila varias veces. Si esto ocurre, la aplicación puede reintentar la consulta. Si la tabla es grande, este evento es raro y podemos ignorarlo – a menos que la función RAND()no sea fiable. Pero para las tablas pequeñas, esto puede ser un problema.

También, una clave primaria puede tener agujeros – en otras palabras, algunos números pueden faltar. Esto se debe a eliminaciones y transacciones fallidas. Los números inferiores al máximo no se reutilizan. Para solucionar este problema, podemos utilizar dos técnicas.

Usar >=

Si utilizamos el operador >= en la cláusula WHERE, la consulta siempre devolverá una fila. Si el número generado no está presente, se utilizará el siguiente. Pero esto significa que los valores inmediatamente posteriores a un agujero tendrán más posibilidades de ser seleccionados. Cuanto mayor sea el agujero, mayores serán las posibilidades.

Puede que piense que esto no debería importarle, y probablemente tenga razón. Pero antes de que su decisión sea definitiva, considere la posibilidad de un gran agujero.

Esforzarse

Si la consulta no devuelve ninguna fila, podemos volver a intentarlo. Para tablas grandes con sólo unos pocos agujeros pequeños, esto está perfectamente bien. Pero para agujeros grandes con muchos agujeros, o agujeros grandes, esta técnica podría consumir demasiados recursos.

Por favor, no seas demasiado paranoico con esto. Simplemente haz algunos cálculos. ¿Cuál es la proporción de valores perdidos en su tabla? Esto le indica cuántas veces se reintentará la consulta, por término medio.

Seleccionar varias filas

Para seleccionar varias filas con esta técnica, podemos:

• Repetir la consulta varias veces;
• O, para un mejor rendimiento, utilizar el operador >= y usar un LIMIT mayor que uno. Sin embargo, esto hace que los resultados sean mucho menos aleatorios.

Trasladar la elección aleatoria a la aplicación

En su forma más sencilla, esta técnica consiste en elegir aleatoriamente un bloque de id’s contiguos. La aplicación elegirá aleatoriamente cuáles utilizará, y luego seleccionará las filas coincidentes.

Supongamos que se quiere elegir entre bloques de 1000 valores:

Cuanto más grande sea el bloque, más recursos consumirá, y más aleatorio será el resultado. La aplicación tiene la responsabilidad de elegir aleatoriamente los id’s únicos existentes de los bloques, por lo que nunca debería ser necesario reintentar una consulta.

La variante MOD

Un problema con esta técnica es que las filas se devuelven del mismo bloque de id’s contiguos. Esto podría ser perfectamente aceptable, especialmente si el bloque es grande. Pero si no lo es, podríamos añadir algo de complejidad para seleccionar un bloque de filas no contiguas.

La idea de esta variante es:

• Definir macrobloques de filas mayoritariamente no contiguas;
• Elegir aleatoriamente un macrobloque;
• Devolver un bloque de él.

Para ello, podemos calcular el módulo del id, y utilizarlo para seleccionar resultados aleatorios. Por ejemplo, podemos definir una columna virtual indexada con una expresión como (id MOD 4). Cada fila tendrá un valor entre 0 y 3. Aunque haya agujeros, las filas de estos macrobloques serán en su mayoría no contiguas y deberían ser aproximadamente el mismo número.

La aplicación debería generar un número aleatorio entre 0 y 3. Luego, para seleccionar bloques de estos macrobloques:

SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;

Una forma similar de implementar esta idea es usar particiones, donde la función de partición es el módulo del id. Yo sugeriría esto sólo si la tabla se beneficiara de la partición por otras razones.

Elegir una técnica

La técnica de bloques ejecuta más consultas en comparación con la primera con el operador >=, y el resultado podría ser mejor o no. En comparación con la variante retry, ésta podría ejecutar más o menos consultas, y el resultado es peor.

En general, las técnicas de bloque son mejores si tenemos agujeros en la clave primaria.

Cachear series aleatorias

Los métodos anteriores son un compromiso: rendimiento frente a mejor aleatoriedad, donde la solución más rápida también es más compleja de implementar. Mientras no utilicemos el antipatrón ORDER BY RAND(), la selección de filas aleatorias no debería causar problemas de rendimiento. Pero, ¿y si lo hace?

Podríamos almacenar en caché algunos id’s ordenados aleatoriamente obtenidos con cualquiera de las soluciones anteriores. Podríamos utilizar una consulta como esta (sintaxis de MySQL):

Podríamos utilizar las series en orden ascendente o descendente, de forma aleatoria. O la aplicación podría barajarlas.

Problemas:

• Cuando se añade un elemento, deberíamos elegir aleatoriamente si debe insertarse en una serie, sustituyendo a un elemento aleatorio.
• Cuando se elimina un elemento, deberíamos borrarlo de todas las series. Debería ser reemplazado por otro elemento aleatorio.
• Podríamos eliminar periódicamente las series más antiguas y reemplazarlas por otras nuevas, para mejorar la aleatoriedad en la experiencia del usuario.

Conclusiones

Como siempre, por favor, comenta y hazme saber si detectas algún error en este artículo, si no estás de acuerdo en algo, cuéntame tu experiencia personal, o si tienes más ideas que añadir.