Query Optimizer

ก่อนจะพูดถึงเรื่อง optimizer เราจะต้องทำความเข้าใจในเรื่อง index ก่อนดังนี้
Primary Index หรือ clustered index คือ index บน column ที่ระบุ physical sequence ของ table
หมายถึงว่า table นั้นได้ถูกเรียงไปในทางเดียวกัน index

Secondary Index หรือ non-clustered index คือ index บน column ที่ไม่ได้ระบุ physical sequence ของ table

Statistic ใน database จะเก็บ

• n_r จำนวน tuple in relation r
  
• b_r จำนวน block containing tuples of relation r
  
• s_r ขนาดของ tuple ของ relation r
  
• f_r จำนวน tuple ใน 1 block
  
• V(A, r) จำนวนของ distinct value ใน attribute A ใน relation r
  
• SC(A, r) คือ selection cardinality ของ attribute A ของ relation r
  

optimizer จะเลือกแต่ะละ plan นั้นดูจาก cost แต่ละ plan
สำหรับ basic algorithms มีด้วยกัน 2 algorithm
A1 (linear search) หรือเรียกว่า table scan
A2 (binary search) โดยจะใช้ได้ต่อเมื่อ table ถูก physically sort เท่านั้น

สำหรับกรณีที่มี index ร่วมด้วย มีด้วยกันอีก 3 algorithm
A3 (primary index on candidate key, equality) cost จะเท่ากับ HTi + 1
A4 (primary index on non-key) cost จะเท่ากับ HTi + number of blocks containing retrieved records
A5 (secondary index) สำหรับ candidate key cost จะเท่ากับ HTi + 1 แต่ละสำหรับ non-key จะเท่ากับ HTi + number of records retrieved

algorithm ที่กล่าวไปแล้ว สำหรับการ select แบบ equal แต่ในกรณีที่มีการ comparison เข้ามาด้วยจะมีอีก 2 algorithm
A6 (primary index, comparison)
A7 (secondary index, comparison)

ซึ่งแต่ละ algorithm ก็จะมี วิธีการคิด cost ที่แตกต่างกันไป ซึ่ง

DB Optimizer: Relational Calculus & Relational Algebra

Relational Calculus คือภาษาที่ให้ในการดึงข้อมูลจาก database แต่เนื่องจากไม่ user-friendly จึงไ้ด้เปลี่ยนเป็น SQL ในปัจจุบัน โดยที่ Relational Calculus เป็นการบอกว่าต้องการข้อมูลอะไร (what) จาก database

Relational Algebra คือภาษาที่บอกว่า จะดึงข้อมูลที่ต้องการมาได้อย่างไร (how) โดยแปลจาก relational calculus เป็น relational algebra

แล้วตัว optimizer จึงมาคำนวณว่าควรจะใช้วิธีไหนประกอบกับ statistics ให้เป็น execution plan ที่จะทำงานจริงๆ บน database

ตัวอย่างของ relational algebra คือ
Πbalance(σbalance<2500(account))

ซึ่งแปลงมาจาก SQL ดังนี้ select balance from account where balance <>

σ คือ select การเลือกเราเฉพาะ row ที่มี balance < 2500
Π คือ project การดึงเฉพาะ column account

relational algebra มี basic operators 8 ตัว
1. σ (sigma) คือ select
2. π(pi) คือ project
3. ∪ (cup) คือ union
4. ∩(cap) คือ intesection
5. - (minus) คือ difference
6. ρ (rho) คือ rename
7. ×(times) คือ product ก็เหมือนกับ cross join
8. (bow-tie) คือ join คล้ายกับ product แต่ว่ามีเงื่อนไข

operator 1 - 6 เป็น unary operator ส่วน operator 7 - 8 เป็น binary operator

Deadlock Handling

Deadlock คือการที่ Transaction A wait for resource that transaction B obsess and transaction B waits for resource that transaction A obess

Deadlock detection คือการเช็คว่าจะมีลักษณะของการเกิด deadlock ในขณะนั้น หรือไม่ ซึ่งโดยปกติจะเป็นคำสั่งที่ DBA จะสั่งเพื่อดู deadlock process ในขณะนั้น เมื่อทราบว่า มี transaction ไหนที่ deadlock ก็สามารถ kill process ไปได้ หรืออีกวิธีหนึ่งก็คือปล่อยไปเรื่อยๆ จนกว่า transaction ใด transaction หนึ่งจะ timeout

วิธีที่จะป้องไม่ให้เกิด deadlock มี 2 วิธีคือ
1. wait-die scheme คือ ให้ transaction ที่มาก่อนรอ และ transaction ที่มาหลังให้ die คือหยุด process ไปเลย
2. wound-wait scheme คือให้ transaction ที่มาก่อน wound transaction ที่ถือครอง resource แต่ว่ามาทีหลัง (เหมือนกับ kill transaction ที่ถือครอง resource อยู่) ถ้า transaction ที่มาหลังมาขอ resource จะให้ wait ไปก่อน

