6 ms·
Writing a SQLite Clone from Scratch in C (2022)
- lucasmedeiros7 3y agocool project
- skripp 3y agoI love these type of projects. This is definitely on the top of my reading list now. Another wonderful “from scratch” resource is “Crafting interpreters” [0] that I was recommended here on hn. [0] https://craftinginterpreters.com/introduction.html https://craftinginterpreters.com/introduction.html
- tmountain 3y agoAnother good one is handmade hero for creating a game from the absolute beginning. It’s extremely lengthy, but very information dense, and it’s only $15 USD. https://handmadehero.org/ https://handmadehero.org/
- AlchemistCamp 3y agoWow, you weren’t kidding. I can’t imagine how anyone could join in and get caught up to the present day state of the code. > ”How long is the series expected to last?” > ”The series started on November 17th, 2014. Sessions are limited to two hours or less per day so it remains manageable for people who practice coding along with the series at home. There is no prescribed length for the series. It will continue until all the game and engine code is complete.”
- smaddox 3y agoEven just watching the first ~20 episodes dramatically altered how I approach coding, for the better. At least, when combined with his blog posts, e.g. https://caseymuratori.com/blog_0015 https://caseymuratori.com/blog_0015 (you can skip the snarky intro)
- AlchemistCamp 3y agoThat sounds fantastic. I’m going to bookmark this for my next vacation.
- detrites 3y agoI clicked around, read the FAQ and skimmed some videos, but I could find no description, nor images of the actual game. The best I could find was in a 2hr episode numbered in the 600's, about 20 wireframe boxes being moved around. Is there any description of the game you're going to invest all this time to build? And, if those wireframe boxes really are the result of 1200 hrs of coding - count me out.
- ternaryoperator 3y agoAnother good one is Jacobin[0], a JVM being written in go. [0] http://jacobin.org http://jacobin.org
- teleforce 3y agoThis is a book on Building Git clone: https://shop.jcoglan.com/building-git/ https://shop.jcoglan.com/building-git/ HN post on the review of James Coglan’s Building Git: https://news.ycombinator.com/item?id=35626698 https://news.ycombinator.com/item?id=35626698
- comfypotato 3y agoDoesn’t SQL have decades worth of optimizations? I remember something from my databases class where the professor was mentioning how it’s to the point now where nobody really understands every aspect of what goes on between the query and the machine instructions. Still cool as a hobby project.
- valleyer 3y agoSQL is not the name of a piece of software, and SQLite is developed by a single person.
- scblock 3y agoWhile SQLite is developed by a very small team[1] and does not openly accept patches[2], it is not developed by a single person. 1: https://www.sqlite.org/crew.html https://www.sqlite.org/crew.html 2: https://www.sqlite.org/copyright.html https://www.sqlite.org/copyright.html
- valray 3y agoFrom the link, it appears that it was developed by a single person in 2000, who then brought on board 2 other people as contributors in 2002 and after.
- deleted 3y ago[deleted]
- klabb3 3y agoThat’s probably true but building a clone that people understand, even if slower, is extremely valuable. Understanding an existing technology deeply is a gateway to innovation. That said, SQLite is so remarkably stable, lightweight like a feather, and incredibly battletested, that even a hypothetically superior alternative would have an immense uphill battle to reach the same value prop.
- nickpeterson 3y agoHow about a C clone in SQLite?
- euroderf 3y agoSounds like a job for a LLM !
- fooker 3y agoSqlite has a fairly exhaustive test suite. I wonder how far we are from auto-generating code which manages to pass these tests and maybe produce same results on random queries compared to SQLite3. Two years ago, I’d have said 50 years. That estimate is now blown.
- tonyedgecombe 3y agoOr generating the test suite from the specification. Or finding ambiguities in the specification. I suspect our jobs are going to change quite a lot in the coming years.
- chasil 3y agoThe final test suite was used to pass DO-178B, allowing SQLite to be the only major database that is approved for use in critical avionics. Dr. Hipp remarked that he spent years of 80 hour weeks attaining this quality. C can be used safely, but it can be very hard.
- bruce511 3y agoIn software, as in most things, most of learning is done by doing. Creating a clone of something from scratch is a really useful learning technique and has the benefit of a defined specification. It doesn't even really matter if the job is even completed or if the program is ever used. The important part is the doing, not the result. I confess we did similar things at uni 30 years ago, although we mostly re-implemented arcade games, not sql databases. Databases are likely more useful to understand. All programmers have to go through 3 stages; A) I program to prove to myself I can B) I program to prove to others I can C) I know I can write this, you know I can write this, but its cheaper and easier to use this existing, available, code to do the job. I like c) programmers in business because they understand that the goal of the business is making money not generating code. A guy who -could- write SQLite, but then understands why -using- SQLite would be better, is enormously valuable. (Not to mention his SQL chops are probably pretty good by then)
- asveikau 3y agoRegarding C), I think it actually gets tough. > but its cheaper and easier to use this existing, available, code to do the job. What often happens is that the existing, available, sometimes even popular and well regarded code has lots of issues that you may only find after you deploy the thing. Then, you need to decide what tack to take. Can you engage upstream? Do you end up maintaining third party code yourself to fix the issues? Working around quirky bugs? You may even find yourself so frustrated with all of the above that you wind up abandoning the dependency and writing something new in-house. But honestly, getting back to the topic, sqlite is not one of those things. Sqlite is a very solid library.
- bruce511 3y agoYes, I agree not every bit of available code is perfect. A lot of it is crap. Choosing an existing library is worth taking dome time and research over. Inevitably some libraries will need replacing. In some cases we've ended up rolling our own. But in these cases the time spent with the discarded library is not wasted. Rather it gives us a chance to understand the domain better, to understand our needs better, and ultimately to have better criteria for making our choices. Things like documentation, support, bug fixing, source code, and so on have all become important parts of the evaluation process. Interestingly our internal libraries are often less-well documented (if at all) the author is sometimes no longer around, and it usually has all kinds of quirks we work around. This after taking longer, and costing more, written from an unclear spec by people not terribly familiar with the domain. And yes, we've hone the nuclear route of ripping out and rewriting, and that is expensive , but no more expensive than defaulting to "write ourselves ", and indeed usually cheaper because we have a better idea of what we want.
- simula67 3y agoHow unfortunate that Sqlite Virtual Machine has opcodes to directly manipulate B-Trees. The opcode documentation[1] is even written in terms of B-Trees. This means that it would be too complicated to replace the storage engine with something else, necessitating the need for seperate products such as duckdb. [1] https://www.sqlite.org/opcode.html https://www.sqlite.org/opcode.html
- pyrolistical 3y agoSince SQLite is already written in C, it would be interesting to do a rewrite in a different system language like zig
- nine_k 3y agoIndeed: Zig, Rust, Ada/spark, Nim, ATS — anything would be more interesting to see than C. OTOH two different C implementations would be more interesting to compare for a C connoisseur.
- eatonphil 3y agoHere's one I wrote about a SQL database on top of RocksDB in Zig. In the next year or two though I'll probably get around to doing the LSM tree bits myself. But not yet. https://notes.eatonphil.com/zigrocks-sql.html https://notes.eatonphil.com/zigrocks-sql.html
- rurban 3y agoThis would be a good chance to outline and fix some of the worst design decisions of the various sqlite hacks and security issues. No stack, so no proper subfunction model, such as triggers or functions calling other functions. Simple remote queries can be made destructive, due to the extremely hackish design. The horrible, insecure by default text search engine. Unfortunately this guy treats sqlite as a role model of a good design. Maybe he will find out when it's too late. https://github.com/rurban/hardsqlite https://github.com/rurban/hardsqlite
- emrah 3y agoBuilding is a great way to learn for sure but exact cloning gets boring for me. I always end up needing to introduce some kind of twist to the original idea to keep the project interesting beyond a certain point
- Shorel 3y agoGood, hopefully this will be the second implementation that the W3C standards committee will accept, so SQLite is an approved web standard instead of the disappointing thing we got.
- detrites 3y agoLooks like this is from 2017-2019, incomplete, and hasn't been active much since then. Unanswered issue about the likelihood of continuation: https://github.com/cstack/db_tutorial/issues/94 https://github.com/cstack/db_tutorial/issues/94
- esaym 3y agoYea, disappointing.
- unwind 3y agoThis seems serious, and a very nice introduction/primer on how databases work under the hood, thanks for sharing! One minor nitpick after glancing quickly at the code: there's pointer arithmetic with 'void *' pointers [1], which is a GCC extension and not portable [2]. It should be rewritten using the proper casts, in my opinion. [1]: https://cstack.github.io/db_tutorial/parts/part8.html#accessing-leaf-node-fields https://cstack.github.io/db_tutorial/parts/part8.html#access... [2]:https://stackoverflow.com/questions/3523145/pointer-arithmetic-for-void-pointer-in-c https://stackoverflow.com/questions/3523145/pointer-arithmet...
- planede 3y agoI would probably just avoid all GNUism in C. Some GNU C extensions are just plain crazy: // this compiles in GNU C int * foo(int x) { return x; } Just stick to -std=c<year> -pedantic-errors if you have to write C.
- unwind 3y agoYes, I agree especially for code intended to teach something else it's not a good idea to include GCCisms. I didn't find any section about compilation set-up (compiler, warning levels, flags etc) at all in the OP, but didn't spend a lot of time looking. Perhaps it would be a good addition too to specify which dialect of C is used.
- morelisp 3y agoWhat's the GNUism here? Silently casting ints to pointers is a time-honored C tradition.
- planede 3y agoWell, that's just ill formed in ISO C. edit: hmm, maybe not: https://cigix.me/c17#6.3.2.3.p5 https://cigix.me/c17#6.3.2.3.p5 Looks like gcc rejects the implicit conversion with -std=c17 -pedantic-errors as it's such a bad idea to allow this, but ISO C actually allows this.
- rohitpaulk 3y agoDid a version of this myself using Python, was a great learning experience. I got hooked on the whole “build your own X” format after watching a pluralsight course called “Learn by building Redis with Ruby” by Xavier Shay - highly recommend.
- lang4d 3y agoFrom Part 3, does malloc(PAGE_SIZE) actually guarantee a single full page is allocated or would the allocation be positioned arbitrarily and stretch across two pages?
- webshit2 3y agoThat should be a valloc or aligned_alloc for it to actually be page-aligned
- glonq 3y agoEven as an oldschool C programmer, I would be hesitant to do somthing like this in C. Why not C++, where you can stay close to the metal but enjoy a few niceties?
- erichocean 3y agoI would love to see the equivalent of Crafting Interpreters for SQLite, including the two-part structure with a simple (but slow) Java implementation in Part 1 followed by a more-complicated (but fast) rewrite in C in Part 2. But this is good too.