Hace no mucho escribí una entrada en este blog sobre, bromas aparte, cómo no escribir código SAS. Habría respondido in situ a uno de los comentarios que hicieron mis lectores pero, abusando de mi condición de dueño del blog, lo voy a hacer desde más encumbrado púlpito: una entrada ad hoc. Conste que escribo para discrepar. Pero conste también que lo hago desde la más genuina cordialidad y con la esperanza de generar un debate que a todos nos enriquezca.

El comentario venía a ser una crítica al uso de SQL dentro de SAS motivada parcialmente por el hecho de que quienes abusan de tal procedimiento de SAS son, precisamente, quienes menos SAS conocen (opinión con la que estoy bastante de acuero).

Dicho lo cual, manifestaré que cuando programo en SAS suelo utilizar SQL siempre que me es posible por las razones que enumero a continuación.

Las tres primeras son anecdóticas:

• SQL es parte integrante de SAS Base tanto como los pasos data. No es como SAS IML, SAS SCM u otros lenguajes de dominio que pueda vender SAS Institute.
• SAS utiliza SQL profusamente: por ejemplo, prácticamente todo el código que genera su herramienta de ETL es SQL (con algún paso data circunstancial para usar hashes y poco más). ¡Algún motivo tendrá!
• SAS, de alguna manera, promueve el uso de SQL. Véase si no este artículo que plantea 10 motivos (no los más poderosos) para usar SQL.

Consideraciones de legibilidad

La legibilidad es condición imprescindible para que el código sea bueno. Dejando aparte el hecho de que un código legible suele ser más eficiente que otro que no lo es, la legibilidad es condición indispensable para la mantenibilidad. Y comparemos dos pedazos de código aparecidos en un artículo que ya conocemos. El primero es el código feo y malo:

proc sort data=sales;
by region;
proc summary data=sales nway;
by region;
var saleprce;
output out=stats
mean=meansale;
data report;
merge stats sales;
by region;
if saleprce gt meansale;

El segundo es una reescritura del primero usando SQL:

proc sql;
create table report as
select * from sales
having saleprce gt mean(saleprce)
group by region;

Menos de la mitad de caracteres, muy expresivo.

Condiciones de interoperabilidad

El código bueno tiene que ser interoperable. Tiene que poder ser analizado y modificado por diversos usuarios. Y muchos conocen SQL (todos si yo fuese ministro de educación) pero sólo una minoría conoce la enrevesada sintaxis de un lenguaje sesentero.

Además, código que utiliza SQL es más fácil de migrar a otros sistemas y entornos fuera de SAS. Quien hubo de trabajar en uno de tales proyectos sabrá muy bien a qué me refiero.

Condiciones de rendimiento

Una de las pegas que los programadores de SAS de la vieja escuela ponen al uso de SQL en sus programas es el rendimiento. Gustan alegar que merge es mucho más eficiente que un join de SQL. Y eso siempre me parece síntoma de que la Wikipedia se lee menos de lo que se debiera. Existen varios algoritmos para cruzar tablas, uno de los cuales, el llamado merge join, es:

• Uno de los menos eficientes (con las salvedades que apunto debajo).
• El que usa merge en SAS Base.

Un merge join ordena las tablas que se quieren cruzar primero y luego lee filas una a una buscando coincidencias. Es el mejor algoritmo de cruce sólo cuando las tablas iniciales estás ordenadas precisamente por los campos de cruce. En el resto de los casos, es el algoritmo menos recomendado.

No sé qué técnica de cruce utiliza PROC SQL. Pero en el peor de los casos puede optar por un merge join y tener, cuando menos, el mismo rendimiento que merge. Si utiliza otro (o, mejor aún, si utiliza el que el optimizador considera más adecuado a la vista de los datos), sólo puede ser mejor.

Puede que quienes programaron SQL en SAS sean mucho más tontos que el resto de los programadores de la empresa y que, por lo tanto, el rendimiento de SQL sea inferior al que cabría esperar. Pero también es cierto que si un día los despiden y contratan a otros más avispados, el rendimiento de las aplicaciones podría mejorar substancialmente sin cambiar una sola línea de código.

SQL, ¿siempre?

No, hombre, no. No seamos como el proverbial tonto del martillo. Hay motivos poderosos para usar SQL, pero hay cosas que se hacen mejor programáticamente. Por ejemplo, cuando se usa first o last, cuando hay que echar la vista atrás para comparar la línea actual con alguna previa (operaciones que, merece la pena advertir, forman parte de las nuevas especificaciones del estándar de SQL). Pero fuera de eso, honestamente, no.

Y, para el caso, Postgres y OpenOffice.

