Building a SQL Database from Scratch: B-Trees, ACID, and Storage Engines

[00:00:00]Welcome to #mkown, episode 1. That's how I'm going  to call this series and we are basically going to be reinventing the wheel for learning purposes.  I'm going to be writing programs that you take for granted that they exist like databases,  compilers, HTTP servers, network protocols, you name it. I'm going to be writing those  programs from scratch and walking you through the process of how you can go from knowing almost  nothing about these topics to basically writing a toy project. I've done this a couple times  before, I wrote a memory allocator once, I also wrote a reverse proxy HTTP server, so I kind  of learned how to approach this type of projects.

[00:00:39]Okay so back to the database thing. Here's  my current, limited understanding of how databases work internally. Let's take MySQL for  example. When you create a database using MySQL, what happens is that MySQL itself, the program,  creates a folder for that database which you can see here at this location. Now, when you create  a table inside of that database what happens is that MySQL or rather the storage engine that's  used internally creates a file inside of the database folder which you can see here. That's  the users file. This file contains two things: first the table data. If I insert rows into  this table, all this data is going to be stored in here. And then additionally this file also  stores an index for the primary key in this case, which you need because you have to be  able able to search by primary key fast, like you can't do that linearly one by one, row  by row. And I know that this index, internally, is built using some esoteric data structure called  B-Tree or B+Tree. They're not even the same thing, they're different, but it doesn't matter.  The thing is that this data structure can be somehow stored on disk and it speeds up primary  key lookup in this case or any other field if you index that field. This data structure can  also be modified through main memory or RAM, although it's persisted on disk. But I  don't know how any of that works. How do you implement a B-Tree? I have no idea.  How do you store that on disk? I don't know.

[00:02:10]Which means I need to do more research.  And so Phase 1 of this project begins.

[00:02:54]Okay so I've done some research, I  still haven't figured everything out yet but I think I know just enough to  get started. Let's try try to implement a database without using B-Trees  and see why they're necessary.

[00:03:07]So imagine we want to store some user data.  Let's say that for each user we need to know their unique ID, which is also going to be the  primary key, and we also need to know their full name. So we have a table with two columns and  then we can have as many rows as necessary, this is basically a spreadsheet. Okay now remember  that a database table is stored in a file, right? How can we store this spreadsheet-like data  in a file? Well, we could use the CSV format and insert what's called a delimiter between each  column and also between each row. But this is going to complicate things because I can't jump  from one row to another immediately, I'd have to find where the row delimiter is instead. And by  find I mean search for it linearly, byte by byte, until one of the bytes matches. Since this  would be extremely inefficient we're going to get rid of delimiters and make all the rows  the same size. The user name has variable length, so we need to force strings to have a maximum  number of characters, for example 255. If the user name can contain at most 255 characters, I'm going  to need 255 bytes to store the string itself, assuming ASCII encoding of course. And then I'm  also going to need one byte to store the length of the string. That's because one byte is made of  eight bits and with eight bits you can count up to 255. That's why everybody uses 255 as the  maximum character capacity for short strings such as names and emails by the way because if you  use 256 or more you're going to need two bytes per row instead of one to store the length of each  string. So with that in mind now we know the exact byte length of each row. The primary key  is an integer so that's going to be 4 bytes, then the user name is a string that needs  1 byte for the length and 255 bytes for the maximum character capacity, which means that  each row is going to be 260 bytes in total.

[00:04:51]So now let's say I receive a query asking for  the user with ID 50. If I'm searching linearly, I can read the first primary key in the file,  if the key doesn't match, skip 260 bytes, read the second primary key, if the key doesn't match,  skip 260 bytes again, read the next primary key and so on and so forth until I find the key that  matches. This is better than the CSV approach but the problem is that I'm still searching linearly,  O(n) right? If I have 50,000 rows this is going to be an issue because reading from the disk is  much slower than reading from memory and even more so if you have to do it thousands of times.  And that's why we need to index the primary key.

[00:05:33]An index is going to allow us to search in  logarithmic time, O(log n), which is much more efficient than O(n), especially as the  data grows. We said that we're not going to use B-Trees just yet so let's try to use a normal  binary tree for the index and see what happens.

