Exploración de tablas y exploración de índice en SQL

Question

¿Cuál es la diferencia entre la exploración de tabla y la exploración de índice en SQL y dónde se usa específicamente?

Answer 1

Exploración de tabla significa iterar sobre todas las filas de la tabla.

Exploración de índice significa iterar sobre todos los elementos de índice, cuando el índice de elemento cumple la condición de búsqueda, la fila de la tabla se recupera a través del índice.

La exploración de índice de Usualy es menos costosa que una exploración de tabla porque el índice es más plano que una tabla.

Son mucha bibliografía sobre este tema. Muestra:

• Microsoft: Which is Faster: Index Access or Table Scan?:

acceso Índice es un método de acceso en la que SQL Server utiliza un índice existente para leer y escribir las páginas de datos. Debido a que el acceso al índice significativamente reduce el número de operaciones de lectura de E/S, a menudo supera un escaneo de tabla .

• Oracle: The Query Optimizer

En este método, una fila se recupera por la que atraviesa el índice, utilizando los valores de columna indexadas especificados por el comunicado. Un análisis de índice recupera datos de un índice basado en el valor de una o más columnas en el índice. Para realizar un análisis de índice, Oracle busca en el índice los valores de columna indexados a los que accede la instrucción. Si la instrucción accede solo a las columnas del índice, Oracle lee los valores de las columnas indexadas directamente desde el índice, en lugar de desde la tabla.

• MySQL: How to Avoid Table Scans

Answer 2

La mayoría de los motores de consulta tienen un optimizador de consultas, que trata de generar una estrategia efectiva ejecución de la consulta. Si los índices están disponibles, lo que puede hacer que una consulta sea más rápida, el optimizador de consultas realizará un análisis de índice o búsqueda de índice, de lo contrario, un examen de tabla.

Ejemplo:

SELECT * FROM tbl WHERE category_id = 5; 

Si no hay índice en category_id continuación, se realizará una exploración de tabla, es decir, cada registro individual en la tabla será inspeccionado para la category_id derecha.

Sin embargo, si category_id está indexado, las cosas se vuelven más complicadas. Si la tabla es muy grande, probablemente se elija una búsqueda de índice. Sin embargo, si la tabla es pequeña, el optimizador puede decidir que una exploración de tabla sea aún más rápida, ya que se requiere una sobrecarga para acceder a un índice. Si category_id no es lo suficientemente selectivo, por ejemplo, si solo hay dos categorías, escanear la tabla puede ser más rápido incluso para tablas grandes.

Los índices suelen estar organizados como estructuras de árbol. Encontrar un elemento en un árbol es una operación O (log n).Un escaneo de tabla es una operación O (n). La velocidad está determinada principalmente por la cantidad de accesos al disco requeridos para realizar la consulta. Buscar primero el índice y luego acceder a la tabla para las entradas encontradas puede generar más accesos al disco para tablas pequeñas.

Vamos a echar un vistazo a otra consulta:

SELECT category_id FROM tbl WHERE category_id BETWEEN 10 AND 100; 

Aquí hay otra opción disponible. Una búsqueda de índice podría no ser más rápida que una exploración de tabla en esta situación, pero, dado que solo estamos recuperando catergory_id, un análisis de índice (no búsqueda de índice) podría ser aún más rápido. Un análisis de índice lee cada entrada de la tabla de índice en lugar de aprovechar la estructura de árbol (lo que hace la búsqueda de índice). Sin embargo, dado que la información solicitada está completamente contenida en el índice, no se requerirá acceso a la tabla de datos. La exploración de índice es, como la exploración de tabla una operación de O (n), pero dado que el índice es generalmente más pequeño que la tabla, se requieren menos accesos de disco para escanear el índice que para escanear la tabla.

Todo el asunto es muy complicado y depende mucho del motor de la base de datos. Si quiere saber más, lea la documentación provista por el proveedor de db.

Answer 3

Como @danihp ha respondido la primera parte de la pregunta, intentaré responder al segundo "donde se usa específicamente". Esto es para Oracle, pero es cierto para la mayoría de RDBMS.

