Advent of Code 2024 yang Diimplementasikan dengan SQL Murni

• Semua soal di Advent of Code 2024 dapat diselesaikan hanya dengan SQL murni, dan inti utamanya adalah bahwa SQL memaksa cara berpikir yang berbeda dari pemecahan puzzle pada umumnya
• Penelusuran medan berskala kecil dapat ditangani secara cukup alami di dalam SQL, mulai dari parsing input hingga penelusuran dan agregasi berbasis kueri rekursif
• Pada masalah seperti Day 16, ketika jumlah state membesar, masalah utamanya bukan pada ekspresi melainkan pada biaya evaluasi, dan inefisiensinya menjadi sangat besar hingga membutuhkan memori lebih dari 200GB pada input nyata
• Masalah maksimum clique di Day 23 cocok dengan algoritme Bron-Kerbosch, tetapi struktur yang ingin menangani beberapa himpunan berbenturan dengan model SQL rekursif yang hanya meneruskan satu himpunan
• Menulis algoritme kompleks dengan SQL memang memungkinkan, tetapi agar eksekusi di dalam basis data lebih praktis, diperlukan pembaruan state selama rekursi serta manipulasi state yang lebih kaya

---

Menyelesaikan Advent of Code 2024 Hanya dengan SQL

• Advent of Code 2024 diselesaikan dengan SQL murni, dan semua soal dapat dipecahkan hanya dengan SQL
• Seluruh solusi dipublikasikan di repositori GitHub
• Ini memaksa cara berpikir yang berbeda tentang masalah, dan dalam banyak kasus SQL bekerja sebagai alat yang nyaman melebihi dugaan

Day 11: SQL yang Cocok untuk Masalah Penelusuran Kecil

• Solusi lengkap Day 11 disusun sebagai satu SQL, termasuk input puzzle-nya
• Pemrosesan input mengikuti alur yang mengubah string secara bertahap menjadi struktur tabel
  • Menyimpan input puzzle sebagai string
  • Memisahkan input menjadi baris-baris individual
  • Mengubah tiap karakter menjadi koordinat dan nilai untuk membentuk tabel berbentuk array 2D
• Bagian algoritmenya tetap relatif singkat
  • Menelusuri medan dengan kueri rekursif
  • Mengekstrak jawaban puzzle dari hasil penelusuran
• Untuk penelusuran berskala kecil seperti ini, SQL bekerja cukup baik

Day 16: Biaya Penyimpanan State pada SQL Rekursif

• Day 16 menelusuri medan seperti Day 11 dan menghitung jarak penelusuran minimum untuk tiap titik yang dikunjungi
• Hal ini mudah diekspresikan dalam SQL, tetapi proses evaluasinya boros
• Pada input puzzle nyata, ketika medan membesar, kueri rekursif menghasilkan dan mempertahankan banyak state
  • Yang benar-benar dibutuhkan sebenarnya hanya hasil iterasi terakhir dari kueri rekursif
  • Meski begitu, sebagian besar tuple yang telah dihitung tetap dipertahankan
• Karena itu, menjalankan kueri tersebut membutuhkan memori lebih dari 200GB
• Menggunakan semantik iterasi (iteration semantic) selama rekursi dapat mengurangi penggunaan memori yang berlebihan
  • Umbra dapat melakukannya
  • Postgres dan DuckDB tidak mendukungnya
  • Karena itu, fitur tersebut tidak digunakan dalam solusi

Day 23: Batasan Algoritme yang Membutuhkan Banyak Himpunan

• Day 23 adalah masalah yang mengharuskan pencarian maksimum clique pada graf jarang
• Masalah ini dapat dihitung secara masuk akal dengan algoritme Bron-Kerbosch
• Namun, algoritme ini berusaha mempertahankan beberapa himpunan, sedangkan SQL rekursif hanya meneruskan satu himpunan
• Implementasinya memang mungkin, tetapi ekspresi SQL-nya menjadi cukup rumit, dan kode hasilnya juga tidak terlalu rapi

Fitur yang Masih Dibutuhkan SQL Rekursif