[00:05:49]I'm going to skip the binary tree explanation,  let's just assume everybody knows how they work, this is basically data structures 101. So  let's suppose we have a file with the table data stored in the the format we've discussed  before and we want to find the row that holds primary key 8. Keep in mind that this row could  be located anywhere in the file because primary keys don't necessarily have to be integers that  increment by one as in this example. You can't just jump to row number 7, it's not that easy.  If we want to find that row faster than O(n), we could store a balanced binary tree  somewhere, in memory for example, where each node holds a primary key value and  also a pointer to the row where that primary key is located. Or in other words, the row number.  If we had that and we wanted to find primary key number 8 we could traverse the binary tree until  we find the key we're looking for and then once we have that we also know the row number, so  we can just jump straight to that row in the file because all the rows are the same size, so  we can just multiply. This binary tree approach has a couple problems. First of all, normal binary  trees are not balanced by default. If our primary key is actually an integer that increments by  one and we keep inserting keys into the tree in ascending order we'll end up with a linked  list instead of a tree. So we've solved nothing, our worst case search time complexity is still  O(n). The second problem of binary trees is that it's not easy to store them on disk. Think  about it, how would you even store a binary tree in a file? And you must do it of course because  you have to persist the index. And also keep in mind that if the index is big enough, if you have  hundreds of millions of rows or terabytes of data, the index itself could be gigabytes in size, so it  might not even fit into main memory. You might not even be able to load the entire tree into memory,  you'd have to load it one chunk at a time somehow.

[00:07:39]Okay, so this seems pretty complicated  but B-Trees solve both of these problems.

[00:07:47]Here's a B-Tree. You can see that its  structure is somewhat similar to normal binary trees in the sense that smaller keys  are kept to the left while larger keys are kept to the right. The difference is that  each node can have more than two children and each node can hold multiple keys. How many  of them? Well, to answer that we need to define the minimum number of children per node. Let's  call that number C and let's make it equal to 2.

[00:08:10]Once we have that number we can compute the rest  of properties using some simple formulas. These properties apply mostly to internal nodes because  the root node and leaf nodes are exceptions.

[00:08:21]But the reason you need to keep track of these  properties is because B-Trees are self-balancing, they always stay balanced no matter how you insert  the keys. The self balancing algorithm is pretty complicated so I'll try to summarize it as simply  as I can. Before we start, from all the properties that you see here, the one you need to remember  for now is the maximum number of keys, which is 3 in this case. All right, so let's try to insert  10 keys in ascending order into the B-Tree and see what happens. First of all we create the root  node of the tree and we start inserting keys into that node in ascending order as if it was a  sorted array, and we do that until we reach the maximum number of keys. Once that happens, further  insertions will cause the tree to self balance, here's how it works: key number 4 cannot be  inserted into the root node because the root node has already reached the maximum number of  keys. So we take the median key, which is 2 in this case, because you know, 1-2-3, two is in the  middle. So take the median key and move it into the parent node. Since there is no parent node  because we're already at the root of the tree, we're going to have to create a new node. That  node will become the new root of the tree and then we're going to split the old root into two  different nodes, the first one containing the keys before the median and the second one containing  the keys after the median. Finally insert key number 4 into the rightmost node in ascending  order. That's the general description of the self-balancing and insertion algorithm. I'm going  to let the animation play until we insert all of the remaining keys, but basically there's only a  couple things you need to do. First find the node where the new key should be inserted. If that  node has already reached the maximum number of keys then move the median into the parent. And  after that split the node into two different nodes. This algorithm is recursive so  it becomes more and more complicated as the tree height grows because at some point  you're going to have to split multiple nodes, you're going to have to move multiple keys upwards  and also the root is a special case because it doesn't have a parent. So you have to create a new  root and all of that, but that's how you ensure that the B-Tree stays balanced. And as such,  searching is always O(log n). It never becomes a linked list where searching is O(n). That solves  the balancing problem. Now, how do we store this B-Tree in a file? Before I explain that, one  last thing you need to know about storage is that when you read from the disk you can't read 1  byte at a time or 2 bytes at a time or 5 bytes at a time. You have to read in "blocks". Blocks  of size 512 bytes or 4,096 bytes, it depends on the physical disk itself, on the drivers,  on the operating system and a bunch of lower level layers in between. But that's not important,  what's important is that we can take advantage of this to minimize disk reading operations. The way  we're going to store the B-Tree is we're going to figure out how many keys and children pointers  we can fit into one block. For example let's say that we can fit 100 keys. Okay then each B-Tree  node is going to have 100 as the maximum number of keys and then we're going to store each B-Tree  node into one single block. If the block size is 4 Kibibytes (KiB), not Kilobytes, I'm talking  about 4,096 bytes, if that's the block size you can imagine a file where the first 4 KiB store  the root node. The next 4 KiB store a child of the root node. The next 4 KiB store another  child of the root node. The next 4 KiB store a child of one of the internal nodes and so on  and so forth. So we can read this tree one node at a time with one disk operation at a time, it  could be Gigabytes in size and it doesn't matter.