Supongamos que tenemos una tabla my_table, que está indexado de forma única en una columna id y tiene un segundo índice, que es no único, en la columna de yet_another_column:

create my_table (id varchar2(20) not null 
       , another_column not null 
       , yet_another_column 
       , constraint pk_my_table primary key (id) 
       ); 

create index i_my_table on my_table (yet_another_column); 

Ahora, si tuviéramos que select * from my_table where id = '1' esto debería/debería hacer un escaneo de índice único del índice pk_my_table. Luego volvemos a ingresar a la tabla, usando el índice, para devolver todo en my_table donde id = '1'.

Si la consulta fue, en cambio, select id from my_table where id = 'a', entonces no hay necesidad de la segunda etapa, ya que todos los valores que necesitamos están contenidos en el índice. En este caso, la consulta solo haría un escaneo de índice único .

A continuación, si nuestra consulta se select * from my_table where yet_another_column = 'y' entonces tenemos un índice en la columna, pero no es único así que vamos a tener que mirar a través de todo el índice para tratar de encontrar todos los valores que coinciden con nuestra condición donde , es decir, un escaneo de índice . Una vez más, seleccionamos columnas que no están en nuestro índice, por lo que debemos volver a ingresar a la tabla para obtenerlas.

Por último, si nuestra consulta fuera select id from my_table where another_column = 'yes'. No tenemos índice en another_column, por lo que tenemos que hacer una exploración de tabla para encontrar el valor, es decir, tenemos que encontrar todo en la tabla where another_column = 'yes'.

Ahora, no parece haber mucha diferencia, entre un escaneo de tabla y un escaneo de índice en estos casos. Todavía tenemos que ir y encontrar un valor en un objeto en la base de datos. Sin embargo, como el índice es mucho más pequeño y está especialmente diseñado para ser escaneado (ver otras respuestas) es generalmente mucho más rápido hacer un escaneo de índice si solo desea una pequeña proporción de las filas en la tabla. Si quiere decir el 10% de la tabla, este punto se convierte en "depende".

Answer 4

Para SQL Server al menos:

Un recorrido de índice puede ser más rápido, ya que, presumiblemente, el índice no cubre todo el conjunto de columnas en la tabla, mientras que una tabla (o índice agrupado) de exploración tiene que leer todos los datos. Si un índice incluye todas las columnas de la tabla, entonces debería ser más o menos equivalente a un escaneo de tabla, y la elección entre un escaneo de índice y escaneo de tabla (o CIX) será un lanzamiento de moneda. La diferencia es que cuando tiene menos columnas en el índice, puede incluir más filas de índice en una página de 8kb, lo que genera menos páginas generales que debe leer para escanear todos los datos en el índice.

Para ilustrar lo que quiero decir, imagínese si tiene dos copias de la guía telefónica, una con su apellido, nombre, dirección postal y número de teléfono, y otra con el apellido, el nombre y el número de teléfono. Ahora imagine que debido a que la dirección de la calle no tiene que estar impresa, puede incluir dos columnas adicionales de nombres y números de teléfono en cualquier página de la guía telefónica. El resultado final de esto es que la guía telefónica es más delgada, porque puede caber la misma cantidad de números de teléfono en menos páginas. Luego, imagina que te cobran por contar la cantidad de números de teléfono en el libro. ¿Cuál elegiría, el que tiene la dirección de la calle (que tiene más páginas, análoga a una exploración de tabla) o el que no tiene la dirección (que tiene menos páginas, análoga a la mayoría de las exploraciones de índice)? Yo elegiría el que tenga menos páginas.

Otra arruga en esto es que algunos índices se pueden filtrar, lo que significa que no solo tienen menos columnas en la mayoría de los casos (y por lo tanto caben más filas en una sola página), sino que también pueden tener una cláusula WHERE elimina muchas filas. En este caso, un escaneo de índice será mejor que un escaneo de tabla (pero esto solo funcionará para consultas que tengan una cláusula WHERE coincidente y la misma semántica).