What is a transaction? 🔁

flowchart TD
    start[DB Starting State] -->
    begin[BEGIN Transaction] --> work[One unit of work]
    work --> commit[COMMIT Transaction]
    work --> rollback[ROLLBACK Transaction]
    rollback --> start

BEGIN TRANSACTION;
SELECT balance FROM accounts WHERE account_id = 1;

balance - 100 > 0;

UPDATE accounts SET balance = balance - 100
WHERE account_id = 1;

COMMIT TRANSACTION;

Atomicity

• All queries in a transaction must succeed,
  or the transaction must be rolled back.

• Even if 1/100 query fails,
  the entire transaction must be rolled back.

• It the database went down prior to a commit of a transaction,
  the transaction must be rolled back.

flowchart TD
    start[DB Starting Snapshot] -->
    begin[BEGIN Transaction] --> update_1[Queries 5/100]
    update_1 --> db_crash{DB CRASH}
    db_crash -->|yes| cleanup[DB Cleanup / Rollback]
    db_crash -->|no| COMMIT[COMMIT Transaction]
    cleanup --> start

Isolation

Consistency

• Consistency in data is user defined (DBA team)
  Referential integrity (through foreign keys) data is inconsistent across tables.
  Atomicity, isolation affects consistency.

  Data consistency between tables,

  id

  blob

  likes

  1

  a

  1

  2

  b

  2

  users

  id

  Mate

  1

  Mark

  1

  Jack

  2

• Consistency in reads,

  mermaid

  flowchart LR
   data --> |update| db[(DB)] --> |read| data

  If a transaction update a row,
  will the change be immediately visible during a read?.

  Both SQL and NoSQL databases suffer from this problem.

• Eventual consistency

  mermaid

  flowchart LR
   data_v1 --> |update| db[(DB)] -->
   |read| data_v2
   db --> |read| data_vn
   db --> |read| data_v1

  You will eventually get the latest version of the data.

  mermaid

  flowchart LR
    master_db[(Master - X)]
    slave_1_db[(Follower - Z)]
    slave_2_db[(Follower - Z)]
    data -->|updated to x| master_db
    master_db --> slave_1_db
    master_db --> slave_2_db
    slave_1_db -->|Inconsistent data| read

  mermaid

  flowchart LR
    master_db[(Master - X)]
    slave_1_db[(Follower - X)]
    slave_2_db[(Follower - X)]
    data --> master_db
    master_db -->|replicate| slave_1_db
    master_db -->|replicate| slave_2_db
    slave_1_db -->|Consistent data| read

  When we introduce caching or we introduce horizontal scaling,
  you are eventually consistent.

  If you do not have atomicity,
  or have inconsistent data,
  you do not have consistency at all.

Durability

• Process of persisting data to disk (non-volatile storage).

• Durability slows write down,
  write to disk is slower than write to memory

• Durability techniques

  • WAL - Write ahead log / AOF - Append only file

    Any change to the database is written to a log file, the log file is flushed to disk.

    mermaid

    flowchart LR
     data --> |update| db[(DB)] --> |write| log[(Log)] --> |flush| disk[(Disk)]

    mermaid

    flowchart LR
     db[(DB)]
     log[(Log)]
     disk[(Disk)]
     log --> db
     disk --> db
     db --> reconstructed_db[(DB reconstructed)]

    Writing all the changes to disk is expensive (indexes, data, files, rows...)
    The log file is a compressed version of the data stored in the database.

    mermaid

    flowchart LR
        db[(DB)] --> |flush request| os -->
        os_cache[(OS Cache)] -->
        |batched flushes| disk[(Disk)]
    
        db --> |fSync| disk

    fSync forces the OS to flush the data to disk.
    This prevents data loss in case of OS crash.

  • Async snapshots

    mermaid

    flowchart LR
     data --> |update| db[(DB)] --> |async| snapshot[(Snapshot)] --> |flush| disk[(Disk)]
     db --> |sync| snapshot[(Snapshot)]

    Asynchronously write the data to disk

Serializability vs Repeatable reads

flowchart LR
    transaction_1[BEGIN transaction_1] --> read_1[a, a, b, b] --> |update a's to b's|update_1[b, b, b, b] --> commit
    transaction_2[BEGIN transaction_2] --> read_2[a, a, b, b] --> |update b's to a's|update_2[a, a, a, a] --> commit -->
    result[a, a, b, b]

