Database Internal and Indexes

Row_id

• row_id is an internal and system-maintained ID

• In certain databases, it’s the same as the primary key, but other databases like Postgres have a system column row_id (tuple_id)

Page

• Depending on the storage model (row vs column), the rows are stored and read in logical pages

• The database DOES NOT read a single row; it reads A PAGE or more in a single IO

• Each page has a size - example 8KB in PostgreSQL, 16KB in MySQL

So let’s say each page can hold 3 rows. With 1,001 rows, we will have approximately 333 pages.

IO

• IO operation (input / output) is a read request to the disk

• We try to minimize this as much as possible, as they are expensive

• An IO can fetch 1 page or more but cannot fetch a single row

Heap

• Heap is a data structure where the table is stored with all its pages one after another

• Traversing the heap is expensive as we need to read so much data to find what we want

Index

• An index is a data structure separate from the heap that has “pointers” to the heap => it tells EXACTLY which page to fetch in the heap

• It holds a part of the data and is used to search for something quickly. Yes, it just copies part of our database, and they need to be updated whenever the underlying table changes. => Don’t index everything, or it will slow your DB

• We can index on one column or more

• Once we find a value of the index, we go to the heap to fetch more information, where everything is there

• Index is also stored as pages and costs IO to pull the entries of the index => Keep index small so it can fit in memory for faster search

Where to add indexes

We cannot just look at the schema, but need to look at our query pattern

Where clauses with high cardinality

select * from users where name = "Huy"

Order by

Reason: Data has already been sorted in index

select * from users order by birthday;

Cardinality and Selectivity

• Cardinality: the number of distant values in the column

• Selectivity: the ratio

Let’s say we have a boolean isAdmin: bool - The cardinality is low here as we only have 2 values: true or false (cardinality= 2). If we have a million rows, the index on this column doesn’t help much narrow down the data. Here we also need to look at the selectivity

// calculate cardinality
select count(distinct birthday) from users;

// is that selective
select (count(distinct birthday)::decimal / count(*):: decimal)::decimal(7,4) from users;

// results: 0.011
// 🚀 The closer to 1 the better

Then again, we need to examine the query pattern. It doesn’t make sense to add an index on a field which we never query!

Composite indexes

We can enhance query performance by indexing multiple columns together. For optimal efficiency, the most frequently used query conditions should be placed at the beginning of the index.

Let’s create a composite index

create index multi on users using btree(first_name, last_name, birthday);

// ORDER MATTERS
- first_name
- last_name
- birthday

1. We have to go left to right

No index is used here. It’s because we are skipping the first_name

explain select * from users where last_name = 'Last_name_15';

// ‼️ Result - No index used
 Gather  (cost=1000.00..16587.93 rows=996 width=44)
   Workers Planned: 2
   ->  Parallel Seq Scan on users  (cost=0.00..15488.33 rows=415 width=44)
         Filter: (last_name = 'Last_name_15'::text)
(4 rows)

// ordering doesn't matter on the query side
explain select * from users where last_name = 'Last_name_15' and first_name = 'First_name_7';

// Results - Index used
 Index Scan using multi on users  (cost=0.42..8.45 rows=1 width=44)
   Index Cond: ((first_name = 'First_name_7'::text) AND (last_name = 'Last_name_15'::text))
(2 rows)

2. No Skipping

Even if we skip the last_name, PG still uses the first_name to narrow down the results. And from here, it will scan the birthday.

// We skip the last_name
explain select * from users where first_name = 'First_name_7' and birthday = '2003-10-30';

// ‼️ Results: index is used
 Index Scan using multi on users  (cost=0.42..42.39 rows=1 width=44)
   Index Cond: ((first_name = 'First_name_7'::text) AND (birthday = '2003-10-30'::date))
(2 rows)

If we are not skipping the last_name, Index is fully used - No filtering step

explain select * from users where first_name = 'First_name_7' and last_name = 'Last_name_15' and birthday = '2003-10-30';

