There is a more recent lecture on the same topic from 2015 at CMU: https://youtu.be/gpxnbly9bz4
this video is a 100ft overview, original link is about SQL internals
Detailed explanations start at 26m40s:
How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
91–100 of 134 posts
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#92so I was trying to figure out why a query was slow the other day... it was a nasty query with like 14 joins... I used explain and saw that it was a mess... now in my case I was able to switch to outer joints and nest related joins and got it fast.. but I had some interesting thoughts. In SQL, indexes are implicit.. they are used if available but it's easy get a large query to scan sometimes when it shouldnt... what i…
MySQL has or had a way of forcing index use, and while it was very occasionally a life-safer, it was much less useful than you might think, as often when a DB engine falls back to sequential scan, it's for a reason (e.g. the query planner might have found that the indexes don't cover the columns you need, and the number of indexed lookups into the table that is needed are costly enough that a sequential scan might end up being faster, for example).
It was useful occasionally "back in the day" when MySQL's query planner was really bad, but today it will mostly appear useful if there's something subtly wrong with your config. I don't use MySQL much any more, but on Postgres one typical mistake might be that the costs configured for the query planner doesn't match your hardware (e.g. if your seek cost is configured to be high enough relative to sequential reads, sequential scans starts to look really good even when you need only a small portion of the data; principle will be the same on MySQL but I don't know if you have the same control over the query planner costs or not).
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#93Gosh, I must say there seems to be some misunderstanding of RDBMS concepts in some posts in this thread!
I was writing database systems professionally, back in the days before the RDBMS concept was even a thing. So here's my (enormously long and convoluted) 2 cents worth. Please be sure to pack a sandwich and get hydrated before you continue.
Say you were dealing with doctors and patients, and needed to store that information in a database. Back in the day, you'd typically use a so-called hierarchical database. To design one of those, you need to decide, what is the most common access method expected to be: getting the patients for a given doctor, or the doctors for a given patient? You'd design the schema accordingly. Then, the preferred access method was easy to code, and efficient to run. The "other" access method was still possible, but harder to code, and slower to run. The database schema depended on how you thought the users would access the data.
But that is absolutely what NOT what to do with an RDBMS. Certainly you look at the users' screens, reports, and so on - but that's just to determine what unique entities the system must handle - in this case, doctors and patients. Then you ignore how the users will access the data, and work out what are the inherent logical relationships between all the entities.
Your initial answer might be this. A doctor can have many patients, and a patient can have many doctors. As any competent relational designer will instantly know, this means you need a resolving table whose primary key is a composite key comprising the primary keys of the other two tables. So if Mary was a patient of Tom, you'd add Mary to the patients table (if not already there), Tom to the doctors table (ditto), then add a Mary/Tom record to the resolving table. By that means, a doctor could have any number of patients, a patient could have any number of doctors, and it's trivially easy to write simple, performant SQL to access that data however you want.
But then you'd have a ghastly thought: patients can also be doctors, and doctors can also be patients! Say Tom was also a patient of Mary! Now you need a Tom record in the patient's table, but that would inappropriately duplicate all his data from the doctors table! Something's clearly wrong. You'd soon see that from a data modelling viewpoint, you don't want doctors and patients as separate entities - you want a single entity Person, and a resolving table to relate arbitrary people in specified ways.
So what?!!
So this. IMHO, many developers using relational databases have absolutely no idea about any of that. They design hopelessly unnormalised schemas, which then need reams of ghastly SQL to get anything out. The query planner can barely parse all that crap, let along optimise it. The database has to stop every five minutes to wet its brow and take a drink.
So here's my advice to any inexperienced relational database designers who have actually managed to get this far!! If you can answer the following questions off the top of your head, you're probably on the right track. If you can't, you're lacking basic knowledge that you need in order to use an RDBMS properly:
- what is a primary key? - what is a foreign key? - what is an important difference between primary keys and foreign keys? - what is a composite key? When would you use one? - what are the three main relations? - what is normalisation? - what is denormalization? - what is a normal form? and so on.
Just my 2c! :-)
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#94Earlier quoted context omitted.
You're not scared, you're just too lazy to learn the tools of your trade. Databases are not very complex and use pretty much only textbook data structures and algorithms. Understanding how they process a given query and how a query will probably perform/scale (even without EXPLAIN ANALYZE) is not hard to learn. You do need to learn it (at some point; you don't for small data, which is most). But it's far from difficu…
Databases are amongst the most complex systems you will ever use as a developer. At the limit, they rival operating systems for complexity - distributed concurrent systems with lots of low-level memory and filesystem action, along with a parser, optimizing compiler and often a code generator too.
While that may be true for some of them, a lot of databases are far simpler.
Sqlite for example is conceptually very simple, and it's fairly cleanly layered, so you can aim to understand the parser, the compiler and the bytecode execution engine separately.
It's also exceptionally well documented. Look at the "Technical and Design Documentation" section here [1].
It won't tell you everything about how a more complex database like e.g. Postgres works, but it will give a very good overview of most of what is relevant for a database user that wants a better understanding of why a database does what it does with a given query.
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#95Earlier quoted context omitted.
> I never really know if my query will be O(1), O(log(n)), O(n), etc, or what kind of algorithm will optimize my query Aka leaky abstractions. SQL just wasn't designed for performance. A query language that takes performance into account should definitely ignore any ideas from SQL. Maybe have declared data structures instead of tables with operations that use known algorithms, explicitly chosen.
SQL just wasn't designed for performance. That is strictly true in the literal sense that SQL is just a textual representation of relational algebra and calculus, and noone says a mathematical notation is "designed for performance" or otherwise. But in a more practical, useful sense, it's the language most designed for performance, since the query planner has so much leeway to perform optimisation. It can do more dra…
If you cannot predict performance of a query you cannot write a query with guaranteed performance characteristics and cannot guarantee performance of your application. So, no, SQL and RDBMSs in general are neither designed for performance nor are any good at it. Which is one of the reasons we have the whole world outside of them.
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#96Gosh, I must say there seems to be some misunderstanding of RDBMS concepts in some posts in this thread! I was writing database systems professionally, back in the days before the RDBMS concept was even a thing. So here's my (enormously long and convoluted) 2 cents worth. Please be sure to pack a sandwich and get hydrated before you continue. Say you were dealing with doctors and patients, and needed to store that in…
I imagine you've written more than your fair share of PROGRESS 4GL code in the past .. your qualifications questions are pretty much straight out of the PROGRESS 4GL user guide .. ;)
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#97Earlier quoted context omitted.
"You describe what you want, not how to get it." The entire archive of the pgsql users' mailing list disagrees. Every wants to know why their plan is suboptimal, or why it changed. People also want to know why the planner takes 100ms to generate the plan and only 1ms to execute the query, and so forth. The idea that you just say what you want and you get the optimal result from your database is just ridiculous to any…
> The entire archive of the pgsql users' mailing list disagrees. Every wants to know why their plan is suboptimal, or why it changed. And rather a lot of the archives of $scripting_language_of_your_choice are people confused about duck-typing/type system failures. That doesn't mean scripting languages should be replaced with statically typed ones; just that there are pain points in every system, and right (or wrong)…
The biggest tradeoff SQL gives you is exactly the one GP points out: it's a leaky abstraction where understanding performance is tied to implementation so much, that you pretty much lose all the benefits of SQL, except familiarity with the technology.
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#98Gosh, I must say there seems to be some misunderstanding of RDBMS concepts in some posts in this thread! I was writing database systems professionally, back in the days before the RDBMS concept was even a thing. So here's my (enormously long and convoluted) 2 cents worth. Please be sure to pack a sandwich and get hydrated before you continue. Say you were dealing with doctors and patients, and needed to store that in…
I imagine you've written more than your fair share of PROGRESS 4GL code in the past .. your qualifications questions are pretty much straight out of the PROGRESS 4GL user guide .. ;)
Nope! I've never used postgres at all. Most of my RDBMS work was done on HN NSFW ALERT - oracle :-) But your comment supports my general point, which is, that data modelling and relational schema design skills are product agnostic; normalization is normalization, as it were.
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#99Earlier quoted context omitted.
> I really wonder who, today, have data that cannot fit in RAM, apart from big actors. Keeping all your data in RAM has significant problems, even if it all fits. For example, would you want to lose all your customers' orders and billing information if your code crashed? In addition to the relational database model, SQL databases offer ACID transactions, which are useful if you want to have consistent and reliable da…
> For example, would you want to lose all your customers' orders and billing information if your code crashed? There are things like WAL and snapshots. Having your dataset in RAM and querying directly doesn't exclude persisting it to disk. Read Stonebraker's "The End of an Architectural Era"[0]. Basically the OP is right in that SQL DBs were designed assuming that RAM was scarce and that asumption is no longer valid.…
> exclude
As a non-native speaker, I think that preclude is the word you're looking for. Not disagreeing with what you say.
Re: How SQL Database Engines Work, by the Creator of SQLite (2008) [video]
#100Earlier quoted context omitted.
Databases are amongst the most complex systems you will ever use as a developer. At the limit, they rival operating systems for complexity - distributed concurrent systems with lots of low-level memory and filesystem action, along with a parser, optimizing compiler and often a code generator too.
The performance characteristics of them, though, are easy to learn, and easier to get a grasp on via EXPLAIN and such.
Given a database and a query, yes, you can understand the execution profile.
What you can't do is start out with a schema and a query and understand the execution profile. Query planners take statistics into account when determining which indexes to use or to fall back to scanning, and can normally only examine a fraction of possible join orders. So you can usually only fully predict the performance profile of simple queries. Databases can run perfectly well one day and fall off a performance cliff the next, when statistics change; doesn't happen often, but it can happen.
More likely, something works perfectly well in test and in the early days, but rapidly becomes untenable as the data grows and superlinear slowdowns emerge.
Thus you need to put run-time monitoring into place, and have a routine process of examining slow-running queries, and fixing things that are slow: rewriting queries, adding indexes, possibly denormalizing data, materializing views, etc. It's an ongoing process in any application that works with lots of data.