Pues en que quienes los diseñan piensan que los usuarios finales son, somos,  abuelitas. Y por tanto, toman decisiones por nosotros (usar mayúsculas donde no se debe, cruzar tablas como les da la gana, empeñarse en que incoar se escribe con hache intercalada, etc.). En particular, mi queja de hoy se refiere a lo estúpidos que pueden llegar a ser los presuntos optimizadores de consultas en bases de datos y en un pequeño —aunque universal— método para doblegarlos a nuestra voluntad soberana.

Ya sé, ya sé que este tipo de problemas es consustancial a eso tan moderno que son los lenguajes declarativos, como lo es R, a los que soy tan afín: uno dice qué quiere y delega la tediosa labor de cómo hacerlo. Pero sus implementadores deberían mostrar algún grado de respeto hacia quienes hemos aprendido a no dispararnos en el pie gratuitamente.

Y paso a describir el problema de hoy (en Teradata, por centrar ideas). En primer lugar, presentemos nuestras tablas:

• A es una tabla enorme, del orden de 1.000 millones de filas (de ahí que su nombre esté en mayúsculas).
• b es una tabla de 250.000 filas que cruza con A
• c es una tabla pequeña, de 800 filas que cruza con b

El objetivo es cruzar A, b y c para después agregar por ciertos campos de A y c. Veamos la query (simplificada en extremo):

select
     A.c1, A.c2, c.c3, c.c4, sum( A.c5 ) as c5
from
     A join b  on ( A.c1 = b.b1 and A.c2 = b.b2 )
       join c  on ( b.b1 = c.c3 and b.b3 = c.c6 ) 
group by
     1, 2, 3, 4
;

Si llamamos (a,b) al operador que cruza las tablas a y b, entonces se sabe que:

• (A,b) es una tabla inmensísima, mucho mayor que A
• (b,c) es una tabla mucho menor que b

Es evidente que el plan de ejecución adecuado es (A, (b,c)), y no ( (A,b),c). Pero éste último es en el que se empeñaba el cretino del optimizador de Teradata independientemente del orden en que se escribiesen los cruces o el número de paréntesis en que se quisiese encerrar el cruce (b,c).

Quoi faire?

Existe un ardid, un ardid universal, un ardid ladino, que merece ser anotado en la primera página de todos los vademécums de ardides y que consiste en reescribir así la query:

select
     A.c1, A.c2, c.c3, c.c4, sum( A.c5 ) as c5
from
     A join b  on ( A.c1 = b.b1 and
                    A.c2 = b.b2 || substring ( c.c3, 3, 0 ) )
       join c  on ( b.b1 = c.c3 and b.b3 = c.c6 ) 
group by
     1, 2, 3, 4
;

¿En qué consiste? En el cruce de A con b se introduce subrepticiamente una dependencia con c. Es una dependencia, sí, porque involucra una columna de c. Y es subrepticia porque no altera para nada el valor de la columna de cruce real, la de b: no se le añade ningún caracter de la columna de c.

Alternativamente, para campos numéricos, se puede sumar a un valor de b cero por un valor de c o cosas similares. En eso la imaginación del lector habrá de ser ley.

Existen alternativas. Teradata, se ha demostrado hoy, las tiene. Existen mecanismos, como si heredados de la moderna pedagogía, que tratan de educar al optimizador: un adulto lo guía pacientemente proponiédole, a guisa de juegos con figuras de colores, estadísticas sobre combinaciones de variables. Con paciencia, a través de esas estadísticas que luego nunca nadie recrea cuando se debe, se puede lograr el deseado fin. Al menos, una vez, en desarrollo y con propósitos ilustrativos.

No sé cómo tomarme que este ardid —que paga la hipoteca de los yates de algunos afamados gurús de la optimización de consultas— haya sido saludado con un “tu (no es mío) truco (no es un truco: es una estrategia victoriosa) no es generalizable (dígame Vd. dónde pudiera no funcionar, señor valedor de una tecnología caduca)”.

Lo importante es, no obstante, que las estirpes de consultores condenados a cien años de overtime disponen, por fin, de una alternativa sobre la faz de la tierra.

No hace mucho me enfrenté con un problema en el trabajo. Quería cruzar dos tablas, una de algunos miles de millones de registros y otra de algunos cientos de miles para, simplemente, contar el número de filas finales que aparecían por fecha.

Cada una de las tablas tenía algunos filtros y agregaciones; el cruce final se realizaba sobre las subconsultas resultantes. El gestor de bases de datos que utilizamos, Teradata (sin comentarios), no podía con el cruce: las decisiones que tomaba internamente el presunto optimizador de consultas conducían inexorablemente a un error de espacio.

Decidí comprobar si esta tarea que una instalación de Teradata de varios millones de euros de precio era incapaz de realizar podía llevarse a cabo en mi pequeño ordenador con el software adecuado. Así que realicé las dos subconsultas independientemente, volqué los resultados a sendos ficheros de texto (de 5 y 367MB respectivamente, que corresponden a 150k y 12M de filas) y los cargué en R.

