Resumen

  • El optimizador de System R seleccionaba el menor coste estimado dentro del conjunto de planes que llegaba a examinar. Sumaba lecturas de páginas y llamadas a la interfaz de almacenamiento ponderadas, no segundos ya medidos.
  • La selectividad alimentaba la cardinalidad; esta cambiaba el valor aparente de índices, exploraciones, órdenes de unión y operadores. Un «orden interesante» podía justificar conservar una ruta localmente más cara por el trabajo posterior que evitaba.
  • Selinger dirigió y articuló una contribución colectiva junto con Morton Astrahan, Donald Chamberlin, Raymond Lorie y Thomas Price. Su arquitectura perdura porque permite contrastar el pronóstico con la ejecución y corregir los supuestos.

Un incidente que el coste no explica por sí solo

Imaginemos una consulta de facturación que une clientes, contratos y movimientos. El lunes devuelve el resultado en menos de un segundo. Tras una carga de datos, el martes tarda cuarenta. No hay error de lógica: las filas finales son correctas. Tampoco es necesario que el optimizador haya ignorado su propia regla: el plan lento puede ser, todavía, el de menor coste según el modelo.

La causa suele estar antes del número final. Quizá el catálogo aún describe la distribución del lunes. Tal vez dos predicados que el modelo trata como independientes están correlacionados. Una unión estimada en cien filas produce cien mil; el operador elegido para la primera cifra se derrama a disco con la segunda. El resultado semántico no cambia, pero la ruta física pierde su economía.

Esa escena resume la frontera intelectual de 1979. El optimizador debe comprometerse cuando la ejecución aún no existe. Utiliza una imagen estadística del sistema, calcula alternativas y autoriza una. Después, la realidad puede confirmar o refutar el pronóstico.

Por eso un coste bajo no es una medición de futuro. Es la conclusión de una comparación bajo condiciones explícitas, algunas visibles y otras incrustadas en el diseño.

La consulta dejó de ser un procedimiento

SQL permite declarar qué resultado se desea sin enumerar instrucciones de almacenamiento. La misma sentencia puede seguir siendo válida cuando aparecen índices, crecen las relaciones o cambia el hardware. Esa libertad exige que otra capa controle el «cómo».

En Access Path Selection in a Relational Database Management System, el flujo de System R contiene cuatro fases. El análisis prepara la representación de la sentencia. La optimización produce una especificación de acceso. La generación de código convierte esa especificación en una forma ejecutable. La ejecución ocurre al final.

El orden importa. Elegir un índice, una exploración, un orden de uniones o una propiedad de ordenamiento es una decisión anterior a la evidencia de esa corrida. El planificador no puede observar primero el tiempo total y luego escoger el plan que lo produjo; solo puede estimarlo.

También importa separar equivalencia y rendimiento. Dos expresiones relacionales pueden conservar la misma semántica y usar métodos físicos diferentes. Si las respuestas difieren, hay un problema de corrección. Si coinciden pero una llega tarde, hay un problema de estimación, planificación o ejecución. Una explicación que confunde ambas capas diagnostica mal el sistema.

Un mapa estadístico deliberadamente incompleto

System R trabajaba con estadísticas del catálogo. NCARD describía el número de tuplas, TCARD las páginas de una relación, P una medida de ocupación, ICARD las claves distintas del índice y NINDX sus páginas. El optimizador necesitaba ese resumen para comparar rutas sin recorrer previamente todo aquello que pretendía consultar.

Las estadísticas se inicializaban y actualizaban periódicamente con UPDATE STATISTICS. No se mantenían después de cada modificación: el artículo explica que las escrituras del catálogo y los bloqueos harían demasiado cara esa precisión.

La antigüedad estadística es, por tanto, una decisión económica. Observar siempre cuesta. Un resumen muy detallado y perfectamente actual consumiría recursos de escritura, almacenamiento y coordinación. Uno barato puede perder cambios relevantes. La planificación vive entre esos extremos.

Esta idea sigue siendo útil frente a la frase «las estadísticas están bien». ¿Bien para qué distribución, qué combinación de columnas, qué partición y qué instante? El catálogo no es la realidad completa; es el conjunto de señales que el sistema decidió que merecía conservar.

La cadena selectividad-cardinalidad

Para estimar filtros, System R asignaba factores de selectividad: la fracción esperada de filas que sobreviviría. La cantidad de claves distintas de un índice servía para ciertas igualdades. Sin mejor evidencia, se aplicaban convenciones: una décima parte para una igualdad sin índice, un tercio para un intervalo abierto y un cuarto para uno cerrado.