Concurency Control: Timestamp-Based Protocol

เป็นความพยายามที่จะทำให้เกิดความถูกต้องใน concurrency execution แต่ว่าไม่ต้อง lock เลย เพื่อให้มีความ flexible ในการทำงาน เช่น Oracle ใ้ช้ timestamp-based รวมกัน lock-based

โดย timestamp ของ transaction อาจจะไม่ใช่เวลาก็ได้ แต่จะต้องสามารถบอกได้ว่า transaction ใดเกิดก่อนเกิดหลัง transaction ที่เกิดก่อน จะต้องมี timestamp น้อยกว่า transaction ต่อๆ มา

แต่ละ data item จะมี timestamp สองตัว คือ
1. W-timestamp คือ timestamp ของ transaction ล่าสุดที่มา write ข้อมูลนั้นๆ
2. R-timestamp คือ timestamp ของ transaction ล่าสุดที่มา read ข้อมูลนั้นๆ

จากนั้น Timestamp-Ordering Protocolจะมีกฎในการ read/write data ดังนี้

1. กรณีที่จะ read แล้วพบว่า data นั้น มี w-timestamp มากกว่า จะไม่ยอมให้ read ก็จะถูก rollback (คือมี transaction ที่เกิดขึ้นทีหลังมี write data ไปแล้ว) ถ้ามี w-timestamp มีค่าน้อยกว่า ก็จะให้ read ได้ และจะ update r-timestamp นั้นเป็น timestamp ของ transaction ใหม่ที่มี read


2. กรณีที่จะ write แล้วพบว่า data นั้น มี r-timestamp มากกว่า จะไม่ยอมให้ write ก็จะถูก rollback (คือมี transaction ที่เกิดขึ้นทีหลังได้ read ค่าไปก่อนที่เราจะ write ค่าแล้ว) หรือ ถ้าพบว่า data นั้นมี w-timestamp มากกว่า ก็จะไม่ยอมให้ write เช่นเดียวกัน (คือมี transaction ที่มีทีหลัง write ค่าไปแล้ว) แต่ถ้าพบว่า timestamp ของเรามีค่ามากกว่าหรือเท่ากับทั้ง r-timestamp และ w-timestamp ก็จะยอมให้ write ค่าได้ และ update w-timestamp เป็น timestamp ของ transaction ใหม่

แต่เนื่องจากเมื่อมีปัญหาเกิดขึ้นในทุกกรณี protocol นี้บอกว่า จะต้อง rollback จึงทำให้เกิดการ rollback บ่อยครั้ง สำหรับ DBMS ที่เป็น timestamp-based อย่างเดียว ก็จะมีวิธีแก้ปัญหานี้คือ เมื่อ rollback แล้วให้นำกลับมา start transaction ใหม่อีกครั้ง ซึ่งไม่พบใน DBMS ในเชิงพาณิชย์ทั่วๆ ไป แต่อาจจะพบใน database ที่ใช้ใน controller

สำหรับ Oracle ที่ใช้ protocol นี้เ่ช่นกัน ใช้ multi-version scheme ในการแก้ปัญหา คือ แต่ละ transaction จะีสร้าง version ของ data ขึ้นมา เช่น data Q ก็จะมี Q1, Q2, Q3, ...
1. ในกรณีที่ read ข้อมูล ให้ read ค่า Qk โดยที่ Qk คือ version ของ data ที่เป็น transaction ก่อนหน้าเราสำหรับ data นั้น (นิยาย คือ version ที่มี w-timestamp(Qk) มากที่สุดที่ยังน้อยกว่า timestamp ของเรา) ดังนั้นจะ read ค่าได้เสมอ
2. การ write data ที่ Qk (ซึ่ง version k จะเป็น version ที่มี w-timestamp ที่มากที่สุดที่ยังน้อยกว่า timestamp ของเรา) ในกรณีที่ Qk มี r-timestamp ที่มากกว่า timestamp เรา ก็ต้อง rollback transaction นั้น นอกนั้นสามารถ write ได้เป็น version ใหม่ คือ Q(k+1) ซึ่งนั้นหมายถึงการทำ multi-version ไม่ได้แก้การ write data (หรือ lost update ยังคงแก้ไม่ได้)

ซึ่ง multiversion scheme จะทำให้ lost update ยังคง rollback แต่ว่า ปัญหาเรื่อง uncommitted dependency จะต้องใช้ commit bit เข้ามาช่วย คือจะ read เฉพาะ transaction ที่ commit แล้วเท่านั้น แต่สำหรับ inconsistent analysis และ phantom phenomenon สามารถแก้ได้โดยตรง

ดังนั้นเพื่อที่จะแก้ปัญหา lost update ที่ยังคงต้อง rollback อยู่ จึงทำ two-phase locking มาใช้ รวมเรียกว่า multiversion two-phase locking

