Advent of Code 2024 được triển khai bằng SQL thuần
(databasearchitects.blogspot.com)- Có thể giải tất cả bài toán của Advent of Code 2024 chỉ bằng SQL thuần, và điểm cốt lõi là SQL buộc ta phải tư duy khác với cách giải đố thông thường
- Việc duyệt các trường ở quy mô nhỏ, từ phân tích đầu vào đến tìm kiếm và tổng hợp dựa trên truy vấn đệ quy, được xử lý khá tự nhiên ngay trong SQL
- Với các bài như Day 16, nơi trạng thái tăng mạnh, vấn đề không nằm ở cách biểu diễn mà ở chi phí đánh giá; với đầu vào thực tế, mức kém hiệu quả lớn đến mức cần hơn 200GB bộ nhớ
- Bài toán clique cực đại ở Day 23 rất hợp với thuật toán Bron-Kerbosch, nhưng cấu trúc cần xử lý nhiều tập hợp lại xung đột với mô hình SQL đệ quy chỉ truyền một tập hợp duy nhất
- Việc viết các thuật toán phức tạp bằng SQL là khả thi, nhưng cần có cập nhật trạng thái trong quá trình đệ quy và khả năng thao tác trạng thái phong phú hơn để việc thực thi bên trong cơ sở dữ liệu trở nên thực tế hơn
Giải Advent of Code 2024 chỉ bằng SQL
- Đã giải Advent of Code 2024 bằng SQL thuần, và có thể giải tất cả bài toán chỉ với SQL
- Toàn bộ lời giải được công khai trong kho GitHub
- Việc này khiến ta phải nghĩ về bài toán theo cách khác, và trong nhiều trường hợp SQL hoạt động như một công cụ dễ chịu hơn dự đoán
Day 11: SQL phù hợp với các bài duyệt nhỏ
- Toàn bộ lời giải của Day 11 được cấu thành trong một câu SQL duy nhất, bao gồm cả đầu vào của câu đố
- Xử lý đầu vào là luồng chuyển đổi dần chuỗi thành cấu trúc bảng
- Đặt đầu vào của câu đố dưới dạng chuỗi
- Tách đầu vào thành từng dòng riêng lẻ
- Chuyển từng ký tự thành tọa độ và giá trị để tạo bảng dạng mảng 2D
- Phần thuật toán được giữ tương đối ngắn
- Duyệt trường bằng truy vấn đệ quy
- Trích xuất đáp án của câu đố từ kết quả duyệt
- Với kiểu duyệt quy mô nhỏ như vậy, SQL hoạt động đủ tốt
Day 16: Chi phí lưu giữ trạng thái của SQL đệ quy
- Day 16 cũng duyệt trường tương tự Day 11 và tính khoảng cách duyệt tối thiểu tới từng điểm đã ghé thăm
- Biểu diễn bằng SQL thì dễ, nhưng quá trình đánh giá lại lãng phí
- Với đầu vào câu đố thực tế, trường lớn hơn khiến truy vấn đệ quy tạo và lưu giữ nhiều trạng thái
- Thứ thực sự cần chỉ là kết quả của vòng lặp cuối cùng trong truy vấn đệ quy
- Dù vậy, phần lớn các tuple đã tính vẫn được lưu giữ
- Vì thế, việc chạy truy vấn này cần hơn 200GB bộ nhớ
- Nếu dùng ngữ nghĩa lặp (iteration semantic) trong quá trình đệ quy, có thể giảm mức sử dụng bộ nhớ quá mức
- Umbra có thể làm điều này
- Postgres và DuckDB không hỗ trợ
- Vì vậy, tính năng này không được dùng trong lời giải
Day 23: Giới hạn của thuật toán cần nhiều tập hợp
- Day 23 là bài toán cần tìm clique cực đại trong đồ thị thưa
- Bài toán này có thể được tính toán hợp lý bằng thuật toán Bron-Kerbosch
- Tuy nhiên, thuật toán này muốn duy trì nhiều tập hợp, còn SQL đệ quy chỉ truyền một tập hợp duy nhất
- Việc triển khai vẫn khả thi, nhưng biểu diễn SQL trở nên khá phức tạp, và mã kết quả cũng ở dạng không mấy gọn gàng
Những tính năng SQL đệ quy còn cần thêm
- Các thuật toán phức tạp vẫn có thể được viết bằng SQL, và trong nhiều trường hợp mã SQL dễ đọc, dễ viết hơn dự đoán
- Nếu SQL đệ quy có cơ chế cập nhật trạng thái, nó có thể trở nên hiệu quả hơn và dễ viết hơn
- Nghiên cứu về cơ chế trampoline để hỗ trợ luồng điều khiển phức tạp hơn trong đệ quy đang được tiến hành, và cách tiếp cận này cũng hữu ích
- Cũng cần xem xét thêm các cơ chế thao tác trạng thái phức tạp hơn
- Chỉ cần thêm một vài tính năng nhỏ, SQL có thể trở thành một lựa chọn vững chắc để chạy trực tiếp các thuật toán phức tạp bên trong cơ sở dữ liệu
1 bình luận
Ý kiến trên Hacker News
Chỉ những người thật sự xuất sắc mới làm được chuyện như thế này. Đây là nghệ thuật thuần túy, và trong thế giới lập trình không có đủ nhiều thứ như vậy
Khi thấy tiêu đề này, tôi đã phản ứng gần giống như lúc nhìn thấy món mới của Taco Bell. Một cảm giác pha trộn kỳ lạ giữa ham muốn, xấu hổ và sự thán phục trước sức sáng tạo của con người
Với các bài như Advent of Code, có lẽ phân tích cú pháp đầu vào là phần khó nhất
Có lẽ nếu đào sâu vào giao diện tablet thì có thể biết được nguyên liệu, nhưng hiện tại cảm giác như một trò chơi phó mặc may rủi. Nghiêm túc mà nói, https://www.amazon.com/Joe-Celkos-SQL-Smarties-Programming-d... là một lớp học tuyệt vời để học tay nghề SQL cực hạn
Tôi tưởng toàn bộ HN là nơi nói về sức sáng tạo của con người, và không chắc có phải nên tiếp nhận tất cả như cảm giác khi nhìn thực đơn Taco Bell hay không
Làm tốt đấy. Ban đầu trông có vẻ điên rồ, nhưng tôi nghĩ SQL cỡ lớn là một trong những cách tốt nhất để chứa đựng độ phức tạp.
Nó phức tạp vì bản thân vấn đề phức tạp. SQL là chuẩn, súc tích, rất nhanh, thực sự có thể kiểm thử được và là một ngôn ngữ logic. Không phải ai cũng có thể bảo trì ngay, nhưng nếu viết bằng Java với rất nhiều dòng và hàm thì cũng vậy thôi.
Tôi cũng thích việc SQL có chiều sâu. Nó đã chống đỡ thế giới dữ liệu hơn 40 năm, nên việc người ta yêu cầu các tính năng ngách là điều tự nhiên. Mệnh đề model của Oracle là một trong những tính năng tôi thích vì có thể triển khai mảng đa chiều, và một người bạn đã dùng nó để triển khai Trò chơi Sự sống của Conway với số dòng ít hơn nhiều so với dự đoán
Cuối cùng tôi viết lại bằng native code và giảm xuống dưới 1 giây; phần lớn công việc là chứng minh rằng nó cho cùng kết quả và viết, ghi tài liệu cho các test case để người sau không phải chịu khổ như vậy. Từ đó trở đi tôi nhìn chung tránh đưa quá nhiều business logic vào SQL
Cá nhân tôi cho rằng thứ phức tạp phải dễ kiểm thử cả thủ công lẫn tự động. SQL dễ kiểm thử thủ công, nhưng kiểm thử tự động thì khó hơn so với code trong ngôn ngữ lập trình. Một đống spaghetti code ít nhất còn có thể được gỡ ra cho bớt đặc và xử lý từng phần, còn spaghetti SQL rối rắm thì tôi không biết phải đụng vào thế nào.
Tôi cũng không hoàn toàn đồng ý với câu nói rằng càng nhiều dòng thì nguy cơ bug càng lớn. Vì không phải dòng nào cũng như nhau. Một dòng SQL dài 400 ký tự có khả năng khó lướt bằng mắt để tìm vấn đề hơn 400 dòng Java, và tôi nói vậy dù bản thân ghét Java vì nhiều lý do
Nếu bạn thích kiểu thử thách suy đồi này, năm nay tôi đã thử làm Advent of Code bằng Google Sheets.
Tôi chỉ đi được đến ngày 6 và cũng không phải ngày nào cũng lấy đủ hai sao. Tôi khá chắc lời giải ngày 7 là đúng, nhưng với input dài thì vướng giới hạn số ký tự trên mỗi ô.
Chúc xem vui. Nhưng tốt nhất đừng mở trên di động. Một số sheet sẽ làm chết ứng dụng.
https://docs.google.com/spreadsheets/d/10FY-89y19tnRM_EAAnCd...
Trong suốt sự nghiệp, tôi đã viết SQL nhiều hơn bất kỳ loại code nào khác. 5 năm gần đây thì dùng ít hơn nên chắc đã quên khá nhiều, nhưng trước kia tôi thật sự rất thích nó
Khi ngừng suy nghĩ theo kiểu lặp đi lặp lại và bắt đầu nghĩ bằng phép toán tập hợp, nó trở nên khá tự nhiên và mạnh mẽ
Nếu schema được tổ chức tốt và khớp với góc nhìn của các bên liên quan trong kinh doanh, logic nghiệp vụ được định nghĩa bằng truy vấn SQL có thể khá trực quan
Code, framework, ORM, “best practice”, pattern, v.v. rốt cuộc đều là những thứ gây xao nhãng. Có cả triệu cách để đưa dữ liệu vào và lấy dữ liệu ra khỏi database, còn bản thân việc di chuyển bit thì có giá trị thấp. Có rất nhiều giải pháp phần mềm bị thổi phồng trong khi chỉ cần một câu lệnh merge đơn giản hoặc thao tác import CSV là đủ
Phần lớn hiểu lầm và ác cảm với SQL xuất phát từ việc phải xử lý các schema lộn xộn. Bản thân ngôn ngữ này thật sự mang tính chuyên biệt theo miền. Nếu ngay từ đầu không cần viết những truy vấn như vậy, người ta đã không phàn nàn nhiều đến thế về các truy vấn lồng nhau kinh khủng và nỗi khổ cú pháp SQL kéo theo. Khi căn chỉnh tuple và quan hệ theo cách doanh nghiệp thường nói, theo thời gian bạn sẽ ít phải vật lộn với những thứ này hơn. Nhiều khi không thể refactor schema từ đầu, nhưng có thể đặt các bản sao hoặc view quanh schema xấu và lấy chúng làm đối tượng cho phát triển mới và refactor
Tất nhiên SQL có khiếm khuyết, có cả những vấn đề nghiêm trọng như khả năng kiểm thử. Dù vậy, rốt cuộc tôi vẫn ước mọi lập trình đều được như thế: máy tính quyết định cách làm bên trong, còn con người tập trung vào logic
Tôi đã thử đọc lướt Prolog để tiến thêm một bước, nhưng đến giờ vẫn chưa thành công. Một phần mục đích cũng là cố quên bớt SQL để không bị mắc kẹt quá sâu trong nó. Có lẽ tương lai của lập trình nằm đâu đó giữa SQL và Prolog
Nếu chỉ nghĩ theo góc nhìn phép toán tập hợp, rất dễ tạo ra truy vấn chạy 5 phút thay vì 5 mili giây. Quá trình trong đầu gần như luôn là lặp lại các câu hỏi: “bắt đầu từ bảng nào, xem những hàng nào theo thứ tự nào, join với cái gì theo điều kiện nào, aggregate ra sao”. Cuối cùng bạn nghĩ gần với mô hình tinh thần của vòng lặp và tổng hợp hơn là phép toán tập hợp
Nhiều người nhảy sang đủ thứ linh tinh, nhưng phần lớn kỹ nghệ phần mềm là đưa đúng dữ liệu vào đúng định dạng và di chuyển nó một cách đáng tin cậy
Gần đây tôi đã refactor lớn một codebase phân tán phức tạp, và thứ thật sự được tính là “công việc” gần như chỉ là thiết kế lại schema. Phần còn lại mất rất nhiều thời gian code, nhưng thật ra gần với triển khai hơn
Ngoài SQL cũng có những cách định nghĩa schema, nhưng SQL là một cách hoàn hảo để học kỹ nghệ hệ thống thực thụ
Tôi dùng SQL cực kỳ nhiều, và đang triển khai phần lớn logic nghiệp vụ của một ứng dụng xử lý stream bằng SQL. Tôi đặc biệt thích cách đưa tính toán về phía dữ liệu thay vì chuyển dữ liệu sang phần tính toán
Nhưng tôi cũng thường gặp các developer ghét ý tưởng đó. Họ muốn chấp nhận chi phí I/O khổng lồ để chuyển toàn bộ dữ liệu về backend, rồi biểu diễn phép tính bằng một ngôn ngữ lập trình “thật sự”
Khái niệm SQL thì tốt, nhưng tôi cho rằng vấn đề nằm ở ngôn ngữ SQL. Nó có quá nhiều chỗ gượng gạo, và cũng không lạ khi khoảng 40 năm gần như không có cạnh tranh. Mô hình chương trình trong đầu thì ổn, nhưng để thấy được sự tao nhã, bạn phải nhìn xuyên qua cú pháp để thấy chương trình thực sự đang được viết
Tôi nghĩ thứ cần thiết là một ngôn ngữ lập trình đúng nghĩa, được thiết kế để nhắm tới các database hiện có (Postgres, MSSQL) và compile xuống các dialect SQL. Có vài ứng viên, nhưng hoặc bị bó trong một phạm vi cụ thể như PreQL vốn không cho phép thay đổi dữ liệu, hoặc gắn với một database khác
Tôi cũng muốn tự làm, nhưng khối lượng công việc quá lớn, con đường để được chấp nhận thì rất dài, không có gì đảm bảo thành công, và cũng không nghĩ ra mô hình doanh thu nào
Các ngôn ngữ backend phổ biến được các tập đoàn lớn tạo ra, nhưng việc code bằng SQL dường như đang mắc trong thế tiến thoái lưỡng nan: bị coi thường cho đến khi có một ngôn ngữ tốt hơn, nhưng sẽ không có ngôn ngữ tốt hơn cho đến khi nó trở nên phổ biến hơn
Common table expression và window function đã tạo ra khác biệt lớn; đặc biệt window function tuy hơi xoắn não, nhưng giúp những việc khó trở nên dễ hơn một chút
Tôi đang dùng BigQuery, nó hỗ trợ struct và array, và chỉ gần đây mới có thể group array, nhưng vẫn chưa có những thứ như kiểm tra bằng nhau
BigQuery đang từ từ thêm các cú pháp tiện lợi như aggregate UDF, UDF đa hình dùng tham số
ANY TYPE. Điều đó khiến tôi đưa nhiều logic tái sử dụng hơn vào các hàm gọn gàng, nhưng cá nhân tôi muốn temporary function được khai báo và có scope giống common table expression hơn, để tích hợp tốt hơn với các công cụ như DBT vốn muốn nhét mọi thứ vào một câu lệnhNếu chọn một tính năng giúp tăng năng suất nhất, đó sẽ là cho phép chỉ định hành vi với null trong
JOIN USING. Việc viết dàifoo.bar IS NOT DISTINCT FROM bar.bartrong join vừa không trực quan vừa xấu. Một kiểu nhưUSING (bar RESPECT NULLS)có lẽ sẽ tốt hơn nhiềuNgược lại, với kiến trúc kiểu microservice, nơi các service nhỏ mỗi cái sở hữu database riêng và chỉ một nửa trong số đó là database quan hệ, người ta càng muốn đặt ít code phức tạp trong chính database hơn. Lý do là chúng thường di chuyển giữa các instance hoặc cluster đơn lẻ, chỉ mang theo các bản dump dữ liệu tương đối đơn giản, hoặc gắn thêm bản sao mới như con tàu Theseus
Việc làm được bằng SQL thuần túy đã rất ấn tượng, nhưng dấu hiệu thật sự của năng lượng kỹ sư nứt não có lẽ là một trang Blogspot được duy trì suốt 10 năm
Khó giải thích chính xác, nhưng nó mang đậm cảm giác “cao thủ trong một ngách”. Dù không biết các tác giả, vài người duy trì một trang Blogspot tên “database architects” trong 10 năm thì có lẽ trong đúng cộng đồng đó họ chẳng cần giới thiệu thêm
Nhân tiện, tôi đã thử làm Advent of Code bằng EdgeQL trong vài ngày, và đó là một trải nghiệm khá thú vị
Tôi đã đăng vài tweet, chắc nên viết thành một bài blog
https://x.com/1st1/status/1864069589245858083
So sánh với SQL: https://x.com/1st1/status/1864412869108092997
Hoàn toàn kinh khủng. Nhưng vẫn làm tốt lắm
Bổ sung cho những ai chưa biết: tác giả là một trong những nhà nghiên cứu cơ sở dữ liệu hàng đầu thế giới