Los autores advirtieron que esos números no poseían un significado especial aparte de permitir un orden aproximado. Eran mecanismos de decisión bajo ignorancia, no constantes universales.

Las condiciones unidas por AND podían multiplicar sus factores. La operación supone independencia. En datos comerciales, esa hipótesis falla con facilidad: región y moneda, tipo de cliente y descuento, producto y temporada se mueven juntos. Multiplicar selectividades marginales puede convertir una relación frecuente en una coincidencia que el modelo cree casi imposible.

La cardinalidad convierte la proporción en filas. El cálculo QCARD combina tamaños de relaciones y selectividades, y el resultado entra en el coste de los pasos siguientes. Una subestimación temprana vuelve atractivo un bucle anidado porque parece repetirse pocas veces. En ejecución, un exterior enorme multiplica accesos. Una sobreestimación puede expulsar una ruta por índice que tocaba muy pocos datos.

No son dos nombres para lo mismo. Selectividad es un cociente esperado; cardinalidad, una cantidad. La segunda depende de la primera y del tamaño de entrada. Luego se propaga: cambia el orden de unión, el operador, la memoria, el paralelismo y los resultados intermedios.

En 2015, Leis y sus coautores observaron que los errores de cardinalidad perjudicaban más la calidad de planes que pequeñas imprecisiones del modelo de costes. Diez años después, su retrospectiva seguía señalando cardinalidad, robustez y adaptación como problemas abiertos. El punto vulnerable continúa en el mismo lugar de la cadena.

El coste como unidad contable

La ecuación de System R decía:

COST = PAGE FETCHES + W × (RSI CALLS)

Las lecturas de páginas representaban E/S. Las llamadas a la Research Storage Interface aproximaban trabajo de CPU. W expresaba un precio relativo. Incorporar ambos componentes era sofisticado y práctico, pero la suma no era un reloj.

La fórmula no sabía con exactitud qué páginas estarían calientes, cuánto costaría una lectura bajo contención, si un resultado intermedio se derramaría, qué parte consumiría el cliente ni cómo se comportaría el hardware. Convertía recursos diferentes en una moneda común para ordenar candidatos.

«Más barato» es correcto dentro de esa contabilidad. «Más rápido» es la hipótesis que nace de ella. «Óptimo» requiere especificar objetivo y universo de búsqueda. Incluso una clasificación perfecta dentro del modelo puede omitir un plan que el enumerador nunca generó.

La documentación de PostgreSQL muestra la misma frontera hoy. Los costes son unidades convencionales dependientes de la plataforma, no milisegundos. EXPLAIN presenta pronósticos sin ejecutar la sentencia; EXPLAIN ANALYZE ejecuta y añade filas y tiempos reales. Una salida explica la decisión; la otra aporta el veredicto empírico.

No confundir camino, operador y orden

El camino de acceso decide cómo llegar a una relación base: por exploración o por un índice aplicable. El operador físico decide cómo unir, ordenar o agregar. El orden de unión decide qué relaciones se combinan primero y qué volumen alimenta a los pasos posteriores.

Un índice puede reducir filas y a la vez entregar un orden. Una unión selectiva temprana puede encoger todo el resto. Un operador excelente para una entrada pequeña falla cuando la cardinalidad real es grande. Ordenar ahora puede resultar rentable si elimina otro ordenamiento más tarde.

Estas decisiones no deben ocultarse bajo la idea vaga de que «el optimizador eligió mal». Conviene localizar el tipo de compromiso: ¿faltó una ruta de acceso?, ¿la cardinalidad cambió el orden?, ¿el operador tenía otro umbral?, ¿una propiedad útil se perdió? Cada respuesta conduce a una corrección distinta.

El valor futuro de un orden

System R llamó «interesante» a un orden que podía beneficiar una unión posterior, un GROUP BY o el ORDER BY final. Un recorrido de índice podía costar más que una exploración en el paso inmediato, pero evitar un ordenamiento completo después.

El optimizador no retenía solo el plan parcial más barato. Guardaba el mejor sin orden y el mejor para cada orden interesante. Así, dos planes que producían las mismas filas se comparaban también por las propiedades físicas que llevaban consigo.

Esta decisión evita la codicia local. Un coste ligeramente mayor compra una opción: la posibilidad de que el futuro consuma el orden ya disponible. El valor no se observa si cada nodo se juzga aislado.

También delimita qué merece memoria. Conservar todo sería imposible; conservar un único ganador sería miope. Las clases por subconjunto y orden útil mantienen justamente las diferencias capaces de alterar el resto de la consulta.