flowchart LR
    transaction_1[BEGIN transaction_1] --> read_1[a, a, b, b] --> |update a's to b's|update_1[b, b, b, b] --> commit --> result[a, a, b, b]
    transaction_2[BEGIN transaction_2] --> read_2[a, a, b, b] --> |update b's to a's|update_2[a, a, a, a] --> commit_error[Could not serialize transaction]

How tables and indexes are stored on disk?

flowchart TD
    heap[(Heap)]
    index[(Index)]
    indexed_query --> |select|index --> |page,row|heap --> |row|indexed_query

Row vs Column oriented databases

flowchart TD
    page_1[1-200,name,age]
    page_2[200-400,name,age]
    page_3[400-500,name,age]
    sum[sum age] --> |fetch| page_1 --> |fetch| page_2 --> |fetch| page_3

flowchart TD
    page_1[age: 1:row_id-500:row_id]
    sum[sum age] --> |fetch| page_1

Primary key vs Secondary key

There is no order maintained by default in the table,

Clustering, order enforced by the database on a table,
through a primary key or secondary key.

Postgres Clustered table / heap organised table, mySQL Index ordered table

Primary key is order inforced on the table itself,
Secondary key is order inforced through an index table on the actual table.

Adding rows in a secondary key enforced table is slow,
since you need to update the secondary index table.

Buffer pool

flowchart LR
  heap[(Heap)]
  index[(Index)]
  buffer_pool[(Buffer pool)]
  wal[(WAL)]
  read_query --> |select|index --> |select|heap --> |page,row|buffer_pool --> |row|wal
  update_query --> buffer_pool --> wal

To reduce the number of IO's,
all row reads are stored in a buffer pool temporarily,
this allows for subsequent reads / writes to be served from the buffer pool,
thus reducing the number of IO's.

Creating table with random vaues.

insert into temp (t) select random()*100 from generate_series(0,100000)

Explaining the explain command

Returns statistics about the query plan,

explain select * from temp where t > 50;
Seq Scan on temp  (cost=0.00..2087.00 rows=100000 width=4)

• Scan types ( Seq vs Index )

• Cost Time to start executing the query,
  Time to finish executing the query

• Rows
  Number of rows return

• Width
  Avg size of returned rows in bytes

Creating an index

create index temp_t_idx on temp(t);

Without index scan,

Seq Scan on temp  (cost=0.00..1443.01 rows=100001 width=4)

With index scan,

Index Only Scan using temp_temp_idx on temp  (cost=0.29..1258.40 rows=59549 width=4)

If info is available in the index, the database will not do a heap lookup.
Dont ask for more info than you need, ask for stuff in the index if possible.

With an index search,

• Time to prepare increases 0.00 vs 0.29

• Time to execute decreases

• Number of rows returned visited decreases

Seq table scan vs Index scan vs Bitmap index scan (postgres)

explain select id from t_records where t > 10;

 Seq Scan on t_records  (cost=0.00..15233.01 rows=898039 width=4)
   Filter: (t > 10)
 (2 rows)

flowchart LR
  index[(Index)]
  heap[(Heap)]
  select --> heap --> resolve

explain select id from t_records where t > 5000;

 Index Scan using t_records_t_idx on t_records  (cost=0.42..8.44 rows=1 width=4)
   Index Cond: (t > 5000)
 (2 rows)

flowchart LR
  index[(Index)]
  heap[(Heap)]
  select -->| Index Scan | index --> heap --> resolve

flowchart LR
  index[(Index)]
  bitmap[(Bitmap)]
  heap[(Heap)]
  recheck[Condition Recheck]
  index --> bitmap
  select --> bitmap --> recheck --> heap

pages = [0, 0, 1, 0, 0, 0, ...] # 1 if page has rows that satisfy the condition

explain select id from t_records where t > 4000;

 Bitmap Heap Scan on t_records  (cost=1942.75..8103.70 rows=174236 width=4)
   Recheck Cond: (t > 4000)
   ->  Bitmap Index Scan on t_records_t_idx  (cost=0.00..1899.19 rows=174236 width=0)
         Index Cond: (t > 4000)
 (4 rows)

flowchart LR
  index[(Index)]
  bitmap[(Bitmap)]
  heap[(Heap)]
  recheck[Condition Recheck]
  index --> bitmap
  where_clause_1 --> bitmap --> recheck --> heap
  where_clause_2 --> bitmap

