Billion $ Question – When to Prune/Defragment ?

Create Index – Building Index with Broken HOT Chains

Thank you pavan.deolasee@gmail.com pavan.deolasee@enterprisedb.com

1.65M

EnterpriseDB

1. HOT Inside The Technical Architecture

Pavan Deolasee
May 22, 2008

2. Overview

PostgreSQL MVCC
Motivation for Improvement
HOT Basics
HOT Internals
Limitations
Performance Numbers and Charts

3. What Does HOT Stand For ?

Heap Organized Tuples
Heap Optimized Tuples
Heap Overflow Tuples
Heap Only Tuples

4. Credits

• Its not entirely my work
• Several people contributed, some directly, many indirectly
– Simon Riggs – for writing initial design doc and getting me involved
– Heikki – for code review, idea generation/validation and participating
in several long discussions.
– Tom Lane – for patch review and code rework
– Korry – for extensive code review within EnterpriseDB
– Dharmendra, Siva, Merlin – for testing correctness/performance
– Florian, Gregory – for floating ideas
– Denis, Bruce – for constant encouragement and making me rework
HOT thrice
– Faiz, Hope – for excellent project management within EnterpriseDB
– Nikhil – for hearing to all my stupid ideas and helping with initial work
• The list is so long that I must have missed few names – apologies
and many thanks to them

5. Some Background - MVCC

• PostgreSQL uses MVCC (Multi Version Concurrency
Control) for transaction semantics
• The good things:
– Readers don’t wait for writers
– Writer doesn’t wait for readers
– Highly concurrent access and no locking overhead
• The bad things:
– Multiple versions of a row are created
– The older, dead versions can not be easily removed because
indexes don’t have visibility information
– Maintenance overhead to reduce table/index bloat

6. MVCC - UPDATE

Index
Heap
•Transaction T1 Updates V1
V1
T1
V2
T3
V3
T1
T3
•Transaction T1 Commits
V1 is dead, but still visible to older transactions,
so we call it RECENTLY DEAD
•Transaction T3 Updates V2
•Transaction T3 Commits
V2 is dead, but still visible to older transactions,
It’s also RECENTLY DEAD
Live
Retiring Transaction/xmax
Recently Dead
Creating Transaction/xmin

7. MVCC - Visibility

time line
Index
T0
Heap
T1
Transaction T0
V1
T1
V2
T3
T1
T3
T3
V3
T2
T4
T0 started before T1 committed
T0 can only see V1

8. MVCC - Visibility

time line
Index
T0
Heap
V1
Transaction T2
T1
T1
Transaction T2
T1
V2
T3
T3
T3
V3
T2
T4
T2 started after T1 committed, but before T3 committed
T2 can only see V2

9. MVCC - Visibility

time line
Index
T0
Heap
T1
Transaction T4
V1
T1
V2
T3
T1
Transaction T4
T3
Transaction T4
T3
V3
T2
T4
T4 started after T3 committed
T4 can only see V3

10. MVCC – Tuple States

Index
Heap
V1
T1
V2
T3
V3
T1
T3
• V1 and V2 are RECENTLY DEAD, V3 is
the most current and LIVE version
• V1 and V2 can not be removed, because
T0 and T2 can still see them
• T0 finishes, V1 becomes DEAD
• T2 finishes, V2 becomes DEAD
• Only V3 remains LIVE
Live
Recently Dead
Dead

11. Removing DEAD Tuples

Index
Heap
V1
V2
• V1 is DEAD. If it’s removed, we would have
a dangling pointer from the index.
• V1 can not be removed unless
the index pointers pointing to it are also
removed
Note: Index entries do not have any visibility
Information
• Near impossible to reliably find index pointers
of a given tuple.

12. MVCC - Index/Heap Bloat

Updates
Inserts
Deletes
Heap
Index A
Index B

13. MVCC - Index/Heap Bloat

VACUUM
Heap
Index A
Index B

14. Vacuum – Two Phase Process

Heap
Index A
Index B

15. Vacuum

• VACUUM can release free space only at the
end of the heap. Tuples are not reorganized
to defragment the heap
• Fragmented free space is recorded in the
Free Space Map (FSM)
Heap
Index A
Index B

