4 ms·

Mini-SQL-Engine – A Simple Educational SQL Engine in 297 LOC in Python

peter_d_sherman 3y ago
The problem, broadly defined: You'd like to learn how modern SQL databases (SQL Server, Oracle, MySQL, Postgres, etc., etc.) work, "under the hood"... ...but most modern SQL databases, even if they are open source, comprise tens of thousands, hundreds of thousands, millions of lines of code, usually in C or C++ -- and you either don't understand C or C++ and/or are not a C or C++ expert... What to do? Well, one approach would be to attempt to study the simplest (in terms of LOC) working open source SQL database, of which an early version of SQLite would be a reasonably good candidate: https://stackoverflow.com/questions/55791432/how-to-compile-sqlite-1-0-1-which-released-18-years-ago https://stackoverflow.com/questions/55791432/how-to-compile-... But this approach has some problems! Most notably that even the earliest version of SQLite is still many LOC, and it's in C -- which DBA's, Power Users, and many beginner to intermediate level programmers -- might not have a good enough grasp on. So, what to do? Well, how about studying a 297 LOC SQL Engine -- written in Python! Would that be easier? While still arguably not the most perfect solution to teaching/learning what SQL databases do "under the hood" -- it is very very good(!) -- a huge step forward from having to study 10,000+ lines of SQLite code in C! In other words -- its about 99% of the "way there"... What would be 100%? Well, I don't as-of-yet know... But I do know that if it were to exist -- it would have to do with abstraction. In other words, think of each program as a series of layers, a pyramid of layers. At the highest level is the shortest set of the most general instructions, ideally in English (or the native language of the learner) -- or as close to that as possible. At each lower level -- instructions become more and more specific. So, what's the right number of abstraction layers for each program? Well, I as-of-yet don't know that... But we can observe that any given program could be written as really long single file of very specific functions -- but we could also "fold" this set of functions into various different levels of more general ones. That leads to the following question: Could, in the future, a LLM or other AI -- know enough about a given program of significant complexity -- to fold and unfold it (refactor it) -- along arbitrary dimensions of abstraction? ? In other words, be able to ask the AI questions something like: "Here is a program with a million lines of code. I'd like you to refactor it such that at the highest level of abstraction, it only performs 3 appropriately named functions. Each of these individual functions will then call 3 other appropriately named functions (for 3 functions calling 3 other more specific, less abstract functions (in the next layer down) each for 9 total functions called in the second layer of abstraction), then 27 in the 3rd layer -- until the level of the most specific instructions/functions were reached, etc. etc., So, refactor (and appropriately name) functions along various dimensions of abstraction (and make it so that the program still works correctly!) Then anyone who wanted to understand any program -- could simply ask the AI to fold or unfold the program along those dimensions of abstraction resulting in much, much, much more readable code! OK, I've went off on a tangent... point is, if you want to learn about the heart and core of how SQL databases work -- then you would be interested in the following code: https://github.com/chaitanya100100/Mini-SQL-Engine/blob/master/src/mini_sql.py https://github.com/chaitanya100100/Mini-SQL-Engine/blob/mast... ...which gets an A+, 10/10, and a GitHub Star from me -- for educational purposes! Related: https://www.sqlite.org/opcode.html https://www.sqlite.org/opcode.html

The problem, broadly defined: You'd like to learn how modern SQL databases (SQL Server, Oracle, MySQL, Postgres, etc., etc.) work, "under the hood"... ...but most modern SQL databases, even if they are open source, comprise tens of thousands, hundreds of thousands, millions of lines of code, usually in C or C++ -- and you either don't understand C or C++ and/or are not a C or C++ expert... What to do? Well, one approach would be to attempt to study the simplest (in terms of LOC) working open source SQL database, of which an early version of SQLite would be a reasonably good candidate: https://stackoverflow.com/questions/55791432/how-to-compile-sqlite-1-0-1-which-released-18-years-ago https://stackoverflow.com/questions/55791432/how-to-compile-... But this approach has some problems! Most notably that even the earliest version of SQLite is still many LOC, and it's in C -- which DBA's, Power Users, and many beginner to intermediate level programmers -- might not have a good enough grasp on. So, what to do? Well, how about studying a 297 LOC SQL Engine -- written in Python! Would that be easier? While still arguably not the most perfect solution to teaching/learning what SQL databases do "under the hood" -- it is very very good(!) -- a huge step forward from having to study 10,000+ lines of SQLite code in C! In other words -- its about 99% of the "way there"... What would be 100%? Well, I don't as-of-yet know... But I do know that if it were to exist -- it would have to do with abstraction. In other words, think of each program as a series of layers, a pyramid of layers. At the highest level is the shortest set of the most general instructions, ideally in English (or the native language of the learner) -- or as close to that as possible. At each lower level -- instructions become more and more specific. So, what's the right number of abstraction layers for each program? Well, I as-of-yet don't know that... But we can observe that any given program could be written as really long single file of very specific functions -- but we could also "fold" this set of functions into various different levels of more general ones. That leads to the following question: Could, in the future, a LLM or other AI -- know enough about a given program of significant complexity -- to fold and unfold it (refactor it) -- along arbitrary dimensions of abstraction? ? In other words, be able to ask the AI questions something like: "Here is a program with a million lines of code. I'd like you to refactor it such that at the highest level of abstraction, it only performs 3 appropriately named functions. Each of these individual functions will then call 3 other appropriately named functions (for 3 functions calling 3 other more specific, less abstract functions (in the next layer down) each for 9 total functions called in the second layer of abstraction), then 27 in the 3rd layer -- until the level of the most specific instructions/functions were reached, etc. etc., So, refactor (and appropriately name) functions along various dimensions of abstraction (and make it so that the program still works correctly!) Then anyone who wanted to understand any program -- could simply ask the AI to fold or unfold the program along those dimensions of abstraction resulting in much, much, much more readable code! OK, I've went off on a tangent... point is, if you want to learn about the heart and core of how SQL databases work -- then you would be interested in the following code: https://github.com/chaitanya100100/Mini-SQL-Engine/blob/master/src/mini_sql.py https://github.com/chaitanya100100/Mini-SQL-Engine/blob/mast... ...which gets an A+, 10/10, and a GitHub Star from me -- for educational purposes! Related: https://www.sqlite.org/opcode.html https://www.sqlite.org/opcode.html