Buscar planes también consume tiempo

El número de órdenes de unión crece de forma combinatoria. Probar todas las permutaciones se acerca al crecimiento factorial. Un optimizador que tarda demasiado en encontrar una buena ejecución puede destruir el ahorro que persigue.

System R aplicó programación dinámica. Construyó soluciones para subconjuntos de relaciones, conservó los mejores representantes para cada propiedad relevante y reutilizó esos resultados al añadir otra relación. Una heurística retrasó productos cartesianos, que normalmente inflan resultados intermedios sin aportar un predicado de unión.

El artículo habla de una búsqueda acotada por subconjuntos y órdenes interesantes, y relata uniones de ocho tablas optimizadas en segundos sobre un IBM 370/158. Esa disciplina volvió practicable la idea.

Sin embargo, podar no demuestra que se exploró todo lo concebible. La programación dinámica puede garantizar el mejor miembro de su espacio definido; el espacio depende de operadores, formas de árbol, equivalencias y reglas de descarte. «Globalmente óptimo» solo tendría sentido si todos esos límites se declararan.

El tiempo de optimización y el de ejecución son cuentas separadas. Ampliar la búsqueda beneficia consultas costosas; repetir ese esfuerzo para una operación breve puede ser absurdo. Un plan genérico preparado ahorra compilaciones, pero puede ser inferior si valores distintos necesitan rutas distintas.

El modelo aceptaba ser refutado

La conclusión de 1979 reconoce que las predicciones absolutas solían ser imprecisas. A la vez, el sistema elegía el mejor camino probado en la mayoría de los casos y necesitaba más validación. Un ranking puede ser útil sin estar calibrado como duración real.

Mackert y Lohman realizaron en 1986 una evaluación de R* comparando estimaciones con recursos observados. Gran parte del componente de E/S funcionaba, pero la CPU requería más detalle; los supuestos del búfer importaban; y los bucles anidados eran difíciles porque interactuaban cardinalidad de unión, cardinalidad exterior y páginas disponibles.

La formalidad no blindó la fórmula. La ejecución podía contradecirla y señalar mejoras. Esa apertura convierte el modelo en infraestructura científica: hipótesis, observación, revisión.

El trabajo posterior de IBM sobre estadísticas justo a tiempo conserva la lógica. Si una estadística separada de la optimización falta o envejeció, el planificador puede solicitar una observación dirigida cuando descubre su valor. No pretende obtener conocimiento infinito, sino comprar la evidencia adecuada en el momento adecuado.

La autoría colectiva de una líder

Patricia G. Selinger llegó a IBM Research en 1975. La historia de IBM la sitúa al frente del optimizador de System R y más tarde de R* y de organizaciones de tecnología de bases de datos. Fue nombrada IBM Fellow en 1994, ingresó en la National Academy of Engineering estadounidense en 1999 y se retiró de IBM en 2018.

El artículo de 1979 fue firmado por P. Griffiths Selinger junto con Morton M. Astrahan; también por Donald D. Chamberlin, además de Raymond A. Lorie y, finalmente, Thomas G. Price. Chamberlin, en su historia oral, atribuye a Selinger la organización del trabajo y del artículo, y nombra expresamente a Lorie, Price y Astrahan como colaboradores importantes. La historia de IBM añade el modelo relacional de Edgar Codd, el SQL de Chamberlin y Raymond Boyce, el compilador de Lorie y el programa System R completo.

Reconocer al equipo no reduce el liderazgo. Lo define con mayor precisión. Selinger articuló estadísticas, selectividad, cardinalidad, costes, propiedades físicas y búsqueda en una arquitectura implementable. Esa contribución no necesita presentarse como obra individual ni llamarse inteligencia artificial: sus métodos explícitos son suficientemente transformadores.

Una arquitectura honesta sobre la incertidumbre

El legado no consiste en encontrar una ruta eterna. Consiste en separar el significado estable de una consulta de su realización cambiante. Las estadísticas pueden enriquecerse, las correlaciones modelarse, los pesos adaptarse, los operadores aumentar y la retroalimentación modificar la decisión sin convertir cada consulta en un procedimiento manual.

El plan elegido merece llamarse pronóstico autorizado. Ganó la comparación que el sistema supo realizar con la evidencia disponible. Solo la ejecución dirá si su cardinalidad, recursos y duración se acercaban a la realidad.

Guardar ambas historias —estimación y observación— permite aprender. El optimizador responsable no promete infalibilidad; expone qué creyó, qué eligió y qué ocurrió.

Fuentes