[00:11:55]Also how does a node point to its children? Well  children pointers are basically block numbers. We start counting blocks at 0 and then we can point  to any of them and jump to any of them in the file by multiplying. I'm not sure how all of this node  splitting business is going to work in a file, and I'm also skipping a lot of details but keep  in mind I'm explaining all this stuff as I'm learning myself so a lot of things may be wrong  here take everything I say with a grain of salt.

[00:12:23]Last thing before I start writing code.  What exactly am I going to write? Well, we're going to have a storage engine that's going  to take take care of all the B-Trees and blocks and all of that business. Then we're going to have  an SQL parser or "Sequel" or "Squeal" however you want to call it, and this component is basically  going to take in statements like CREATE TABLE, SELECT and turn them into some sort of  data structure that the storage engine can understand. Finally we're going to expose  this service through TCP. I'm not sure if I'm going to use async or a thread pool, I don't  know that yet. We'll also need to deal with concurrency and multiple connections updating  the same rows and all of that, I guess that's just a mutex but we'll see. Optionally we could  also Implement a caching mechanism to keep B-Tree nodes in main memory to speed up searching,  but I'm not sure if I'm going to do that in this video because caching is hard and I have to  deal with enough hard stuff anyway. Implementing all of this is going to take a lot of time so I'll  get back to you when I'm done, Phase 2 starts now.

[00:14:15]So after 7 months, 251 commits and 25,000  lines I finally have something basic that I can show you in practice. So I'm going  to do a quick demo and then I'll explain how the internals of the database work.  First things first, I can create tables, of course. Then I can also create unique  indexes, either manually or automatically, and in order to keep track of all these relations  there's a special table called "mkdb_meta". So when I had to implement this I was like hold on  a second, how can I create tables if I already need to be able to create tables in order to  create tables? That's how you know you're in deep computer science territory when everything  becomes so recursive that you're starting to question your own existence. Now these indexes  of course are not there for no reason at all, the program actually makes use of them. So if I  send a query like this one that searches by email, you're going to see that the program makes  use of the email index to get all the rows.

[00:15:14]And it's also going to decompose this expression  into multiple parts depending on where they need to be evaluated. So this is a query plan, I'll  explain later how that works. Now, moving on, I can also do all the CRUD operations. So  I can insert data, I can also select data, I can update data, so there's the update. And  finally I can delete rows, so after this there should be only one row left. That's everything in  terms of CRUD, but I can also do sorting, which you might think it's easy but it's actually not at  all. Mainly because the results of the query might not fit in RAM, and that's one of the constant  problems that you face when developing a database, it's that you can never assume that something fits  in RAM because a 100 million rows will not fit in there. So you got to sort on disk. And also the  reason I'm showing you all these weird expressions is because SQL has to actually be able to execute  any random expression that you throw at it, which is something that I didn't even think about  until I actually had to build the parser and the virtual machine that runs all this. And I find  that interesting because one of the projects I had in mind was writing my own compiler or  interpreter but with this I'm already half way through. Moreover, we have all the transaction  business. So I can start a transaction, I can apply some changes to this table and  now I can decide whether I want to commit, which means that all these changes will be written  to disk, or rollback which is going to reverse all these changes even if they were written to disk.  Because you don't actually know when that happens, it's kind of hard to know due to how the system  works internally with caching and stuff. Rollback is extremely important for databases because this  is also related to crash recovery. So for example what happens if the client is in the middle of  a transaction, the client applies some changes to some table and before the client gets to commit  or rollback the database server crashes? The power goes out or something like that happens, the  server is down. So what should happen to these changes? Because the client didn't commit, didn't  do anything and the database is down. Well when the database server gets back up it must revert  all the changes and go back to the state it was in before the transaction started. So if the client  reconnects again and attempts to read the data, the data is in the exact same state it was  before the transaction. Finally there's the whole multi-threading part which I didn't put  much effort into because I said, you know what?