16. Motivation

• Frequent Updates and Deletes bloat the heap and indexes resulting
in performance degradation in long term – spiral of death
• Each version of a row has it’s own index entry, irrespective of
whether index columns changed or not – index bloat
• Retail VACUUM is near impossible (dangling index pointers)
• Regular maintenance is required to keep heap/index bloat in check
(VACUUM and VACUUM FULL)
– Normal VACUUM may not shrink the heap, VACUUM FULL can but
requires exclusive lock on the table
– VACUUM requires two passes over the heap and one or more passes
over each index.
– VACUUM generates lots of IO activity and can impact the normal
performance of the database.
– Must be configured properly

17. Pgbench Results

• scale = 90, clients = 30, transactions/client = 1,000,000
• two CPU, dual core, 2 GB machine
• separate disks for data (3 disks RAID0) and WAL (1
disk)
• shared_buffers = 1536MB
• autovacuum = on
• autovacuum_naptime = 60
• autovacuum_vacuum_threshold = 500
• autovacuum_vacuum_scale_factor = 0.1
• autovacuum_vacuum_cost_delay = 10ms
• autovacuum_vacuum_cost_limit = -1

18. Heap Bloat (# blocks)

Postgres 8.2
Original
Size
Increase
in Size
Postgres 8.3
Pre HOT
Original
Size
Postgres 8.3
Post HOT
Increase
in Size
Original
Size
Increase
in Size
Branches
1
49,425
1
166
1
142
Tellers
6
18,080
5
1,021
5
171
155,173
243,193
147,541
245,835
147,541
5,523
Accounts
In 8.2, the heap bloat is too much for small and large tables

19. Postgres 8.3 – Multiple Autovacuum

Postgres 8.2
Original
Size
Increase
in Size
Postgres 8.3
Pre HOT
Original
Size
Postgres 8.3
Post HOT
Increase
in Size
Original
Size
Increase
in Size
Branches
1
49,425
1
166
1
142
Tellers
6
18,080
5
1,021
5
171
155,173
243,193
147,541
245,835
147,541
5,523
Accounts
Multiple autovaccum processes helped small tables, but not large tables

20. Postgres 8.3 – HOT (Retail Vacuum)

21. Several Ideas

• Update In Place
– The first design. Replace old version with the new version and
move old version somewhere else
– It was just too complicated!
• Heap Overflow Tuple
– That’s what HOT used to stand for
– A separate overflow relation to store the old versions.
– Later changed so that the new version goes into the overflow
relation and pulled into the main relation when old version
becomes dead.
– Managing overflow relation and moving tuples around was
painful.
• Heap Only Tuple
– That’s what HOT stands for today
– Tuples without index pointers

22. HOT Update

Necessary Condition A: UPDATE does not change any
of the index keys
Example:
CREATE TABLE test (a int, b char(20));
CREATE UNIQUE INDEX textindx ON test(a);
INSERT INTO test VALUES (1, ‘foo’);
UPDATE test SET b = ‘bar’ WHERE a = 1;
UPDATE test SET a = a + 1 WHERE a = 1;
First UPDATE changes the non-index column – candidate for HOT update
Second UPDATE changes the index column – HOT update not possible

23. HOT Update

Index
Heap
• V1 is updated – no index key change
Single Index Entry Update Chain
V1
V2
HOT
• V2 is updated – no free space in block
V3
Necessary Condition B: The new version should fit in
the same old block – HOT chains can not cross block
boundary.

24. HOT Update – Necessary Conditions

Necessary Condition A: UPDATE does not change any
of the index keys
Necessary Condition B: The new version should fit in
the same old block – HOT chains can not cross block
boundary.

25. Inside A Block

• Page Header followed by line pointers
Page Header
1
2
3
4
pd_upper
5
6
N
• Line pointers point to the actual tuples
• Indexes always point to the line pointers
Free Space
and not to the actual tuple
tuple N
pd_lower
• HOT chains originate at Root LP and
may have one or more HOT tuples
Used Space
• HOT tuples are not referenced by the
tuple 6
tuple 5
tuple 4
tuple 3
tuple 2
Root Tuples/LP
tuple 1
HOT Tuples/LP
indexes directly.

26. HOT – Heap Scan

Index Ref
V1
• No change to Heap Scan
• Each tuple is examined separately and
V2
sequentially to check if it satisfies the
transaction snapshot
V3
V4

27. HOT – Index Scan

Index Ref
V1
• Index points to the Root Tuple
• If the Root tuple does not satisfy the
V2
snapshot, the next tuple in the HOT chain
is checked.
V3
• Continue till end of the HOT chain
• The Root tuple can not be removed even
V4
if it becomes DEAD because index scan
needs it

28. Pruning – Shortening the HOT Chain

Index Ref
V1
V2
V3
V4
• V1 becomes DEAD
• V1 is removed, but it’s line pointer (LP)
can not be removed – index points to it
• Root LP is redirected to the LP of
next tuple in the chain

29. Pruning – Shortening the HOT Chain

Index Ref
V2
V3
V4
• Root LP is a redirected LP
• V2 becomes DEAD
• V2 and it’s LP is removed – HOT tuple
• Root LP now redirects to the next
tuple in the chain

30. Pruning – Shortening the HOT Chain

• Root LP is a redirected LP
• V3 becomes DEAD
• V3 and it’s LP is removed – HOT tuple
• Root LP now redirects to the next
tuple in the chain
Index Ref
V3
V4

31. Pruning – Shortening the HOT Chain

• Root LP is a redirected LP
• V4 becomes DEAD
• V4 and it’s LP is removed – HOT tuple
• Root LP is now DEAD – still can’t
be removed
Index Ref
V4

32. Pruning – Normal UPDATEs and DELETEs

Index Ref
V1
• Normal UPDATEd and DELETEd
tuples are removed and their LPs
are marked DEAD – LPs can’t be
removed
• A very useful side-effect of HOT

33. Pruning and Defragmentation

Page Header
1
2
3
4
pd_upper
5
6
N
Free Space
tuple N
pd_lower
Used Space
tuple 6
tuple 5
tuple 4
tuple 3
tuple 2
Root Tuples/LP
tuple 1
HOT Tuples/LP

34. Pruning – Recovering Dead Space

Page Header
1
2
3
4
5
6
N
Free Space
tuple N
Used Space
tuple 6
tuple 5
tuple 4
tuple 3
tuple 2
tuple 1

35. Defragmentation – Collecting Dead Space

Page Header
1
2
5
6
N
Free Space
tuple N
Used Space
tuple 6
tuple 5

36. Billion $ Question – When to Prune/Defragment ?

• Pruning and defragmentation (PD) happens together –
requires cleanup lock on the buffer and shuffles tuples
in a page.
• Too frequent PD may conflict with other backends
accessing the buffer.
• Too infrequent PD may slow down reclaiming dead
space and create long HOT chains.
• Page level hint bits and transaction id is used to
optimize PD operations.

37. Page Level Hints and Xid

• If UPDATE does not find enough free space in a page,
it does COLD UPDATE but sets PD_PAGE_FULL flag
• The next access to page may trigger prune/defrag
operation if cleanup lock is available.
• PD never waits for cleanup lock
• Page Xid is set to the oldest transaction id which
deleted or updated a tuple in the page. PD is usable
only if RecentGlobalXmin is less than the Page Xid.

38. Lazy Vacuum / Vacuum Full

• Lazy Vacuum is almost unchanged.
• DEAD line pointers are collected and reclaimed.
• Vacuum Full clears the redirected line pointers by
making them directly point to the first visible tuple in the
chain.
V
V

39. Headline Numbers - Comparing TPS

transactions per second
2500
2300.88
2000
PG 8.2
1500
1000
500
736.98
828.32
PG 8.3 Pre HOT
PG 8.3 Post HOT
0
That’s a good 200% increase in TPS

40. Comparing Heap Bloat (# blocks)

Postgres 8.2
Original
Size
Increase
in Size
Postgres 8.3
Pre HOT
Original
Size
Postgres 8.3
Post HOT
Increase
in Size
Original
Size
Increase
in Size
Branches
1
49,425
1
166
1
142
Tellers
6
18,080
5
1,021
5
171
155,173
243,193
147,541
245,835
147,541
5,523
Accounts
HOT significantly reduces heap bloat; for small and large tables

41. Comparing Index Bloat (# blocks)

Postgres 8.2
Original
Size
Postgres 8.3
Pre HOT
Increase
in Size
Original
Size
Postgres 8.3
Post HOT
Increase
in Size
Original
Size
Increase
in Size
Branches
2
1,023
2
588
2
4
Tellers
5
353
5
586
5
19
24,680
24,679
24,680
24,677
24,680
0
Accounts
HOT significantly reduces index bloat too; for small and large tables

42. Comparing IO Stats

Postgres 8.2
Blks Read
Branches
H
I
Tellers
H
I
Accounts
H
I
Blks Hit
Postgres 8.3
Pre HOT
Blks Read
Blks Hit
Postgres 8.3
Post HOT
Blks
Read
Blks Hit
576,949
810,688,147
8,595
2,904,470,056
784
74,640,567
7,540
330,165,668
68,992
254,298,111
7
56,184,941
685,599
219,033,182
7,710
452,528,173
678
62,275,473
366
135,684,700
599
210,984,757
28
60,655,207
20,138,195
167,902,036
19,065,032
173,465,111
162,867
101,354,726
464,641
266,747,533
482,835
270,662,463
49,327
181,307,038

43. Comparing IO Stats

44. Comparing IO Stats

45. What Should I Do ?

• Nothing! HOT is always enabled and there is no way to
disable it.
• It works on user and system tables
• A heap fill factor less than 100 may help
• A significantly smaller heap fill factor (as low as 50) is
useful for heavy updates where most of the updates
are bulk updates
• Non index key updates is a necessary condition for
HOT – check if you don’t need one of the indexes.
• Prune-defrag reclaims COLD UPDATEd and DELETEd
DEAD tuples by converting their line pointers to DEAD
• You still need VACUUM – may be less aggressive

46. Limitations

• Free space released by defragmentation can only be
used for subsequent UPDATEs in the same page – we
don’t update FSM after prune-defragmentation
• HOT chains can not cross block boundaries
• Newly created index may remain unusable for
concurrent transactions
• Normal vacuum can not clean redirected line pointers

47. Create Index

• This was one of the most interesting challenges in HOT
development.
• The goal was to support CREATE INDEX without much
or no impact on the existing semantics.
• Did we succeed ? Well, almost

48. Create Index - Challenges

• Handling broken HOT chains
• New Index must satisfy HOT properties
– All tuples in a HOT chain must share the same index key
– Index should not directly point to a HOT tuple.
• Create Index should work with a ShareLock on the
relation

49. Create Index – Sane State

• All HOT chains are in sane state
1
2
1, a, x
• Every tuple in a chain shares the
1, a, y
same index key
3
4
2, b, x
• Index points to the Root Line Pointer
2, c, y
indexA(col1)
3, d, x
4, e, x
4, f, y
Create Table test (col1 int, col2 char, col3 char);
Create Index indexA ON test(col1);

50. Create Index – Broken HOT Chains

• Create a new Index on col2
1
2
1, a, x
• Second and fourth HOT chains,
1, a, y
marked with
3
4
2, b, x
, are broken
w. r. t. new Index
2, c, y
indexA(col1)
tuples are recently dead, but
may be visible to concurrent txns
3, d, x
4, e, x
4, f, y
indexB(col2)
Create Index indexB ON test(col2);

51. Create Index – Building Index with Broken HOT Chains

• Recently Dead tuples are not indexed
1
2
1, a, x
• Index remains unusable to the
1, a, y
transactions which can potentially
3
4
2, b, x
see these skipped tuples, including
2, c, y
the transaction which creates the
indexA(col1)
a
index
• Any new transaction can use the index
3, d, x
• xmin of pg_class row is used to check
c
d
4, e, x
4, f, y
f
indexB(col2)
Create Index indexB ON test(col2);
index visibility for transactions

52. Thank you [email protected] [email protected]

English Русский Rules