• Algoritme kompleks pun dapat ditulis dengan SQL, dan dalam banyak kasus kode SQL ternyata lebih mudah dibaca dan ditulis daripada yang diperkirakan
• Jika SQL rekursif memiliki mekanisme pembaruan state, SQL bisa menjadi lebih efisien dan lebih mudah digunakan
• Riset tentang mekanisme trampolin untuk mendukung alur kontrol yang lebih kompleks dalam rekursi sedang berlangsung, dan pendekatan ini juga berguna
• Perlu juga meninjau mekanisme manipulasi state yang lebih kompleks
• Hanya dengan sedikit fitur tambahan, SQL dapat menjadi pilihan yang kuat untuk menjalankan algoritme kompleks langsung di dalam basis data

[GN⁺]

Komentar Hacker News

• Hanya orang yang benar-benar luar biasa yang bisa melakukan hal seperti ini. Ini seni murni, dan di dunia pemrograman tidak ada cukup banyak hal seperti ini

  • Thomas adalah salah satu peneliti sistem basis data terbaik di dunia, dan benar-benar orang yang hebat

• Melihat judul ini, reaksi saya mirip saat melihat menu baru Taco Bell. Ada campuran aneh antara hasrat, rasa malu, dan kekaguman pada kreativitas manusia

  • Saya sudah banyak berkutat dengan basis data dan melihat berbagai macam hal, tetapi kalau tahu apa yang sedang dilakukan, ini tidak seburuk yang dibayangkan. Sebagian besar sistem manajemen basis data relasional mendukung recursive common table expression, jadi rasanya seperti menulis Prolog dengan sintaks yang agak sadistis
    Untuk soal seperti Advent of Code, mungkin parsing input adalah bagian tersulitnya
  • Solusi di repositori GitHub artikel ini juga sama mengejutkannya dengan chicken nugget baru Taco Bell
  • Yang sulit ditahan di Taco Bell adalah keju nacho palsunya. Keju parut biasa di hard taco memang bukan yang terbaik, tapi masih oke; yang memakai Velveeta butuh pengendalian diri yang cukup besar agar bisa ditelan
    Mungkin kalau menggali antarmuka tablet, kita bisa mengetahui bahan-bahannya, tapi untuk saat ini rasanya seperti permainan untung-untungan. Secara serius, https://www.amazon.com/Joe-Celkos-SQL-Smarties-Programming-d... adalah kuliah luar biasa untuk mempelajari keahlian SQL ekstrem
  • Saya tidak mengerti mengapa kreativitas manusia ditanggapi dengan rasa malu dan hasrat. Entah itu masalah di pihak Anda sendiri atau masalah khusus Taco Bell juga agak tidak jelas
    Rasanya seluruh HN memang tentang kreativitas manusia, dan saya tidak yakin apakah semuanya harus diterima seperti perasaan saat melihat menu Taco Bell

