6 ms·
Writing a SQL database from scratch in Go
- eatonphil 6y agoUnexpected, but welcome, to see the first part in the series on here right now. I just published the second part [0] today, featuring binary expressions and WHERE filtering. It also updates the REPL to use a prettier table-printing library and a readline implementation. The repo [1] has some additional bare notes on architecture and links to similar, more mature projects (primarily go-mysql-server and ramsql). [0] https://notes.eatonphil.com/database-basics-expressions-and-where.html https://notes.eatonphil.com/database-basics-expressions-and-... [1] https://github.com/eatonphil/gosql https://github.com/eatonphil/gosql
- bogomipz 6y agoThis is great. Do you plan on continuing this blog series? If so I hope you post it here. Cheers.
- eatonphil 6y agoDefinitely! I typically do post here. There are also links for various ways to subscribe on the site itself (e.g. twitter, email).
- nednar 6y agoThe idea is nice, but it seems like the text is not explaining much. If you don't have a background in parser writing you have no clue what types are defined there and why in the very first code block. If you're not an SQL expert you might still know what SELECT and WHERE is, but do you think everybody knows what's an INTO keyword is used for? Where does the lex function come from? Why do I have a lexer and a lex()? Where does the cursor come from that I give into it? Why don't I give it a string? My user input SQL statement is a string, right? Why does the lex function have two for loops? What can't be done in one? Does this whole logic actually have a name maybe? What other alternatives to parsing SQL are out there? Why choose this path? All that knowledge can't be gathered by just staring at the source code. And for people who understand the source code well enough to gather all this info themselves maybe they don't need the blog post around it, right? Now all this I don't say to demotivate you. I hope you're strong enough to get over negative feedback and think about rewriting it to something more useful. I see a lot of potential here. But every good writer needs one (or ten million hacker news reading) editors to get to the really good content.
- zoom6628 6y agoProbably the first article Ive ever read about lexical parsing with code that i have actually understood - and I dont even program in golang. Great job.
- throwlaplace 6y agoLexical analysis using these bespoke methods (writing the finite state machine) is so tedious and error prone. I don't have that much experience but I just went through crafting interpreters and replaced this same module with https://github.com/J-F-Liu/pom https://github.com/J-F-Liu/pom, which is a parser combinator library, and it was way easier.
- gpetukhov 6y agoI guess it's relevant. Here is a great set of videos from "Low Level Javascript" channel explaining how to write parser combinators from scratch. - https://www.youtube.com/watch?v=6oQLRhw5Ah0&list=PLP29wDx6QmW5yfO1LAgO8kU3aQEj8SIrU https://www.youtube.com/watch?v=6oQLRhw5Ah0&list=PLP29wDx6Qm...
- arcticbull 6y agoParser combinators are neat. nom is my go-to now in Rust, it's nice not have to separate your lexer and parser in simpler grammars.
- dilap 6y ago(it’s actually also straightforward to write a recursive descent parser directly on the char stream w/o a lexing step.)
- throwlaplace 6y agohow? it's not like you can magically skip the actual tokenization. you're basically saying you can do lexical analysis and semantic analysis in the same function. sure but that makes the code that much hairier - there's a reason why they're typically factored into a lexer and a parser.
- userbinator 6y agoselectKeyword keyword = "select" I don't work with Go, so this may be a requirement of the language that I don't know, but whenever I see lines like this, it automatically brings up the question why? --- do you really expect to need to rename the SELECT keyword? Especially when it's named "selectKeyword". Why not just use the string constant? Ditto for the others like "leftparenSymbol" --- I see there's explicit character constants in some of the other code too... it reminds me of the classic anti-pattern like "int five = 5;". Also, you may find the full SQL grammars interesting to look through --- they are quite a bit more complex than the subset presented in the article: https://ronsavage.github.io/SQL/ https://ronsavage.github.io/SQL/
- eatonphil 6y agoThe biggest reason to do this in Go is to approximate enums. Now anywhere the `keyword` type is used, it must be one of the ones specified there (or you'd have to cast a string). Yep, it would be a little harder to implement all of the SQL spec in a single post. Maybe over time though.
- ycnewsreader 6y agoAnother reason is that by providing an identifier for this string literal, misspellings of it can be detected by the compiler whereas there is nothing tying separate string literals together.
- userbinator 6y agoI can hardly imagine a case where you would misspell "select" and not notice it at some point, nor use it in more than one place (the keyword detector) in the parser.
- triyambakam 6y agoYou'd be surprised...
- Townley 6y agoThe pattern (which I employ only sometimes) is to have almost all literals defined in this way. Perhaps SELECT isn’t likely to be the word you misspell, but I’m a careless typist and make 10 typos a minute. Taking this added step helps your editor save you from yourself.
- alexanderhorl 6y agoAre you going to add persistence in an upcoming part?
- eatonphil 6y agoProbably! That's the most interesting and most difficult part so it may take me a while.
- cube2222 6y agoGreat blog post! I'd just like to add for the curious, that usually you'd use goyacc for parsing SQL. And most serious SQL projects in Go have started with the SQL parser from vitess and adapted it to their use case (which is just funny trivia, but for anything big, I recommend it, did the same for OctoSQL [0]). [0]: https://github.com/cube2222/octosql https://github.com/cube2222/octosql
- pizza234 6y agoThis is not the first educational project I've seen that insists on manually writing the parser. Call me contrarian but I find the article's approach poor (at least, as it is now). If one looks at the overall content of the two articles of the series, 70%/80% of the content (or possibly more) is parsing, which is arguably the least interesting, or at least, the most boilerplate, part of a database system.
- tbrock 6y agoWhy did all of the Golang SQL parsers come from Vitess? I would love to know more about this history. Was it because they were the first and people just started using it or is it the best for some reason?
- eatonphil 6y agoSQL is a humongous spec. Any serious project would rather piggy-back off an existing parser. Most of the interesting parts for most people is implementing backends against in-memory, disk, S3, HDFS, etc.
- eatonphil 6y agoAlso, a contributor to dolthub shared on Reddit last time this post came up that they originally wrote their own SQL frontend but gave up because it was so much to maintain and get correct. They ended up going with go-mysql-server which uses vitess. https://www.reddit.com/r/golang/comments/fgwwlx/database_basics_writing_a_sql_database_from/fk84dq9/?context=3 https://www.reddit.com/r/golang/comments/fgwwlx/database_bas...
- alperakgun 6y agoCurious - would Rust be more appropriate than Go for such a task?
- cultofmetatron 6y agorust would be more appropriate if your intention was to use this in production. Databases ad GC don't mix well. (its done but it makes tuning a nightmare) As much as I love rust, its learning curve is high and I'm sure Op doesn't want to spend half his article teaching all the intricacies of types and the borrow checker. Go is easy to learn over a weekend so its probably a better medium for illustrating the concepts as everything is laid out simply.
- arendtio 6y agoSometimes I wonder how Go would look like with a borrow checker...
- eatonphil 6y agoTruth is I've written about how to parse in better languages before (JavaScript, Python, Standard ML, etc.) and I wanted to figure out a good approach for doing it in Go. As for databases and GC, you may be right but there are still major databases out there written in Java for example. https://www.quora.com/Which-databases-data-stores-are-written-in-Java https://www.quora.com/Which-databases-data-stores-are-writte...
- matttproud 6y agoA garbage collector is not inherently incompatible with a low-latency database. I was generally very happy with the performance of Go's garbage collector enough to have built Prometheus, the time series database, on it back in 2012, when the collector was considerably more naive. https://blog.golang.org/ismmkeynote https://blog.golang.org/ismmkeynote
- speedgoose 6y agoGolang works too. There is a few databases written in Golang, such as Prometheus, InfluxDB, CockroachDB, or tidb. https://github.com/topics/database?l=go&o=desc&s=stars https://github.com/topics/database?l=go&o=desc&s=stars
- rochak 6y agoDo you know about a tutorial or a book that helps write Database from scratch either in Java or C?