การใ้ช้เทคนิคนี้ จำเป็นจะต้องเก็บทุกๆ ค่าของแต่ละ transaction ไว้ จนกว่า w-timestamp ของ version นั้นๆ จะน้อยกว่า transaction ที่เก่าที่สุด (หรือมี timestamp น้อยที่สุด) ในระบบ แต่เนื่องจาก memory ไม่เพียงพอกับข้อมูลที่มากมายขนาดนั้น จึงต้องลบค่าเก่าๆ ออก ซึ่งนั้นก็ทำให้บาง transaction เก่าๆ ที่ยังทำงานไม่เสร็จและ ต้องการค่าใน version เก่าๆ จำเป็นจะต้องไปตามเอาค่าเหล่านี้จาก BIJ ดังนั้น Oracle จึงต้องเก็บ BIJ ไว้ใน DB space ด้วย เพื่อให้สามารถดึงข้อมูล old value ขึ้นมาได้

Concurency Control: Lock-Based Technique

ลัำกษณะการทำงานของ lock-based technique

1. Lock primitive
   ถ้าเราทำ x-lock (wlock) จะได้ทั้งสิทธิ์ read & write
   ถ้า s-lock (share lock) จะทำได้แค่ read
   
2. Lock Compatibility Matrix
   

   	S	X
   S	true	false
   X	false	false

   ซึ่งหมายถึงถ้าเรา ทำ slock กับข้อมูลใดๆ คนอื่นสามารถเข้ามาทำ slock กับข้อมูลนั้นๆ ได้
   
3. Lock protocol คือลำดับขั้นตอนในการใช้คำสั่ง lock และ unlock ซึ่ง DBMS ในปัจจุบันจะใช้ Two-Phase Locking Protocal
   

Two-Phase locking มี 2 phase คือ
1. Growing phase: transaction จะ lock ได้ แต่ละ ปลด lock ไม่ได้
2. Shrinking phase: transaction จะปลด lock ได้ แต่จะ lock ข้อมูลเดิมอีกไม่ได้

lock-based technique นี้ รับประกัน conflict serializability ดังนั้นจะไม่เกิดปัญหา lost update และ inconsistent analysis แต่ว่ายังพบปัญหา uncommitted dependency และ phantom phenomenon ดังนั้นจึงมีการพัฒนา protocol ที่จะใช้เพิ่มขึ้นเป็น strict two-phase locking protocol ซึ่งจะทำ shrink phase ที่ sync point เท่านั้น (จุดที่ commit transaction) ดังนั้น strict two-phase locking protocol จะแก้ปัญหา uncommitted dependency ได้ด้วย

การที่ใช้ protocol นี้ทำให้
1. lost update เป็น dead lock

T1	T2
read(A) (acquire s-lock on A)
	read(A) (acquire s-lock on A)
