¿Cómo implementan las bases de datos SQL 'ORDER BY x'?

Question

Me pregunto cómo funcionan debajo del capó, especialmente para grandes conjuntos de resultados. Por ejemplo, ¿el DB probablemente escribiría el resultado en bruto en el disco y luego haría una ordenación externa?

También me pregunto cómo funciona esto con LIMIT ... OFFSET. Si el DB no puede utilizar un índice existente, parece que el DB tendría que ordenar todo y obtener el subconjunto del conjunto de resultados sin procesar.

Answer 1

Los índices están ordenados; si hay un índice adecuado, que será utilizado. De lo contrario, deberán ordenar, como supones. El plan de ejecución para una consulta (que puede obtener, por ejemplo, EXPLAIN o client menus; el método exacto para obtenerlo varía con el DBMS) puede contener sugerencias sobre cómo se ordenará una consulta.

Ver:

1. MySQL: ORDER BY Optimization
2. PostgreSQL: Indexes and ORDER BY
3. SQL Server Indexes
4. Oracle: Understanding Indexes

Answer 2

Usted puede encontrar esta página interesante:

http://dev.mysql.com/doc/refman/5.6/en/order-by-optimization.html

Answer 3

MySQL muestra su propia Orden Por optimización de this link

Oracle muestra teor propia Orden Por un procedimiento algoritmo here

Básicamente, si usted tiene un índice, se ordena. Pero cuando no se realiza la clasificación, que es O(n log n)

Answer 4

Tiene prácticamente todo el derecho a ello. Si no se preparó ni planeó nada (es decir, índices o datos previamente preparados o almacenados en caché), entonces sí, se deben leer todos los datos que se deben considerar para generar el orden correcto y si la cantidad de datos a ser trabajado no puede caber en la memoria disponible/asignada, entonces el almacenamiento en caché del disco tendrá que hacerse.

Es un problema de rendimiento no trivial, y cada RDBMS tendrá formas inteligentes de abordarlo y optimizarlo, para que pueda utilizar su producto y no ese imitación de la marca "Marca X".