How a SQL database works

Is a btree with a million nodes really going to be any easier to understand? Like I understand some times its better to have more realistic data (e.g for presenting results related to benchmarking performance), but for a post explaining the data structures behind a database it wouldn't help at all.

The main thing to learn about btrees is that they have very high branching to ensure shallowness and thus trade off more sequential accesses for fewer random accesses, a good tradeoff for disk I/O. The other thing is to recognise that sorted access is still better than random access even over an index; better for disk / block cache, better for CPU cache, and seemingly redundant sorts can e.g. have outsize constant factor performance wins for some joins over materialized subtable queries.

IIRC Microsoft provided a full blown demo database ( either for SQL Server or from Access, I can't remember ).

Alternatively, analytics databases don't use indices by design, as for most queries they need to shuffle entire datasets anyways. For example, https://dbdb.io/db/vertica: "Indexes are not support in Vertica."

Hi, - thanks for the feedback - I appreciate it. Negative feedback is always helpful :)

I did originally try using a meatier example but I found that doing that a) makes writing the article really hard - for example, diagramming a meaningful database is a lot of work and makes the diagrams incomprehensive and b) it is that much harder to trasmit the principles than when the example is trivial.

Almost everything is down to join order, and that's mostly down to which join order ends up with the fewest rows to process.

MySQL IMHO is better for this than Postgres because it's more predictable and you have more tools to force its behaviour, with straight_join and index hints, whereas with Postgres you're forced to use CTEs to control evaluation behaviour when you have application knowledge that the DB doesn't have stats for.

If you know nothing about how databases work, and deal in mostly simple queries, Postgres is a better choice though.

I'll try! :) I wanted to cover this material because I found that most of the "how SQL works" intros discuss query planning but I think knowing the underlying datastructures gives people pretty useful intuition.