Tras algunas modificaciones en los datos (cambios de tipos y nombres de las columnas, etc.) obtuve dos dataframes:

> head(epi)
 cta prtda
1 8301 77920
2  476 45526
3 5350 65100
4  878 46057
5 6614 80059
6 8470 78830

de 150.000 filas que asigna a cada cuanta, cta, una serie de partidas, prtda, y

> head( saldos )
 fec cta ofi
[1,]   1   4  40
[2,]   1   4  70
[3,]   1   4   1
[4,]   1   4  11
[5,]   1   4  21
[6,]   1   4  31

de 12 millones de filas que para cada fecha, fec, y oficina, ofi, lista los correspondientes tipos de cuenta, cta, existentes.

Estas tablas cruzan por el campo cta, cuenta. A cada cuenta le corresponde una partida y el objetivo final era saber para cada fecha (fec), cuántas combinaciones de oficina (ofi) y partida existían. Un merge directo requería más memoria de la disponible, así que fabriqué el cruce a mano mediante el siguiente código:

foo <- function( prtda ){
    tmp <- epi$cta[ epi$prtda == prtda ]
    unique( subset( saldos, cta %in% tmp, select = c( fec, ofi ) ) )
}

tmp <- sapply( unique( epi$prtda ), foo, simplify = F )
table( do.call( rbind, tmp )$fec )

El código aplica a cada partida la función foo que hace lo siguiente:

1. Selecciona las cuentas que la tienen asociada en la tabla epi.
2. Devuelve una subtabla de saldos que contiene las fechas y oficinas en las que existe esa cuenta.

Finalmente, estas subtablas se apilan y la función table cuenta el número de filas por fecha.

Aunque tal vez no sea la manera más rápida de hacerlo, se trata de la implementación manual del método de los bucles anidados para realizar cruces de tablas. Que es, de hecho, el más robusto (en el sentido de que utiliza la mínima cantidad posible de memoria) y, aunque no siempre sea el óptimo, no suele estar nunca muy alejado de él. Eso dice,al menos, la teoría.

Para implementar correctamente el algoritmo de los bucles anidados uno debe recorrer la tabla más pequeña y buscar las coincidentes, una a una, en la más grande. Y para que el proceso no se eternice, el acceso a esta última debe realizarse a través de un índice.

En R no hay índices y, de hecho, casi todo el tiempo de ejecución se consume en

subset( saldos, cta %in% tmp, select = 1:2 )

Recordemos que saldos tiene 12 millones de líneas y ese comando implica:

1. Ver cuáles de las cuentas de un vector de longitud 12 millones están contenidas en el vector tmp (de longitud media 15).
2. Seleccionar dichas filas de una tabla de longitud 12 millones.

Aunque esas operaciones son muy rápidas para tablas pequeñas (para las que R fue concebido originalmente, téngase presente), 12 millones es un número lo suficientemente elevado como para que O(n) —el tiempo que consume una búsqueda lineal, que es la que hace subset en un data.frame— sea significativamente superior a O(log n) —el de una búsqueda binaria.

Pero el paquete data.table enriquece R con una nueva estructura de datos, las data.tables, que vienen a ser data.frames indexados. Usando dicho paquete, se puede hacer

saldos <- data.table( saldos )
setkey( saldos, cta )
foo <- function( prtda ){
   tmp <- epi$cta[ epi$prtda == prtda ]
   unique( data.frame( saldos[ J(tmp), j = c( "fec", "ofi" ),
        mult = "all", with = FALSE ] ) )
}

La primera línea transforma saldos de un data.frame en un data.table. La segunda, lo indexa por la columna cta. La única diferencia en la función es que para filtrar por tmp se utiliza la expresión

saldos[ J(tmp), j = c( "fec", "ofi" ), mult = "all", with = FALSE ]

que busca en saldos utilizando el índice sobre cta. El porqué de esta sintaxis, tal vez poco intuitiva, puede consultarse en las ayudas del paquete.

Los tiempos de ejecución para la primera alternativa son de

> system.time( kk <- sapply( unique( epi$prtda ), foo, simplify = F ) )
 user  system elapsed
5566.15  873.94 7088.15

mientras que para la segunda quedan en:

> system.time( tmp <- sapply( unique( epi$prtda ), foo, simplify = F ) )
 user  system elapsed
 994.96   18.63 1776.70

Aunque los tiempos reales (elapsed) son muy elevados hay que tener en cuenta que, en mi prueba, están exagerados por las circuntancias de la ejecución: simultáneamente en una misma máquina, con restricciones de memoria y, por lo tanto, algo de paginación. En cualquier caso, lo verdaderamente relevante son los ratios entre ambos procedimientos, muy favorables para las data.tables con respecto a los data.frames originales.

