7 ms·

SQLite internals: How the most-used database works

244 points by cube2222 4y ago

fmajid 4y ago
Really like this: > Richard liked the idea of a consorsium. He started devising a plan of his own. Luckily someone from the Mozilla foundation reached out to him. They did not like the way he was setting up the framework around the consorsium by giving members voting rights. They proposed keeping the direction of the project in developers hand. The friend from Mozilla being a lawyer was adamant on this point and saw through the implementation of the current setup.
veltas 4y ago
- samwillis 4y ago
  While the first bit is a little stilted at times, similar to some of the chatGPT stuff we have seen recently, I can't see AI writing the rest of the article. It goes very deep into the technical architecture of SQLite, I don't think AI could do that. But maybe AI is better than I think.
  - osdotsystem 4y ago
    @samwillis, It is converted from notes i wrote, from a presentation i gave. This did not start as a book. Yes you are right, i did not pass this through chatGPT.
    - samwillis 4y ago
      No worries, and I completely agree with the other reply suggesting it's disrespectful to comment on others writing. I'm Dyslexic and have had to cope with people criticising my writing, judging my ability based on simple mistakes, it hurts and I'm sorry you have had that today. I haven't had the chance to fully read it yet, but I'm going to later as it's super interesting to me.
      - osdotsystem 4y ago
        Great that you like it! I guess when typing fast and the mind is dazed, errors crop up. Re-reading i saw i wrote piece of mind instead of peace of mind. Thanks for the kind words!
    - avinassh 4y ago
      Any chance, that presentation is recorded and public? I would love to watch that
      - osdotsystem 4y ago
        The one i gave in person (more energetic) is lost forever, but, the one i gave to the LibSQL community is up and online: https://www.youtube.com/watch?v=poA497gSs-4 https://www.youtube.com/watch?v=poA497gSs-4 Edit: The book has more info.
- 5e92cb50239222b 4y ago
  Are we going to see this under every submission now? The author comes from a completely different culture than most of HN users. English doesn't seem to be their first language. It can be hard to formulate your thoughts without sounding weird to native speakers, I know that feeling perfectly well.
- avinassh 4y ago
  Author could be from a non native english speaking country. It's disrespectful to attribute to AI without any benefit of doubt.
- osdotsystem 4y ago
  I am the author, no it was written by a human!
  - havnagiggle 4y ago
    Hmmm, that's what a human-imitating robot would say... /s
  - veltas 4y ago
    Apologies, reading it I got stuck on the same sentence about 3 times and gave up. If you want, I don't mind giving more constructive feedback on what's wrong.
    - osdotsystem 4y ago
      I am open! Since new material is constantly being added, feel free to bookmark it and check in about a week. You can also raise a pull request!
red_admiral 4y ago
I love how the SQLite author is so committed to the quality of his tools that he _wrote his own text editor_ as part of the project. In about 99% of cases, for 99% of people, this is the wrong thing to do - but DRH pulled it off. On the "why use flex/yacc ... when you can roll your own", I think the tradeoff is: if you have a deep understanding of theory of parsing and parser generators, then it's actually less mental effort for you to write your own from scratch, than it would be to learn the exact syntax and quirks and possibly bugs of someone else's implementation. Or to find out that some feature that's easy to implement from scratch, doesn't exist in the library. I wonder, do we teach "classical" parsing that well anymore, in a way that could create the next generation's DRH?
- deleted 4y ago
  [deleted]
- emrah 4y ago
  Doing is the best way to learn. The mind looks over gaps in understanding which are revealed when trying to build. I think DRH picked a self-imposed constraint that sqlite would not have any external dependencies. A lot of his decisions are due to this constraint.