[00:17:44]I'm not spending another seven months on this  project, so I just threw everything behind the mutex and called it a day. So basically we can  have multiple connections at the same time and they all work simultaneously, but there can only  be one transaction at the same time. So if this one here starts a transaction, the other one will  have to block on the mutex until this transaction ends. So let's insert some data here and let's  commit, and once this this transaction ends the other one can go through, but there can only  be one at a time. And in case you didn't know, if you don't start a transaction manually,  each statement by itself is a transaction.

[00:18:25]So that's my database. In terms of  functionality it's extremely basic. You can only work with one table at a time, there  are no foreign keys, no joins, no group by, no subqueries. So it's pretty simple, but in  terms of how it works it's not simple at all, which is interesting because in the beginning I  wanted to do something trivial. I wanted to force all the rows to have the same size, but I didn't  because even for a toy database that would waste a lot of space especially with strings. And so  just to be clear, a serious production database will not allocate 255 bytes for every single  string because that would waste a lot of space, it will only allocate what's necessary to  allocate for each string. So what's the problem with that? The problem is that now you  don't know what size each row is going to be, now you're dealing with variable length data.  And this introduces so much complexity that I had to spend half a year coding the  solution for this. Now of course my database is by no means a production database  but it does work with variable length data.

[00:19:26]Let's start with the basics. How are we going to  store our database on the file system? Because there are multiple approaches. The most logical  approach, I guess, is what Postgres does. They basically store every table and index in a  separate file and then they have one directory for each database, so they keep everything  organized that way. On the opposite side of the spectrum we find SQLite which stores all the  information about a database in a single file, so all the tables and all the indexes in one  single file. But in terms of I/O performance it doesn't really matter how you structure your  database, doesn't matter whether you have a giant single file or 10 smaller files, you still  have to spin the disk in order to read them. So you won't actually see much of a difference  in that regard. If you want to improve I/O performance you have to do sequential I/O, so  reading or writing one block after the other instead of random I/O. Random I/O is bad even  with SSDs that don't actually have to spin, so you still need to favor sequential  I/O. That being said, my database, MKDB, works just like SQLite, it uses a single file  to store all the tables and all the indexes.

[00:20:33]We've talked earlier about how you have to  read in blocks when reading from the disk, but we don't want to be limited to the block size,  so we're going to introduce our own storage unit called a "page". So a page is made of one or many  blocks and we are the ones who define its size, so we can have 8 KiB pages, we can have 16 KiB  pages, 64 KiB pages or any other power of two in that range. Now in my case I usually set  the page size to 4 KiB, so the database file is a sequence of 4 KiB pages one after the  other. There are multiple types of pages but let's focus for now on B-Tree pages, since  those are the most important. From now on, B-Tree page and B-Tree node are synonyms that  we can use interchangeably. And B-Tree pages point to their children using page  numbers instead of block  numbers, it's the same concept but with pages. So each  B-Tree page is something called a "slotted  page".

[00:21:26]Slotted pages allow you to store and organize  variable length data more efficiently. Because if I simply stored variable records in the  page one after the other as if it was an array, first of all I can't easily do a binary search  on them because there are no fixed indexes, I don't know where to jump. And I need the binary  search in order to maintain the O(log n). The second problem is that sorting is expensive, so  imagine I'm storing variable records with keys 10, 20, 40 and 50 in this page, and now all of a  sudden I need to insert the record with key 30.