condition_1 = [0, 0, 1, 0, 0, 1, ...]
condition_2 = [0, 0, 1, 0, 1, 0, ...]

bitmap_and = [0, 0, 1, 0, 0, 0, ...] # only page 3 staifies both conditions

explain select id from t_records where t > 5000 and t < 1000;

 Bitmap Heap Scan on t_records  (cost=62.55..4302.44 rows=4500 width=4)
   Recheck Cond: ((t > 5000) AND (t < 1000))
   ->  Bitmap Index Scan on t_records_t_idx  (cost=0.00..61.42 rows=4500 width=0)
         Index Cond: ((t > 5000) AND (t < 1000))
 (4 rows)

explain select id from t_records where t > 5000 and t < 1000;

vacuum t_records;

create index a_idx on temp(a) include (b,c);

flowchart LR
  index[(Index)]
  select -->| Index only Scan | index --> resolve

create index a_b_c_combined_idx on temp(a,b,c);

select * from temp where a > 1 and b < 3 and c > 5;

flowchart LR
  index[(a,b,c)]
  select --> |index only scan|index --> resolve

Concurrent Index Creation's

• Waits for all transactions to finish, before creating the index.

• Does not lock the table read's or writes.

• Takes longer time to execute.

• Can crash if inserting duplicate values, while creating the index.

create index concurrently a_idx on temp(a);

Bloom Filters

flowchart LR
  client[Client]
  server[Server]
  bloom_filter[(Bloom Filter)]
  db[(DB)]
  client --> |request| server <--> |get / set| bloom_filter
  server --> |request| db

A bloom filter is a probabilistic data structure, that can be used to check if an element is in a set.

# bloom filter
filter = [0, 0, 1, 0, 0, 0, 0, 0, 0, 1]
filter_posstion = hash("req") % len(filter)

if filter[filter_posstion] == 1:
  # maybe in set
  return request_db()

# set bit
filter[filter_posstion] = 1

Working with Billion row tables

Why do we need a billion row table? We have many ways to solve a problem.

• Avoid having a billion row.

If thats not possible,

• Can you index it?

• Can you partition it in the same disk.

• Can you shard horizontally on different disks, on multiple DB's.

• Map Reduce (not suitabale for transactions).

Full Table Scan

• Reading the entire table, to find the rows that satisfy the query.

• Reading pages from disk, that are not in memory.

• Requires a lot of I/O to read the pages. (8KB - 16KB per page)

• DBMS's implement multi threading to read pages in parallel.

B-Tree (Original)

• B trees are not binary trees (each node can have more than 2 children),
  B trees stands for balanced tree.(distance from root to any leaf node is the same)

• Each node in a B tree contains multiple keys that form a page.

graph TD
  root[2:702, 4:704]
  internal_1[1:701]
  internal_2[3:703]
  internal_3[5:705]
  root --> |page|internal_1
  root --> |page|internal_2
  root --> |page|internal_3

The above example has 2 keys, and 3 children.

• Each key in the node points to a value on the heap (tuple),
  or the primary key.

• Max no of degrees, no of keys per node.

• The parent must have (n - 1) keys,
  where n is the number of children.

• The nodes are ordered from left to right.

• You cannot see this in the diagram,
  each key in the node has a before and after pointer.

• Before pointer is used to find the next node,
  that has a value less than the following key.

Limitations of B-Trees

• Because each node stores both keys and values,
  the number of keys per node is limited.

• The values are not used until the node is found.

• This increases the number of I/O's required to find the node
  (reading each node / page is an IO).

• Range queries are slow, since we need to traverse for all the keys in the range.

B+ Tree

• Nodes only store keys in internal and root nodes.

• The values are only stored in the leaf nodes.

• This allows us to store more keys per node.

• Leaf nodes are linked, eacn node has a pointer to the next node linked list.

• Range queries are much faster.

graph TD
    root[5] --> root_1[3]
    root --> root_2[7 9]
    root_1 --> root_3[2]
    root_1 --> root_4[4]
    root_2 --> root_5[6]
    root_2 --> root_6[8]
    root_2 --> root_7[10]
    root_3 --> leaf_1[1:row_id]
    root_3 --> leaf_2[2]
    root_4 --> leaf_3[3]
    root_4 --> leaf_4[4]
    root_5 --> leaf_5[5]
    root_5 --> leaf_6[6]
    root_6 --> leaf_7[7]
    root_6 --> leaf_8[8]
    root_7 --> leaf_9[9]
    root_7 --> leaf_10[10,11]
    subgraph linked list
      leaf_1
      leaf_2
      leaf_3
      leaf_4
      leaf_5
      leaf_6
      leaf_7
      leaf_8
      leaf_9
      leaf_10
    end

