Writing a SQLite Clone from Scratch in C (2022)
cstack.github.io
cstack.github.io
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)
> 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.
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.
It seems to be very hard to make that call in time, and in the past I feel like every time we chose to implement something on our own, the existing solution would have been better in hindsight, and every time we said "ok, that existing solution looks fine" it turned out to be a dumpster fire a year down the line. But obviously the times where you made the right call just don't stick out that much because stuff "just worked", and also, in case you think you made the wrong decision, the alternative could've been ever worse. But still, I guess everybody knows that feeling? :-)
Type B is writing code for money, so it almost never gets reused outside an organisation.
They love programming, which means they do it a lot (beyond the bare minimum), which means they're probably pretty good!
Working with other people's code is one of the most valuable skills. Be willing to live with existing code for a while and understand why it was implemented that way. Only then can you know what you should change.
My problem is that quite a few libraries we use eventually stop being sufficient (either because it has bugs, performance issues, limited use-case, too-wide use-case etc), and then we have to either contribute to it, with the politics involved which can be more work than the code changes, or we just bite the bullet and write things ourselves. For that reason, I find it really good to be capable enough to write things from scratch when that makes sense.
Another wonderful “from scratch” resource is “Crafting interpreters” [0] that I was recommended here on hn.
> ”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.”
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.
https://shop.jcoglan.com/building-git/
HN post on the review of James Coglan’s Building Git:
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#access...
[2]:https://stackoverflow.com/questions/3523145/pointer-arithmet...
// this compiles in GNU C
int * foo(int x) {
return x;
}
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.
edit: hmm, maybe not:
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.
void * ptr;
uintptr_t x = (uintptr_t)ptr;
uintptr_t x = ptr;
> Several operators convert operand values from one type to another automatically. This subclause specifies the result required from such an implicit conversion, as well as those that result from a cast operation (an explicit conversion). The list in 6.3.1.8 summarizes the conversions performed by most ordinary operators; it is supplemented as required by the discussion of each operator in 6.5.
Weather a conversion is allowed in a certain context should be specified for wording for that given context.
For example assignment:
https://cigix.me/c17#6.5.16.1.p1
Return statements are similarly restricted:
https://cigix.me/c17#6.8.6.4.p3
> If the expression has a type different from the return type of the function in which it appears, the value is converted as if by assignment to an object having the return type of the function.
(emphasis mine)
However I can't make sense of the footnote:
> The return statement is not an assignment. The overlap restriction of subclause 6.5.16.1 does not apply to the case of function return. The representation of floating-point values may have wider range or precision than implied by the type; a cast may be used to remove this extra range and precision.
Why doesn't the overlap restriction apply, if return is "as if by assignment"? Makes no sense to me.
Not being in ISO C(99, I'm less sure about 89) doesn't make it a GNUism. At best you're disagreeing with GCC over its default standards version.
Clang only changed the default in 2022, for example. https://reviews.llvm.org/D129881
$ gcc -c test.c
test.c: In function ‘foo’:
test.c:3:12: warning: return makes pointer from integer without a cast [-Wint-conversion]
return x;
^
ISO C doesn't say that translation must be terminated.
ISO C doesn't define different classes of diagnostic like "error" or "warning".
I didn't tell GCC to be an ISO C compiler. The above diagnostic tells us that while conversions from integers to pointers happen implicitly, the GNU C dialect, like ISO C, wants that diagnosed. You have to go out of your way to modify the dialect not to have that diagnosed, like:
$ gcc -Wno-int-conversion -c test.c
$
OTOH two different C implementations would be more interesting to compare for a C connoisseur.
In the next year or two though I'll probably get around to doing the LSM tree bits myself. But not yet.
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.
I suspect our jobs are going to change quite a lot in the coming years.
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.
Still cool as a hobby project.
1: https://www.sqlite.org/crew.html 2: https://www.sqlite.org/copyright.html
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.
Unanswered issue about the likelihood of continuation: https://github.com/cstack/db_tutorial/issues/94
But this is good too.
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.
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