[00:21:58]Well, I'd have to move a bunch of bytes towards  the end of the page to make space for the new record and maintain ascending order. Doing that  over and over again is pretty much unacceptable, especially when the page size is big. So  slotted pages what they do is they say; you want to insert a variable length record here?  We'll put it at the end of the page and at the beginning we're going to store a pointer or offset  to the record. Want to insert a new record? Again, put it at the end of the page and at the beginning  we store a pointer. And we keep doing this over and over again. So the pointers at the beginning  are called a slot array and this array grows towards the right. The variable records at the  end are called "cells", although you can call them however you want, and they grow towards  the left. So when the cells meet with the slot array the page is considered full. The slot array  offers many performance advantages. First of all, if I want to do a binary search I'm going to do  it on the slot array because now I have fixed indexes so I know where to jump. Then if I want to  insert a new cell maintaining a ascending order, I don't have to move the rest of cells, I  can just insert the cell normally and then shift the slot array, which is way cheaper than  shifting the variable length cells because each pointer in the slot array is only 2 bytes. The  maximum page size is 64 KiB, so you don't need more than 2 bytes to store each offset. Now we  said that this is a B-Tree page, so where are we going to store children pointers? Well, each  cell will have a header where we're going to store a page pointer or a page number. And these page  numbers must also be ordered, so for example if I follow the pointer in the cell that stores key  50 I know for a fact that all the cells in the new page will contain keys that are less than  50 and greater than 40, which is the previous key in the current page. And that's what allows  me to traverse the B-Tree in an ordered manner.

[00:23:47]So how do we store rows? In terms of how the row  looks like it's basically the same format I showed you in the beginning where columns are stored  one after the other in binary format, the only difference is that now strings are not wasting any  space. So if a string only needs 5 bytes I'm only using 5 bytes. And I'm also using UTF-8 instead of  ASCII, so we got to be smarter about how we store the length, but not important. The more important  question is where are we going to store rows? How are we going to store the tables? Right? And we  also have to point to rows from external B-Tree indexes, so how do we do this? Well, there  are two main formats. Again, going back to Postgres and keeping it extremely simple, they  have a table file that stores rows in slotted pages. This is not a B-Tree, it's just pages one  after the other sequentially. And so each cell is a row and each row has a location defined by its  page number and its slot index in the slot array, that's why they use slotted pages. And so now if  you want to point to a row from an external B-Tree index, from the primary key index for example,  which would be a separate file for Postgres, you just have to store the primary key and the  row location. And once you find the key you also know where the row is. The problem with this  approach is that now in order to keep track of all the pages in the table file you need something  called a "page directory", which is another file where each page stores metadata about pages in  the table file, because you need to know exactly where to find free pages or free space and you  can't do that linearly, of course, because that's inefficient. So you basically need 3 different  disk data structures: you need the B-Tree for indexes, you need the page directory and you need  the table file. But then there's another approach called "index-organized storage". This is what  SQLite does. In this approach we store tables as B-Trees sorted by the primary key, and so each  cell in the B-Tree is a row. So when I found out about this, I was like you're telling me that  all the code that I wrote for indexes I can reuse it to store tables and I don't need to change  anything and I don't need more data structures?

[00:25:47]Then I'm definitely doing this, so I copied SQLite  here. Now this approach has a drawback which is that we can't use the row location to point to  rows from external B-Tree indexes because the row location will change frequently due to the B-Tree  balancing algorithm which needs to keep everything sorted by primary key. So we need to use the  primary key to point to rows from external indexes, from a unique email index for example.  This index would store the email and the primary key associated to that email, so we would find the  email in O(log n) time and then we would find the row in another O(log n) time, whereas the previous  approach skips the second O(log n) because once it finds the email it already has the row location.  However, we have the added benefit that the primary key is not an external index for us, so  queries searching by primary key will not have to read a B-Tree index first and then the table  B-Tree, they straight up read the table B-Tree, it's like an automatic index on the primary key.  That's why it's called index-organized storage.

[00:26:53]There's only one piece missing. We said that pages  are fixed size, 4 KiB in this case, so what are we going to do with rows that require more space  than that? Well, we're going to use something called "overflow pages". Basically, when the size  of a single row goes past a predefined threshold, like for example 1/4 of the page size, then we're  going to split the payload into multiple chunks.