// Results
 Index Scan using multi on users  (cost=0.42..8.45 rows=1 width=44)
   Index Cond: ((first_name = 'First_name_7'::text) AND (last_name = 'Last_name_15'::text) AND (birthday = '2003-10-30'::date))
(2 rows)

3. Stop at the first range

In a compound index, PostgreSQL can use the index efficiently for equality conditions from left to right until they hit a range condition like (<, >, Between)

Index on (a, b, c)

create index first_last_birth on users using btree(first, last, birth)

create index first_birth_last on usrs using btree(first, birth, last)

explain select * form users where first = 'A' and last = 'B' and birthday < '1989-12-31'

// result: it will use the first_last_birth as it's more efficient to
// scan first and last directly and from the results, it filters the birthday

Example with PostgreSQL

We have a table called employees which has a million rows. The primary key is automatically indexed using B-tree

CREATE TABLE employees (
  id SERIAL PRIMARY KEY,
  name TEXT NOT NULL,
  age INT,
  address TEXT
);

Find by id

// 1
explain analyze select id from employees where id = 2000;

// result
// Since we only select id, it can fetch that data from the (Index Only)
// no need to access the heap
Index Only Scan using employees_pkey on employees  
(cost=0.42..4.44 rows=1 width=4) 
(actual time=0.041..0.043 rows=1 loops=1)
   Index Cond: (id = 2000)
   Heap Fetches: 0
 Planning Time: 0.131 ms
 Execution Time: 0.079 ms
(5 rows)

// 2
explain analyze select id, name, age from employees where id = 2000;

// result 
// Here we also select name and age which aren't stored in index
// Postgres fetches id from the index, then accesses the heap for the rest
 Index Scan using employees_pkey on employees  (cost=0.42..8.44 rows=1 width=19) (actual time=0.140..0.142 rows=1 loops=1)
   Index Cond: (id = 2000)
 Planning Time: 1.004 ms
 Execution Time: 0.271 ms
(4 rows)

Find by name

explain analyze select id from employees where name = 'Name_3';

// Results
//  Parallel Seq Scan => Full table scan
 Gather  (cost=1000.00..14541.43 rows=1 width=4) (actual time=1.659..93.076 rows=1 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on employees  (cost=0.00..13541.33 rows=1 width=4) (actual time=50.701..80.321 rows=0 loops=3)
         Filter: (name = 'Name_3'::text)
         Rows Removed by Filter: 333333
 Planning Time: 0.235 ms
 Execution Time: 93.123 ms
(8 rows)

Find by name with like

explain analyze select id, name from employees where name like '%ZA%'

// Results
// It will do a full stable scan even we have an index on the name ‼️
// Reason: like is NOT a single value, and B-tree doesn't support it

Having the index doesn’t mean the DB will use it. Postgres will create a plan and use whatever it thinks the best

explain select name from employees where id < 100;

// Result: ok 100 rows, I can check the index
Index Scan using employees_pkey on employees  (cost=0.42..10.19 rows=101 width=11)
   Index Cond: (id < 100)

explain select name from employees where id < 1000000;

// Result: too many rows, I rather reach out for the HEAP ‼️
Seq Scan on employees  (cost=0.00..20833.00 rows=999999 width=11)
   Filter: (id < 1000000)

Understanding query planner

// Query plan
- (Parallel) Seq Scan
- Index Scan
- Index Only Scan

// cost in ms
// first number: how many ms to fetch the first row - PG decides to do some work BEFORE fetching
// second number: the finished time
cost=0.00...289025

// estimation: approximate the number of rows it's gonna fetch (statistically)
// width: bytes of a row - AFFECTED if we select * ‼️
rows=123221 width=31

Conclusion

1. Without an index, WHERE clause doesn’t make the query faster in large tables

2. Having the index doesn’t mean the DB will use it - see the like case

B-tree