[MUSIC PLAYING]
CARTER ZENKE: Well hello, one and all, and welcome
back to CS50 Introduction to Databases with SQL.
My name is Carter Zenke, and today we'll focus
on optimizing-- trying to reduce the time our queries take
as well as reducing the storage space our database might use.
We'll also see how to handle concurrency.
That is, many queries all at once.
Now we'll do all of this in the context of a new database,
this one-- the Internet Movies Database, or IMDb for short.
If you've been to imdb.com you may have seen this whole big database of movies,
and we've compiled that into our very own SQLite database for us today.
Now this database is big.
It is much bigger than anything we've seen so far.
In fact, it has over 200,000 movie ratings, over 400,000 movies,
and 1.4 million stars or people who have acted in some movie.
And the goal of this database is to represent movies, the people in them,
and the average ratings for each of those movies.
Now we have ourselves an entity relationship diagram
to describe this database, and it looks a bit like this.
We have people in one table, movies in another,
and ratings in a separate table down here.
Notice that people have a name and a birthday
along with an ID, the primary key for that table.
Movies too have a title and the year they were released
as well as their own primary key ID here.
Rating down here has the average rating for a given movie
as well as the number of votes that went into calculating
that average rating here.
And notice too that the movie and people table has a many-to-many relationship.
That is, a person can star in more than one movie
in the same way a movie can have multiple stars.
So if we want to implement this many-to-many relationship,
we've seen one way to do that.
Let me actually ask the audience here, how
have we implemented a many-to-many relationship historically?
What kind of tables do we need for this, do you think?
All right.
So not to worry if you don't have an idea of what we're going to use here.
Let's take a peek at what tables we can actually use.
So here as we've seen historically we might have two tables, one for people
and one for movies.
And notice here in the people table we have names
along with a primary key called ID.
And similarly in our movies table, we also have a title
column along with a movies own primary key, an ID column over there.
Now to implement the relationship between people and movies,
we have to have some table in the middle of these two.
One that relates people IDs or person IDs with movie IDs.
And if we look at this table, I could see
that if I see person ID next to some given movie ID, well
it means that the person with this ID has starred in,
played a role in, this movie here.
We see person 158--
let's see, Tom Hanks-- was in the movie ID with 114709, or Toy Story
as we see in the movies table.
And now knowing this, how can we figure out which
movies Kristen Bell has starred in?
If we know of Kristen Bell's ID, what should we
then do to find the movies Kristen Bell has starred in?
AUDIENCE: You could select the ID of the people then look into the stars
table, then look at [INAUDIBLE] the movies table.
CARTER ZENKE: Yeah, I like your thinking.
So there's multiple steps here.
We have to go through each table to find ultimately the movie that Kristen
Bell has starred in.
The first step might be to ask, what is Kristen Bell's ID?
Well it seems to be 68338.
Then, to your point, we could look at the stars table
and find out what movie IDs correspond to that ID here.
So it seems like 2294629 corresponds with Kristen Bell's ID here.
Then finally we look up in the movies table, well,
what title corresponds with 2294629?
It seems to be the movie Frozen.
So visually, we have this relationship among these tables here.
So let's now dive into our movies database
to actually get a sense of what data is inside of this.
And for that I'll go back to my computer so we can open this database up
in SQLite.
I'll come back over here and I'll open up my own environment
where I can type sqlite3 movies.db.
movies.db.
And now if I zoom in just a bit, I can then type .schema to show you all
the tables that exist in this database.
I see up top I do have a movies table that has a primary key called ID,
a column called title and a column called year.
I have that same people table with names and birthdays,
and I also have this stars table that corresponds with person IDs and movie
IDs, relating in this case people and movies.
OK, so let's try selecting then from our movies table
to see what movies we have, take a peek at our data.
Well, we saw a little bit ago, we could try
to take a peek at our data using a certain SQL keyword.
I could SELECT * from "movies" to see all columns from movies,
but if I have let's say 400,000 rows I don't
want to print all those to the screen.
So what could I use instead?
A certain SQL keyword.
I'm hearing LIMIT, so let's try that.
I'll say LIMIT 5.
I only want the first five results here.
I'll hit Enter, and here I'll see those first five movies in my movies table.
They each have their own unique ID, a primary key.
They have a title and the year that they were published.
But if you've been to imdb.com, you may have wanted
to search for a particular movie.
Maybe you wanted to find your favorite movie among all the possible movies
in their database.
And we can simulate that kind of query by querying the database here.
Whenever you type in IMDd's browser-- that's like the search for a movie
called Frozen, for example--
odds are that behind the scenes a database is actually
running that same query to return to you what
movies have that title called Frozen.
Now for me my favorite movie since I was a kid
is one called Cars, so let me try to search for Cars here.
I'll try to find SELECT * from "movies" where the "title" = 'Cars'.
And you could imagine me going to IMDb, typing in Cars in the search bar,
and behind the scenes this SQL query gets
run to find what movies have the title Cars.
So let me hit Enter here, and now I'll see that one movie has that title Cars.
Came out in 2006 and the ID is 317219.
But this is a lecture on optimizing, so it's worth
asking how much time did it take for this query to run?
Let's find out.
Well I can use a SQLite command here called timer.
I'll say .timer on to make sure that I time my future queries.
I'll hit Enter now.
And now if I try selecting again, I'll hit the up arrow twice
to get back my old query.
I can type Enter and I'll see not just the results
but the time it took to run that query.
Now notice, we have several different measures of time here.
I have the quote, unquote "real time" which is essentially
the stopwatch time, meaning from the time I press Enter to the time I saw
these results, how long did that take?
But of course you're familiar with computers.
You know there's more involved than just this query running.
I also have to wait for the operating system
to finish other processes as well.
That's where user and system time come in.
User time is how much time this query particularly took on the CPU.
System time is how long I spent waiting around for other processes
to finish before I could run this query.
For us, we'll focus on real time.
What was the wall clock time, the stopwatch time, so to speak,
between the time I pressed Enter and the time I saw these results.
OK.
So here we have a query taking 0.084 seconds.
I mean, that is pretty good.
If I only wait around for less than a tenth of a second, I'm not complaining.
But if I'm an engineer at IMDb, why might I
be concerned about a query that takes 0.084 seconds, particularly
if I have lots and lots of users?
What's the problem there?
AUDIENCE: For users, the database might be overwhelmed by the queries.
And you should also consider how much time the application takes
to form the query to the database too.
CARTER ZENKE: Yeah.
So the basic idea here is that when I have
a single query that takes maybe less than tenth of a second, that's fine.
But if I have many, many users running those queries all at once,
that time is going to add up.
And so if I'm an engineer or even somebody in finance,
I want to reduce that time because I'm paying per second that I
run this database on some other server.
So we can optimize these queries, but let's first
get a sense of how they're presently running.
What is SQLite doing underneath the hood to find this movie called Cars?
Well for that, I'll bring up a certain visual here of our titles column.
So imagine here that we have a smaller database called Movies
that just has titles in this case.
And now I want to search these titles, but I'm a computer.
I'm not a human.
Meaning I can only look at one item at a time.
I can only look at one row and check its title.
Now if I want to find the row or the rows that have Cars in them,
what's the best I could do if my titles are not sorted?
What's the best approach I could take here?
If I can only look at one row at a time, how might I search this column?
AUDIENCE: You should use a linear search then, right?
CARTER ZENKE: So I like your intuition.
There is an algorithm, a step-by-step process
called linear search where we look at one element
at a time or, in this case one row at a time.
That's exactly what we can do for this table.
I can look at one row at a time to find is this title in this column
or is it not?
So here to visualize, I could take this title column.
I can only look at one at a time.
But if this data is not sorted, I can do no better than looking at every row
exactly once.
So here we start with Toy Story.
We ask, is Toy Story equal to Cars?
It's not, so we'll keep going.
Here I'll check Cars 3.
Is Cars 3 strictly equal to Cars?
It has Cars in it, but it's not Cars exactly.
So I'll keep going.
I'll look at Frozen.
And Frozen is not Cars either, so I'll keep going again and here I see Cars.
So maybe I could stop here.
But why couldn't I?
Well if I need to find not just the one row that has Cars but all the rows
that have Cars, I have to keep going to see is Cars elsewhere in this column?
Is it not just here, but also in other rows too?
So I'll keep going.
I'll look at WALL-E, Ratatouille, Soul, Turning Red
until I get to the end of this column.
And this process is called a scan of the table.
We're scanning our column top to bottom looking for the result
that we need to find.
But it turns out we can actually optimize this search.
We can do a bit better than going one by one by one by one,
and for this we need a bit of a metaphor to think
about how we can search our table.
So if you have ever seen a kind of textbook,
you might have seen something a bit like this here.
This is a Handbook of Education Research.
And maybe I want to find which pages correspond
to how students learn computer science.
So one thing I could do is open to the start of the book.
I could go page by page looking for which pages have "how students
learn computer science."
I keep going here, and if I want to find all the pages that have
"how students learn computer science" on them,
I can do no better than going through every one
by one by one until I'm at the end of this textbook.
But chances are you yourself don't do this.
You do something better.
And there's some built-in structure in this book that could
help you find what you're looking for.
What might you use to find something in a textbook or some other book too?
AUDIENCE: We can use the index of the book.
CARTER ZENKE: You can use the index.
So often a book like a textbook has something
at the very back of the book that tells me
all the subjects that are inside this book, but in alphabetical order.
So I can see here there is a subject index in the back of the book
here that lists the subjects in alphabetical order, A to Z.
And if I want to find "how students learn computer science,"
I could perhaps search for computer science in this index.
I could find A, B, C. There's C, and here I see computer science.
Now I know all the pages I need to look at inside this book
without going through each of them one by one by one.
So in the same way that books have an index, so too
can databases and tables have an index as well.
So let's see a definition here for what an index is.
Well an index is a structure that we can use.
It's built into our database to help us speed up
the retrieval of rows from that table.
I first search my index, find out what rows my given search term is in,
and then look those rows up in my table.
Now if I want to create an index on a table, I can use some SQL syntax.
I can say "create index" and give it some name.
But I need to also specify a few other things.
Similar to my books index, that index has some content.
It's an index by subject or an index by author.
So I need to tell this index what to include.
So I should also say create index, give it a name on some table
and some columns in that table, telling my index what data for my table
it should include.
So let's create our very own index in the movies table
to identify how we can make this query just a bit faster overall.
So I'll come back to my computer here, and let's now try to create this index.
I will open up a new tab here.
A new tab.
And then I'll log back into my database.
I'll say sqlite3 movies.db.
And now I want to first create some index here.
So I'll turn my timer back on and now I'll type the syntax we just learned.
I want to create an index.
And if I'm searching my title column in Movies,
I should probably include the Title column in this index.
So I'll say call this the "title_index" here.
It'll be on the Movies table and it'll contain the data in the Title
column of Movies a bit like this.
Now I'll hit Enter and I'll see this index took some time to be created.
There's some stuff going on underneath the hood
where I'm putting this data in a new structure we're calling the index here.
But now if I rerun this query, if I say SELECT * FROM "movies,"
SELECT * from "movies" where the "title" = 'Cars' semicolon,
it was a lot faster.
Here I see 0.01 seconds real time compared to 0.084 seconds.
That's a savings of almost eight times.
Almost eight times faster now that we have this index.
Now it took some time to create the index.
If I run just a few queries, I much easily
make that time up in terms of the time I'm
using on my server to look up these kinds of pieces of information.
OK, so let's actually take a look at how we can ensure a query
is using some index.
Here I'm just kind of taking it on my word.
Here it was faster, so it used the index.
But there is a way for you to know whether an index was used.
I could use a SQL statement called EXPLAIN QUERY PLAN.
Other DBMSs might call this just simply EXPLAIN,
but in SQLite it's EXPLAIN QUERY PLAN.
And then after EXPLAIN QUERY PLAN, I can type the query
that I want to learn the plan for.
That is, how does SQLite plan to find me this information?
How does it plan to execute this query?
So now I'll type SELECT * FROM "movies" WHERE "title" = 'Cars'
like this, semicolon.
I'll hit Enter.
And now I don't get the results, but I do
get the plan SQLite intends to use to find me this result.
And take a look here.
I see QUERY PLAN, and underneath I see what SQLite intends to do.
It will search the movies table, but it will do so
using the index that we called title_index.
And it will do so given some value for title here.
So we can actually see SQLite does plan to use the index
to speed up this query.
We can confirm that this is exactly what's happening.
But let me try now to remove this index and see
what SQLite would have done when we didn't have this index.
I'll come back over here and I'll go back to my other connection
to my database.
This one over here.
And now I'll remove the index we just created.
To remove an index I can drop it.
I can say DROP INDEX "title_index" semicolon.
And now that took just some amount of time,
but now I don't have the index anymore.
I can type .schema, and I'll see that index is not part of my schema.
But now if I try EXPLAIN QUERY PLAN SELECT * from "movies" WHERE "title"
= 'Cars' semicolon, I'll see that the plan is not to use the index.
The plan is to scan movies, where scan, we saw before,
means to go top to bottom through that title column
and find me all the rows that have Cars in them.
So you can see here the optimization we're already
making by using this index here.
OK, so let's take a moment here and pause.
What questions do we have about indexes and how they're used in this case?
AUDIENCE: Doesn't databases have implicit algorithms to optimize search?
CARTER ZENKE: Yeah, good question.
Do databases have implicit algorithms to optimize search?
They do for some columns.
So if we saw in our table earlier, we had a primary key column like ID.
In SQLite and most other DBMSs, if I specify that a column is a primary key
then that database management system will automatically
create an index via which I can search for a primary key.
If though I have a regular old column like title or like year or so on,
it doesn't go through the process of automatically optimizing
that search for me.
I have to try to do that myself as we're doing here.
Let's take one more.
AUDIENCE: Would it be advisable to create a different index
for every column in case we need it?
CARTER ZENKE: Yeah, I mean it seems like indexes are so good.
They speed up queries for us.
Why not create an index on every column we have?
Well as we'll see in just a moment, there
are some trade-offs involving space and also the time it later takes
us to insert or add new data.
So good questions.
I'll come back to my laptop where we can continue on.
So we've seen how indexes can speed up queries.
We're searching for one column here, but they could also speed up
queries across multiple tables.
So let's try a different kind of query here.
What I might do now is try to find all of those movies
that Tom Hanks starred in.
And we did a bit of a example of this a little earlier visually,
but my goal is to find all of those titles that Tom Hanks played a role in.
Well if my goal is to end up with titles of movies,
I could try selecting "title" from the "movies" column like this.
But if I look at that movie's table, oh no, I only
have titles, year, and the ID of those movies.
I don't have anything related to Tom Hanks.
Well Tom Hanks though is probably showing up in the stars table
where I could correspond Tom Hanks's ID with the movie IDs
that Tom Hanks played a role in.
So let me try filtering these movies by an ID.
I'll say WHERE the "id" of that movie is IN some list of movie IDs
that also correspond with Tom Hanks's person ID.
So I'll make a subquery here to find exactly those films.
Now I'll say SELECT "movie_id" FROM "stars" where the "person _id"
is equal to--
well I don't know Tom Hanks's person ID.
I could try to hard-code it here, but I could do better
by having another subquery to find what is Tom Hanks's ID?
Now I'll indent not just four times but eight
to show this is my next level of a subquery here.
I'll now SELECT "id" FROM "people" WHERE the "name" = 'Tom Hanks'.
'Tom Hanks' like this.
And now I can close out my subqueries.
I've found the ID of Tom Hanks, I've found those movie IDs that
correspond with the person ID of Tom Hanks,
and then I've found the titles that correspond to those movie IDs.
Now I'll hit a semicolon here, press Enter, and I should see--
I get back all of Tom Hanks's movies, all of those that he played a role in.
And I'll also see the time that it took.
The real time for this query was about 0.197 seconds.
So getting a little bit slower now that we're looking across multiple tables
and having multiple subqueries.
One index could speed this up as well.
I can make a new terminal here.
Let me open up the connection to my database again.
I'll say sqlite3 movies.db.
And now I should figure out what columns do
I need to index to speed up this query?
Well one thing I could do is try EXPLAIN QUERY PLAN again.
I want to understand what SQLite plans to do to execute this query.
So I'll EXPLAIN QUERY PLAN and I'll type in the same query from before.
I'll say SELECT the "title" FROM "movies" WHERE
the "id" is IN those movies that Tom Hanks played a role in.
So I'll SELECT in this case movie_id from the "stars" table where
the person_id equals Tom Hanks's ID.
Now I'll find that.
I'll indent eight times to show this is my next level subquery.
I'll SELECT "id" from "people" WHERE "name"
= 'Tom Hanks' and I'll wrap the line just a little bit.
Let me zoom out so you can see it all in one go.
And now I'll close out these subqueries just like this, hit Enter,
and I should see if I zoom back in the plan SQLite intends to use to find me
the results of this query.
Now let's take a look here.
I'm planning to first scan people.
To understand the structure of this I need
to first go all the way in to this bottom part here.
I'm going to scan people to find presumably Tom Hanks's ID.
Then after I do that, I'm going to scan stars presumably
to find all the movie IDs that have Tom Hanks's ID.
But then up here I'm finally going to search movies
using integer primary key.
Some index is automatically created for me
as we saw before for my primary keys.
So it seems like the optimization here could be in the people
table and the stars table.
Now let me ask, if I wanted to create an index on either the people
table or the stars table, what do you think I should include?
Which column should I include in this index given my query here?
What column should I include in this index given this previous query?
AUDIENCE: We could index the ID and the name of the person?
CARTER ZENKE: Yeah, good idea.
Index the ID and the name of the person.
So if we look at this query again we'll see that our WHERE clause here
is searching by the name in the people table,
and up here this WHERE clause is searching by the person ID
column in our stars table.
So it would stand to reason that I should actually
create an index that includes the name column in people
and the person ID column in stars.
Perhaps two separate indexes.
One for each year.
So let's go ahead and create those now.
I'll come back to my computer and here I will try to create this index.
I'll say first create an index.
CREATE INDEX called "person_index."
And I'll create it on stars and the person ID column in stars
as we just discussed.
Now if I hit Enter I should let it take some time to build up this index,
but now I can also create my next one.
I'll say CREATE INDEX, and then I'll choose "name_index" on people table.
And I'll include the name column here.
So now I'll hit Enter.
That too will take some time to run, but now
if I try to explain the query plan again--
I'll clear my screen, try EXPLAIN QUERY PLAN, and then I'll type in this query
again.
I'll say SELECT "title" FROM movies WHERE the "id" is IN those movies
that Tom Hanks played a role in that have the person ID next to it.
Then I'll say which is Tom Hanks's ID?
And I'll close out the subquery here just like this.
And now if I explain the plan yet again, I
should see I'm now optimizing this query even further.
I can see down below here, my plan is to search the people table.
Not to scan it, but to search it using what we call
a covering index called "name_index."
The one we just created.
We'll explain covering index in just a little bit.
Next though, I'm going to search stars using
the index we just created called "name_index" given some person ID.
And then finally, I'll search movies using
an integer primary key index, the one that's
automatically created for me here.
So here we see some new vocabulary.
Not just using index, but using a covering index.
Well, what is a covering index?
A covering index, it turns out, is still an index.
It's the same kind of idea, but it is one
in which we have all the data we need inside the index itself.
It's one in which the query data can be found only by searching the index.
There's no need for me to go from the index to the table.
I can just look it up in the index.
It's similar to me searching this textbook and getting to the index
and not then needing to actually go back in the book's pages.
I can find everything I'm looking for in the index itself.
And this is good because if I need to not just find the items in my index
but then look them up in my table, that look up in the table takes some time.
So if I instead have a covering index, one
that includes all data I want to find exactly right there in it,
that's going to be faster for me than a regular old index.
So let's try then turning one more index into a covering index.
I'll come back over here.
And we saw before that we had the index on the stars
table using just a regular old index.
Using index person index.
But what are we trying to find from this index?
We're trying to find the movie ID column.
So I could create an index that includes the movie ID column as well.
I can have indexes that span multiple columns.
So let's try that here.
I'll come back over and I'll create this new index
that intends to cover our search here.
I want to include not just the person ID column but also the movie ID
column so I can quickly find that data inside the index itself.
Let me drop our current implementation of the person index like this.
And I'll hit semicolon here, and now that index is gone.
But if I type now CREATE INDEX, I'll also
call this "person_index" ON "stars."
and I'll say let's include not just the person ID column.
Let's also include in this case, the movie ID column like this.
Now I'll hit semicolon, Enter.
And it'll take a bit of time to run, but once it's
done I can probably try to explain the query plan again and see
if we have our covering index.
I'll go back up top here, I'll EXPLAIN QUERY PLAN,
and I'll choose to recreate this query from before just like this.
I'm going to select the "movie_id" FROM "stars" and then find Tom Hanks's ID
and then close out these subqueries here just like this.
And now once I EXPLAIN QUERY PLAN, we've optimized even further.
Now I have two covering indexes.
I can find all the information I need just by looking in these indexes,
not by doing a table lookup.
So let's now run this query and see just how much faster it might be.
I'll come back to my laptop here, and let's get rid of EXPLAIN QUERY PLAN.
Let's now turn our timer on.
I'll turn the timer on like this and I'll rerun this query.
I'll say we select title from movies where the ID is in the stars table
so long as the movie ID aligns with the person ID.
Then I'll find Tom Hanks's person ID here, I'll close out my subqueries,
and I should be able to find that this query is just a little bit--
this is an understatement here.
A lot faster.
So if I go back to my old query here, I'll see this one took 0.197 seconds.
This one with two covering indexes takes 0.004 seconds.
This is an order of magnitude faster than my prior query
because I've used indexes now.
So, let's see.
If we have all these benefits of indexes, we must be paying something.
If I have this book here and I'm trying to find some data inside of it,
what might the trade-offs be if I want to create an index?
Let me think first about this database on my computer.
What am I giving up?
If I'm making sure my query is faster, what am I losing, do you think?
AUDIENCE: Space will require for indexing also.
The more index we would have, the more space and more memory
we would have to consume for that.
CARTER ZENKE: Yeah.
So it's a general theme that when I try to speed up
something in computer science, I have to pay some cost which
is often in terms of space.
That when I create an index I'm using more space in my database.
And this similarly applies to an old fashioned textbook.
If I have an index in here, I'm literally
paying in pages to print so people can find content better.
This is some extra money I have to spend,
extra pages I have to print in order to make my queries faster,
either on this book or in my database.
So let's understand why indexes take up so much space
by looking at the underlying data structure they
use to store information.
Well it turns out that the part of the reason indexes
take up so much space is because they use a certain data structure,
a way of organizing data called a B-Tree, or a balanced tree structure.
So not to worry if you don't know what a tree structure is.
Here's a visual to keep in mind as you think about using trees in computer
science and in indexes in particular.
A tree might look a bit like this.
And notice how it's similar to a family tree with grandparents
and parents and children and so on.
You could if you wanted to kind of do a 180 on this diagram.
Flip it right side up and now you might see
more of a tree structure going from top to bottom.
You can see down here what might call the trunk of the tree followed
by some branches-- these over here.
And then the leaves.
These up top kind of the edge of this tree diagram.
And there's a few vocabulary words you might
want to know when you talk about trees.
One of them is this idea of a node.
So this right here is a single node in our tree.
A tree is made up of a collection of nodes, and each of these nodes
stores some value.
Maybe it's a value in the column we're trying to index, for example.
But in addition to that value, this node also
stores pointers, kind of arrows metaphorically, to other nodes
to tell us where in memory these nodes are.
And by stringing these nodes together, we
can build up this tree-like structure.
Now this node here points to three other nodes.
And some new vocabulary here is that this node has three children.
Going back to that family tree example, we
see that this node here has three children which are these right here.
But these nodes themselves also have three children of their own.
So if I were to go down to the next level of our tree--
well if I'm referring to this node here, these nodes down below
are that node's grandchildren.
The children of its children.
Now these nodes here also have another name.
We saw before they're often called leaf nodes.
They're the edge of our tree.
And we know a node is a leaf node when there are no other nodes it points to.
So this is the general idea of what an index looks like.
But let's get a little more concrete and try
to build an index from our title column in our movies table here.
So let's assume we have a table of IDs and titles here,
and I want to create an index on this title column
to search it more efficiently.
Well we saw before that the best I can do when this data is unsorted
is to go top to bottom.
First look at Toy Story, then look at Cars 3,
then look at Frozen, all the way down to the bottom.
I can only scan this column, so to speak.
But I know I could probably do a little better if the data is sorted.
If the data is sorted I could look roughly in the middle,
and if I've gone too far, go back a little bit.
Or if I haven't gone far enough, go forward a little bit
and do a fewer number of lookups to find data I'm looking for.
So let me sort this title column.
I'll put it like this.
What have I done wrong?
First I had this, then I wanted to sort my title
column to make it faster to search.
But what rule did I break here by sorting this title column like that?
AUDIENCE: Yes, Carter, the thing is that by sorting only the movie's
name and not the ID you will break the entire other databases that
relates to that one.
So for example, let's look for a movie in which, I don't know,
Johnny Depp is working or has worked on.
And the result may be, I don't know, Titanic.
CARTER ZENKE: Yeah, I love that example.
That really drives it home here.
And in more general terms, I had this primary key called ID.
And in the prior state I had Toy Story with the ID of 114709.
A primary key means that Toy Story should be consistently identified
with this number, 114709.
But to your point, Mateo, if I sort only the title column,
well now Cars has that ID--
114709.
I've broken that relationship, particularly
if other tables are relying on Toy Story being identified by 114709.
So I can't do this.
This is bad.
I need some other way to sort my title column.
So let's bring this back to what it was here.
Let me focus just on the title column.
Well I can't sort this title column because it's part of my table
and the ordering of that table does matter.
What I could do though is create a copy of this column
and maybe sort that copy.
So I'll literally create a copy of this title column elsewhere in memory.
And let me just remove this title column identifier here
so I have just the data.
Just the data in this column somewhere else in memory.
And now I could sort this data like this.
So let's say I now want to find Cars.
Well now that my data is sorted, what could I do?
I could look first in the middle-- at Ratatouille for instance--
and then realize, well Cars comes before Ratatouille.
Maybe I'll go a little higher in my index here.
I'll search in the middle of this first half.
I'll look at, in this case, Frozen.
And Cars-- well it still comes before Frozen,
so let me look up at the first half of this first half.
I'll then go up here and I'll have spotted Cars.
So a much faster way to search for information now once I have it sorted.
But I don't think we're quite there yet.
If I wanted to find the year that Cars was released,
I found that it's in my title column but what am I not able to do at this point?
I've copied the data somewhere else, but now I
want to find some other data in my table.
What can't I do?
AUDIENCE: We need to point to index.
CARTER ZENKE: Yeah.
I need to be able to find some way to relate
this index with the rows in my table.
So here this is elsewhere in memory.
It's good that I can find that Cars is in my title column.
But if I want to find the other data in this row like the year
that Cars was released, well I have to have
some way of linking this data here, Cars, to my table.
So often in an index, we won't just copy the data to some new location
and sort it.
We'll also have some link between these indexed pieces of data over here
and our rows and our table back here.
So for instance here is Cars, and Cars appears to be in row 4.
Similarly Cars 3 looks to be in row 2 in my table.
And I could metaphorically visually draw some lines between Cars over here
in my index and Cars in my table.
I could draw one that looks a bit like this going from Cars in my index
to actually Cars in my table.
I could draw one for Cars 3 going from this index place
here to row 2 in my title column.
So that is the way I can link my index with my table data.
I could do the rest of these too for all of my other pieces of data in my index.
So let's focus on this now just to check for understanding.
I have this index.
That index has my sorted title data and also
the row number in which I found that piece of data.
So let's say here I want to find the movie Soul.
I want to find the movie Soul.
How could I find Soul in my index?
AUDIENCE: Yeah, since it is already sorted
I believe you could use binary search.
CARTER ZENKE: Yeah.
I could use algorithm called binary search, which if you're not familiar
simply means start in the middle and if I've gone too far,
look at either the left half or the right half
and repeat that process over and over.
So here is my index again.
I'll go roughly to the middle and I'll look at Ratatouille here.
Well Soul, I know, comes after Ratatouille alphabetically,
so what should I do?
I should now look in this second half here.
I might go to Toy Story.
Once I see Toy Story, I know I've gone a little bit too far.
Soul comes before Toy Story alphabetically,
so I'll look in the first half of this second half.
And what do I see?
I see Soul right there.
OK.
So our index seems to be working.
It allows me to more efficiently find data.
I no longer have to look through every single row.
I can simply use a more efficient algorithm like binary search.
But now there's one more catch which is, if I had many, many, many rows--
not just nine but literally thousands or hundreds of thousands or millions
of rows in this index, that's a lot of data to store in one location in memory
or even to load into my computer's RAM, so to speak--
its random access memory--
so it can do all this jumping around.
Ideally what I would do is break this index up into smaller pieces
so I don't have to load all of this at once.
And in reality our index is not a single column like this,
but often individual nodes where each of these--
1, 2, 3-- might be some node scattered about the computer's memory.
But what problem have I introduced now?
If these are around the computer's memory,
I can't actually jump between them anymore.
I can't go maybe one space above Toy Story and find Soul.
This node might be elsewhere in memory.
And so we'll need some other nodes to actually help
us find what we're looking for in this index.
I might have one more over here that tells me what kind of data
is in each of these nodes.
Maybe I have one here that has both Frozen and Soul.
Notice how here Frozen is the furthest down alphabetically in this
node up here.
And notice down below here Soul is the furthest down
alphabetically in this node here.
That is, if what I'm looking for comes before Frozen,
I should look at this node.
If what I'm looking for comes after Frozen but before Soul,
I should look in this node.
Or if what I'm looking for comes before none of these, it comes after Soul,
I should look at this node down here.
So let's find an example.
Let's say I want to find Cars now.
Well I'd start in this root node, this base of this tree
we're building here that I've turned kind of right side--
this way.
Let's say Frozen.
I'll go here and does Cars come before Frozen?
Well it does, so I'll look in this node now.
I'll come up here and I'll find Cars in that node.
Let's see here.
Maybe I want to find Ratatouille.
I'll go back to the beginning and I'll look through this root node.
I'll say, does Ratatouille come before Frozen?
It doesn't.
It comes after Frozen, so I'll look and check Soul.
Does Ratatouille come before Soul?
Well it does, so I'll look in this node now.
I'll go find Luca.
I'm not quite there yet, but I will see Ratatouille
so I know that I've now found Ratatouille in my index.
And now for one more--
let me check for understanding here.
How could I find Turning Red?
What steps would I follow to find Turning Red?
I might start at that root node, but then what questions should I ask?
AUDIENCE: From Frozen also we can see Ratatouille is to the right
so that we move in direction of Soul.
Now once we get there we find the middle elements and we can see Ratatouille
is to the right of the middle elements.
So that's how we find it.
Divide the list into two halves and look into the half
that the element is found.
CARTER ZENKE: Yeah, I like what you were thinking here.
So you're talking about traversing this tree we've built and turned on its side
here.
And let's visualize that search here.
So first we'll start at Frozen and ask, does Turning Red come before Frozen?
It doesn't.
It comes after, so I'll keep looking.
I'll look at Soul.
Does Turning Red come before Soul?
It doesn't.
It comes after Soul, so I know I need to look at this node down here.
I'll go find Toy Story.
Not quite there yet, but now I'll see Turning Red.
I'm able to find what I'm looking for.
And not just that.
I can find what row number Turning Red is actually in in my table.
So when you use an index, SQL or SQLite is using some algorithm a bit
like this.
It creates some tree structure a bit like this here
with individual nodes that has your column data.
It then uses this kind of algorithm to search that index
and find whether or not that piece of data is in your index.
And if it is, it will go ahead and look up that piece of data in your table.
So see here, although this is turned on its side, the relationship
between a kind of tree.
We had a root node or a trunk node here pointing to some of these leaf nodes--
the edge of our graph right here.
And you can see some relationship between these nodes here
and our tree as well right here with arrows
pointing across these individual nodes.
So let me pause here and ask what questions do we have on this structure
and how we've searched it?
AUDIENCE: Is that related to linked lists or arrays?
CARTER ZENKE: Good question.
Is this related to linked lists or arrays?
So if you're familiar, a linked list is some set
of nodes that have been linked together in memory using these arrows like we
saw on our diagram here.
It is the case that sometimes an index will include a linked list.
Let's take one more here.
AUDIENCE: I want to know, a covering index--
how is the [INAUDIBLE] covering index and what has been--
I mean, if we just [INAUDIBLE] index and then we just start covering index,
how SQL automatically getting that covering index that's here?
CARTER ZENKE: Yeah, so I think we're asking, how is the index created?
Like, what is the process for doing that?
Well it turns out that just as we saw here in the slides, SQLite or whatever
DBMS you're using will take a copy of the data that should be in that index
and organize it into a tree structure like we saw here.
It may or may not be similar to the structure we saw just
a little earlier with nodes that have different pieces of row data in them.
Good question there.
OK.
So we've seen now the trade-off that we get
with index, which is they're very fast to look up some data
but they take up a lot more space.
There's a lot of redundancy to them here.
There's also one more trade-off, which is
if I want to insert something into this structure, it'll take me more time.
I have to navigate this structure here.
I have to figure out should it come before this value or after this value?
And I'll have to traverse this tree every time verses
without an index I could just add something to the end of this list.
But with a B-Tree, with an index, I need to traverse all these nodes
and figure out where should that piece of data go?
So these trade-offs are something you should
keep in mind as you build indexes and optimize your queries.
OK.
There are ways though to actually optimize the space
that we use using a tree like this.
We can use a structure called not an index, but a partial index.
And if you're concerned about space, a partial index might be good for you.
A partial index only includes a subset of the data from a given column,
thus making your index smaller overall.
You could think of a partial index being useful when
you know that your users will only query a subset--
only a small number of rows from that table.
And for example in IMDb, maybe we know people
are more likely to search for a movie that came out this year versus someone
that came out 15 years ago or so.
So we could create an index that focuses on those movies that
came out this year versus 15 years ago or so, and we'll do just that.
If I want to create a partial index I can use this syntax here.
I could say create an index and give it some name,
then include some data from this table and this column here,
or a list of columns I can provide.
But then what I need0 to do is add a condition where some condition is true.
These are the rows I want to include in this index.
Before we had just create index name on table from a list of columns.
Now we can add in this WHERE clause that says only include those rows where
this condition is true.
So let's try that now.
I'll come back to my computer.
And why don't we try creating a partial index
to help speed up the lookup of movies that came out this year.
Well I could come back to my terminal and I could remove, let's say,
this one over here.
Now I'll try to create this partial index.
I'll say create an index called "recents" to indicate this
will help us search for recent movies.
Now I'll make this "recents" ON "movies" in the ("title") column.
I want to look up titles ultimately, but now I
only want to create an index for those rows where the year equals 2023.
I only want to include those titles in my index that were released in 2023.
So I'll hit Enter now and I'll see I created this index for myself here.
Now let me try searching for those.
I'll SELECT "title" FROM "movies" WHERE the "year" = 2023.
Enter.
And I'll see a lot of movies came out in 2023.
Now, it's taking 1.3 seconds here.
But now I could prove to you that we are using some index.
I could say EXPLAIN QUERY PLAN and now type SELECT "title" FROM "movies"
WHERE the "year" = 2023.
Hit Enter.
And now we'll see-- what are we doing?
We're going to-- we'll scan movies but we're still
going to use the index we just created called "recents."
So it's helping speed us up just a little bit overall.
Now let me try dropping this index and showing you the opposite.
I'll come back over here and I could try dropping it.
And actually, before I do that let me show
you what would happen if I didn't search for movie in 2023.
I would try EXPLAIN QUERY PLAN.
And let me try SELECT "title" FROM "movies" where the year = 1998
like this.
And see now I'm only back to scanning movies.
So before in my prior query I was able to use the index
because my WHERE clause included 2023.
Now though I'm using 1998, which were rows that were not
included in this partial index.
OK.
So let me ask now, what questions do we have
on these partial index which we can use to optimize some
of the space these indexes take up?
AUDIENCE: Are indexes not saved in schema?
CARTER ZENKE: A good question.
Are indexes saved in the schema?
In SQLite if I type .schema I can actually see them in my schema.
So let me go back here and show you.
If I now type something like--
let me turn timer off here--
.schema, you can see down below here that I actually have these indexes
as part of my schema.
I'll see the create index statements I used down below here.
Create an index called name_index, called person_index, called recents.
And all that I used to create these indexes now inside my schema.
If I drop some index it'll then be just removed from my schema altogether.
Good question.
OK.
So speaking of dropping indexes, one other way
we can more efficiently use space is to do a bit of vacuuming so to speak.
So let's introduce this idea of vacuuming up our database.
Let me show you a slide here.
And this one involves this idea of trying to clean up
unused space in our database.
Often when we delete something, either a rows or an index,
we don't actually delete those bits that were
being used by those rows or that index.
We just mark them as being available for whatever we next insert.
They can be overwritten, so to speak.
But if I want to actually reduce the size of my database
after I delete something, I should use something like vacuum in SQLite
or optimize in some other DBMS.
Vacuuming is a bit like taking those unused bits and just sucking them up.
Taking them back in so we can give them back to the operating system.
And the keyword we can use for vacuum is just simply vacuum.
So let's try this.
I'll come back to my computer over here.
And let me open up a new terminal-- one that I can use
to find the current size of movies.db.
So I'll hit this + button here and now I could type a command.
Not a SQL command or a SQLite command, but actually a Unix command.
I could type du -b for the disk usage in bytes.
How many bytes is a particular file?
I could then say movies.db here, and if I hit Enter I should see movies.db
is something like 158 million bytes or 158 megabytes.
So let's see what happens if I were to delete an index which you know takes up
some amount of space in our database.
I'll go back to my terminal here.
And let me try to drop an index that we had recently created.
I'll say DROP INDEX "person_index" to remove the person index in this case.
I'll hit Enter and now I see that "person_index" is dropped.
If I type .schema here, I no longer see it in my schema down below.
So now let me check the disk usage in bytes and see if it's any smaller.
I'll hit the up arrow to get access to that same command, hit Enter.
It seems like it's the same size.
It's still 158 megabytes.
So let me try dropping something more here.
I'll go back to my terminal here and now I'll try--
what other do I have?
I have "name_index" so I'll say let's DROP index "name_index" like this.
I'll hit Enter and I'll see that index is now gone.
Well now I'll also try dropping recents.
I'll DROP INDEX "recents" and now I believe all of my indexes
should be gone.
If I type .schema, I don't see any more indexes.
So now let's check on the disk usage in bytes.
I'll go back to my other terminal, hit du -b again,
and it's still 158 megabytes.
Well what can we do to clean this up?
We could run vacuum.
If you remember here when we delete an index-- we drop the index,
we don't actually shrink our database file.
We just mark those bits that were part of the index as being
available for re-use.
So let's now vacuum and compress our file
to give back those bytes and those bits to the operating system.
I'll come back to my terminal here and type VACUUM; hit Enter,
and I'll wait for it to find those bits and bytes,
wait for it to give them back, to de-allocate them,
to go back to the operating system.
And now if I come back and I type du -b again, hit Enter--
I should see a much smaller file.
So before we had about 158 million bytes.
We're down to in this case 100 million after dropping our indexes
and using VACUUM.
So let me ask now, what questions do we have on vacuuming?
AUDIENCE: Can we do vacuuming in a faster way?
CARTER ZENKE: Can you vacuum in a faster way?
So I think it depends on the size of the vacuum
that you're trying to implement here.
If you have a lot of bits and bytes you're
trying to de-allocate, that could take more time.
The process here is the computer has to find those bits and bytes you're
no longer using and then give each of those back to the operating system.
So it could depend on the size and how long they take to find.
And let's take another question here.
AUDIENCE: Initially you said once we drop a database, we don't lose the--
the data is not deleted.
The space is just reallocated, right?
If I go you right.
So does that mean the queries we run today,
are they locked somewhere that-- let's say you mistakenly did a query.
You can go back and pull that data back?
Is that possible?
Kind of like a reversal of a query.
CARTER ZENKE: Yeah, so you're talking about some forensics here.
Like, could we mark something as deleted but still find it later?
There actually are people who are trained in this, in forensics,
to find pieces of data that you thought were deleted
but are actually still on your computer just forgotten, if you will.
In this case in SQLite it would take a lot of work
to go ahead and find all of those bits and bytes we've removed.
But once we vacuum, once we actually give them back to the operating system,
we can no longer find those in the database
because they're not just marked as being de-allocated.
They actually have been given back and they're no longer part of our database.
Good question there.
OK, so we've seen here how we can optimize
our queries by reducing the time that they take
although at the cost of some space.
When we come back, we'll see how we can handle not just one query at a time
but many all at once.
See you in a bit.
And we're back.
So we've seen so far how to optimize individual queries, ensuring
they take less time and also to ensure our databases
use as little space as possible.
What we'll focus on now is trying to ensure
we can handle not just one query at a time but multiple all at once.
And this is this idea of concurrency.
Concurrency is when I get multiple queries, multiple interactions, all
at roughly the same time and my computer system, my database,
needs to figure out how to handle all of those at once.
This is particularly important for websites that get a lot of traffic,
or even for the financial sector.
People are constantly making trades, placing orders,
exchanging money, and so on.
So let's see one example here of a bank.
Let's say here I have a table of accounts
and each account has a name and some balance to it.
Well we decide here that maybe Alice wants to pay Bob $10.
So what should I do to update the balances here?
Maybe the first thing I should do is make sure that Bob receives that money.
I could update Bob's account to have a balance not of $20 but of $30 now.
From $20 to $30.
But here's the thing.
If at this moment somebody looks at this table, what will they see that's wrong?
What will they see that they might not get the right picture of at this point?
I'm hearing they might not see the correct balance for Alice.
Bob has gotten some money.
He's gone from $20 here to $30.
But now I have not just--
let's see, $60 in the bank.
I now have $70 it looks like.
So if somebody looks at this transaction in this moment
they'll see some incorrect information.
What I should then do is update Alice's balance,
subtracting $10 so we're at the right amount of dollars across our bank
accounts here.
So this is an issue.
When I have one ongoing transaction like this
and somebody else wants to look at that data,
they really shouldn't be able to until this transaction is
complete in its entirety.
So ideally-- let's go back to what we had before with Alice at $10
Bob at $20.
Ideally if Alice wants to pay Bob, this should happen to an outside observer
all at once.
Bob should get those $10 and Alice should
lose those $10 at the same exact moment so nobody
can look and see that Bob has more money while Alice doesn't have less money.
Now we can implement this idea of this transaction using
a very similarly-named idea in databases called a transaction.
Now a transaction in the world of databases
is an individual unit of work.
That means a transaction can't be broken down into smaller pieces.
It happens all at once or not at all.
And in fact a transaction has several properties
and helps implement several properties of a database.
Among these are ACID--
A-C-I-D. You may have heard of these if you've looked up something about
databases, but each one stands for some principle of ensuring a consistent
and reliable database.
In fact, A stands for atomicity, which means I can't break a transaction down
into smaller pieces.
I can't break a transaction between Alice and Bob
into Bob's update and then Alice's update.
It's just update both accounts at the same time.
Consistency means a transaction to help me ensure that I
don't violate some database constraint.
Let's say I try to pay Bob from Alice's account,
but Alice doesn't have the money.
If that is the case, a transaction will revert, undo.
So I go back to being in this consistent state for my database.
Isolation means if I have more than one person trying to access
this database, their queries--
their transactions won't interfere with each other.
And then finally, durability means if I were to unplug this database
or we were to encounter a power failure or the server to crash,
all that data would still be there from the time we committed our transaction
or saved the results there.
So transactions do a lot for us, but they have some very simple syntax.
I can simply use BEGIN TRANSACTION and then follow it up with some statements
I want to include in that transaction.
And once I'm sure I want to save the results of these statements,
I can then say COMMIT, meaning save these changes thus far.
And it's using this kind of syntax we can
ensure that nobody sees incorrect balances,
let's say, for this bank account table here.
So let's try this out and implement a payment between Alice and Bob,
but now using a transaction.
I'll come back to my computer here.
And let me show you a new database.
I'll type sqlite3 bank.db.
I'll hit Enter.
Oh, sqlite3.
Sorry.
bank.db.
I'll hit Enter, and now let me type .schema to see the schema of this
database.
I'll see here a few different columns.
But I have an "id" column, my primary key,
a "name" column like we saw in our slides that is text and can't be null,
and then a "balance" column.
There's an integer, a whole number of dollars, that also must have a value.
Can't be null.
And I have a check constraint here saying
the balance must be at all times greater than or equal to 0.
So this is our implementation of a table of bank accounts.
Let me try querying here to see what our account balances look like.
I'll say SELECT * FROM "accounts" semicolon.
And now I'll see that very same arrangement we saw in our slides.
Alice has $10, Bob has $20, and Charlie has $30.
So let me try then processing this transaction between Alice and Bob.
Well at this moment I might try to update Bob's account
at the first [? bat. ?] I'll say--
let's try update and I'll update the accounts
table, set the "balance" equal to "balance" + 10 where the "id" equals 2.
Remember, Bob's accounts "id" is 2.
So now if I hit Enter here, Bob should have gotten just 10 more dollars.
But there's a problem.
If I also connect to this database through another connection here,
sqlite3 bank.DB.
Maybe I'm somebody who's checking on the balances of the bank.
I say SELECT * FROM "accounts."
What do I see but an incorrect total balance?
We should have $60, but here I see $70.
So I need to complete this transaction to ensure
that I actually have the right amount of balances across the board.
Let me go back here and let me try to run the next part here.
Let we update this.
I'll say UPDATE "accounts," and I'll SET "balance" equal to "balance" minus 10.
Minus 10 where the "id" equals in this case 1 where Alice's bank account ID
is 1.
Now if I hit Enter I should be able to go back to my other terminal
and check on the balances again.
And now I'll see the right balances all together.
But there is a way to avoid me looking at this table
and seeing an incorrect state, and the way to do that is called a transaction.
So let's go back here, and I will reset my terminals.
I'll now also give back Alice's money.
Let me give back Bob the $10.
I'm going to go back--
[INAUDIBLE] say where "id" equals 1 here.
Now Alice will have 10 more dollars.
And I'll go back and I'll update accounts.
I'll set the "balance" equal to "balance" minus 10
where the "id" equals 2.
So I'm giving Bob back the $10 that they just gave to Alice.
Now if I SELECT * from "accounts" we're back to where we began.
So ideally I should able to complete this transaction between Alice and Bob
without somebody seeing the intermediate process of Bob
having more money than Alice.
So let's try this.
I'll say BEGIN TRANSACTION; Enter.
And now I can include what I want to have happen in this transaction.
First I want to update Bob's account.
I'll say UPDATE "accounts" and SET "balance" equal to "balance" + 10
where the "id" in this case equals--
let's see, 2, because Bob's account ID is 2.
Now I'll hit Enter, and now I'm in the middle of this transaction.
But if I go to my other terminal-- let's say I'm somebody new
and I check on the balances of the bank.
I say SELECT * FROM "accounts".
What do I see?
I don't see any change from before.
Alice still has $10, Bob has $20, and Charlie has $30.
And even though in this terminal I've been
able to update the account balance, I haven't committed those changes.
I haven't saved them to the database just yet.
So let me try now removing money from Alice's account.
I'll say UPDATE "accounts" and set "balance" equal to balance minus 10
where the "id" equals 1.
Now I'll remove $10 from Alice's account.
Hit Enter, and still if I go back to this other perspective
here from somebody else checking on the bank balances, I see--
well everything is still the same.
But the moment I then go to this transaction
and finish it by typing COMMIT, meaning save these changes, I'll commit here.
I can go back and I'll see all in one moment
that it appears Alice has paid Bob $10.
So this is the atomicity part of transactions.
I don't see the intermediate steps in the transaction.
I only see that it happened all at once or not at all.
OK, so this is one example here of a transaction.
Let me ask what questions we have so far on the transactions we've made
and how they can be used.
AUDIENCE: You are searching based on ID--
like an ID is equal to a question mark.
But in a real-world scenario, how they would Search maybe
like using the Transaction ID or basic account number?
CARTER ZENKE: Good question.
So here I'm searching by ID.
I'm saying that I want to update the balance of account with ID 1 or ID 2,
for instance.
And this is similar in spirit to how your bank account likely
has some unique number, an account number so to speak.
So here in this table I'm updating balances
by referring to the account number.
You could imagine me using names, but there
might be in some world multiple Alices, multiple Bobs.
So I should uniquely identify each account using its ID in this case.
OK, so let's come back and think through more kinds of transactions here.
And let's think through a transaction we actually don't want to complete.
So let's go back to our balance sheet where we have Alice at $0 and Bob
at $30, and let's say Alice wants to pay Bob 10 more dollars.
Well if I go through this transaction, what's going to happen?
Alice will have -$10 and Bob will have $40,
and that violates our check constraint that we saw in our schema.
The balance of Alice's account must always be at least $0.
So if I were to complete this transaction,
that would bring our database to an inconsistent state.
It violates some constraint that we have.
But what I can do is undo these changes.
Revert them so that we go back to the original state
if we ever violate some constraint like we just did.
There's a technical name for this, which is rolling back.
So if I ever want to not save the changes in this transaction,
I can say ROLLBACK.
Go back to the beginning, think about it as if this transaction never even
happened at all.
So let's try it.
So I'll come back to my computer, and what I'll do
is try to implement this idea first without a transaction.
I'll go back to, let's say this first terminal here,
and I'll SELECT * FROM "accounts" like this.
Notice how Alice has $0 and Bob has $30.
Well I want to pay Bob 10 more dollars from Alice,
so I'll update Bob's account.
I'll find here my prior statement, UPDATE "accounts"
SET "balance" equal to "balance" + 10 where the "id" equals 2.
And recall that Bob's account ID is 2
I'll hit Enter, and now if I SELECT * FROM "accounts"
if we're looking somewhere else--
SELECT * FROM "accounts," I'll see Bob has 10 more dollars.
But now I need to subtract money from Alice's account.
So I'll use the same thing but now I'll say minus 10 where the "id" equals 1.
Alice's account ID is 1.
Now I'll try to subtract $10 from Alice, but I get a constraint failure here.
My check constraint failed on the balance column.
Why did it do that?
Because I now have less than $0 in that balance column.
So I need to undo this but I don't have a transaction here.
What could I do instead to undo what I've just done?
AUDIENCE: So we can roll back.
CARTER ZENKE: We could roll back, but here's the thing.
A rollback only works while we're inside of a transaction.
And a transaction begins when we say begin transaction.
So here I actually didn't say begin transaction.
What I have to do instead is run another update statement.
I have to update, let's see, Bob's account
to remove the $10 that Alice paid Bob.
So let's try that.
I'll come back to my computer and I will then revert back.
I'll say let's undo this.
Let's subtract $10 now from Bob's account where the ID is 2.
Now we're back to where we began.
If I check in from some other [INAUDIBLE] here,
I'll see we're back to Alice having $0 and Bob having $30.
But we ideally want to use rollback to undo some changes that we
have made in a transaction.
So for that let me now use a transaction.
I'll say BEGIN TRANSACTION like this, hit Enter.
Now I want to update Bob's balance.
I'll say UPDATE "accounts SET "balance" equal to "balance" +
10 where the "id" = 2.
Bob's account ID is 2.
Now let me subtract $10 from Alice like this.
- 10.
I'll go back here and say where the "id" equals 1
for Alice's account, hit Enter.
But now I get that same constraint failure.
Alice has less than $0, which can't be possible.
So what do we do?
Instead of having another update, we could just roll back.
We could undo all of these previous statements here.
ROLLBACK like this, hit Enter, and now I should see from another perspective
here my table exactly as it was before with no intermediate step of Bob
having money but Alice having negative $10.
So let me ask m we've seen COMMIT and ROLLBACK.
What questions do we have on transactions now?
OK.
Seeing none so far, so let's keep going.
Transactions are helpful for ensuring that our data is consistent
like we just saw, and that they're also--
we have atomic transactions.
We can't break things down into smaller pieces.
But there is a case that transactions can help guard
against some adversarial kind of attack.
We're into what we call race condition.
A race condition is when we have multiple people, multiple processes
trying to access some value and also making a decision based on that value.
If unaddressed it can lead to a scenario that's inconsistent in our database.
And actually hackers can exploit race conditions
to bring our database to an inconsistent state in a way that benefits them.
So let's say our friends Charlie and Alice here, they
decide to rob our bank.
They decide to take money from it by exploiting race conditions.
And here are the logs of what Charlie and Alice actually did.
We see here that Charlie and Alice executed three concurrent transactions
with our bank.
On the one hand Charlie opened up his bank account
on two different computers.
He logged in and he said let me transfer $30 to Alice.
He at the same time clicked transfer on both computers knowing just well
he had only $30 to give to Alice, but he was going to send her $60 in this case.
He was hoping that we weren't guarding against race conditions.
That he could send $30 on both accounts to Alice.
Now at the same time Alice is at the ATM,
and they're hoping that at the same time Charlie presses transfer
Alice hits confirm on their transaction to withdraw $60 from the ATM.
And when all of these happen at once, we might
run into some inconsistent states in our database.
Let's say first we run this transaction here.
Let's focus on this one.
The first step is to check Charlie's balance.
Does Charlie have $30?
It seems like Charlie does.
We continue we might say, OK, let me add $30 to Alice's account like this.
Then let me subtract $30 from Charlie's account down below here.
And finally, that's the end of our transaction.
We checked Charlie's balance, we added $30 to Alice,
and subtracted $30 from Charlie.
But now at the same time, we're also processing the other transfer of $30
to Alice.
So here we check in terms of our time, top to bottom here--
we check Charlie's balance at this point.
It's still $30.
Knowing this, this process goes ahead and says
let's add $30 to Alice's account.
And now only later let's subtract $30 like this.
Now Charlie well appears to have no money in his account.
But at this time above we've already sent $30 to Alice's account two times.
And if Alice is waiting at the ATM over here
and they press Confirm on that withdrawal, what might happen
is something like this.
At that moment that Alice has $60 in their account--
they check and they see it-- they could then withdraw that $60.
And now that money is gone from our bank,
even if we realize Charlie shouldn't have been
able to make that transaction happen.
So what logically is a solution here?
It seems these transactions happened all at the same time.
But what would you do to reorder these statements to make it clear
that we can only do one at a time?
What would you do in this case to update this table to fix this problem?
AUDIENCE: I would do the withdrawal and the debits as one transaction.
So the subtraction is done and the addition
is done as one unit of work in order for the double transfer not to happen.
CARTER ZENKE: Yeah.
So ideally we should treat each of these as a separate transaction.
Literally a transaction in the database sense where if I go back to this table
if Charlie transfers $30 to Alice at roughly the same time,
I should handle these sequentially.
I should first do this one, then I should do this one.
And only after that should Alice be able to withdraw their $60, or at least
try to in this case.
So we need to make these transactions sequential, and the word for this
is isolating our transactions.
Here they are not isolated.
They're working at the same time.
But in reality I want them to be isolated--
happen one after another after another.
So ideally our table looks more like this.
Charlie hits transfer at the exact same time on two laptops,
but because we're working in transactions we only process one first.
We start with this one here.
We check the balance, we say let's add $30 to Alice's account and subtract $30
from Charlie's.
Once we're sure that is OK, we'll commit the transaction
and that is a done deal.
Now though, we'll go down below.
We'll say begin transaction.
We'll then say Charlie's balance is $0 because we're doing this
after we did our first transaction.
Charlie has no more money to give Alice.
At that point what we'll do is try to add $30 to Alice
but subtract $30 from Charlie, and we'll realize we made a mistake.
We should roll back and undo what we just did here.
So these now are separate transactions happening sequentially,
and we avoid our error of giving Alice $60 when
she shouldn't have that money at all.
And then only after this is done do we let Alice try to withdraw $60.
We'll go over here and see.
Alice tries to have a balance of $60, withdraw $60, and commit it.
But at this point she wouldn't actually have that money there.
So let's see now what questions do we have on the way transactions
are sequential in this case?
AUDIENCE: In particularly I want to ask that there are millions
of transactions that are going on.
Particularly, also, is it like there that sequentially these transactions
are being handled for the financial transaction over here
that because there are a number of banks in a single country
or international transactions.
Are they handle sequentially or there is some parallel earning mechanism
also exist if you may please clarify.
CARTER ZENKE: Yeah, good question.
So here visually we see these transactions are actually
sequential in the operation here.
And then your question is, are they literally sequential, like one
after another after another?
In reality they are very much just sequential like this.
A database can get creative with use of locks
as we'll see you in just a minute, but by and large they
are sequential one after the other.
And it's the job of a database module to ensure
that these transactions are executed sequentially in an isolated way.
Good question.
OK.
So let's see now how, if a database is able to make these sequential,
it must be using something underneath the hood
to ensure that these transactions don't interfere.
And in SQLite and other DBMSs we use this idea of a lock on the database
to ensure people can't access data when they really shouldn't be able to.
So here let's look at an idea of what SQLite
has at different kinds of locks on this database.
We have a few different kinds--
unlocked, shared, and exclusive, among some others here.
Each one has a different meaning for different processes.
So let's take a look here at our bank account table.
Let's say two computers want to access this account's table.
Well at this time because nobody is accessing our database, it is unlocked.
Anyone could read from the database, sort of see what's inside,
or write to it-- add some data or update some data.
But let's say we have one computer here who wants to read from this database.
They want to see what data is inside.
Well that database in SQLite would acquire
what's called a shared lock like this.
They're able to read the database but also
it's to allow others to read as well.
A shared lock means I'm only reading.
You too could read as well.
So let's say this computer comes in.
They decide to read from this table.
They could acquire the same shared lock.
And because we're only reading, not updating,
multiple transactions can read all at once.
We don't have to make these sequential.
But if we have a transaction that's hoping to write to the database,
to update some value--
well that's when things get a little weird.
I can't let somebody else read my data while I'm updating it.
So what I need is for this process here, if it's
writing, to acquire an exclusive lock.
Meaning this is the only computer, only transaction that
can read and write to this database.
All others must hold off in order to be sequential.
So we've seen transactions then are sequential
and they use this idea of a lock to ensure other folks
can't read when they're doing something sensitive like writing to the database.
Let me ask now what questions we have on locks and how they work for us here?
AUDIENCE: OK, my question is that suppose
you're one computer [INAUDIBLE].
For what amount this would allow to do the exclusive lock?
Maybe if the timestamp is larger, then some other computers
will get timeout exception and other things, right?
Because it's not allowed to do--
exclusively it's a lock.
How are we going to decide those things?
At what time one instance is going to be--
put the exclusive lock on the resource?
CARTER ZENKE: So the question is, at what point
does the transaction actually get an exclusive lock,
and how do we decide how to prioritize different transactions here?
Well there are a few algorithms you could use, one of which
is simply taking the transaction that just came first.
If at this point I receive a request for an exclusive lock,
I might just wait for others to finish reading and allow that one to proceed.
I could also use a process called time-stamping, which is similar to this
where I look at the timestamp, the time my database tried to write to the log
and use the one that is earliest in that case.
Now it's important to note that an exclusive lock does block others
from running their own transactions.
If I have an exclusive lock, no one else can run their transaction.
That is kind of a necessary downside in this case
to ensure that I don't make mistakes in updating my table.
Let's take one more here.
AUDIENCE: What's the granularity on locking?
I mean, you seem to say you locked the database, but that's craziness.
Do you lock a table or do you lock a record on a table?
CARTER ZENKE: Yeah, it might depend on the DBMS itself.
So at the very coarsest, a lock might just lock the entire database.
I can't actually see anything inside of it.
And I'll be able to demonstrate that for you in a minute here.
Let me go back to my computer.
Let me try to deliberately lock this database.
If I go to my terminal, I can begin a transaction that
automatically has an exclusive lock.
In SQLite the statement is BEGIN EXCLUSIVE.
BEGIN EXCLUSIVE TRANSACTION.
I'll hit Enter like this, and now I'm in the middle of this transaction.
It's exclusive.
Has an exclusive lock nobody else can read.
If I go back to my other terminal here, connect to my database,
I could try SELECT * FROM "accounts" just to read from this table.
And now I see Runtime error--
database is locked.
The entire database cannot be read from at the very coarsest level
of an exclusive lock.
Now because these locks are so coarse--
I have to lock the entire database, SQLite has its own module,
a way of prioritizing transactions and ensuring that a transaction only
has an exclusive lock for the duration it absolutely needs to.
Because otherwise you would slow down substantially
if I had to wait and wait and wait for somebody
to finish with their transaction.
OK.
So this then is how we can handle not just one query at a time but multiple.
And today we've seen how to optimize our databases from making sure queries
are faster to also making sure our databases use as little space as
possible.
We'll see next time how to actually scale up
our databases using other DBMSs--
like MySQL-- besides SQLite.
We'll see you next time.