[00:27:15]The first chunk will be stored in a cell of the  B-Tree page, the last 4 bytes of this cell will point to an overflow page that's going to store  the next chunk. This overflow page will have a header that's going to point to the next overflow  page, which is going to store the next chunk. And so now we have a linked list of overflow pages.  Whenever we need to read the contents of this row we have to sort of reassemble the entire  thing into a continuous sequence of bytes.

[00:27:45]Putting it all together, the database file is  a collection of table B-Trees, index B-Trees and overflow pages. So you might think that this  is a mess because everything's in the same file, but it's not because the file is just a sequence  of 4 KiB pages one after the other and we know where every single B-Tree is because each B-Tree  has its own root page and we have pointers to all the overflow pages, so everything's nice and tidy.  Initially, this was my goal with this project, I wanted to understand how a database is  structured. How do the individual bits and bytes look like in this mysterious database file? But  once you have all these complicated disk storage data structures laid out, you got to implement  some sophisticated algorithms to work with them.

[00:28:32]So B-Trees yet again. The problem we have with  B-Trees now is that we're storing variable length cells in them, so all the formulas I showed  you in the beginning... they don't work anymore because how many keys will each B-Tree page have?  Nobody knows, as many as you can fit basically, there's no upper bound which of course makes  things complicated. And there's another problem, the default balancing algorithm keeps pages  only half full when inserting sequentially, because each time a node splits the  node at the left remains only half full, because you take the median so you split in half  but then you insert into the right node. And so by the end you will have a bunch of pages  that are only half full, wasting space. So the balancing algorithm is actually one of the  most complicated parts of the entire code base.

[00:29:13]I probably spent two months just on this, because  now this algorithm is a giant recursive function that I copied from SQLite. Object-oriented gurus  are going to hate me for this one, but hey this is low-level systems programming, we don't do Java  here. Explaining in detail how this works would take forever but it's based on this simple idea:  if we take a closer look at how insertion works, you realize, hold on a second, do I actually  need to split a node every time it's full? No I don't because I can just sort of reorganize  the keys around and delay node splitting while populating sibling nodes. I can do that until  there is no more space left and then I split, and repeat again. This algorithm does  exactly that but with variable length data.

[00:29:55]So now that we have a working storage engine, the  user will send us SQL right? Which is basically a string. So how do we go from a string to running  B-Tree algorithms on disk? Well, first of all we got to parse the string. I'm not going to talk  much about parsing in this video even though I wrote a lot of code just for parsing alone, but  I don't think it's that relevant to databases, so topic for another video. Here I am basically going  to speedrun parsing. Step 1, you need something called a tokenizer which takes characters as  inputs and outputs token types. Step 2, now you got to feed these tokens to the actual parser  which is going to produce something called an Abstract Syntax Tree (AST). This tree represents  the entire SQL statement in this case. As I said I'm going to keep things simple but if you're  interested in parsing I used something called Top Down Operator Precedence (TDOP) parsing, which  is an algorithm that came out in the 1970s and it makes it pretty easy to write parsers. Because  the biggest problem is knowing when to execute an operation inside of a larger expression and  that depends on the operator. And so this type of parsing consists of a couple of mutually  recursive functions that keep calling each other until they end up building an expression  tree, and with that the AST is complete. Then there's something called the analyzer which  basically does context dependent analysis, so things like this table doesn't exist, this data  type is wrong for this column, all that stuff is handled here. And then on top of that there's  the optimizer, which basically simplifies the SQL statement to avoid computing unnecessary  operations over and over again, because this is not machine code running on the CPU, it runs  on the interpreter so it's pretty expensive. So parsing... it looks complicated because of all  this mutual recursion and stuff but honestly I have never written a serious parser like this one  before and still this was the easiest part of the entire code base to write. Mainly because it's not  low level, you're not dealing with bits and bytes, you keep everything high level and if the language  you're using supports pattern matching this is a joy to write, you don't even have to think  about it you just write it, it writes itself.

[00:31:56]So now that we have a complete AST, just like  a compiler would turn its AST into machine code that the CPU can run we have to turn our AST  into something that our storage engine virtual machine can run. So that's the query plan,  which you saw earlier in the demo. The query plan is yet another tree... man computer science  pretty much boils down to pointers and trees, but anyway the query plan tree represents all the  steps needed to compute the results of a query. So a basic example would be: select a couple columns  from a table where some condition. The first step is scanning the table, so how are you going to  scan? Are you going to use an index? Multiple indexes? Or you just do it sequentially? Then  once you know how to scan you have to filter the output based on the where condition, and  finally do something called a "projection", which is the fancy relational algebra term for  picking columns from a row. In relational algebra rows are called tuples, so I'll also use that term  because that's what I'm using throughout the code.