Each node usually store 100's of thousands of keys, above diagram is just an example.

• Leaf nodes have duplicate keys.

• Leaf pointers are cheap to traverse.

• 1 Node = 1 DBMS Page

• Internal nodes fit in memory.

• Leaf nodes can be stored in the heap.

• Most DBMS uses B+ trees.

Storage cost in Postgres vs mySQL

• Postgres points to the heap. mySQL points to the primary key.

• Write amplification is higher in Postgres. (any update to the heap, needs to be replicated in the index).

• If primary keys are large (UUID), inserts in mySQL will be slower.
  (Since UUID's don't have a pattern.)

• Leaf nodes in mySQL contains all the data (clustered index).

Partitioning types.

• Range partitioning By date, customer id, etc.

• By List By location, zip codes, etc.

• Hash partitioning By hash of the primary key, etc. (consistent hashing)

Partitioning vs Sharding

• In partitioning, the data is stored in the same DB. The client is agnostic.

• Each shard sits in a seperate DB, the client needs to know which shard to query.

• In partitioning, the table name changes.

• In sharding, the table name is the same, but the DB ip changes.

Creating a partition

create table grades (id serial not null, g not null) partition by range (g);

create table g0035 (like grades including indexes);
create table g3570 (like grades including indexes);
create table g7080 (like grades including indexes);
create table g80100 (like grades including indexes);

alter table attach partition g0035 for values from (0) to (35);
alter table attach partition g3570 for values from (35) to (70);
alter table attach partition g7080 for values from (70) to (80);
alter table attach partition g80100 for values from (80) to (100);

insert into grades (g) select floor(random() * 100) from generate_series(1, 10000000);
create index on grades (g);

or

insert into grades (g) select g from another_table;

select max(g) from g0035; -- 34
select max(g) from g3570; -- 69
select max(g) from g7080; -- 79
select max(g) from g80100; -- 99

Make sure ENABLE_PARTITION_PRUNING is set to on in postgresql.conf.

use the show command to check.

show enable_partition_pruning;

set enable_partition_pruning = on;

Checking partition size

select pg_relation_size(oid), relname from pg_class order by pg_relation_size(oid) desc;

 pg_relation_size |                    relname
------------------+-----------------------------------------------
        126935040 | g3570
        126754816 | g0035
         72572928 | g7090
         36241408 | g90100
         24305664 | g3570_g_idx
         24272896 | g0035_g_idx
         13910016 | g7090_g_idx
          6955008 | g90100_g_idx

Pros of sharding

• Horizontal scaling (Data / Memory / CPU).

• Security (Access control).

• Smaller Indexes.

Cons of sharding

• Complex client side code. (need to know which shard to query)

• Atomic transactions across shards are impossible.

• Rollbacks are complicated AF.

• Schema changes are harder (need to change all shards).

• Joins are harder (need to query all shards).

• Sharding key should be known.

When should we shard?

• Sharding should be your last resort.

• Partition first, then shard.

• TCP connections are reaching the limit?
  Try replication first.
  Writes only to primary server.

• Two way replication, two availabilty zones (multiple primary databases).

• You cannot maintain ACID complaiance accross shards. (eventual consistency).

• Sharding is an overkill for most applications.

• Vitesse is a good sharding library for go.

Exclusive lock's vs Shared lock's

gantt
    title Timeline
    section Alice
        Exclusive lock  :a1, 2020-01-10, 42h
    section Bob
        Shared lock     :b1, 2020-01-11, 24h
    section Charlie to Bob
        Shared lock on Bob failed  :crit, c1, 2020-01-11, 1h
        Update bob                 :cirt c2, 2020-01-12, 24h

Dead locks

graph LR
  A[Transaction 1]
  B[T2]
  l1{{Release lock 1 event}}
  l2{{R2}}
  A --> l1 --> B
  B --> l2 --> A

flowchart TD
    t1[Transaction 1]
    t2[Transaction 2]
    a1[Insert 10]
    a2[Insert 20]
    b1[Insert 20]
    b2[Insert 10]
    t1 --> a1 --> a2 --> wait --> commit
    t2 --> b1 --> b2 --> rollback[rollback due to deadlock]

