Databases · Lesson 1.1
Reading every row to find a few
When you answer a question on Simplified, its server sends Postgres an INSERT.
Postgres adds one row to attempts, holding your user ID and the lesson's ID.
Rows go in as answers arrive, from every learner at once.
So Ada's rows, rows 1, 2 and 4, are spread among Ben's and Dee's.
Now say Simplified has grown, and attempts holds 400,000,000 rows.
Ada has answered 250 questions, so 250 of those rows are hers.
Then she opens her progress, so the server asks Postgres for her attempts.
So how does Postgres find Ada's 250 rows among 400,000,000?
The query is SELECT star FROM attempts WHERE user ID equals 1.
As with every WHERE, Postgres checks each row, one at a time.
Row 1 has user ID 1, so it passes. Row 2 passes too.
Row 3 is Ben's, with user ID 2, so it fails.
But Postgres doesn't know Ada has 250. It only has the rows, as the answers came in.
So any row it hasn't checked yet could be hers, even the very last one.
So it reads all 400,000,000 rows, to send back 250.
Reading every row of a table to answer a query is called a full scan.
A full scan means Postgres reads every row, and checks each one against the condition.
The rows are on disk, and reading 400,000,000 of them takes seconds.
But a page should open in a moment, and every learner who opens their progress waits through a full scan.
And what if a learner has no attempts yet?
Say Gia has just signed up, so she hasn't answered anything.
Her user ID is 7, so the server asks for attempts WHERE user ID equals 7.
Postgres checks row 1, then row 2, and on, all the way to the last row.
No row passes, so it sends back an empty result.
But it still read all 400,000,000 rows to find that out.
So a full scan costs the same, whether a learner has 250 rows or none.
So what would a full scan mean for Instagram's search?
Say you search Instagram for Cristiano Ronaldo's username, cristiano.
Instagram has over 2 billion accounts.
With a full scan, it would check every one of them, for one search.
Yet Instagram's search answers in a moment, so it can't be reading every account.
A full scan reads every row, however few rows it sends back.
Simplified's attempts table holds 400,000,000 rows, one for each answer any learner has given. Its rows are in the order the answers arrived. Dee, whose user_id is 4, has given 90 answers. Simplified's server sends Postgres SELECT * FROM attempts WHERE user_id = 4;.
How many rows does Postgres read to answer it?
Explanation
First, the rows are in no order by learner, so any row could be one of Dee's, even the last.
Then, Postgres does a full scan: it checks every row against user_id = 4.
Therefore, it reads all 400,000,000 rows, to send back Dee's 90.
Simplified's attempts table holds 400,000,000 rows, one for each answer a learner has given, in the order the answers arrived. Ada has 250 rows in it, and Ben has 40. Simplified's server sends Postgres two queries: SELECT * FROM attempts WHERE user_id = 1; for Ada, then SELECT * FROM attempts WHERE user_id = 2; for Ben.
How many rows does Postgres read for the two queries together?
Databases · Lesson 1.2
A sorted copy of one column
So finding Ada's 250 attempts means a full scan of 400,000,000 rows.
Because the rows are in no order by learner, Postgres can't skip any of them.
So how could Postgres go straight to Ada's rows?
Think of the Contacts app on your iPhone.
Your contacts are sorted A to Z, by name.
Down the side runs the alphabet, from A to Z.
Tap M, and you're at the M's, with Mom right there.
You never scroll past A to L: the names are sorted, so the M's are all together.
But Postgres can't sort attempts itself, because new answers arrive every moment.
So it keeps a sorted copy of the user ID column, beside the table.
To ask for that copy, Simplified's server sends a new statement: CREATE INDEX.
Like CREATE TABLE, it makes something new: a sorted copy, not a table.
After ON comes the table, attempts, and in brackets, the column to copy, user ID.
Postgres copies the user ID out of every row of attempts, and sorts them: 1, 1, 1, 2, 2, 4, 4.
Beside each one, it keeps the row it came from.
So Ada's three 1s say row 1, row 2 and row 4.
That sorted copy is called an index.
An index is a sorted copy of one column, where each entry says where its row is.
attempts itself stays just as it was, in the order the answers came in.
And where did Ben's answers go?
Ben's user ID is 2, and his answers are rows 3 and 6 of attempts.
In the table, they're apart, with Ada's row 4 and Dee's row 5 between them.
In the index, his two entries sit together, right after Ada's 1s.
One says 2 and row 3, and the other says 2 and row 6.
An index is a sorted copy of one column, kept beside the table, each entry saying where its row is.
Say Simplified's attempts table holds four rows, in the order the answers arrived: row 1 has user_id 4, row 2 has user_id 2, row 3 has user_id 4, and row 4 has user_id 1. Simplified's server sends Postgres CREATE INDEX ON attempts (user_id);.
What is the index's first entry?
Explanation
First, the index copies the user_id from every row, and sorts them: 1, 2, 4, 4.
Then, each entry keeps the row it came from, and the 1 came from row 4.
Therefore, the first entry is user_id 1, row 4.
Simplified's attempts table holds its rows in the order answers arrived, so the first three rows hold user_ids 1, 1 and 2. Simplified's server sends Postgres CREATE INDEX ON attempts (user_id);.
What happens to the order of attempts' own rows?
Simplified's attempts table has an index on user_id. Ben's user_id is 2, and his two answers are rows 3 and 6 of attempts.
What do Ben's two entries in the index hold?
Say Simplified's attempts table holds three rows, in the order the answers arrived: row 1 has user_id 5, row 2 has user_id 3, and row 3 has user_id 5. Simplified's server sends Postgres CREATE INDEX ON attempts (user_id);.
What does the index hold, in order?
Simplified's attempts table has three columns: id, user_id and lesson_id. Say Simplified's server sends Postgres CREATE INDEX ON attempts (lesson_id);.
What does the new index hold?
Simplified's attempts table gets a new row every time any learner answers a question.
Why does Postgres keep a sorted copy of user_id beside attempts, instead of sorting attempts' rows by user_id?
Simplified's attempts table holds 400,000,000 rows. Simplified's server sends Postgres CREATE INDEX ON attempts (user_id);.
How many entries does the new index hold?
Databases · Lesson 1.3
Going straight to the right rows
So attempts now has an index on user ID: every user ID, sorted, each with its row.
And Ada's progress still sends the same query as before.
So how does Postgres use the index to find Ada's attempts?
The query is SELECT star FROM attempts WHERE user ID equals 1.
Postgres sees there's an index on user ID, and uses it by itself.
Like the A to Z down the side of Contacts, the index keeps signposts to where each user ID starts.
So Postgres goes straight to the 1s, at the top.
It reads Ada's entries, and follows each one to her row: 1, 2 and 4.
With 400,000,000 rows, that's her 250 entries and 250 rows, not every row.
And what about Gia, who has no attempts yet?
Gia's user ID is 7, so Postgres goes straight to where the 7s would be, after the 4s.
There are none, so it stops, and sends back an empty result at once.
Without the index, it read all 400,000,000 rows to find that out.
So how might Instagram find cristiano among over 2 billion accounts?
Instagram's accounts might have an index on their username column.
The usernames are sorted, so its database goes straight to where cristiano sits.
Then it follows that entry to Ronaldo's account, without reading the other 2 billion.
An index keeps one column in order, so Postgres goes straight to the rows it needs.
Simplified's attempts table holds 400,000,000 rows, and has an index on user_id. Dee, whose user_id is 4, has given 90 answers. Simplified's server sends Postgres SELECT * FROM attempts WHERE user_id = 4;.
How many rows of attempts does Postgres read?
Explanation
First, Postgres uses the index on user_id, and goes straight to the 4s.
Then, it reads Dee's 90 entries, and follows each one to its row.
Therefore, it reads 90 rows of attempts, not all 400,000,000.
Simplified's attempts table holds 400,000,000 rows and has an index on user_id. Ada, whose user_id is 1, has 250 rows in it. Fay, whose user_id is 6, hasn't answered any questions yet. Simplified's server sends Postgres SELECT * FROM attempts WHERE user_id = 1; and then SELECT * FROM attempts WHERE user_id = 6;.
How many rows of attempts does Postgres read for the two queries together?
An index on attempts' user_id holds, in order, the user_ids 1, 1, 1, 2, 2, 4, 4. Cy's user_id is 3. Simplified's server sends Postgres SELECT * FROM attempts WHERE user_id = 3;.
Where in the index does Postgres look?
For months, Simplified's server has sent SELECT * FROM attempts WHERE user_id = 1;, and Postgres has done a full scan each time. Today the server sends Postgres CREATE INDEX ON attempts (user_id);.
What has to change in the progress query for Postgres to use the new index?
Simplified's attempts table holds 400,000,000 rows and has an index on user_id. Ben, whose user_id is 2, has 40 rows in it. Simplified's server sends Postgres SELECT * FROM attempts WHERE user_id = 2;.
How many fewer rows of attempts does Postgres read than it would with no index?
Say Spotify's songs table might have an index on its title column, sorted A to Z, with each entry saying where its row is. You search for the song Yellow.
What does Spotify's database do?
Simplified's attempts table has an index on user_id. In order, its entries are: 1 (row 1), 1 (row 2), 1 (row 4), 2 (row 3), 2 (row 6), 4 (row 5), 4 (row 7). Simplified's server sends Postgres SELECT * FROM attempts WHERE user_id = 2;.
Which rows of attempts does Postgres read?
Databases · Lesson 1.4
Why not index every column?
So with an index on user ID, Ada's progress reads her 250 rows, not 400,000,000.
So why not put an index on every column?
Say Ada answers one more question, in lesson 3.
The server sends an INSERT, and Postgres adds row 8 to attempts: user ID 1, lesson ID 3.
But the index has to stay sorted, and hold an entry for every row.
So Postgres also adds an entry to it, 1 and row 8, in its place after the other 1s.
So her one answer is now two writes: the row, and its entry in the index.
So every INSERT also adds an entry to every index on the table.
Say attempts also had an index on lesson ID.
Then Ada's answer writes row 8, an entry in the user ID index, and an entry in the lesson ID index.
That's three writes for one answer.
And every learner's answer, every day, pays those three writes.
And where do all those entries go?
On disk, beside the table, so they survive a restart, like the rows.
The user ID index holds an entry for every row: 400,000,000 entries.
So every index takes extra disk: a second copy of its column.
So an index makes reads by its column faster, but every INSERT slower, and the disk fuller.
That's why Simplified indexes user ID: every progress page searches by it.
But a column nobody searches by gets no index. It would cost on every answer, and speed up nothing.
An index trades slower writes and more disk for faster reads.
Simplified's attempts table has an index on user_id and an index on lesson_id. Ben answers 3 questions, so Simplified's server sends Postgres 3 INSERTs into attempts, one for each answer.
How many index entries do those 3 INSERTs add?
Explanation
First, every INSERT adds an entry to every index on the table: here, 2 for each INSERT.
Then, Ben's answers are 3 INSERTs: .
Therefore, they add 6 index entries, as well as Ben's 3 new rows.
Say a table has 2 indexes. Its app sends Postgres 10 INSERTs, each adding one row.
Counting each new row and each new index entry as one write, how many writes do the 10 INSERTs make in all?
Simplified's attempts table holds 400,000,000 rows and has no index on user_id. Simplified's server sends Postgres CREATE INDEX ON attempts (user_id);.
Which of these does Simplified now do with more work than before?
Simplified's attempts table gets an INSERT every time any learner answers a question. Its progress page searches attempts with WHERE user_id = …, and nothing ever searches attempts by lesson_id.
Which indexes should Simplified give attempts?
Say Simplified's attempts table holds 400,000,000 rows, and has an index on user_id and an index on lesson_id.
How many index entries do those two indexes store on disk in all?
Simplified's attempts table has an index on user_id. Say the machine Postgres runs on restarts at 3 am.
What happens to the index?
Say an app keeps a log table that gets a million INSERTs a day, one for each event, and no query ever searches it with WHERE.
Should it have an index on its timestamp column?