Advent of Code 2024 implementado em SQL puro
(databasearchitects.blogspot.com)- Foi possível resolver todos os problemas do Advent of Code 2024 usando apenas SQL puro, e o ponto central é que SQL força uma forma de pensar diferente da resolução comum de puzzles
- Percursos em campos de pequena escala são tratados de forma relativamente natural dentro do SQL, desde o parsing da entrada até a exploração e agregação baseadas em consultas recursivas
- Em problemas como o Day 16, nos quais o estado cresce bastante, o problema não foi a representação em si, mas o custo de avaliação; com a entrada real, a ineficiência ficou grande a ponto de exigir mais de 200 GB de memória
- O problema da clique máxima do Day 23 combina bem com o algoritmo Bron-Kerbosch, mas a estrutura que tenta lidar com vários conjuntos entra em conflito com o modelo de SQL recursivo que passa um único conjunto
- É possível escrever algoritmos complexos em SQL, mas a execução dentro do banco de dados se tornaria mais prática se houvesse atualização de estado durante a recursão e manipulação de estado mais rica
Resolvendo o Advent of Code 2024 apenas com SQL
- O Advent of Code 2024 foi resolvido em SQL puro, e todos os problemas puderam ser solucionados usando apenas SQL
- A solução completa está publicada no repositório no GitHub
- Isso levou a pensar nos problemas de outra forma e, em vários casos, SQL funcionou como uma ferramenta mais confortável do que o esperado
Day 11: SQL funciona bem para pequenos problemas de percurso
- A solução completa do Day 11 é composta por um único SQL, incluindo a entrada do puzzle
- O tratamento da entrada segue um fluxo que transforma gradualmente uma string em uma estrutura de tabela
- A entrada do puzzle é mantida como string
- A entrada é separada em linhas individuais
- Cada caractere é convertido em coordenadas e valor, criando uma tabela em forma de array 2D
- A parte do algoritmo permanece relativamente curta
- Uma consulta recursiva percorre o campo
- A resposta do puzzle é extraída do resultado do percurso
- Nesses percursos de pequena escala, SQL funciona suficientemente bem
Day 16: o custo de preservar estado no SQL recursivo
- O Day 16 percorre um campo de forma semelhante ao Day 11 e calcula a distância mínima de percurso para cada ponto visitado
- É fácil expressar isso em SQL, mas o processo de avaliação é desperdiçador
- Com a entrada real do puzzle, à medida que o campo cresce, a consulta recursiva gera e preserva muito estado
- O que realmente é necessário é apenas o resultado da última iteração da consulta recursiva
- Mesmo assim, a maioria das tuplas calculadas é preservada
- Por isso, a execução dessa consulta exige mais de 200 GB de memória
- Usar semântica de iteração (iteration semantic) durante a recursão pode reduzir o uso excessivo de memória
- O Umbra consegue fazer isso
- Postgres e DuckDB não oferecem suporte a isso
- Por esse motivo, esse recurso não foi usado na solução
Day 23: limites de algoritmos que exigem vários conjuntos
- O Day 23 era um problema que exigia encontrar a clique máxima em um grafo esparso
- Esse problema pode ser calculado de forma razoável com o algoritmo Bron-Kerbosch
- Porém, esse algoritmo tenta manter vários conjuntos, enquanto o SQL recursivo transmite apenas um único conjunto
- A implementação foi possível, mas a expressão em SQL ficou bastante complexa, e o código resultante também acabou em uma forma pouco limpa
Funcionalidades que o SQL recursivo ainda precisa
- Algoritmos complexos também podem ser escritos em SQL e, em muitos casos, o código SQL foi mais fácil de ler e escrever do que o esperado
- Se o SQL recursivo tivesse um mecanismo de atualização de estado, poderia se tornar mais eficiente e fácil de escrever
- Há pesquisas em andamento sobre um mecanismo de trampolim para oferecer suporte a fluxos de controle mais complexos na recursão, e essa abordagem também é útil
- Também é necessário examinar mecanismos mais complexos de manipulação de estado
- Com apenas alguns recursos adicionais, SQL pode se tornar uma opção sólida para executar algoritmos complexos diretamente dentro do banco de dados
1 comentários
Opiniões no Hacker News
Só alguém realmente incrível consegue fazer algo assim. É arte pura, e não há coisas desse tipo em quantidade suficiente no mundo da programação
Reagi a esse título de um jeito parecido com quando vejo um novo item no cardápio do Taco Bell. Uma mistura estranha de desejo, vergonha e admiração pela criatividade humana
Em problemas como os do Advent of Code, acho que a parte mais difícil provavelmente é o parsing da entrada
Talvez, fuçando na interface do tablet, dê para descobrir os ingredientes, mas por enquanto parece um jogo de sorte. Falando sério, https://www.amazon.com/Joe-Celkos-SQL-Smarties-Programming-d... é uma aula excelente para aprender artesanato SQL extremo
Tenho a impressão de que o HN inteiro é sobre criatividade humana, e não sei bem se devo encarar tudo como se estivesse olhando para o cardápio do Taco Bell
Bem feito. No começo parece loucura, mas acho que SQL grande é uma das melhores formas de conter complexidade
A complexidade existe porque o problema em si é complexo. SQL é padronizado, conciso, muito rápido, de fato testável e é uma linguagem lógica. Não é algo que qualquer pessoa consiga manter de imediato, mas o mesmo vale quando isso é escrito em Java com muitas linhas e funções
Também gosto do fato de SQL ser profundo. Ele sustentou o mundo dos dados por mais de 40 anos, então é natural que as pessoas tenham pedido recursos de nicho. A cláusula model do Oracle é uma das minhas favoritas porque permite implementar arrays multidimensionais, e um amigo a usou para implementar o Jogo da Vida de Conway em muito menos linhas do que eu esperava
No fim, reescrevi em código nativo e reduzi para menos de 1 segundo. A maior parte do trabalho foi provar que produzia o mesmo resultado e escrever/documentar casos de teste para que a próxima pessoa não passasse pelo mesmo sofrimento. Depois disso, passei a evitar, em geral, colocar muita lógica de negócio em SQL
Pessoalmente, acho que coisas complexas precisam ser fáceis de testar tanto manual quanto automaticamente. SQL é fácil de testar manualmente, mas testes automatizados são mais difíceis do que em código de uma linguagem de programação. Um bloco de código espaguete ao menos pode ser descompactado em partes menos densas e atacado por etapas; já com um espaguete SQL emaranhado, fico sem saber por onde começar
Também não concordo totalmente com a ideia de que, quanto maior o número de linhas, maior o risco de bugs. Nem todas as linhas são iguais. Uma linha de SQL com 400 caracteres provavelmente é mais difícil de passar os olhos e encontrar problemas do que 400 linhas de código Java — e digo isso mesmo sendo alguém que não gosta de Java por vários motivos
Se você gosta desse tipo de desafio decadente, tentei fazer o Advent of Code deste ano no Google Sheets
Só cheguei até o dia 6, e nem consegui as duas estrelas todos os dias. Tenho bastante certeza de que minha solução do dia 7 está correta, mas, com a entrada longa, bati no limite de caracteres por célula
Divirtam-se. Só recomendo não abrir no celular. Algumas planilhas derrubam o app
https://docs.google.com/spreadsheets/d/10FY-89y19tnRM_EAAnCd...
Ao longo da carreira, escreveu mais SQL do que qualquer outro tipo de código. Nos últimos 5 anos usou menos e provavelmente esqueceu muita coisa, mas antes realmente gostava
Quando você para de pensar de forma iterativa e começa a pensar em operações de conjuntos, isso se torna bastante natural e poderoso
Quando o esquema é bem organizado e alinhado à perspectiva das partes interessadas do negócio, a lógica de negócio definida por consultas SQL pode ser bastante intuitiva
Código, frameworks, ORMs, “boas práticas”, padrões etc. acabam sendo elementos de distração. Existem um milhão de maneiras de colocar dados no banco e tirá-los dele, e o ato de mover bits em si tem baixo valor. Há muitas soluções de software exageradas para coisas que poderiam ter sido uma simples instrução de merge ou uma importação de CSV
Grande parte dos mal-entendidos e sentimentos ruins em relação a SQL vem de ter que lidar com esquemas bagunçados. A linguagem em si é realmente específica de domínio. Se, em primeiro lugar, não fosse necessário escrever esse tipo de consulta, as pessoas não reclamariam tanto de consultas horrivelmente aninhadas e da dor sintática de SQL que vem com elas. Quando tuplas e relações são alinhadas à forma como o negócio costuma falar, com o tempo você passa a brigar menos com essas coisas. Muitas vezes não dá para refatorar o esquema desde o início, mas é possível colocar réplicas ou views em torno de um esquema ruim e usá-las como alvo para novos desenvolvimentos e refatorações
Claro que SQL tem defeitos, alguns graves, como testabilidade. Ainda assim, no fim, seria bom se toda programação fosse assim: o computador decide como fazer internamente, e o humano se concentra na lógica
Tentou ler Prolog por alto para ir um passo além, mas ainda não conseguiu. Parte do objetivo também era esquecer um pouco de SQL para não ficar preso demais a ele. Talvez o futuro da programação esteja em algum lugar entre SQL e Prolog
Pensar só em termos de operações de conjuntos facilmente leva a consultas que demoram 5 minutos em vez de 5 milissegundos. O processo mental quase sempre é uma repetição de “por qual tabela começar, quais linhas olhar e em que ordem, com o que fazer join e sob quais condições, como agregar”. Acaba-se pensando mais próximo de um modelo mental de loops e agregações do que de operações de conjuntos
Muita gente pula para todo tipo de lugar irrelevante, mas a maior parte da engenharia de software é colocar os dados certos no formato certo e movê-los de forma confiável
Recentemente fez uma grande refatoração em uma base de código distribuída complexa, e praticamente a única coisa que conta como “trabalho” de verdade foi o redesenho do esquema. O resto envolveu muitas horas de programação, mas na prática foi mais implementação
Há outras formas além de SQL de definir esquemas, mas SQL é uma maneira perfeita de aprender engenharia de sistemas de verdade
Usa SQL em grande escala e implementa em SQL boa parte da lógica de negócio de aplicações de processamento de streams. Gosta especialmente da ideia de levar a computação até os dados, em vez de mover os dados para a computação
Mas encontra com frequência desenvolvedores que odeiam essa ideia. Eles preferem arcar com enormes custos de entrada e saída, mover todos os dados para o backend e expressar os cálculos em uma linguagem de programação “de verdade”
O conceito de SQL é bom, mas a linguagem SQL é o problema. Há partes estranhas demais, e isso não surpreende depois de uns 40 anos sem concorrência. O modelo de programa na cabeça é bom, mas, para enxergar a elegância, é preciso olhar além da sintaxe e ver o programa que de fato está sendo escrito
O que parece necessário é uma linguagem de programação adequada, projetada para bancos de dados existentes (Postgres, MSSQL) e compilada para dialetos SQL. Há candidatos, mas ou são presos a um domínio específico, como o PreQL, que não permite alterações de dados, ou são acoplados a outro banco de dados
Dá vontade de criar uma, mas seria trabalho demais, haveria um caminho muito longo até a adoção, não há garantia de sucesso e nenhum modelo de receita evidente
As linguagens populares de backend foram criadas por grandes empresas, mas programar em SQL parece preso em um beco sem saída: é menosprezado até surgir uma linguagem melhor, e uma linguagem melhor não surge enquanto isso não se torna mais popular
Expressões de tabela comuns e funções de janela fizeram uma grande diferença, e as funções de janela, em especial, embaralham um pouco a cabeça, mas tornam tarefas difíceis um pouco mais fáceis
Usa BigQuery, que oferece suporte a structs e arrays, e só recentemente passou a permitir agrupar arrays, mas ainda não tem coisas como verificação de igualdade
O BigQuery vem adicionando aos poucos açúcar sintático, como funções definidas pelo usuário de agregação e funções definidas pelo usuário polimórficas com parâmetros
ANY TYPE. Isso permite colocar mais lógica reutilizável em funções limpas, mas pessoalmente gostaria que funções temporárias fossem declaradas e escopadas como expressões de tabela comuns, para se integrarem melhor a ferramentas que, como o DBT, querem colocar tudo em uma única instruçãoSe fosse escolher um único recurso que mais aumentaria a produtividade, seria permitir especificar o comportamento de nulos em
JOIN USING. Escrever por extensofoo.bar IS NOT DISTINCT FROM bar.barem joins não é intuitivo e é feio. Algo comoUSING (bar RESPECT NULLS)pareceria muito melhorPor outro lado, quanto mais microservices-like é a arquitetura, com pequenos serviços cada um dono do próprio banco de dados e só metade deles sendo bancos relacionais, menos se quer colocar código complexo no próprio banco. Isso porque se migra com frequência entre uma instância única ou um cluster, levando apenas dumps de dados relativamente simples, ou anexando novas réplicas como o navio de Teseu
É realmente impressionante que tenham feito isso em SQL puro, mas o verdadeiro sinal de energia de engenheiro fissurado parece ser um site no Blogspot mantido há 10 anos
É difícil explicar com precisão, mas passa muito a sensação de “especialista em um nicho”. Mesmo sem conhecer os autores, acho que algumas pessoas mantendo por 10 anos um site no Blogspot chamado “database architects” provavelmente dispensam apresentações na comunidade certa
Como referência, passei alguns dias fazendo o Advent of Code em EdgeQL, e foi uma experiência bem interessante
Publiquei alguns tweets e acho que preciso escrever um post no blog sobre isso
https://x.com/1st1/status/1864069589245858083
Comparação com SQL: https://x.com/1st1/status/1864412869108092997
Completamente horrível. Ainda assim, mandaram bem
Para quem não sabe, o autor é um dos maiores pesquisadores de bancos de dados do mundo