- specialist 4y ago
  > ...than it would be to learn the exact syntax and quirks and possibly bugs of someone else's implementation... Yup. Also, having deep knowledge of the language is required. SQLite's grammar is neat, modest. Creating a compatible parser would make a fun project. Here's a pretty good example: https://github.com/bkiers/sqlite-parser https://github.com/bkiers/sqlite-parser (Actual ANTLR 4 grammar: https://github.com/bkiers/sqlite-parser/blob/master/src/main/antlr4/nl/bigo/sqliteparser/SQLite.g4 https://github.com/bkiers/sqlite-parser/blob/master/src/main... ) Postgres, which tries to be compliant with the latest standards, however... SQL-2016 is a beast. Not to mention all the dialects. I'm updating my personal (soon to be FOSS) SQL DML grammar from ANTLR 3 LL(k) to ANTLR 4 ALL(Star). I've long had a working knowledge of SQL-92, with some SQL-1999 (eg common table expressions). But all the new structures and extensions are a bit overwhelming. Fortunately, ANTLR project has ~dozen FOSS grammars to learn from. https://github.com/antlr/grammars-v4/tree/master/sql https://github.com/antlr/grammars-v4/tree/master/sql They mostly mechanically translate BNFs to LL(k) with some ALL(Star). Meaning few take advantage of left-recursion. https://github.com/antlr/antlr4/blob/master/doc/left-recursion.md https://github.com/antlr/antlr4/blob/master/doc/left-recursi... Honestly, I struggled to understand these grammars. Plus, not being conversant with the SQL-2016 was a huge impediment. Just finding a succinct corbis of test cases was a huge hurdle for me. Fortunately, the H2 Database project is a great resource. https://github.com/h2database/h2database/tree/master/h2/src/test/org/h2 https://github.com/h2database/h2database/tree/master/h2/src/... Now for the exciting conclusion... My ANTLR grammar which passes all of H2's tests diverges significantly from the official or product specific BNFs. Mostly wrt recursion. Further, I found discrepancies between misc product's BNFs and their implementations. So a lot of trial & error is required for a "real world" parser. Which would explain why the professional SQL parsing tools ask for money. I still think creating a parser for SQLite is a great project. Hand-made or using grammar toolkit of choice. (I hope to play around with Pratt and PEG parsers some day.)
pingiun 4y ago
This is highly upvoted but I wouldn't say this document is well-written
- deleted 4y ago
  [deleted]
- osdotsystem 4y ago
  Thank you for the feedback. It is pulled from my notes and is an ongoing book aimed towards contribution to the project. I did not yet pass some spellchecks on it. The book is OpenSource though and you can have a go at improving sections. I would really appreciate making the material available to a wider audience.
  - kayodelycaon 4y ago
    A note on styling. The font is rather large. On my phone, this means the column is narrow. Full justification is hard to read when you have 2 emdash spaces between words.
    - osdotsystem 4y ago
      I added the download if display broken, beacause yes, it needs fixing on phone
Sakos 4y ago
Quick question to the author: Do you have any references for the "From First Principles approach"? Or is it more just an informal thing?
- osdotsystem 4y ago
  See the co-recursive podcast episode in the references section. It is Adam's words but, i find it reasonably describing the whole attitude.
  - Sakos 4y ago
    Cool, thanks.

244 points by cube2222 4y ago

Really like this: > Richard liked the idea of a consorsium. He started devising a plan of his own. Luckily someone from the Mozilla foundation reached out to him. They did not like the way he was setting up the framework around the consorsium by giving members voting rights. They proposed keeping the direction of the project in developers hand. The friend from Mozilla being a lawyer was adamant on this point and saw through the implementation of the current setup.

veltas 4y ago

samwillis 4y ago
While the first bit is a little stilted at times, similar to some of the chatGPT stuff we have seen recently, I can't see AI writing the rest of the article. It goes very deep into the technical architecture of SQLite, I don't think AI could do that. But maybe AI is better than I think.
- osdotsystem 4y ago
  @samwillis, It is converted from notes i wrote, from a presentation i gave. This did not start as a book. Yes you are right, i did not pass this through chatGPT.
  - samwillis 4y ago
    No worries, and I completely agree with the other reply suggesting it's disrespectful to comment on others writing. I'm Dyslexic and have had to cope with people criticising my writing, judging my ability based on simple mistakes, it hurts and I'm sorry you have had that today. I haven't had the chance to fully read it yet, but I'm going to later as it's super interesting to me.
    - osdotsystem 4y ago
      Great that you like it! I guess when typing fast and the mind is dazed, errors crop up. Re-reading i saw i wrote piece of mind instead of peace of mind. Thanks for the kind words!
  - avinassh 4y ago
    Any chance, that presentation is recorded and public? I would love to watch that
    - osdotsystem 4y ago
      The one i gave in person (more energetic) is lost forever, but, the one i gave to the LibSQL community is up and online: https://www.youtube.com/watch?v=poA497gSs-4 https://www.youtube.com/watch?v=poA497gSs-4 Edit: The book has more info.
5e92cb50239222b 4y ago
Are we going to see this under every submission now? The author comes from a completely different culture than most of HN users. English doesn't seem to be their first language. It can be hard to formulate your thoughts without sounding weird to native speakers, I know that feeling perfectly well.
avinassh 4y ago
Author could be from a non native english speaking country. It's disrespectful to attribute to AI without any benefit of doubt.
osdotsystem 4y ago
I am the author, no it was written by a human!
- havnagiggle 4y ago
  Hmmm, that's what a human-imitating robot would say... /s