[00:32:55]What's interesting about plans is that I'm using  something called the the "iterator model", which essentially what it does is it processes tuples  one by one. So every node in the query plan tree is an iterator itself, an iterator over tuples.  So when the top level plan is asked to return a tuple, we basically call.next() on the plan,  that node in turn calls.next() on its child, which in turn calls.next() on its child. At  some point we're going to get to the bottom of the tree where we're going to find the scan  plan or the scanner. The scanner has a cursor that goes over all the rows and returns tuples  one by one without using any memory because the only state that it needs is the cursor. And  that's what's interesting about this pattern, we can process a giant table one row at a time  without worrying about RAM. Now query plans are not the only way of doing this, Postgres does  this, but SQLite for example generates some sort of byte code and then they run that. It's the same  thing but I thought plan trees would be easier, so I copied Postgres here. So thanks to Postgres and  SQLite because they carried me through the entire database development journey. I would not have  been able to write all this code without Postgres and SQLite, and yes I know the correct  pronunciation is "S-Q-L-lite"... (So what is S-Q-L-lite?) But it's kind of annoying  to say "S-Q-L" all the time at this point.

[00:34:12]I also used the lectures from "CMU Intro to  Database Systems". They're very well done and they're available on YouTube for free, so that's  pretty much all I needed to write my own database.

[00:34:25]Moving on, what happens with algorithms that need  to work with the entire entire dataset? Like for example sorting. Well, there's a special kind  of plan which is the collect plan that basically has a fixed size in-memory buffer where it stores  tuples coming from the source and once the buffer is full it writes it to a temporary file. So it  collects all the tuples into a temporary file.

[00:34:44]Now if the rows can actually fit in the memory  buffer then everything is drastically easier, you want to sort them? You can just call .sort() on the array and you're done. But when stuff doesn't fit in memory that's when  you got to work with files on disk instead.

[00:34:57]So how do we sort a giant file of unsorted  tuples? There's an algorithm called "K-Way External Merge Sort" I'll make an entire video on  that algorithm alone because it's very complex, but in a nutshell this algorithm divides the  file into fixed size pages and it does a number of passes through the file until it's fully  sorted. The algorithm has K input buffers for reading pages and one output buffer for writing  pages. Let's say K = 2. In that case pass zero would do something called "2-page runs". Each  run produces a sequence of 2 pages that are fully sorted from start to end. Then pass one is able to  do 4-page runs, pass two: 8-page runs, pass three: 16-page runs, and so on. It keeps multiplying by  K so it scales logarithmically, which is pretty awesome because if you have five buffers instead  of two, pass zero does 5-page runs, pass one does 25-page runs. Essentially, you're reducing the  number of passes through the to the file, so less I/O at the expense of using more RAM. And it does  all this loading only K pages at a time in memory, it's not going to load 25 pages because it only  has five buffers, and that's the complicated part.

[00:36:09]When I implemented this algorithm, even though I  know exactly how dumb I am, I felt like a genius because I was like, damn, this algorithm all  of a sudden can sort terabytes of data and it won't even flinch. This is another one of those  giant functions that will make OOP gurus mad, and this time I implemented it iteratively instead  of recursively, so it has like three nested loops.

[00:36:27]It's like "while, while, while, for, for", I don't  know it's awesome. And what you have to understand is that every single algorithm that works with  large data sets like aggregation algorithms, join algorithms, they all need to take into account  the fact that the underlying data might not fit in RAM. And so they all have to be able to operate  on disk which as you can see is anything but easy.

[00:36:52]Even though I'm talking about caching now it's  actually one of the first things I implemented after the B-Tree. Caching is another one  of those famous computer science problems right? But luckily there's a simple solution.  The simplest replacement algorithm I found is the "clock algorithm". So the cache is basically  a circular array where we load pages from disk.