• Most DBMS's have a deadlock detection mechanism,
  They will fail one of the transactions.

Two phase locking

The double booking phenomenon.

graph TD
    t1[Transaction 1] --> s1[id=10, isBooked=false] --> u1[id=10, isBooked=true, name=Bob] --> commit
    t2[Transaction 2] --> s2[id=10, isBooked=false] --> u2[id=10, isBooked=true, name=Steve] --> commit -->
    status[id=10, isBooked=true, name=Steve]

Both transactions read the same data, and updated it.

Solution, create a two phase locking mechanism.

graph LR
    t1[Transaction 1] --> s1[id=10, isBooked=false] --> u1[id=10, isBooked=true, name=Bob] --> commit
    t2[Transaction 2] --> hang --> s2[id=10, isBooked=true]

begin transaction;
select * from seats where id = 10 for update; -- creates an exclusive lock
update seats set isBooked = true, name = 'Bob' where id = 10;
commit;

begin transaction;
select * from seats where id = 10 for update;
-- hang
-- updated data is returned

for UPDATE creates an exclusive lock on the row indefinitely
set lock_timeout = 1000; will timeout the lock after 1 second.

Alternate solution (not ideal)

flowchart LR
    t1[Read committed transaction 1] --> s1[Update when clause] ---> commit
    t2[Read committed transaction 2] --> s2[Update when clause] --> hang --> rollback

update seats set isBooked = true, name = 'Bob' where id = 10 and isBooked = false;

This solution is imperfect, You are at the mercy of the DBMS implementation.
Postgres refreshes the row after the lock is released, the same cannot be said for other DBMS's.
Always rely on explicit locks instead of relying on implicit locks.

flowchart TD
    t1[update clause] --> |reading row on heap for lock info|heap[(Heap)] --> wait{{Wait for lock to be released}}
    wait --> |refresh row|heap
    wait --> resolve

SQL pagination with offset is very slow

This is slow, because, DBMS needs to iterate through the first 10,00,010 rows,
and then filter out the last 10 rows.

select * from users order by id limit 10 offset 1000000;

instead, make user query for more data using the last-seen-id.

select * from users where id > 1000000 order by id limit 10;

Connection pooling.

• For every connection, the DBMS needs to allocate resources, this takes time.

• If we create a connection for every request, the latency and throughput will be very bad.

• If the no of connections increase, the DBMS will overload and crash.

• Connection pooling is a way to reuse connections.

• The connections are kept alive, and reused.

• Each connection is leased to a request, and returned to the pool after the request is complete.

graph LR
    A[Request 1]
    B[Request 2]
    C((Connection pool))
    C --> |lease|A
    A --> |release|C
    C --> |lease|B
    B --> |release|C

    C --> D[(DB ip:port)]

Default connection pool size is 10, in postgres.

graph LR
  db[(DB ip_address:port)]
  instance_1((instance 1))
  instance_2((instance 2))
  instance_n((instance n))
  lb[Load balancer]
  request --> lb --> instance_1
  lb --> instance_2
  lb --> instance_n
  instance_1 --> |10 connection pool|db
  instance_2 --> |10 connection pool|db
  instance_n --> |10 connection pool|db

• Each instance keeps alive 10 connections to the DB.

• Each instance can send upto 10 concurrent requests to the DB.

• Each function invocation leases a connection from the pool.

• Once the function is executed, the connection is returned to the pool.

const { Pool } = require('pg');
const pool = new Pool({
	max: 20,
	idleTimeoutMillis: 30000, // connection will be closed after 30 seconds in idle
	connectionTimeoutMillis: 2000, // timeout after 2 seconds
});

await pool.query('SELECT something FROM sometable');

We cannot begin a transaction on a pooled connection, transactions need a dedicated connection.

// asking the pool to give us a dedicated connection
const client = await pool.connect();
try {
	await client.query('BEGIN');
	await client.query('COMMIT');
} catch (e) {
	await client.query('ROLLBACK');
} finally {
	// release the connection to the pool
	client.release();
}

Master slave replication

graph TD
  query[C-ED queries] --> master[(Master)]
  master --> |replication| slave_1[(replica 1)]
  master --> |replication| slave_2[(replica 2)]
  master --> |replication| slave_n[(replica n)]
  read_query[R queries] -.-> slave_1
  read_query -.-> slave_2
  read_query -.-> slave_n

Multi-Master replication

