Databases · Lesson 2.1
Which searches does an index speed up?
So Simplified's server sent CREATE INDEX ON attempts, with user ID in brackets.
Now Ada's progress goes straight to her 250 rows, instead of reading all 400,000,000.
Say Simplified's analytics page shows how learners did on lesson 2's quiz.
So it asks Postgres for attempts WHERE lesson ID equals 2.
So does the index on user ID find lesson 2's rows too?
Think of your iPhone's Contacts again.
They're sorted by name, so Mom is one tap away.
But say you want everyone with a number starting with 415.
Alex, Liam and Zoe have one, and they're spread down the whole list.
The names are in order, but the numbers aren't.
So the only way to find them all is to scroll through every contact.
The index on user ID has the same problem.
Its entries are sorted by user ID: Ada's three 1s, then Ben's 2s, then Dee's 4s.
In these seven rows, lesson 2's are row 2 and row 6.
Row 2 is one of Ada's answers, so its entry sits among the 1s.
Row 6 is one of Ben's, so its entry sits among the 2s.
And the index holds only user IDs, so nothing in it even says which lesson a row is from.
So the index can't take Postgres to lesson 2's rows.
So Postgres does a full scan, checking every row's lesson ID against 2.
Rows 2 and 6 pass, and every other row fails.
With 400,000,000 rows, it reads them all, just as if there were no index.
An index helps only a WHERE on the column it's sorted by.
So which searches does the user ID index speed up?
Say Ben opens his progress, so the server asks for attempts WHERE user ID equals 2.
That's a search by user ID, the column the index is sorted by.
So Postgres goes straight to the 2s, and follows them to rows 3 and 6.
So how could lesson 2's quiz be found quickly too?
Simplified would send CREATE INDEX ON attempts, with lesson ID in brackets.
Postgres builds a second index, sorted by lesson ID.
There, lesson 2's entries sit together, pointing at rows 2 and 6.
But that's a second price to pay: every answer now adds an entry to both indexes.
An index is sorted by one column, so it speeds up only searches by that column.
Simplified's attempts table holds 400,000,000 rows, and it has an index on user_id and none on lesson_id. Simplified's analytics page sends Postgres SELECT * FROM attempts WHERE lesson_id = 3;.
Does the index on user_id help find lesson 3's rows?
Explanation
First, the index is sorted by user_id, and holds only user_ids, so it can't say where lesson 3's rows are.
Then, Postgres has no index on lesson_id, so it does a full scan of all 400,000,000 rows.
Therefore, no: the index on user_id doesn't help.
Say Spotify keeps a songs table with columns id, title, album and artist, and has an index on artist, but none on title or album.
Which of these searches goes straight to its rows, instead of reading every row?
Databases · Lesson 2.2
Is every login a full scan?
So an index speeds up only searches on its column.
And attempts got its user ID index because Simplified's server sent CREATE INDEX.
But every time you log in, Simplified's server searches users by email.
It asks for users WHERE email equals ada at simplified dot org, among 2,000,000 learners.
And Simplified never sent CREATE INDEX for users.
So is every login a full scan of 2,000,000 rows?
users' email column has UNIQUE, so no two rows may hold the same email.
Say someone signs up again with ada at simplified dot org.
To refuse it, Postgres must check whether that email is already in users.
And with a full scan, every sign-up would read all 2,000,000 rows.
So when email got UNIQUE, Postgres built an index on it, sorted by email.
It goes straight to ada at simplified dot org, finds it there, and refuses the row with an error.
So UNIQUE builds an index on its column, by itself.
Postgres named it users email key, the same name as in that error.
So when Ada logs in, Postgres uses that index, because the search is by email.
It goes straight to ada at simplified dot org, and follows it to row 1.
So logging in was never a full scan.
Once Ada has logged in, her Learn page asks for her row WHERE ID equals 1.
So does that search read all 2,000,000 rows?
A primary key is NOT NULL and UNIQUE together.
So a PRIMARY KEY builds an index too, on ID.
Postgres named it users p key, short for primary key.
So Postgres uses it for WHERE ID equals 1.
It goes straight to 1, and follows that entry to Ada's row.
So even a search for ID 1 never really checked all 2,000,000 rows.
attempts' ID is its primary key too, so attempts came with an index on ID.
Postgres named it attempts p key.
So a key that must be unique, UNIQUE or PRIMARY KEY, comes with an index.
Simplified's users table holds 2,000,000 rows. Its email column has UNIQUE, and Simplified has never sent CREATE INDEX for users. Dee logs in, so Simplified's server sends Postgres SELECT * FROM users WHERE email = 'dee@simplified.org';.
How many rows of users does Postgres read?
Explanation
First, UNIQUE on email built an index on email, users_email_key, so Postgres uses it for this search.
Then, it goes straight to dee@simplified.org, and follows that one entry to its row.
Therefore, it reads 1 row of users, not 2,000,000.
Simplified's users table is created with these four rules, and Simplified never sends CREATE INDEX for it.
Which rule makes Postgres build an index by itself?
Simplified's users table holds 2,000,000 rows, its email column has UNIQUE, and Simplified has never sent CREATE INDEX for users. Hal signs up with hal@simplified.org, an email no one has used.
To check that his email isn't taken, how many rows of users does Postgres read?
Simplified's users table holds 2,000,000 rows, its email column has UNIQUE, and Simplified has never sent CREATE INDEX for users. Someone signs up with ben@simplified.org, which is already Ben's.
How does Postgres find out the email is taken?
A second sign-up with ada@simplified.org is refused, and Postgres sends back ERROR: duplicate key value violates unique constraint "users_email_key". Simplified never sent CREATE INDEX for users.
What is users_email_key?
Simplified's users table has id integer PRIMARY KEY and email text NOT NULL UNIQUE. Its other columns, name, xp and created_at, have no PRIMARY KEY or UNIQUE, and Simplified has never sent CREATE INDEX for users.
How many indexes does users have?
Simplified's users table holds 2,000,000 rows, and its id column is its PRIMARY KEY. Simplified has never sent CREATE INDEX for users. Dee's Learn page sends Postgres SELECT name, xp FROM users WHERE id = 4;.
How many rows of users does Postgres read?
Databases · Lesson 2.3
The index you add yourself
So UNIQUE and PRIMARY KEY each came with an index: users email key, users p key and attempts p key.
But Ada's progress searches attempts by user ID, and that was a full scan.
So why didn't attempts' user ID come with an index?
User ID is a foreign key, written REFERENCES users, with ID in brackets.
When an answer comes in, Postgres checks its user ID in users, using users p key.
But a foreign key builds no index on its own column.
Postgres leaves that to you.
And what about attempts' lesson ID?
Lesson ID is a foreign key too, written REFERENCES lessons, with ID in brackets.
When an answer comes in, Postgres checks its lesson ID in lessons, using lessons' primary key index.
And Postgres builds no index on lesson ID either.
So a search of attempts by lesson ID is a full scan.
So nothing sorted held attempts' user IDs, and Ada's progress read every row.
That's why Simplified's server sent CREATE INDEX ON attempts, with user ID in brackets.
Postgres named that index attempts user ID idx, short for index.
PRIMARY KEY and UNIQUE each come with an index, but a foreign key doesn't.
Simplified's attempts table has id integer PRIMARY KEY, user_id integer NOT NULL REFERENCES users (id) and lesson_id integer NOT NULL REFERENCES lessons (id). No one has sent CREATE INDEX for attempts yet.
How many indexes does attempts have?
Explanation
First, the PRIMARY KEY on id builds an index: attempts_pkey.
Then, user_id and lesson_id are foreign keys, and a foreign key builds no index.
Therefore, attempts has 1 index, on id.
Simplified's attempts table has lesson_id integer NOT NULL REFERENCES lessons (id), a foreign key, and Simplified has never sent CREATE INDEX on lesson_id. attempts holds 400,000,000 rows.
What happens when the server sends SELECT * FROM attempts WHERE lesson_id = 2;?
Simplified's attempts table has user_id integer NOT NULL REFERENCES users (id), and users' id is its PRIMARY KEY, with the index users_pkey. Ada, whose id is 1, answers a question, so the server sends an INSERT into attempts with user_id 1.
How does Postgres check that user 1 exists?
Simplified's attempts table has lesson_id integer NOT NULL REFERENCES lessons (id), and lessons' id is its PRIMARY KEY. A learner answers a question in lesson 3, so the server sends an INSERT into attempts with lesson_id 3.
How does Postgres check that lesson 3 exists?
Say Reddit keeps a comments table with id integer PRIMARY KEY, permalink text NOT NULL UNIQUE and user_id integer NOT NULL REFERENCES users (id). It holds 500,000,000 comments, and no one has sent CREATE INDEX for it.
Which search of comments goes straight to its rows?
Simplified's users table has indexes users_pkey, on id, and users_email_key, on email. Simplified's attempts table has attempts_pkey, on id, and attempts_user_id_idx, on user_id.
Which of these queries reads every row of its table?
Simplified's attempts table has id integer PRIMARY KEY, user_id integer NOT NULL REFERENCES users (id) and lesson_id integer NOT NULL REFERENCES lessons (id). Simplified's server has sent one CREATE INDEX for it: CREATE INDEX ON attempts (user_id);.
How many indexes does attempts have now?
Databases · Lesson 2.4
Checking without guessing
So users came with users p key and users email key, from its keys.
And attempts has attempts p key, and attempts user ID idx, the one Simplified made.
But a query never names an index: logging in is still SELECT star FROM users WHERE email equals Ada's email.
Postgres decides by itself: read every row, or go straight there with an index.
So how can you check which way Postgres goes, without guessing?
You put EXPLAIN in front of the query.
EXPLAIN sends back Postgres's plan for the query, instead of running it.
The plan is the steps Postgres would take: read every row, or use an index.
Say Simplified's server sends EXPLAIN, then the login query, for Ada's email.
Postgres doesn't send back Ada's row. It sends back the plan.
Its first line says Index Scan, using users email key.
An Index Scan means Postgres would use the index it names to go straight to the matching rows.
Its second line, Index Cond, is what it would look up there: Ada's email.
And what does the plan say for a search with no index?
Say the server sends EXPLAIN, then SELECT star FROM attempts WHERE lesson ID equals 1.
Its first line says Seq Scan on attempts.
A Seq Scan, short for sequential scan, is Postgres's name for a full scan.
It would read every row, one after another.
Its second line, Filter, is the condition it would check on each row: lesson ID equals 1.
So this search would read all 400,000,000 rows: the sign of a missing index.
And EXPLAIN read none of them: it only sent back the plan.
So what does EXPLAIN do with a DELETE?
Say the server sends EXPLAIN, then DELETE FROM users WHERE ID equals 3, Cy's ID.
The plan says Postgres would find Cy's row with users p key, then delete it.
But EXPLAIN runs nothing, so nothing is deleted.
Cy's row is still in users, just as before.
EXPLAIN shows the way Postgres would go, and never runs the query.
Simplified's users table holds Ada's row, with id 1 and 120 XP. Simplified's server sends Postgres EXPLAIN UPDATE users SET xp = 0 WHERE id = 1;.
What is Ada's xp afterwards?
Explanation
First, EXPLAIN sends back the plan for the UPDATE, instead of running it.
Then, the UPDATE never runs, so no row changes.
Therefore, Ada's xp is still 120.
Simplified's users table holds 2,000,000 rows, has an index on email, users_email_key, and holds Ben's row, with the email ben@simplified.org. Simplified's server sends Postgres EXPLAIN SELECT * FROM users WHERE email = 'ben@simplified.org';.
What does Postgres send back?
Simplified's users table holds 2,000,000 rows, and 5,000 learners in it have 0 XP. Simplified's server sends Postgres EXPLAIN DELETE FROM users WHERE xp = 0;.
How many rows does users hold afterwards?
Simplified's team finds that the analytics page, which shows how learners do on quizzes, loads slowly. They want to know whether Postgres reads every row of a table to answer the page's query, without changing anything.
What should they do?
Simplified's server sends Postgres EXPLAIN SELECT * FROM users WHERE xp = 300;, and Postgres sends back Seq Scan on users / Filter: (xp = 300).
What would Postgres do to answer the query?
Simplified's users table has two indexes: users_pkey on id and users_email_key on email. It has no index on xp. Simplified's server sends Postgres EXPLAIN SELECT * FROM users WHERE xp = 40;.
Which plan does it get back?
Simplified's users table holds 2,000,000 rows and has two indexes: users_pkey on id and users_email_key on email.
Which query's plan starts with Index Scan using users_email_key on users?