[00:37:11]Every page has a reference bit so that when  somebody wants to read a page from the cache we set its reference bit to 1. Every page also  has a dirty bit so when somebody wants to modify a page we set both its reference and its dirty  bit to 1. And that's how we know which pages we need to write back to disk. And then there's the  clock replacement algorithm, when somebody wants to read a page that is not cached we have to  evict one of the cached pages. So the clock is yet another pointer whose mission is to find  a page that is not currently referenced. If the page that it currently points to is referenced,  then it resets its ref bit back to 0 and it moves to the next page. If that page is referenced it  resets its ref bit to 0 and it moves to the next page. Once we find a page that is not referenced  we can replace it with one of the disk pages, considering that if the cached page was dirty we  would have to write it to disk first. So yeah, caching, overall, not that hard but I did find  some interesting bugs due to not writing exactly when needed and stuff like that, because you  also want to be smart with this, you want to group writes of multiple pages together to  do them sequentially and reduce I/O overhead.

[00:38:21]So how do we Implement commit and rollback? The  simplest solution I found is what SQLite used to do which is something called the "journal file".  So the database is basically a bunch of pages, a transaction loads some pages into the cache  and modifies them, so now you have a set of dirty pages. Essentially what you do is before modifying  the pages you write their original contents to a journal file. And then you can modify and safely  write the disk. And so if you need to rollback you just need to copy the original pages from the  journal file back to the database file, and you're done, no more complications needed. If you want  to commit instead, you just have to delete the journal file, it's that simple. This solution is  good enough for a toy database that processes only one transaction at a time, but production ready  systems they use something called the "Write Ahead Log (WAL)", which essentially keeps track of all  the changes applied by each individual transaction and also opens the door for multiple writers at  the same time. You can start two transactions in MySQL or Postgres and you'll verify that each  transaction can see its own changes but it can't see the changes of the other transaction until it  commits. Of course this is much more intricate.

[00:39:29]As I said in the beginning this program would  be a TCP server that accepts connections, and so I had to write my own little network  protocol inspired by the Redis protocol, which I like because it's very simple, it doesn't  need fancy stuff, so I made something similar. Now I'm not going to explain the entire format of each  packet, it's all detailed in the documentation, but what's nice about this is that you don't  have to use the console client that I wrote, you can write your own client and you can write  it in any language of your choice, that's what's nice about protocols. So hopefully you've learned  a thing or two about databases today because it's one of the most important pieces of software  in this day and age. If you're a web developer, especially a backend developer, you're using  databases every single day and yet most likely you don't actually know much about how they work  internally. And that's what I find interesting about systems programming, when I was a noob  programmer at some point I realized, hey, all the software that I'm using from the operating  system to the shell that interprets my commands to the pixels on screen, somebody had to write  those. How did they do that? Because all I know is writing hello world in Python... And especially  with databases, you know, for some reason all this time I thought that compiler programmers were like  the "gangsters", but man everybody gangsta till you gotta deal with low-level disk data structures  that don't fit in RAM. So all my respect goes to those who have written Postgres, MySQL, SQLite  or any other serious database that we use daily because it's extremely complicated. So if you're  interested in databases or systems programming because I'm pretty sure I must not be the only one  in the entire world who's crazy enough to want to understand how this works, all the source code  is available on GitHub. This project is meant to be a learning resource, so it's written in such a  way that it's meant for reading and understanding how it works. Even though there are 25,000 lines  here, half of that is probably just documentation, because I wrote like entire dissertations on how  every single algorithm works, there are a lot of ASCII diagrams that make it easy to visualize  what the algorithm is doing in each step, there are also over 270 different tests which you can  use to say okay this is supposed to do that, this is supposed to do that, so you can sort of figure  it out. Now I'm not saying that this code base has any quality whatsoever, all the code in here is  pretty much garbage. The performance is horrible, it's very unstable so if you try it out expect it  to crash. What I'm saying is that it's easier to read and understand than some giant codebase like  Postgres. If you enjoyed this kind of computer science content then leave a like, subscribe,  share the video and do the YouTube algorithm stuff because I have countless ideas for projects like  this and I'm not going to be able to work on them unless you actually watch the videos. So do the  YouTube stuff and I'll see you on the next one.