• Dibuat dengan baik. Awalnya terlihat gila, tetapi menurut saya SQL besar adalah salah satu cara terbaik untuk menampung kompleksitas
  Sesuatu menjadi kompleks karena masalahnya sendiri memang kompleks. SQL itu standar, padat, sangat cepat, benar-benar bisa diuji, dan merupakan bahasa yang logis. Memang tidak semua orang bisa langsung memeliharanya, tetapi hal yang sama juga berlaku jika ditulis di Java dengan banyak baris dan fungsi
  Saya juga suka bahwa SQL itu dalam. Karena sudah menopang dunia data selama lebih dari 40 tahun, wajar saja orang meminta fitur-fitur niche. Klausa model di Oracle adalah salah satu fitur favorit saya karena bisa mengimplementasikan array multidimensi, dan seorang teman pernah menggunakannya untuk mengimplementasikan Conway's Game of Life dengan jumlah baris jauh lebih sedikit dari perkiraan

  • Saat magang, saya pernah mendapat pekerjaan “menyenangkan” mengoptimalkan performa stored procedure yang ditulis oleh seorang PhD matematika. Jika dicetak panjangnya lebih dari 6 halaman, butuh lebih dari 30 menit untuk dijalankan, dipakai dalam sistem penagihan, dan tidak ada tesnya
    Pada akhirnya saya menulis ulang dalam kode native hingga turun menjadi kurang dari 1 detik, dan sebagian besar pekerjaannya adalah membuktikan bahwa hasilnya sama serta menulis dan mendokumentasikan test case agar orang berikutnya tidak mengalami penderitaan yang sama. Sejak itu saya umumnya menghindari memasukkan banyak business logic ke SQL
  • Hanya jika ada cukup banyak orang yang mahir SQL, benar-benar hanya dalam kondisi itu, SQL besar bisa menjadi cara yang baik untuk menampung kompleksitas. Menulis SQL buruk itu terlalu mudah, dan mengurai ribuan baris SQL buruk yang tersebar di ratusan procedure, view, dan function itu sulit
  • Saya paham kesan bahwa SQL besar bagus untuk menampung kompleksitas, tetapi debugging query SQL besar bisa sangat tidak transparan. Hal seperti pl/pgsql memang membantu, tetapi kalau begitu ia mulai semakin berubah menjadi seperti bahasa pemrograman umum
  • Awalnya terlihat gila, dan setelah dipikir-pikir pun keinginan menaruh kompleksitas di SQL masih terlihat gila
    Secara pribadi, menurut saya sesuatu yang kompleks harus mudah diuji baik secara manual maupun otomatis. SQL mudah untuk pengujian manual, tetapi pengujian otomatisnya lebih sulit dibanding kode dalam bahasa pemrograman. Gumpalan spaghetti code setidaknya bisa diurai menjadi bagian yang kurang padat lalu diserang per bagian, tetapi saya bingung bagaimana menangani spageti SQL yang saling kusut
    Saya juga tidak sepenuhnya setuju bahwa semakin banyak baris berarti risiko bug semakin besar. Sebab tidak semua baris itu sama. Satu baris SQL sepanjang 400 karakter kemungkinan lebih sulit dipindai dengan mata untuk menemukan masalah dibanding 400 baris kode Java, dan saya mengatakan ini meski membenci Java karena berbagai alasan

• Kalau suka tantangan dekaden semacam ini, tahun ini saya mencoba Advent of Code dengan Google Sheets
  Saya hanya sampai hari ke-6 dan tidak selalu mendapatkan dua bintang setiap hari. Saya cukup yakin solusi hari ke-7 saya benar, tetapi pada input panjang terkena batas jumlah karakter per sel
  Selamat menikmati. Namun sebaiknya jangan dibuka di mobile. Beberapa sheet bisa membuat aplikasinya mati
  https://docs.google.com/spreadsheets/d/10FY-89y19tnRM_EAAnCd...

  • Saya sedang di ponsel jadi tidak bisa membukanya, tetapi saya penasaran apakah Anda memakai Google Apps Script. Kalau dipakai, itu sepertinya bisa menjadi cara untuk mendapat kekuatan tambahan