graph LR
  query[C-ED queries]
  master_1[(Master 1)]
  master_2[(Master 2)]
  slave_1[(replica 1)]
  slave_2[(replica 2)]
  slave_3[(replica 3)]

  query --> master_1
  query --> master_2
  master_1 --> |replication| master_2
  master_2 --> |replication| slave_1
  master_2 --> |replication| slave_2
  master_1 --> |replication| slave_3

  read_query[R queries] -.-> slave_1
  read_query -.-> slave_2
  read_query -.-> slave_3

• Difficult to implement.

• Need to deal with conflicts.

• Not usually preferred over master-slave replication.

Synchronous replication

graph LR
  query[C-ED queries] --> master[(Master)]
  master[(Master)] --> |replication| slave_1[(replica 1)]
  master --> |replication| slave_2[(replica 2)]
  master --> |replication| slave_n[(replica 3)]
  slave_1 -.-> |ack| master
  slave_2 -.-> |ack| master
  master -.-> |resolve| query

• Replication must be successful before the query is resolved.

• If the replication fails, the query fails.

• Can specify the number of replicas that must acknowledge the replication.
  (first 2 / first 1 / any)

Asynchronous replication

graph LR
  query[C-ED queries] --> master[(Master)]
  master[(Master)] -..-> |Async replication| slave_1[(replica 1)]
  master -..-> |Async replication| slave_2[(replica 2)]
  master -..-> |Async replication| slave_3[(replica 3)]
  master --> |resolve| query

Pros and cons of replication

Pros

• Cursors create a temporary table in memory.

• Cursors are used to iterate over a large number of rows. (without loading all the rows into memory)

• Allows data to be streamed.

• Can cancel the cursor at any time.

• Paging can be done using cursors.

Cons

• Cursors are stateful, if the connection is lost, the cursor is lost.

• Cannot horizontally scale cursors.

• Long running cursors can cause locking issues.

Steps to enable SSL

• Run pg admin

  bash

  sudo docker run -e PGADMIN_DEFAULT_EMAIL="santhosh" -e PGADMIN_DEFAULT_PASSWORD="passwd" -p 80:80 -p 5555:80  --name pgadmin dpage/pgadmin4

• Install vim in postgres docker container

  bash

  docker exec -it pg bash;
  apt-get update;
  apt-get install vim;

• Generate SSH key

  bash

  openssl req -x509 -newkey rsa:4096 -nodes -out cert.pem -keyout key.pem -days 365

• Update postgresql.conf

  bash

  vim var/lib/postgresql/data/postgresql.conf
  ssl = on
  ssl_cert_file = 'cert.pem'
  ssl_key_file = 'key.pem'

• Connect to the db using pg admin

What is the largest sql query we can send before it fails?

• Create table if not exists.

• Different users for CRED operations and Table owners.

• Have different privileges for different users.

• Normal users should not be able to DROP tables.

• Different pools for different routes (routes that require read access only will use a different pool, logged in as normal user).

Best practices when working with databases

What is encryption?

• Symmetric encryption

  • Same key is used to encrypt and decrypt.

  • AES, DES, 3DES, RC4, RC5, RC6, Blowfish, Twofish, etc.

• Asymmetric encryption

  • Different keys are used to encrypt and decrypt.

  • Public key and private key pair.

Why can't we always encrypt data?

• Queries cannot be executed on encrypted data.

• Analysis, indexing, sorting, etc cannot be done on encrypted data.

• Applications must read the data, decrypt it, and then perform the operation.

• TLS termination at layer 7 load balancer requires the data to be decrypted. (needs to know the request, payload, etc)

What is homomorphic encryption?

• Allows us to perform arithmetic operations on encrypted data.

• No need to decrypt the data to perform operations.

• Its damn slow, at the moment.

• Databases can index and optimize without decrypting the data.

• True end to end encryption.

Not ready for production use, yet.

Why does posgres do a bit map heap scan, instead of an index only scan?

create index g_index on grades(g);
explain analyze select count(*) from grades where g = 1;

• Postgres needs to visit the heap to check if the row is visible to all transactions.

• The visibility col is a hidden col in the heap for each row.

• Visibility map is used to check if the row is visible to all transactions.

vaccum grades;

• vaccum command creates a visibility map.

What is cost in explain analyze?

• Cost is the estimated cost of the query.

• Its just a number that postgres uses.

• Higher the cost, slower the query.

All Isolation levels

BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
select COUNT(*) from users where id GTE 100 and id LTE 200;
-- val 10

-- locks the rows that we read
-- parallel transaction cannot update the rows that we read
-- parallet transaction can append new rows
select COUNT(*) from users where id GTE 100 and id LTE 200;
-- val 11

-- same query returns different results, within the same transaction

BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
select COUNT(*) from users where id GTE 100 and id LTE 200;
-- val 10

-- locks the rows that we read
-- parallel transaction cannot update the rows that we read
-- parallet transaction can append new rows
select COUNT(*) from users where id GTE 100 and id LTE 200;
-- val 10

select * from users where id = 1 for update;

Duplicate indexes in a row

• Adding an index to a column that has less unique values, is not useful. (Index selectivity) Index is not selective enough.

• Index is bloated and takes up more space, (same value is repeated multiple times, in the b-tree)

• Postgres 13 has a de-duplication feature, that removes duplicate values from the b-tree index. node - row_id[]

Why use SELECT FOR UPDATE?

• Each transaction obtains a exclusive lock on the rows that it needs to read / update.

• Other transactions cannot read / update the rows that where locked.

• You killed concurrency, your throughput is low.

• Your transactions will never fail due to conflicts.

Serialisable isolation level is better.

• Detects conflicts and fails the transaction, if there is a serialisable error.

• Your throughput is high, and you have concurrency.

• Its a optimistic locking mechanism.

• Your transactions can fail, due to conflicts.

• You need to handle retry logics in your application.

Why use a connection pool?

• If you are using one database connection for every request, you are doing it wrong.

• TCP blocking could happen if a lot of queries need to be executed at the same time.

flowchart LR
    client[Client1]
    client_2[Client2]
    server[Server]
    db[DB]
    client --> |request| server --> |get / set| db
    client_2 --> |faster request| server --> |get / set| db

flowchart RL
    classDef green fill:#ccffcc,stroke:#000,stroke-width:2px;
    classDef red fill:#ffcccc,stroke:#000,stroke-width:2px;

    client[Client1]:::green
    client_2[Client2]:::red
    server[Server]
    db[DB]

    db --> |fast response| server --> |fast response| client
    db --> |slow response| server --> |slow response| client_2

• There is a chance of response misdirection.

• Depends on the DB implementation, if the protocol used by the database does not use query tagging, the response could be misdirected.

But in case of a connection pool,

• Each connection is leased to a request, and returned to the pool after the request is complete.

• No parallel requests are made on the same connection.

What is the value of a bitmap index scan?

• Row can be in multiple pages.

• Creates a bit map on the first condition, if index is present for the same value. This creates a bit map of pages that satisfy the first condition.

• Updates a bit map on the second condition.

• Goes to the heap pulls those pages.

• Filters out the page for the query condition

See, "Bitmap And / Or" for more info this file

• If the query planner decides it has to scan a lot of rows, based on the query condition, it will decide to do an bitmap scan vs an index scan, to reduce IO.

Does composite index order matter?

• Write amplifications, composite indexes touches a lot of cols, the index needs to be updated on row update.

• Composite indexes are created from left to right.

• Minimum filter first. (filter that results in a larger dataset first)

  sql

  select a,b,c where a=10 and b=10 and c=20;
  -- a is minimum filter

In an index only scan, pg still needs to visit the heap?

• To check if the table is visible to the transaction.

• To get old versions (snapshot) of the row, when the transaction started.

• To avoid visits to the heap, use VACUUM command.

• Avoid long running transactions.

Persistence vs Durability

• Persistence is the ability to store data on disk and retrieve it at a later time after a crash.

• My transaction is durable is only successful, when the data is stored on disk. Postgres and Redis use WAL's to flush data to disk periodically.

Can we create index when row's are being inserted / updated?

• Most DB's to create index obtains a update / insert / delete lock on the entire table, until the index is created.

• Postgres allows you to create index concurrently, without locking the table.

• When a transaction is committed, data is expected to be persistent even after system termination.

• A transaction does changes to everything in memory.

• On commit, all changes are flushed to disk. ( this is slow )

• If databases crashes mid commit, what should happen to data?.

• A log of all changes are persisted to disk. (WAL write ahead log).

• Dirty pages are kept in memory.

• Dirty pages (changed pages) are flushed to WAL.

• DB comes back up, detects that WAL is ahead of the data on disk.

• No one reads from the WAL, it's only used for recovery.

