Optimización de Consultas SQL Mediante Índices Efectivos

A continuación, encontrarás una propuesta completa de solución organizada exactamente en el mismo orden que aparece en el examen.

La he escrito como si fuera tu hoja de respuestas: cada apartado incluye la explicación breve que suelen pedir y, cuando procede, justificación de por qué descarto las alternativas que no elijo.

1. Conceptos Fundamentales de Indexación y Hashing

1 a) Tres métodos de resolución de colisiones en hashing interno

Método propuesto	Idea en una línea	Ventaja principal	Inconveniente típico
Encadenamiento (separate chaining)	Cada celda de la tabla guarda un puntero a una lista (o vector) con todas las claves que caen en ese índice.	Sencillo y permite factor de carga α > 1 (la tabla nunca “se llena”).	Necesita punteros, lo que implica más memoria; las listas no están contiguas, resultando en peor localidad de caché.
Direccionamiento abierto (open addressing)	Todas las claves se guardan dentro del propio array: si la posición `h(k)` está ocupada se busca otra siguiendo una secuencia de sondeo (lineal, cuadrático, etc.).	No usa listas ni punteros, lo que lo hace muy compacto y con buena localidad de referencia.	A medida que α→1 crece el número de intentos; puede aparecer clustering (agrupamiento de claves).
Dispersión múltiple (multi-hash / double hashing)	Se aplican varias funciones hash; si la primera da colisión se prueba con la segunda, tercera… o bien se usa la segunda como paso de salto (`h(k)+i·h₂(k)`).	Distribuye mejor las claves, reduce el clustering y mantiene buen rendimiento incluso con cargas altas.	Requiere varias funciones hash “buenas” y aumenta algo el cálculo; si no son coprimas con M, se pueden repetir posiciones.

1 b) Problemática de los filtros LIKE en los índices

Un índice B⁺ solo se aprovecha si la condición fija un prefijo del campo.
Ejemplo: WHERE apellidos LIKE 'Garcia%' usa el índice porque el patrón empieza por texto fijo.
En cambio, patrones como '%cia' o '_arc%' no lo usan: el comodín inicial impide conocer la posición donde empezar a buscar, forzando un escaneo completo o requiriendo un índice invertido.
Además, la mayoría de SGBD convierte el patrón a mayúsculas/minúsculas según la collation, haciendo que los índices “normales” sean todavía menos efectivos con LIKE.

1 c) ¿Una IOT es un índice agrupado?

Sí.

En una Index-Organized Table (Oracle, MySQL InnoDB CLUSTERED, SQL Server clustered index) las filas están almacenadas físicamente dentro de las hojas del árbol B⁺ ordenadas por la clave primaria.

Eso cumple la definición de índice agrupado (clustered): los datos y el índice comparten la misma estructura ordenada, lo que permite un acceso muy rápido por rango de la clave, pero solo puede existir uno por tabla.

Según las hipótesis del enunciado (80 profesores/departamento, muchos departamentos y profesores, distribución uniforme), las igualdades en las cláusulas WHERE son selectivas y los JOIN son por clave primaria/foránea.

2. Selección de Índice para Consulta con Filtros Compuestos

SELECT pnombre, edad, despacho
FROM   PROF
WHERE  sexo = :X  AND  especialidad = :Y;

Opción	¿La elijo?	Motivo
a. B⁺ no agrupado sobre (sexo, especialidad)	✔	Compuesta por las dos columnas filtradas, con una selectividad aproximada de 1/(2 * N_especialidades) ≪ 1, lo que resulta en pocas tuplas. No conviene agrupar porque «sexo» solo tiene 2-3 valores, lo que en un índice agrupado crearía “islas” enormes y reduciría el aprovechamiento para otras consultas.
b. Mismo índice agrupado	✘	“Sexo” tiene una cardinalidad muy baja, lo que haría que la mitad de la tabla quedara en un lado del disco y la otra mitad en otro, resultando en mal clustering.
c. Agrupado por (especialidad)	✘	Necesita además filtrar por sexo, por lo que el índice se usa solo parcialmente.
d. No agrupado por (especialidad)	✘	Peor selectividad (ignora sexo).
e. No crearía índice	✘	El filtrado sí es selectivo, por lo que un índice reduce mucho las operaciones de E/S.

3. Estrategias de Indexación para Consultas con Joins y Subconsultas

CONSULTA 1

SELECT pnombre
FROM   PROF, DEPT
WHERE  DEPT.did = PROF.dept_id
AND  DEPT.director_ssno = PROF.ssno;