• Sepanjang karier, saya menulis SQL lebih banyak daripada jenis kode lainnya. Dalam 5 tahun terakhir saya lebih jarang memakainya jadi mungkin sudah banyak lupa, tetapi dulu saya benar-benar menikmatinya
  Begitu berhenti berpikir secara iteratif dan mulai berpikir dalam operasi himpunan, SQL terasa cukup alami dan kuat

  • Seiring berjalannya waktu, saya makin mendorong lebih banyak tanggung jawab ke sistem manajemen basis data relasional. Sekarang saya melihat sebagian besar hal dari sudut pandang ETL, SQL, skema. Hampir semua percakapan tentang penerapan teknologi pada bisnis bisa diungkapkan dengan istilah-istilah ini
    Jika skemanya tersusun dengan baik dan selaras dengan sudut pandang pemangku kepentingan bisnis, logika bisnis yang didefinisikan lewat kueri SQL bisa cukup intuitif
    Kode, framework, ORM, “praktik terbaik”, pola, dan semacamnya pada akhirnya hanyalah hal-hal yang mengalihkan perhatian. Ada sejuta cara untuk memasukkan dan mengeluarkan data dari basis data, dan memindahkan bit itu sendiri bernilai rendah. Banyak solusi perangkat lunak yang dibesar-besarkan padahal cukup dengan pernyataan merge sederhana atau impor CSV
    Banyak kesalahpahaman dan perasaan negatif terhadap SQL muncul karena harus berurusan dengan skema yang berantakan. Bahasanya sendiri benar-benar spesifik domain. Jika sejak awal tidak perlu menulis kueri seperti itu, orang tidak akan begitu mengeluhkan kueri bersarang yang mengerikan dan rasa sakit akibat sintaks SQL-nya. Jika tuple dan relasi disesuaikan dengan cara bisnis biasanya berbicara, lama-kelamaan kita akan lebih jarang bergelut dengan hal-hal ini. Sering kali skema tidak bisa direfaktor dari awal, tetapi replika atau view bisa ditempatkan di sekitar skema buruk itu dan dijadikan sasaran pengembangan baru serta refactoring
  • Setelah lama memakai SQL lalu mundur selangkah untuk berpikir, keindahannya terlihat. Rasanya seperti, “Tunggu, yang barusan saya lakukan itu sebenarnya logika murni. Tidak ada penyelesaian dependensi library, tidak ada masalah konkurensi, tidak ada masalah mutabilitas, hanya logika”
    Tentu SQL punya kekurangan, termasuk yang serius seperti testability. Meski begitu, pada akhirnya saya berharap semua pemrograman bisa seperti itu. Komputer yang memutuskan bagaimana melakukannya di dalam, sementara manusia berfokus pada logika
    Saya sempat mencoba membaca Prolog secara sepintas untuk melangkah lebih jauh, tetapi sejauh ini belum berhasil. Tujuannya juga untuk mencoba melupakan sebagian hal agar tidak terlalu terkurung dalam SQL. Mungkin masa depan pemrograman ada di suatu tempat di antara SQL dan Prolog
  • Akan menyenangkan jika kita bisa berpikir hanya dalam operasi himpunan, tetapi dalam praktiknya, untuk menulis kueri yang cepat dan mengetahui indeks apa yang dibutuhkan, kita tetap harus memakai pemikiran imperatif dan iteratif
    Jika hanya berpikir dari sudut pandang operasi himpunan, mudah sekali menghasilkan kueri yang berjalan 5 menit, bukan 5 milidetik. Proses di kepala hampir selalu berupa pengulangan “mulai dari tabel mana, baris apa yang dilihat dalam urutan apa, join dengan apa dan dengan kondisi apa, lalu bagaimana melakukan agregasi”. Akhirnya kita cenderung memakai model mental loop dan agregasi, bukan operasi himpunan
  • Menguasai unsur teori, praktik, dan teknis dari perancangan skema basis data yang baik adalah ujian paling nyata untuk melihat apakah seseorang memahami desain sistem
    Banyak orang melompat ke berbagai hal yang tidak penting, tetapi sebagian besar rekayasa perangkat lunak adalah memasukkan data yang benar ke format yang benar dan memindahkannya secara andal
    Baru-baru ini saya melakukan refactoring besar pada codebase terdistribusi yang kompleks, dan hampir satu-satunya yang benar-benar terhitung sebagai “pekerjaan” adalah perancangan ulang skema. Sisanya memang banyak waktu coding, tetapi sebenarnya lebih dekat ke implementasi
    Ada cara lain untuk mendefinisikan skema selain SQL, tetapi SQL adalah cara yang sempurna untuk mempelajari rekayasa sistem yang sesungguhnya
  • Saya baru benar-benar memahami SQL setelah membaca makalah aslinya dan menjelaskannya dari sudut pandang himpunan