- veltas 4y ago
  Apologies, reading it I got stuck on the same sentence about 3 times and gave up. If you want, I don't mind giving more constructive feedback on what's wrong.
  - osdotsystem 4y ago
    I am open! Since new material is constantly being added, feel free to bookmark it and check in about a week. You can also raise a pull request!

red_admiral 4y ago

I love how the SQLite author is so committed to the quality of his tools that he _wrote his own text editor_ as part of the project. In about 99% of cases, for 99% of people, this is the wrong thing to do - but DRH pulled it off. On the "why use flex/yacc ... when you can roll your own", I think the tradeoff is: if you have a deep understanding of theory of parsing and parser generators, then it's actually less mental effort for you to write your own from scratch, than it would be to learn the exact syntax and quirks and possibly bugs of someone else's implementation. Or to find out that some feature that's easy to implement from scratch, doesn't exist in the library. I wonder, do we teach "classical" parsing that well anymore, in a way that could create the next generation's DRH?

deleted 4y ago
[deleted]
emrah 4y ago
Doing is the best way to learn. The mind looks over gaps in understanding which are revealed when trying to build. I think DRH picked a self-imposed constraint that sqlite would not have any external dependencies. A lot of his decisions are due to this constraint.
specialist 4y ago
> ...than it would be to learn the exact syntax and quirks and possibly bugs of someone else's implementation... Yup. Also, having deep knowledge of the language is required. SQLite's grammar is neat, modest. Creating a compatible parser would make a fun project. Here's a pretty good example: https://github.com/bkiers/sqlite-parser https://github.com/bkiers/sqlite-parser (Actual ANTLR 4 grammar: https://github.com/bkiers/sqlite-parser/blob/master/src/main/antlr4/nl/bigo/sqliteparser/SQLite.g4 https://github.com/bkiers/sqlite-parser/blob/master/src/main... ) Postgres, which tries to be compliant with the latest standards, however... SQL-2016 is a beast. Not to mention all the dialects. I'm updating my personal (soon to be FOSS) SQL DML grammar from ANTLR 3 LL(k) to ANTLR 4 ALL(Star). I've long had a working knowledge of SQL-92, with some SQL-1999 (eg common table expressions). But all the new structures and extensions are a bit overwhelming. Fortunately, ANTLR project has ~dozen FOSS grammars to learn from. https://github.com/antlr/grammars-v4/tree/master/sql https://github.com/antlr/grammars-v4/tree/master/sql They mostly mechanically translate BNFs to LL(k) with some ALL(Star). Meaning few take advantage of left-recursion. https://github.com/antlr/antlr4/blob/master/doc/left-recursion.md https://github.com/antlr/antlr4/blob/master/doc/left-recursi... Honestly, I struggled to understand these grammars. Plus, not being conversant with the SQL-2016 was a huge impediment. Just finding a succinct corbis of test cases was a huge hurdle for me. Fortunately, the H2 Database project is a great resource. https://github.com/h2database/h2database/tree/master/h2/src/test/org/h2 https://github.com/h2database/h2database/tree/master/h2/src/... Now for the exciting conclusion... My ANTLR grammar which passes all of H2's tests diverges significantly from the official or product specific BNFs. Mostly wrt recursion. Further, I found discrepancies between misc product's BNFs and their implementations. So a lot of trial & error is required for a "real world" parser. Which would explain why the professional SQL parsing tools ask for money. I still think creating a parser for SQLite is a great project. Hand-made or using grammar toolkit of choice. (I hope to play around with Pratt and PEG parsers some day.)

pingiun 4y ago

This is highly upvoted but I wouldn't say this document is well-written

deleted 4y ago
[deleted]
osdotsystem 4y ago
Thank you for the feedback. It is pulled from my notes and is an ongoing book aimed towards contribution to the project. I did not yet pass some spellchecks on it. The book is OpenSource though and you can have a go at improving sections. I would really appreciate making the material available to a wider audience.
- kayodelycaon 4y ago
  A note on styling. The font is rather large. On my phone, this means the column is narrow. Full justification is hard to read when you have 2 emdash spaces between words.
  - osdotsystem 4y ago
    I added the download if display broken, beacause yes, it needs fixing on phone

Sakos 4y ago

Quick question to the author: Do you have any references for the "From First Principles approach"? Or is it more just an informal thing?

osdotsystem 4y ago
See the co-recursive podcast episode in the references section. It is Adam's words but, i find it reasonably describing the whole attitude.
- Sakos 4y ago
  Cool, thanks.