update(A) (acquire x-lock)
wait	update(A) (acquire x-lock
wait	wait
...	...

2. uncommitted dependency ไม่เกิดขึ้น
3. inconsistent analysis เป็น dead lock
4. phantom phenomenon ยังคงเกิดขึ้น

ปัญหาที่เกิดขึ้นบ่อยที่สุด คือ lost update ซึ่งวิธีการแก้ไข ที่ไม่ให้เกิด dead lock บน lost update ได้ สามารถทำได้ง่ายๆ โดยแทนที่จะ ขอ s-lock ในตอนแรกที่ read ให้ขอเป็น x-lock แทน

นอกจากนั้นปัญหาที่เกิด dead lock บน inconsistent analysis จะต้องใช้ multiple granularity คือแทนที่จะ lock เฉพาะข้อมูลที่จะ read ก็ lock ในระดับ table เลย โดยดูจากคำสั่ง เช่น select sum(amount) from account ก็จะ lock ทั้ง table account เลย ซึ่งทำให้แก้ปัญหาของ phantom phenomenon ได้ด้วย

เปรียบเทียบกับ isolation ถ้าเป็น repeatable read หรือ serializable จะเป็น strict two-phase locking protocol + multiple granularity

แต่การทำ granularity นั้น ยิ่ง lock ในหน่วยเล็ก ก็จะยิ่งเพิ่มงานให้กับ DBMS เช่นการ lock record ก็จะทำให้เกิดงานกับ DBMS มากกว่า lock table ดังนั้นจึงมีเทคนิคการ lock escalation หรือ lock promotion คือ DBMS จะดูว่า ณ.ขณะนั้นเหมาะสมที่จะ lock ในระดับใด เช่น ถ้าในขณะนั้น มี user คนเดียว login อยู่ ก็จะ lock ทั้ง DB เลย หรือถ้ามี user คนเดียวใช้ table นั้นๆ อยู่ ก็จะ lock ที่ table

แต่การที่ DBMS จะรู้ว่า ระดับไหนมี transaction ใดใ้ช้อยู่ ก็โดยการใช้ Intend locking โดยเพิ่ม mode การ locking เพิ่มขึ้นไปอีก 3 mode
1. intention-shared (IS) ถ้า node ที่เล็กกว่าถูก s-lock node นั้นก็จะเป็น IS เช่น ถ้า มี table มีการ s-lock ที่ record ใด record หนึ่ง table นั้นก็จะเป็น IS
2. intention-excusive (IX) ถ้า node ที่เล็กว่า ถูก x-lock node นั้นก็จะเป็น IX
3. shared and intention-exclusive (SIX) คือ การ share เพื่อที่จะ update เช่นการ update a = a + 1

	IS	IX	S	SIX	X
IS	true	true	true	true	false
IX	true	true	false	false	false
S	true	false	true	false	false
SIX	true	false	false	false	false
X	false	false	false	false	false

นอกจากนั้น DB2 ยังมีสองแบบ แบบแรกคือ Cursor stability คือจะ lock เฉพาะที่ cursor อยู่เท่านั้น (ซึ่งเหมือนกับ read uncommitted) อีกแบบคือ Degree-two consistency คือ result ทั้งหมด จะถูก lock ไว้ เมื่อเลื่อน cursor ไปข้างหน้า record ที่ผ่านมา ก็จะถูกปลด lock ไปแต่ละครั้งที่เลื่อน record ไป ซึ่งผลที่ได้ก็จะเป็น read committed

Concurency Control: Recoverability และ Isolation

สำหรับ concurrent transaction และมีบาง transaction fail ซึ่งอาจจะมีผลลัพธ์ที่กระทบกับ transaction ที่ commit ไปแล้วให้ไม่ถูกต้อง ซึ่ง transaction นั้นๆ ก็ควรจะ recover กลับมาด้วย เช่น

T1	T2
read(A)
write(A)
	read(A)
read(B)
...
failed

เมื่อ T1 fail ก็จะทำการ roll back T1 ดังนั้นค่าที่ T2 นำไปใช้จึงเป็นค่าที่ไม่ถูกต้อง และควรจะต้องถูก roll back ด้วย หรือที่เรียกว่า มี recoverability แต่การทำ roll back ย้อยกลับไป (ซึ่งเรียกว่า Cascade Schedule) ดังนี้ จะทำให้เสียเวลาอย่างมาก ดังนั้นจึงมีความคิดในเรื่องการทำเป็น Cascadeless Schedules

Cascadeless Schedule คือการจะ read ค่าใด จะต้องรอให้ transaction ที่มีการ write ค่านั้นๆ commit ให้เสร็จสิ้นก่อน แต่ก็จะทำให้การทำงานของ transaction ช้าลง เนื่องจากต้องรออีก transaction หนึ่งทำงาน ดังนั้น DBMS จึงเปิดให้มีการกำหนดลักษณะการทำงานนี้โดย DBA เอง ที่เรียกว่า Level of Consistency ในมาตรฐาน SQL-92 หรือ Isolation level ดังนี้
1. Serializable คือการรับประกันของ DBMS ที่รองรับ Conflict Serializable + View Serializable + Cascadeless Scheduler + ไม่เกิดปัญหา Phantom phenomenon
หรือเรียกว่าแก้ปัญหา lost update + uncommitted dependency +inconsistent analysis + phantom phenomenon
2. Repeatable read คล้ายกับ Serializable แต่ไม่รองรับปัญหา Phantom phenomenon แต่สำหรับบาง product เช่น DB2 หรือ Infomix ไม่มี Serializable ให้เลือก แต่ที่ Repeatable read สามารถรองรับ Phantom phenomenon ด้วย
หรือเรียกว่าแก้ปัญหา lost update + uncommitted dependency +inconsistent analysis
3. Read committed หรือ Oracle เรียกว่า Snapshot read รองรับแค่ Cascadeless schedule
หรือเรียกว่า แก้ปัญหาเฉพาะ uncommitted dependency
4. Read uncommitted หรือ Cursor Stability หรือ Dirty read จะไม่รองรับ concurrency control problem ใดๆ

Concurency Control: Serializability

การที่ DBMS จะจัดการ concurrent execution ได้นั้น DBMS มี scheduler ในจัดการแต่ละ transaction โดยที่หลักการตามมาตรฐานดังนี้

Conflict Serializable

transaction schedule ที่ conflict กัน ก็คือ ลักษณะที่ 2 transaction ใดๆ มีการคำสั่งที่ทำงานพร้อมกับ ที่ data เดียวกัน และมี transaction หนึ่ง write ข้อมูลนั้นๆ
และ transaction ที่สามารถสลับคำสั่งได้โดยที่ไม่ conflict กับ ถือว่า เป็น conflict equivalent

และถ้า transaction ใดที่เป็น conflict equivalent กับ serializable transaction ก็จะเป็น conflict serializable ซึ่งนั่นหมายถึงว่า transaction นั่นๆ จะให้ผลลัพธ์เช่นเดียวกับการทำงานแบบ serialize ด้วยเสมอ
ลักษณะของ conflict equivalent คือ
1. transaction 2 transaction ทำงานกับข้อมูลเดียวกัน
2. มีอย่างน้อย 1 transaction ที่ write ข้อมูลนั้น

ตัวอย่างเช่น

T1	T2
read(A)
write(A)
	read(A)
read(B)
	write(A)
write(B)
	read(B)
	write(B)

T1	T2
read(A)
write(A)
read(B)
write(B)
	read(A)
	write(A)
	read(B)
	write(B)

ซึ่งทั้ง 2 schedule เป็น conflict equivalent กัน เพราะว่า การสลับคำสั่งดังกล่าว ไม่ conflict กับกฎ 2 ข้อดังกล่าว และ schedule ที่สองเป็น serializable ดังนั้น schedule แรก จึงเป็น conflict serializable

Conflict Serializable schedule คือ schedule ที่สามารถทำ conflict serializable ได้ ซึ่งเป็นการรับประกันว่า้ผลลัพธ์ของ transaction ใดๆ จะเหมือนกับ serializable transaction (ยกเว้นปัญหาเรื่อง Phantom phenomenon)

แต่ทั้งนี้ทั้งนั้น transaction ที่เป็น non-conflict serializable ก็ไม่ไ้ด้หมายถึงว่าผลลัพธ์จะไม่ตรงกับ serializable เสมอไป (แต่ในทางกลับกัน คือ transaction ที่เป็น conflict serializable จะให้ผลลัพธ์ที่เป็น serializable เสมอ)

View Serializable

เนื่องจากการใช้ conflict serializable schedule อาจจะีมีผลกับ transaction เนื่องจากมีบาง transaction ที่เป็น non-conflict serializable แต่ยังให้ผลลัพธ์ถูกต้อง จึงมีคนพยายามจะคิดวิธีใหม่เพื่อขนาดให้สามารถรองรับ transaction แบบนี้ได้

transaction ที่จะเป็น view equivalent กันจะต้องเป็นดังนี้
1. transaction ที่ read ค่าก่อนจะต้องเป็น transaction เดียวกัน
2. transaction ที่ write ค่าหลังจะต้องเป็น transaciton เดียวกัน
3. transaction ที่ read ค่าจากอีก transaction หนึ่ง จะต้องเหมือนกัน

schedule ที่สามารถทำ view serializable คือ schedule ที่สามารถทำ view serializable ได้ ซึ่งหมายถึงรองรับการสลับคำสั่ง แล้วยังคงลักษณะ view serializable ได้

Concurency Control: Basic Problem

ปัญหาของ concurrency control โดยทั่วไปมีดังนี้

1. lost update
   

   T1	T2
   read A= 30
   	read A = 30
   A = A + 1
   	A = A * 2

   ผลลัพธ์สุดท้าย คือ A = 60 เืสมือนว่า transaction t1 ไม่ได้เกิดขึ้นเลย
   ปัญหาข้อนี้ ถือว่า ไม่ conflict serializable
   
2. uncommitted dependency
   ตัวอย่าง
   
   

   T1	T2
   	update(A)
   read(A)
   	rollback

   
   จะเห็นว่า ค่าที่ T1 read ขึ้นไปเป็นค่าที่ผิดพลาดเพราะว่า T2 roll back
   
   
3. inconsistent analysis
   ตัวอย่างเช่น T1 เป็นการ sum ค่าทั้งหมด
   

   T1	T2
   read sum(30) = A(30)
   read sum(50) = sum + B(20)
   	read A = 30
   	A = A(30) - 10
   	C = C(50) + 10
   read sum(110) = sum + c(60)

   
   จะเห็นว่า ผล sum ที่ได้ผิดไป
   ปัญหานี้คือว่า ไม่เป็น conflict serializable
   
   
4. phantom phenomenon จะคล้ายกับ inconsistency analysis problem แต่เป็นปัญหาเนื่องจาก การ insert ข้อมูลเข้าไประหว่างการคำนวณไม่ใช่การ update (ความแตกต่างของ inconsistency analysis problem กับ phantom phenomenon คือ inconsistency analysis problem เป็น conflict serializable แต่ phantom ไม่เป็น conflict serializable)
   

Transaction: Concept

Transaction บน DBMS จะต้องมีลักษณะ ACID ดังนี้

1. Atomicity การทำงานจะทำงานเหมือนเป็นหนึ่งเดียว ถ้ามีการแก้ไขข้อมูล ก็จะต้องทำไปด้วยกัน ไม่มีการทำบางส่วน (ซึ่งต่อจากนั้นอาจจะมี system crash หรือเหตุการณ์อื่น ซึ่งทำให้ส่วนที่เหลือไม่ได้ทำงาน) หรือถ้า fail จะต้องไม่มีข้อมูลเปลี่ยนแปลงเลย
   
2. Consistency การทำงานแต่ละ transaction จะต้องทำเสมือนว่าทำงานแยกจาก transaction อื่นๆ และแต่ละครั้งที่ทำงานจะต้องให้ผลการทำงานเหมือนกัน
   
3. Isolation เป็นลักษณะการทำงานของ concurrent transaction ซึ่งโดยปกติแต่ละ DBMS จะสามารถกำหนดระดับของ isolation ได้ว่า จะให้เป็นแบบไหน
   
4. Durability
   

DB Backup

แบ่งเป็น 2 แบบคือ
1. Volume Backup คือ backup ทั้ง DB space
2. Incremental Backup คือ backup เฉพาะส่วนที่เปลี่ยนแปลง ซึ่งก็คือ log file หรือ AIJ เป็นการ archive log file นั่นเอง

ซึ่งการทำ Recovery จากการ backup นี้สำหรับกรณีที่ disk crash เท่านั้น เพราะในกรณี system crash อื่นๆ DBMS สามารถ recovery อัตโนมัติ เมื่อ start up ได้

ในกรณีที่ disk crash เราจะต้องทำ Roll Forward Activity คือการเอา back up กลับมาทำการ recovery ตามลำดับ เช่นการ backup แบบ volume backup ทุกอาทิตย์และแต่ละวันทำ incremental backup เมื่อต้องการทำ roll forward ก็จะเอา volume backup ทำ recovery แล้วจึงเอา incremental backup ของแต่ละวันทำ backup ทบกลับขึ้นไปเพื่อให้ได้ข้อมูลล่าสุด

DB Recovery: Buffer Management

Log-Record Buffering

กฎการทำงานของสำหรับ log buffer คือ
1. log record จะต้องถูกเขียนตามลำดับการทำงานก่อนหลัง ข้อมูลที่เปลี่ยนแปลงทีหลังจะไม่สามารถเขียน log ก่อนหน้าข้อมูลที่เปลี่ยนแปลงได้
2. เมื่อ transaction จะ commit ได้ จะต้องเขียน log record ลง log ก่อน
3. ข้อมูลที่จะเขียนจาก DB buffer ไปลง DB space จะต้องมีการ เีขียน log record เหล่านี้ลง log file ก่อนเสมอ ซึ่งเราเรียกกฎนี้ว่า Write Ahead Protocol หรือ Write Ahead Logging (WAL) ซึ่งบอกไว้ว่า log record จะต้องทำก่อนเขียน DB buffer ลง DB space ซึ่งการที่จะ write ส่วนไหนลงไปก่อนนั้น DBMS จะต้องทำงานประสานกับ OS เพื่อที่จะให้ DBMS สามารถเขียนข้อมูลลง disk ได้อย่างถูกต้องตาม protocol

Database Buffering

กฎการทำงานของ DB Buffer คือ ถ้าการเรียกข้อมูล B2 ทำให้ B1 จะต้องถูกเขียนกลับไปลง DB Space (คือ buffer เต็มแล้วเมื่อต้องเรียกข้อมูลขึ้นมา ก็จะต้องเขียนข้อมูลบางส่วนกลับลงไปที่ disk เื่พื่อให้ buffer มีที่พอสำหรับข้อมูลที่จะเีรียกขึ้นมาใหม่) DB Buffering จะต้องทำงานดังนี้
1. เขียน log records จาก log buffer ลง stable storage
2. เีขียนข้อมูล B1 กลับลงไปที่ DB space
3. แล้วจึงดึงข้อมูลของ B2 ขึ้นมาแทน B1 ใน buffer

OS Role in Buffer management

การจัดการ DB Buffer สามารถทำได้สองแนวทางคือ

1. DBMS จองเนื้อที่ในหน่วยความจำไว้จำนวนหนึ่ง มีขนาด fixe size (ซึ่งเป็นเนื้อที่ที่อยู่นอกเหนือ Virtual Memory ของ OS) สำหรับเป็น buffer และ DBMS จะเป็นตัวจัดการ buffer นั้นกับ DB space โดยตรง โดยไม่ผ่าน OS ซึ่งวิธีนี้เรียกอีกอย่างว่า Raw Device Option
   ข้อดี: ทำงานได้เร็วกว่า เพราะว่าไม่ต้องผ่าน OS เหมาะกับกรณี OS ทำงานกับ DBMS ได้ไม่ดี
   ข้อเสีย: Buffer จะต้องมีขนาดคงที่ค่าหนึ่ง ซึ่ง DBMS จะให้ DBA เป็นคนกำหนด และค่านี้ถ้ากำหนดน้อยเกินไป ก็ทำให้เนื้อที่ไม่เพียงพอกับข้อมูลที่จะใช้งานทำให้มีการ อ่าน เขียน buffer บ่อย แต่ถ้ากำหนดมากเกินไป ก็จะไปเสียเนื้อที่ใหน memory ทำให้ไม่เพียงพอกับการทำงานของโปรแกรมอื่นๆ ใน server
   


2. DB Buffer จะอยู่ใน Virtual Memory ของ OS และมีขนาดไม่คงที่ การทำงาน DBMS จะทำงานกับ OS เพื่อดึงและเขียนกลับข้อมูล
   ข้อดี: buffer มีขนาดไม่คงที่ จึงยืดหยุ่นในการทำงานได้ดีกว่า
   ข้อเสีย:ใช้กรณี DBMS และ OS ทำงานรวมกันไ้ด้ีดี
   

DB Recovery: Shadow Paging

การทำ shadow paging เป็นอีกเทคนิคในการ recovery นอกจาก log-based recovery ซึ่งใช้บนเครื่อง PC เท่านั้น โดย DBMS จะเขียนข้อมูลลง DB space เสมอ แม้ในขณะทำ transaction แต่การเขียนลง disk จะใช้วิธี shadow paging คือเมื่อมีการแก้ไขข้อมูลใน page ใดๆ ให้มีการสร้าง page ใหม่ขึ้นมาเพื่อเก็บข้อมูลของทั้ง page นั้นๆ ที่มีการเปลี่ยนแปลงแล้ว เมื่อมีการ commit ก็จะชี้ไปที่ page ใหม่ แต่ถ้ามี system crash หรือ transaction fail ก็จะกลับไปชี้ที่ page เก่า

ขอนอกเรื่องนิดหน่อย สำหรับ DB recovery ซึ่งเป็นเกร็ดนอกเหนือจาก Shadow Paging
การ recovery จะต้องเป็น idempotent หรือการปฏิบัิติกิจกรรมใดๆ หลายครั้ง จะต้องได้ผลเหมือนปฏิบัติเพียงครั้งเีดียว เ่ช่นในขณะที่มีการ recovery อยู่และีมี system crash เมื่อ start server ขึ้นมาใหม่ การ recovery ไม่ว่าจะทำกี่ครั้งก็ตามจะต้องให้ผลเหมือนกับทำครั้งเดียว ซึ่ง log-based recovery มีคุณสมบัติ idempotent แน่นอน

DB Recovery: Log-Based Recovery

Log is a widely used structure for recording database modifications.

โดย ปกติ แล้วการที่เราสั่ง commit บน DB ใดๆ ไม่ได้หมายถึงว่า ข้อมูลนั้นๆ จะไม่ถูกเขียนลงบน disk ทันที แค่เป็นการส่งข้อมูลให้ DB ซึ่ง DBMS ก็จะสัญญาว่า ข้อมูลเหล่านี้จะ้ต้องถูกเก็บลงบน disk ไม่ว่า ต่อไปจะมี system crash หรือกรณีใดๆ ก็ตาม

ซึ่ง log-based recovery เป็นวิธีการหนึ่งของ DBMS ที่ใช้ในการทำให้ข้อมูลที่ commit ไปแล้ว สามารถแสดงได้ถูกต้องหลังจากมี system crash แม้ว่าข้อมูลเหล่านั้นจะยังไม่ได้ถูกเขียนบน disk ก็ตาม

วิธีการ คือ ทุกครั้งที่มีการแก้ไขข้อมูลใน DB ข้อมูลนั้นๆ จะถูกเขียนลงบน log buffer บน memory และ log file ด้วย โดยข้อมูลที่เขียนไปลง log จะประกอบไปด้วย transaction id, data-item id, old value, new value และเมื่อมีคำสั่ง commit ก็จะมีการเขียนไปลง log ด้วยว่า transaction id ใด commit

เมื่อมี system crash เกิดขึ้น และเมื่อมีการ restart DBMS หรือใดๆ DBMS จะมีการทำงานตามลำดับคือ
1. อ่าน log file ย้อนกลับจากข้างท้าย และ ดูว่า transaction ใด commit
2. แยก transaction ที่ commit ใส่ไว้ที่ redo list นอกนั้นแยกลง undo list
3. หลังจากนั้น DBMS จะอ่าน old value ใน undo list มาแก้ไขข้อมูลใน DB
4. อ่าน new value ใน redo list ในแก้ไขใน DB

เมื่อทำเสร็จเรียบร้อย เราก็จะได้ข้อมูลที่ถูกต้องใน DB
หมายเหตุ: Oracle ไม่ได้เก็บ log file ไว้เป็น file เหมือนอย่าง file บน disk ทั่วๆ ไป แต่เก็บเป็นเนื้อที่ส่วนหนึ่งของ DB

log file ในปัจจุบันมีการแยกออกเป็น 2 แบบ คือ

1. After Image Journal (AIJ) หรือ Redo log file ซึ่ง จะเก็บเฉพาะ new value ไม่เก็บ old value
   


2. Before Image Journal (BIJ) หรือ Undo log file หรือ Undo จะตรงกันข้ามคือ เก็บ old value ไม่มี new value
   

ซึ่ง BIJ จะใช้สำหรับการ transaction ที่ยังไม่ได้ commit เท่านั้น เพื่อที่จะ rollback ข้อมูลกลับมาเมื่อมี system crash ระหว่างทาง ดังนั้น BIJ สามารถ recycle ตัวเองได้เมื่อ transaction commit ไปแล้ว BIJ จึงอาจจะกำหนดขนาดไว้คงที่ค่าหนึ่ง ให้เพียงพอกับขนาดของ transaction ในกรณีที่ BIJ เต็ม ซึ่งเกิดจากมีการ update หรือ delete ข้อมูลจำนวนมากๆ transaction ที่เป็นต้นเหตุจะ roll back สำหรับวิธีแก้ไข คือ
- ขยายขนาด BIJ ให้ใหญ่พอ
- ยกเลิก BIJ ชั่วคราว หรือ bypass BIJ เฉพาะ transaction ใหญ่ๆ
- หาวิธีแบ่ง transaction ใหญ่ๆ ให้เป็น transaction ย่อยๆ

แต่สำหรับ AIJ ซึ่งใช้เก็บข้อมูล new value ดังนั้นจึงไม่สามารถ recycle ข้อมูลได้ จะต้องเก็บไปเรื่อยๆ ถ้าี่ AIJ เต็ม จะมีผลให้ DBMS หยุดทำงาน หรือบาง DBMS ยังคงทำงานต่อไป แต่ว่า user จะต้องรับความเสี่ยงในกรณีมี system crash แต่ในปัจจุบันมีวิธีแก้ปัญหานี้อย่างถาวร คือ มีชุด AIJ เป็นไฟล์ชุดหนึ่ง เมื่อตัวแรกเต็ม ก็จะเก็บต่อในตัวถัดไป ซึ่งเปิดโอกาสให้ dba หรือ operator archive AIJ ตัวที่เต็มไปแล้ว และสามารถวนกลับมาให้เก็บข้อมูลต่อไป

Log-based Recovery classification

1. ประเภทที่เก็บแต่ BIJ (สำหรับ DBMS ตัวเก่าๆ) ซึ่งเลี่ยงปัญหา AIJ เต็ม ซึ่ง DBMS พวกนี้การ commit แต่ละครั้งจะหมายถึงการถูกเก็บลง DB space เสมอ (แต่ไม่ไ้ด้หมายความว่า เมื่อเราสั่ง commit DBMS จะเขียนข้อมูลกลับลง disk ทันที) ดังนั้น เมื่อมี system crash จึงทำเฉพาะในส่วนของ redo list เท่านั้นได้
   ข้อดี: ตอน recovery ทำไ้ด้เร็ว ไม่ต้องเปลืองเนื้อที่ในการเก็บ AIJ
   ข้อเสีย: การ commit ทำได้ช้า อาจจะเกิดปัญหาเรื่อง performance ต่อไป
   


2. Deferred DB Modification ประเภทนี้เก็บแต่ AIJ ซึ่งกรณีนี้จะมีผลต่อ transaction ที่ fail แต่มีการเขียนข้อมูลที่ update ไประหว่างกลาง transaction ดังนั้นกรณีที่ DBMS ทำงานในแบบนี้จะไม่มีการเขียนข้อมูลกลับจนกว่าจะมีคำสั่ง commit เท่านั้น DB พวกนี้ได้แก่พวก workgroup DBMS
   ข้อดี: DBMS แบบนี้บางครั้งเรียกว่า fast commit server หรือ fast commit option เนื่องจาก DBMS พวกนี้จะ commit ข้อมูลใช้เวลาน้อย เหมาะกับ OLTP
   ข้อเสีย: ไม่เหมาะกับการทำงานกับ transaction ขนาดใหญ่ เพราะว่า อาจทำให้ DB Buffer เต็มก่อนการ commit ดังนั้น DBMS พวกนี้จะต้องมี swap area ที่ใช้ขยายขนาด DB Buffer ที่เต็มให้สามารถรองรับการทำงานกับ transaction ใหญ่ๆ ได้
   


3. Immediate DB Modification แบบนี้จะต้องมี BIJ แต่อาจจะมีหรือไม่มี AIJ ก็ได้ ซึ่งแบบนี้จะสามารถเขียนลง disk ได้ทันที จะทำก่อนหรือหลัง commit ก็ได้
   

Checkpoint คือจุดที่กำหนดไ้ว้ว่า ณ.จุดก่อนหน้านั้นข้อมูลนั้นๆ ได้มีการ write ลง DB space แล้ว เมื่อมีการ recovery จึงสามารถทำหลังจากจุด checkpoint ได้ ซึ่งจะทำให้ประหยัดเวลาในการทำ recovery ได้มาก ณ.จุด checkpoint จะมีการทำงานดังนี้
1. เขียนข้อมูลทั้งหมดจาก log buffer ลง log file (บน stable storage)
2. เขียนข้อมูลทั้งหมดจาก DB buffer ลง disk หรือ DB space
3. mark จุด ลงบน log file