• Saya memakai SQL sangat banyak, dan mengimplementasikan sebagian besar logika bisnis aplikasi pemrosesan stream dengan SQL. Secara khusus, saya sangat menyukai pendekatan membawa komputasi ke data, bukan memindahkan data ke komputasi
  Namun saya sering bertemu developer yang tidak menyukai gagasan itu. Mereka rela menanggung biaya I/O yang sangat besar untuk memindahkan semua data ke backend, lalu ingin mengekspresikan komputasinya dalam bahasa pemrograman “sungguhan”
  Menurut saya konsep SQL itu bagus, tetapi bahasa SQL-lah yang bermasalah. Terlalu banyak bagian yang canggung, dan itu tidak aneh mengingat hampir 40 tahun tidak ada kompetisi. Model program di kepala sebenarnya baik-baik saja, tetapi untuk melihat keanggunannya, kita harus melihat program yang benar-benar sedang dipakai di balik sintaksnya
  Yang dibutuhkan, menurut saya, adalah bahasa pemrograman yang dirancang dengan menargetkan basis data yang sudah ada (Postgres, MSSQL) dan dikompilasi ke dialek SQL. Ada kandidat-kandidat yang terlihat, tetapi mereka terikat pada area tertentu seperti PreQL yang tidak mengizinkan perubahan data, atau digandengkan dengan basis data lain
  Ada keinginan untuk membuatnya sendiri, tetapi pekerjaannya terlalu banyak, jalan menuju adopsi sangat panjang, tidak ada jaminan sukses, dan tidak ada model pendapatan yang terpikir
  Bahasa backend populer dibuat oleh perusahaan besar, tetapi coding dengan SQL tampaknya terjebak dalam dilema ayam-dan-telur: diremehkan sampai ada bahasa yang lebih baik, dan bahasa yang lebih baik tidak akan muncul sampai praktiknya menjadi lebih populer

  • Ada banyak hal yang sangat benar dalam SQL, tetapi beberapa bagian di pinggirannya terasa kasar
    Common Table Expression dan fungsi window membuat perbedaan besar, dan khususnya fungsi window memang agak memelintir otak, tetapi membuat hal-hal sulit menjadi sedikit lebih mudah
    Saya memakai BigQuery; ia mendukung struct dan array, dan baru-baru ini array bisa dikelompokkan, tetapi masih belum ada hal seperti pemeriksaan kesetaraan
    BigQuery perlahan menambahkan gula sintaks seperti aggregate user-defined function dan polymorphic user-defined function yang memakai parameter ANY TYPE. Ini membuat lebih banyak logika yang dapat digunakan ulang bisa dimasukkan ke fungsi yang rapi, tetapi secara pribadi saya berharap fungsi sementara dideklarasikan dan diberi scope seperti Common Table Expression, sehingga lebih terintegrasi dengan tool seperti DBT yang ingin memasukkan semuanya ke dalam satu pernyataan
    Jika harus memilih satu fitur yang paling akan meningkatkan produktivitas, itu adalah kemampuan menentukan perilaku null pada JOIN USING. Menuliskan foo.bar IS NOT DISTINCT FROM bar.bar secara eksplisit dalam join tidak intuitif dan jelek. Sesuatu seperti USING (bar RESPECT NULLS) sepertinya akan jauh lebih baik
  • Sulit menunjuknya secara tepat, tetapi banyak orang tampaknya melihat ini seperti dua mode operasi. Semakin monolitik dan enterprise suatu solusi, serta semakin dekat ia dengan sistem manajemen basis data khusus, semakin besar kecenderungannya untuk menaruh hal-hal kompleks di sisi basis data, bukan hanya indeks dan beberapa trigger
    Sebaliknya, semakin bergaya microservices strukturnya—layanan-layanan kecil masing-masing memiliki basis datanya sendiri dan hanya separuhnya yang merupakan basis data relasional—semakin mereka tidak ingin menaruh banyak kode kompleks di basis data itu sendiri. Alasannya, mereka sering berpindah dari satu instance atau cluster ke yang lain, membawa hanya dump data yang relatif sederhana, atau menempelkan replika baru seperti kapal Theseus
  • PRQL itu bagus. Ada satu pesaing serupa lagi, tetapi namanya tidak teringat sekarang

• Melakukannya dengan SQL murni saja sudah sangat mengesankan, tetapi tanda sebenarnya dari energi insinyur yang retak sepertinya adalah situs Blogspot yang dipertahankan selama 10 tahun
  Sulit menjelaskannya dengan tepat, tetapi nuansanya kuat seperti “pakar di bidang niche”. Meski tidak mengenal para penulisnya, beberapa orang yang mempertahankan situs Blogspot bernama “database architects” selama 10 tahun rasanya tidak perlu diperkenalkan lagi di komunitas yang tepat

• Sebagai catatan, selama beberapa hari saya mencoba Advent of Code dengan EdgeQL, dan itu pengalaman yang cukup menarik
  Saya meninggalkan beberapa twit, dan sepertinya perlu menuliskannya sebagai posting blog
  https://x.com/1st1/status/1864069589245858083
  Perbandingan dengan SQL: https://x.com/1st1/status/1864412869108092997

• Benar-benar mengerikan. Tapi tetap, kerja bagus

• Sebagai tambahan bagi yang belum tahu, penulisnya adalah salah satu peneliti database terbaik di dunia

  • Ini Thomas Neumann melakukan hal yang memang khas Thomas Neumann