- Todos los problemas de Advent of Code 2024 pudieron resolverse usando únicamente SQL puro, y el punto clave es que SQL obliga a una forma de pensar distinta a la resolución habitual de acertijos
- En recorridos de tablero de pequeña escala, desde el parseo de entrada hasta la exploración y agregación basadas en consultas recursivas, todo puede manejarse de forma relativamente natural dentro de SQL
- En problemas como el Day 16, donde el estado crece mucho, el problema no era tanto la expresión sino el costo de evaluación, y la ineficiencia llegó a requerir más de 200 GB de memoria con la entrada real
- El problema de la clique máxima del Day 23 encaja bien con el algoritmo de Bron-Kerbosch, pero su estructura para manejar varios conjuntos choca con el modelo de SQL recursivo que pasa un solo conjunto
- Es posible escribir algoritmos complejos en SQL, pero para que la ejecución dentro de la base de datos sea más práctica hacen falta actualizaciones de estado durante la recursión y una manipulación de estado más rica
Resolver Advent of Code 2024 solo con SQL
- Se resolvió Advent of Code 2024 con SQL puro, y todos los problemas pudieron solucionarse únicamente con SQL
- La solución completa está publicada en el repositorio de GitHub
- Esto obligó a pensar los problemas de otra manera y, en muchos casos, SQL funcionó como una herramienta cómoda más de lo esperado
Day 11: SQL encaja bien en problemas pequeños de recorrido
- La solución completa del Day 11 está compuesta en un solo SQL, incluyendo la entrada del rompecabezas
- El procesamiento de entrada sigue un flujo que convierte gradualmente cadenas en una estructura tabular
- La entrada del rompecabezas se mantiene como cadena
- La entrada se divide en líneas individuales
- Cada carácter se transforma en coordenadas y valor para crear una tabla con forma de arreglo 2D
- La parte del algoritmo se mantiene relativamente corta
- Se recorre el tablero con una consulta recursiva
- A partir del resultado del recorrido se extrae la respuesta del rompecabezas
- En este tipo de recorridos pequeños, SQL funciona lo suficientemente bien
Day 16: el costo de conservar estado en SQL recursivo
- Day 16 recorre un tablero de forma similar al Day 11 y calcula la distancia mínima de recorrido para cada punto visitado
- Es fácil de expresar en SQL, pero el proceso de evaluación es derrochador
- Con la entrada real del rompecabezas, al crecer el tablero la consulta recursiva genera y conserva muchos estados
- En realidad, solo hace falta el resultado de la última iteración de la consulta recursiva
- Aun así, se conservan la mayoría de las tuplas calculadas
- Por eso, ejecutar esa consulta requiere más de 200 GB de memoria
- Usar la semántica de iteración (iteration semantic) durante la recursión puede reducir ese uso excesivo de memoria
- Umbra puede hacerlo
- Postgres y DuckDB no lo soportan
- Por eso esa función no se usó en la solución
Day 23: el límite de los algoritmos que requieren varios conjuntos
- Day 23 pedía encontrar la clique máxima en un grafo disperso
- Este problema puede calcularse razonablemente con el algoritmo de Bron-Kerbosch
- Pero este algoritmo intenta mantener varios conjuntos, mientras que SQL recursivo solo pasa un conjunto
- Fue posible implementarlo, pero la expresión en SQL se volvió bastante compleja y el código resultante quedó en una forma poco elegante
Qué le hace falta al SQL recursivo
- Incluso algoritmos complejos pueden escribirse en SQL y, en muchos casos, el código SQL fue más fácil de leer y escribir de lo esperado
- Si el SQL recursivo tuviera un mecanismo de actualización de estado, podría volverse más eficiente y más fácil de usar
- Está en curso la investigación sobre un mecanismo de trampolín para soportar flujos de control más complejos en la recursión, y este enfoque también es útil
- También hace falta explorar mecanismos más complejos de manipulación de estado
- Con solo unas pocas capacidades adicionales, SQL podría convertirse en una opción sólida para ejecutar algoritmos complejos directamente dentro de la base de datos
1 comentarios
Opiniones de Hacker News
Lograr algo así solo está al alcance de alguien realmente impresionante. Es arte puro, y en el mundo de la programación no hay suficiente de esto.
Al ver este título reaccioné de forma parecida a cuando veo un nuevo producto del menú de Taco Bell. Una mezcla extraña de deseo, vergüenza y admiración por la creatividad humana.
En problemas como Advent of Code, probablemente la parte más difícil sea el parseo de la entrada.
Quizá si uno se mete a fondo en la interfaz de la tablet podría averiguar los ingredientes, pero por ahora parece un juego de azar. Hablando en serio, https://www.amazon.com/Joe-Celkos-SQL-Smarties-Programming-d... es una clase magistral para aprender artesanía SQL extrema.
Siento que todo HN trata de la creatividad humana, y no tengo claro si deberíamos tomarlo todo como si estuviéramos viendo el menú de Taco Bell.
Bien hecho. Al principio parece una locura, pero creo que el SQL grande es una de las mejores formas de contener complejidad.
Lo complejo lo es porque el problema en sí es complejo. SQL es estándar, compacto, muy rápido, realmente testeable y lógico. No cualquiera puede mantenerlo de inmediato, pero lo mismo pasa cuando se escribe en Java con muchas líneas y funciones.
También me gusta que SQL sea profundo. Ha sostenido el mundo de los datos por más de 40 años, así que es natural que la gente haya pedido funciones de nicho. La cláusula model de Oracle es una de mis favoritas porque permite implementar arreglos multidimensionales, y un amigo la usó para implementar el Juego de la Vida de Conway en muchas menos líneas de las esperadas.
Al final lo reescribimos en código nativo y lo bajamos a menos de 1 segundo; la mayor parte del trabajo fue demostrar que producía los mismos resultados y escribir y documentar casos de prueba para que la siguiente persona no pasara por lo mismo. Desde entonces, en general evito meter mucha lógica de negocio en SQL.
Personalmente, creo que lo complejo debería ser fácil de probar tanto manual como automáticamente. SQL es fácil de probar manualmente, pero las pruebas automáticas son más difíciles que con código en un lenguaje de programación. Un bloque de código espagueti al menos se puede desenredar en partes menos densas y atacarlas por separado, pero con espagueti SQL enredado no sabría por dónde empezar.
Tampoco estoy completamente de acuerdo con que a más líneas haya más riesgo de bugs, porque no todas las líneas son iguales. Una línea de SQL de 400 caracteres probablemente sea más difícil de revisar visualmente para encontrar problemas que 400 líneas de Java, y lo digo como alguien a quien no le gusta Java por muchas razones.
Si te gustan este tipo de desafíos decadentes, este año hice Advent of Code en Google Sheets.
Solo llegué hasta el día 6 y tampoco conseguí las dos estrellas todos los días. Estoy bastante seguro de que mi solución del día 7 es correcta, pero con la entrada larga me topé con el límite de caracteres por celda.
Que lo disfruten. Eso sí, mejor no lo abran en móvil. Algunas hojas matan la app.
https://docs.google.com/spreadsheets/d/10FY-89y19tnRM_EAAnCd...
A lo largo de mi carrera escribí más SQL que cualquier otro tipo de código. En los últimos 5 años lo usé menos, así que probablemente olvidé bastante, pero antes lo disfrutaba mucho.
Cuando dejas de pensar de forma iterativa y empiezas a pensar en operaciones de conjuntos, se vuelve bastante natural y potente.
Si el esquema está bien estructurado y alineado con la perspectiva de las partes interesadas del negocio, la lógica de negocio definida mediante consultas SQL puede ser bastante intuitiva.
El código, los frameworks, los ORM, las “mejores prácticas”, los patrones, etc., terminan siendo elementos de distracción. Hay un millón de formas de meter y sacar datos de una base de datos, y mover bits en sí mismo tiene poco valor. Hay muchas soluciones de software sobredimensionadas para cosas que habrían bastado con una simple sentencia de merge o una importación de CSV.
Gran parte de los malentendidos y la mala predisposición hacia SQL surge de tener que lidiar con esquemas desordenados. El lenguaje en sí es realmente específico de dominio. Si para empezar no tuvieras que escribir esas consultas, no te quejarías tanto de las consultas horriblemente anidadas y del dolor que provoca la sintaxis de SQL. Si alineas las tuplas y las relaciones con la forma en que el negocio suele hablar, con el tiempo peleas menos con estas cosas. Muchas veces no puedes refactorizar el esquema desde cero, pero puedes poner réplicas o vistas alrededor de un mal esquema y usarlas como objetivo para nuevo desarrollo y refactorización.
Por supuesto, SQL tiene defectos, incluidos algunos serios como la capacidad de prueba. Aun así, ojalá toda la programación fuera así al final: la computadora decide cómo hacerlo internamente y los humanos se concentran en la lógica.
Intenté leer por encima algo de Prolog para ir un paso más allá, pero todavía no lo logré. Parte del objetivo era olvidar algunas cosas para no quedar demasiado atrapado en SQL. Tal vez el futuro de la programación esté en algún punto entre SQL y Prolog.
Si piensas solo desde la perspectiva de operaciones de conjuntos, es fácil terminar con una consulta que tarda 5 minutos en lugar de 5 milisegundos. El proceso mental casi siempre es una repetición de “por qué tabla empezar, qué filas mirar y en qué orden, con qué hacer join y bajo qué condiciones, y cómo agregar”. Uno termina pensando más con un modelo mental de bucles y agregaciones que de operaciones de conjuntos.
Mucha gente se va por todo tipo de caminos inútiles, pero la mayor parte de la ingeniería de software consiste en poner los datos correctos en el formato correcto y moverlos de manera confiable.
Hace poco hice una gran refactorización de una base de código distribuida compleja, y lo único que realmente contaría como “trabajo” fue casi solo el rediseño del esquema. El resto fueron muchas horas de programación, pero en realidad se parecía más a implementación.
Hay otras formas de definir esquemas además de SQL, pero SQL es una manera perfecta de aprender verdadera ingeniería de sistemas.
Uso muchísimo SQL e implemento en SQL una parte considerable de la lógica de negocio de aplicaciones de procesamiento de streams. En particular, me encanta la idea de llevar el cómputo hacia los datos en lugar de mover los datos hacia el cómputo.
Pero también me encuentro seguido con desarrolladores a los que no les gusta esa idea. Prefieren asumir enormes costos de entrada/salida, mover todos los datos al backend y expresar el cálculo en un lenguaje de programación “de verdad”.
Creo que el concepto de SQL es bueno, pero el lenguaje SQL es el problema. Tiene demasiadas partes torpes, y no es raro si estuvo unos 40 años sin competencia. El modelo de programa en la cabeza está bien, pero para ver su elegancia hay que mirar más allá de la sintaxis, al programa que realmente estás escribiendo.
Creo que lo que hace falta es un verdadero lenguaje de programación diseñado para apuntar a bases de datos existentes (Postgres, MSSQL) y compilar a dialectos de SQL. Se ven algunos candidatos, pero están atados a ámbitos específicos, como PreQL, que no permite modificar datos, o están acoplados a otra base de datos.
Me dan ganas de hacerlo yo mismo, pero es muchísimo trabajo, hay un camino larguísimo hasta la adopción, no hay garantía de éxito y no se me ocurre un modelo de ingresos.
Los lenguajes backend populares fueron creados por grandes empresas, pero programar en SQL parece estar atrapado en un callejón sin salida: se menosprecia hasta que exista un lenguaje mejor, y no aparecerá un lenguaje mejor hasta que se vuelva más popular.
Las expresiones de tabla comunes y las funciones de ventana marcaron una gran diferencia; en particular, las funciones de ventana te retuercen un poco la cabeza, pero hacen un poco más fáciles cosas difíciles.
Uso BigQuery, que soporta estructuras y arreglos, y recién hace poco permitió agrupar arreglos, aunque todavía no tiene cosas como pruebas de igualdad.
BigQuery está agregando poco a poco azúcar sintáctico como funciones definidas por el usuario de agregación y funciones definidas por el usuario polimórficas con parámetros
ANY TYPE. Eso permite poner más lógica reutilizable en funciones limpias, pero personalmente me gustaría que las funciones temporales se declararan y tuvieran alcance como las expresiones de tabla comunes, para integrarse mejor con herramientas como DBT que quieren meter todo en una sola sentencia.Si tuviera que elegir una sola función que más aumentaría la productividad, sería poder especificar el comportamiento de nulos en
JOIN USING. Escribir explícitamentefoo.bar IS NOT DISTINCT FROM bar.baren un join no es intuitivo y se ve feo. Algo comoUSING (bar RESPECT NULLS)sería mucho mejor.En cambio, cuanto más microservicios es la arquitectura, con servicios pequeños donde cada uno posee su propia base de datos y solo la mitad son bases de datos relacionales, menos quieren poner código complejo dentro de la base de datos. Esto se debe a que suelen moverse entre instancias únicas o clústeres, llevándose solo volcados de datos relativamente simples, o agregando nuevas réplicas como el barco de Teseo.
Que lo hayan hecho con SQL puro ya es realmente impresionante, pero la verdadera señal de esa energía de ingeniería desquiciada parece ser un sitio en Blogspot mantenido durante 10 años
Es difícil explicarlo con precisión, pero transmite mucho esa vibra de “especialista en un nicho”. Aunque no conozcas a los autores, si son unas personas que mantienen durante 10 años un sitio de Blogspot llamado “database architects”, probablemente en la comunidad adecuada no necesitan presentación
Como referencia, durante algunos días probé hacer Advent of Code con EdgeQL, y fue una experiencia bastante interesante
Dejé algunos tuits, y creo que debería convertirlo en una entrada de blog
https://x.com/1st1/status/1864069589245858083
Comparación con SQL: https://x.com/1st1/status/1864412869108092997
Completamente horrible. Aun así, buen trabajo
Para quienes no lo sepan, el autor es uno de los mejores investigadores de bases de datos del mundo