• Page is loaded in memory, and the WAL is replayed ( WAL is also called as redo log ).

• Page is flushed to disk, and WAL is marked as flushed.

• How often should the WAL be flushed to disk? (checkpointing)

  • When the wall is full, we need to flush it to disk, before we can write to the wall again.

  • Checkpointing is a IO intensive operation, we need to pause everything until the checkpoint is done.

  • DB warns you before the checkpoint is initiated. (causes spikes in CPU usage)

  • If the WAL is small, the checkpoint is faster and more frequent.

• OS buffers the writes in memory, and flushes it to disk when it's ready ( to reduce IO and wear on the disk ).

• OS waits for the write cache to be full, before flushing it to disk.

• This is a problem, because the WAL is not flushed to disk, and the OS crashes, the WAL is lost.

• fsync() system call is used to flush WAL is flushed to disk directly bypassing the OS cache.

UNDO logs?

• Not all databases have UNDO logs.

• Rollback Transactions: If a transaction fails or is explicitly rolled back by the user, the UNDO log records are used to revert the changes made by that transaction.

• Recovery: In the event of a system crash, UNDO logs are used during the recovery process to ensure that any incomplete transactions are undone, maintaining the consistency of the database.

• Long running transactions, can cause the UNDO logs to grow, and for any new transactions to see the old data, the UNDO logs need to be replayed to get to the old state.

• Undo logs are applied after wall changes are applied when DB is recovering from a crash.

Can Null values improve database performance?

• Default values will take up space, eg (int 32bit will take up 32bits in the row even if the value like 0 does not take up 32 bits))

• PostGres uses a null bitmap, to store null values. Every row has a null bitmap, that stores the null values in the row. Every bit corresponds to a column in the row.

• If you have more than 8 columns, the null bitmap will increment by 8 bytes. | 8cols | 8 bits | | 9cols | 16 bits | | 17cols | 24 bits |

• Nulls are better than default values, in terms of space.

Don't rely on nulls all the time, there are some gotcha's

• select count(field); ignores nulls based on db

• select count(*); counts nulls

• T is null or T is not null, is fine.

• Not all databases support indexes on cols with nulls in them. (PG allows it, but oracle doesn't)

• Postgres limits each page size to 8kb.

• We need to try to fit as many rows as possible in a page.

• More IO's if the row is split across pages.

• If most of the cols are null, the no of rows that can fit in a page can be increased.

• There is a fixed cost of saving null's

• Select user_id from users where user_id is null; will not use the index on user_id.

• Postmaster process

• Everything in postgres is append only mutli version concurrency control.

• Process vs Threads, (threads are faster, but postgres uses processes)

well established mind physical body, mind, emotions, life energies

Distributed transaction ( a transaction spanning across multiple databases / services / processes )

• Each microservice has its own database.

• Making a transaction across multiple microservices is hard.

  mermaid

  flowchart LR
      A[Order service] -->|success| B[Payment service]
      B -->|failed| C[Order service needs to revert]
      C -->|transactions cannot be reverted| D[Problem]

• Ongoing transactions where stored in memory, instead of disk

• But for distributed transactions this is not the case

• Google atomic clocks to sequence of transactions

• Compensatory transactions, revert the previous transaction

• Eventing model, Kafka / Rabbit MQ,

  mermaid

  graph TD
      A[Order queue] --> B[Payment service]
      B --> C[Payment queue]
      C --> D[Shipping service]
      B --> E[Payment fail queue]
      E --> F[...]

• Go back to the old days, have a macro service.

• Debugging is hard in a distributed micro services.

Why did Uber migrate from postgres to mysql

• ctid is a internal parameter used by postgres to identify for physical row identification, it's not meant to be used as a primary key.

• ctid's change with every row update and are not stable.

• When a row is updated, PostgreSQL often creates a new version of the row with a different ctid. The index is updated to point to the new ctid. This is why indexes might get bloated over time with dead tuples, necessitating regular maintenance tasks like VACUUM or REINDEX.

• This is called Write amplification.

• WAL's are used to keep track of these changes.

• WAL's are pushed to standby servers, to keep them in sync.

• SSD's are not good for updates, they are good for inserts (RocksDB and LevelsDB, optimised for SSD's).

  Adding too much indexes are a bad idea, it will cause write amplifications.

• Uber had databases across multiple data centers, and they had to keep them in sync.

• Push WAL updates across multiple data centers, is expensive (network wise).