Opción	¿La elijo?	Motivo
a. Índices B⁺ agrupados (did, director_ssno) en DEPT y (dept_id, ssno) en PROF	✔	Ambos joins se resuelven con *index-only nested-loops* y los dos índices están clusterizados, lo que implica pocas E/S y un orden compatible para un merge-join si el optimizador lo prefiere.
b. Igual que a) pero no agrupados	✘	Más E/S porque tras el índice hay que saltar a la tabla (lookups); sin orden físico.
c. Solo índice agrupado en PROF(dept_id, ssno)	✘	Falta índice en DEPT, lo que fuerza un escaneo completo de DEPT (coste ≈ número de departamentos).
d. Solo índice agrupado en DEPT(did, director_ssno)	✘	Ídem, pero el escaneo completo sería en PROF (tabla mucho mayor).
e. Índice agrupado en PROF(ssno)	✘	No cubre dept_id, por lo que no sirve para la mitad del join.

CONSULTA 3

SELECT pnombre, edad, sexo, puesto
FROM   PROF
WHERE  edad = (SELECT MIN(edad) FROM PROF)
AND  ssno IN (SELECT director_ssno FROM DEPT);

Opción	¿La elijo?	Motivo
a. B⁺ agrupado sobre (edad) de PROF	✔	El `MIN` se resuelve leyendo solo la primera hoja del índice; con la edad obtenida, se hace un range scan sobre el índice (muy pocas filas). La lista de `director_ssno` es pequeña (1 por departamento), por lo que basta un hash join en memoria.
b. Índices no agrupados (director_ssno en DEPT + edad en PROF)	✘	Peor que a): más lookups, sin ventaja de “primera hoja”.
c. Agrupados en director_ssno y edad	✘	El índice extra en DEPT no mejora: para enumerar todos los directores se leerían todas las hojas del índice (similar a escanear la tabla entera). Implica un coste extra de mantenimiento.
d. Solo director_ssno agrupado	✘	Falta el índice clave (edad), por lo que habría que escanear la tabla completa de PROF para encontrar el mínimo.

4. Propuesta de Conjunto de Índices Óptimos

(El SGBD soporta planes index-only, así que añadimos las columnas proyectadas para “cubrir” cada consulta).

Nº Cons.	Índice propuesto	Agrupado	Justificación
1	DEPT(did, director_ssno)	Agrupado	El orden natural de la tabla ya es por `did`; añade `director_ssno` manteniendo el clustering.
	PROF(dept_id, ssno, pnombre)	Agrupado	Cubre los dos atributos del `JOIN` y las columnas seleccionadas, permitiendo un plan index-only y un scan ordenado.
2	PROF(sexo, especialidad, pnombre, edad, despacho)	No agrupado	Concisión: es un índice ancho, pero cubre toda la consulta y es muy selectivo; es preferible dejar la tabla principal ordenada por su clave primaria.
3	PROF(edad, ssno, pnombre, sexo, puesto)	Agrupado	El clustering por edad permite localizar el `MIN(edad)` en una sola operación de E/S y luego leer pocas hojas consecutivas del índice.
	DEPT(director_ssno)	No agrupado	Es pequeño (una clave por departamento); basta con que no sea agrupado.

(Nota: Si se quisiera minimizar el espacio, se podría fusionar el índice de la Consulta 3 con el de la Consulta 2, pero se perdería el clustering por edad.)

5. Ejecución Detallada de la Consulta 1 con la Opción Seleccionada

Scan sobre el índice agrupado DEPT(did, director_ssno)
Se recorre secuencialmente el índice (aproximadamente el número de departamentos, D), ya que ambas columnas forman la clave primaria del índice agrupado.
Para cada par ⟨did, director⟩ encontrado, se procede al paso 2.
Nested Loop Join usando el índice agrupado PROF(dept_id, ssno, pnombre)
Se realiza una búsqueda (probe) en el índice de PROF con la clave compuesta ⟨did, director⟩ (que se corresponde con ⟨dept_id, ssno⟩).
- Dado que el índice es agrupado, la localización es O(log N), y todas las coincidencias para una clave dada aparecen contiguas (normalmente en una sola hoja).
- Las hojas del índice contienen también el pnombre, por lo que no es necesario acceder a la tabla base (plan index-only).
Producción de Resultados
Los pnombre encontrados en las hojas del índice se devuelven directamente. Como el plan es index-only, no hay accesos adicionales a la tabla base (table lookups).