En resumen, gracias al trabajo de Matthew Dowle, disponemos de un nuevo paquete, data.table, que va a conseguir que nuestro código en R vuele cuando tengamos que realizar búsquedas en tablas grandes.

No es éste foro para opinar sobre si nos interesa la Madre Teresa o si los patriotas son idiotas, pero sí para mostrar nuestro desacuerdo con la canción (por abreviar, acá está su letra) y dejar claro que las jerarquías no son una porquería. Si no que se lo digan a un indirecto cliente mío que consume lo que no nos devuelve a los accionistas como dividendo en pagar hordas de consultores poco avisados de lo que acá cuento. Y lo cuento y dejo públicamente escrito para que tengan todavía menos excusa.

El tema que sigue a tan críptico introito es el de las queries recursivas, que forman parte de SQL ANSI desde la revisión de 1999. Para ilustrar lo que cuento usaré PostgreSQL 8.4, que es la primera versión que las implementa.

Comenzaremos, como abreboca, calculando el factorial de un número mediante una query recursiva.

with recursive factorial as (
    select 1 as n, 1 as fact
        union all
    select
        n + 1 as n,
        a.fact * (n + 1) as fact
    from
        factorial as a
)
select * from factorial limit 10;

La última línea de la query es simple: toma todo lo que lo precede como una tabla y extrae 10 líneas de ella. Nótese que en este caso, de no limitar el tamaño de la consulta, ésta continuaría indefinidamente (indefinidamente en este contexto significa hasta que el factorial excediese el tamaño del tipo de dato que lo contiene). Lo importante es lo que ocurre en las líneas anteriores.

Una cláusula with permite definir una tabla temporal que se usa al vuelo en una consulta subsiguiente. Es mero azúcar sintáctico para simplificar la construcción de queries complejas. Un ejemplo triival es:

with tabla_temporal as ( select 1 as valor )
select * from tabla_temporal;

Es decir, con with se puede crear una tabla (la expresión que aparece entre paréntesis) que puede ser utilizada en la query subsiguiente. Conozco a un tipo al que este tipo de construcciones ayudaría a mitigar el innato culteranismo esecueliano del que hace gala con perniciosos efectos para el bienestar de sus exégetas.

Si with se acompaña de recursive, la tabla que se define fuera del paréntesis puede invocarse dentro de él, como en el ejemplo del cálculo del factorial. En él, entre paréntesis, aparecen dos tablas concatenadas mediante un union all. La segunda se construye mediante una referencia a factorial, que se define fuera del paréntesis. Utilizando un símil markoviano, la primera tabla sería el estado inicial y la segunda definiría la transición. El union all permitiría seguir la traza del paseo markoviano.

Modificando la query anterior se puede construir, por ejemplo, el otro ejemplo paradigmático de la recursividad: la sucesión de Fibonacci. Pero ya lo ha hecho alguien por mí.

Información sobre cuestiones relativas a cómo ejecuta PostgreSQL este tipo de quieries puede obtenerse de aquí.

Y, retomando el tema con el que se encabezaba esta entrada, indicaré que el uso principal de queries recursivas en la práctica es el de desenvolver tablas que implementan jerarquías. Imagínese el caso de las piezas de un determinado modelo de avión. Este avión, nivel más alto de la jerarquía, consta de varias partes (fuselaje,…) que respresentarían el segundo nivel más alto. Y así sucesivamente hasta llegar hasta la más humilde arandela. Asignando un determinado código a cada uno de los miembros de la jerarquía, la relación es parte de puede implementarse mediante una tabla de la forma:

La tabla anterior puede contener sólo la relación directa: el ala izquierda “es parte” del fuselaje, pero no “directamente” del avión. ¿Cómo enumerar las arandelas que forman parte del ala derecha del avión? ¿Cómo descender por la cadena jerárquica representada por la tabla anterior?

La query

with recursive tmp( cod_padre, cod_hijo ) as (
    select
        cod_padre, cod_hijo
    from t_padre_inmediato
        union all
    select
        a.cod_padre as cod_padre,
        b.cod_hijo  as cod_hijo
    from
        t_padre_inmediato as a,
        tmp as b
    where
        a.cod_hijo = b.cod_padre
)
select *
from tmp;

asocia a cada elemento de la jerarquía todos los elmentos de nivel superior a los que pertenece a partir de la tabla de padres inmediatos.

Otro día volveré para contar cómo hacer para calcular la mediana de una columna numérica con Postgres. A no ser que alguien averigüe antes cómo hacerlo con Oracle, en cuyo caso calcularía medias winsorizadas o cualquier otra que lo deje en evidencia.