Bài giảng Tối ưu hóa câu hỏi

Nhập môn cơ sở dữ liệu

Tối ưu hoá câu hỏi

Vũ Tuyết Trinh trinhvt@it-hut.edu.vn

Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin Đại học Bách Khoa Hà Nội

Xử lý câu hỏi truy vấn

Câu lệnh SQL

Biểu thức ĐSQH

Phân tích cú pháp (parser)

Biểu thức ĐSQH tối ưu

Bộ tối ưu (optimizer)

Bộ sinh mã (code generator)

Chương trình tối ưu

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Tối ưu hoá

(cid:123) Biến đổi biểu thức ĐSQH để tìm 1 biểu thức

hiệu quả

(cid:123) Tối ưu dựa trên cấu trúc và nội dung của dữ

liệu

(cid:123) Nâng cao hiệu quả thực hiện câu hỏi trên 1 hay nhiều tiêu chí: thời gian, sử dụng bộ nhớ, ...

(cid:123) Lưu ý: (cid:123) Lưu ý:

(cid:122) Không nhất thiết phải tìm biểu thức tối ưu nhất (cid:122) Chú ý tới tài nguyên sử dụng cho tối ưu

Kỹ thuật tối ưu hoá

TYPE TYPE

(cid:123) 2 kỹ thuật chính (

Tối

iti

(cid:122) Tối ưu logic (rewriting) ) i (cid:122) Tối ưu vật lý (access methods)

(cid:123) Mục đích của các kỹ thuật tối ưu

(cid:122) Giảm số bản ghi (cid:122) Giảm kích thước bản ghi

WAGON (NW, TYPE...)

(cid:123) Ví dụ Ví d WAGON (NW, TYPE, COND, STATION, CAPACITY, WEIGHT)

NT = 4002

TRAIN (NT, NW)

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Nội dung

(cid:57) Giới thiệu chung (cid:123) Tối ưu logic (cid:123) Tối ưu vật lý (cid:123) Mô hình giá

Tối ưu hoá logic

(cid:123) Sử dụng các phép biến đổi tương đương để tìm

ra biểu thức ĐSQH tốt ố

ể

(cid:123) Gồm 2 giai đoạn

(cid:122) Biến đổi dựa trên ngữ nghĩa

(cid:122) Biến đổi dựa trên tính chất của các phép toán ĐSQH (cid:122) Biến đổi dựa trên tính chất của các phép toán ĐSQH

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Tối ưu dựa trên ngữ nghĩa

(cid:123) Mục đích:

(cid:122) Dựa trên các ràng buộc dữ liệu để xác định các biểu

ể

thức tương đương

(cid:122) Viết lại câu hỏi trên khung nhìn dựa trên các định

nghĩa của khung nhìn

(cid:123) Ví dụ

EMPLOYEE (FirstName, LastName, SSN, Birthday,

Adrresse, NoDept)

DEPARTEMENT (DNO, DName, SSNManager) PROJECT (PNO, PName, PLocation, DNo) WORK-IN (ESSN, PNO, Heures)

EMPLOYEE (Name, SSN, Birthday, Adrresse, NoDept)

DEPARTEMENT (DNO, DName, SSNManager)

PROJECT (PNO, PName, PLocation, DNo)

WORK-IN (ESSN, NoProj, Heures)

Tên của các nhân viên sinh sau ngày 30/01/70 và làm việc cho dự án "Esprit"

Result

WORK-IN.ESSN

Name

EMPLOYEE. SSN

WORK-IN

PROJECT.PNO

WORK-IN. PNO

NoProj = PNO

ESSN=SSN

“Esprit”

PROJECT.PNO

PROJET

PName = “Esprit”

EMPLOYE

“30/01/70”

Birthday > “30/01/70

EMPLOYEE. Birthday

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Đồ thị kết nối các quan hệ Đồ thị kết nối các thuộc tính

Nhập môn cơ sở dữ liệu

Tối ưu dựa trên ngữ nghĩa (2)

(cid:123) Loại bỏ các đồ thị con không liên kết trong đồ

thị kết nối các quan hệ

ế

ố

(cid:123) Kiểm tra mâu thuẫn trong đồ thị kết nối các

thuộc tính

(cid:123) Biến đổi câu hỏi tương đương

Biế đổi â hỏi t

Tính chất của phép toán ĐSQH

A ~ tập các thuộc tính, C ~ biểu thức điều kiện

1. Phép chiếu và phép chọn

Π (R) => Π (Π (R) nếu A ⊆ A1 A A1 A

(R)) nếu C = C1^C2 σ (R) => σ (σ C1 C2 C

2. Tính giao hoán đối với phép chọn và chiếu

(R)) (R)) σ σ (σ => (R)) nếu các thuộc tính của C2 thuộc A1 Π (σ (Π (R)) σ => (σ C1 C2 C2 C1 A1 C2 C2 A1

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

(R)) σ (Π (R)) => Π (Π (R)) Π (R) => C1 A2 Π (σ A2 C1 A1 A1 A2 nếu A1 ⊆ A2

Nhập môn cơ sở dữ liệu

Tính chất của phép toán ĐSQH (2)

3. Tính giao hoán và kết hợp của các phép toán

ợp

∗, ∩, ∪, −, x

R X S => S X R

R * S => S * R

R ∩ S => S ∩ R

S ∪ R R ∪ S => S ∪ R R ∪ S (R X S) X T => R X (S X T)

(R ∩ S) ∩ T => R ∩ (S ∩ T)

(R ∪ S) ∪ T => R ∪ (S ∪ T)

(R * S) * T => R * (S * T) C1 C2 C1 C2 chỉ nếu Attr(C2) ⊆ Attr(S) U Attr(T)

Tính chất của phép toán ĐSQH (3)

4. Tính phân phối σ và Π trên các phép toán *, ∩,

∪, -, X

Nếu C = (CR ^ CS) và nếu Attr(CR) ⊆ R và Attr(CS) ⊆ S thì :

(S)

(R) * σ

σ (R * S) => σ JC

C

JC CS

CR

(S)

σ (R X S) => σ

(R) X σ

CR CR

CS CS

C C

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Biến đổi biểu thức ĐSQH

R: F1 ∧ F2 ∧ ... Fn

((...(R:F1) : F2 ):...):Fn

[ ]

( [ ]) [ ] (R[Y]) [Z]

⊆

(R[Y]) :F (X)

(R :F(X)) [Y] n(cid:31) u X ⊆ Y

(R: F(X)) [Y]

(R[X ∪ Y]) : F(X) ) [Y] n(cid:31) u X ⊄ Y

(R(X) x S(Y)) : F(Z)

(R(X):F) x S(Y) n(cid:31) u Z ⊆ X

(R(X):F(Z1)) x (S(Y): F(Z2)) n(cid:31) u Z1 ⊆ X và Z2 ⊆ Y

(R:F) ∪ (S:F)

(R ∪ S): F

(R - S): F

(R:F) - S

(R(X) x S(Y))[Z]

R[X ∩ Z] x S[Y ∩ Z]

(R ∪ S) [Z]

T1 _________________________________ T2 R[Z] n(cid:31) u Z ⊆ Y _ T3 _ T4 (R(X) x S(Y)) : F(Z1)∧ F(Z2) _ T5 _ T6 _ T7 _ (R[Z]) ∪ (S[Z]) T8 _________________________________

Trình tự áp dụng

(cid:123) Khai triển phép lựa chọn dựa trên nhiều điều

kiện: T1 kiện: T1

(cid:123) Hoán vị phép chọn với tích đề-các, hợp, trừ: T3,

T4, T5, T6

(cid:123) Hoán vị phép chiếu với tích đề-các, hợp : T2,

T7, T8,

(cid:123) Nhóm các điều kiện chọn bởi T1 và áp dụng T2

để loại các phép chiếu dư thừa

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Bài tập

Lựa chọn cách truy nhập dữ liệu

(cid:123) Giả thiết

TYPE TYPE

(cid:122) TRAIN : có chỉ số trên

ố

(cid:122) WAGON : có chỉ số

trên NW

(cid:123) Thực hiện phép kết

WAGON (NW, TYPE...)

NT = 4002

nối (cid:122) Lựa chọn 1 giải thuật. (cid:122) Lựa chọn cách truy nhập các quan hệ

TRAIN (NT, NW)

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Relation S

Nested-loop-join (NLJ)

(cid:123) Nguyên tắc

(cid:122) Duyệt 1 lần trên quan hệ

Matching

ngoài R & lặp trên quan hệ trong S

Tuple R

(cid:123) Các mở rộng của thuật toán (cid:122) Tuple-based NLJ, block-

based NLJ, index-based NLJ Tuple R

p

p Tuple S

SOURCE R

SOURCE S

Thực hiện như thế nào?

TYPE TYPE

WAGON (NW, TYPE...)

NT = 4002

TRAIN (NT, NW)

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Thông tin về các quan hệ

(cid:123) Kích thước của các quan hệ và bản ghi

Cardinality 200000 60000 80000

Record size 60 30 20

Relation WAGON TRAIN TRAFFIC (cid:123)Thông tin về các thuộc tính (cid:123)Thông tin về các thuộc tính

min -max

5 -45

Attribute NW TYPE COND CAPACITY NT DATE

Cardinality 200000 200 5 400 2000 8 00

Size 20 5 15 15 10 6

(cid:123)Thông tin về các chỉ số

Attributes NW TYPE TYPE COND CAPACITY NT NT DATE

Unique Yes N No No No No No no

Type Principal S Secondary d Secondary Secondary Principal Principal Principal

Num of pages 45 25 25 30 25 18 20 40

Relation WAGON WAGON WAGON WAGON WAGON TRAIN TRAFFIC TRAFFIC Relation

Cardinality

WAGON TRAIN TRAFFIC

200000 60000 80000

Record size (num of rec./page) 60(100) 30 (200) 20 (300)

Num. of pages (NP’) 1500(375) 225(60) 200(60)

Mô hình giá

(cid:123) Chí phí thực hiện câu hỏi phụ thuộc:

ọ g

ộ

(

(cid:122) đọc/ghi bộ nhớ ngoài (số trang nhớ) ) g (cid:122)Kích thước dữ liệu phải xử lý

(cid:123)Chi phí truy nhập dữ liệu

(cid:122)Đọc ghi dữ liệu (cid:122)xử lý y (cid:122)Truyền thông giữa các trạm làm việc

g g

CTA = σ * NBPAGES + τ ∗ NBNUPLETS (+ µ ∗ NBMESSAGES)

(cid:123)Trọng số

(cid:123)σ = trọng số đọc/ghi dữ liệu (ví dụ = 1) (cid:123)τ = trọng số xử lý của CPU (ví dụ = 1/3) (cid:123)µ = trọng số truyền dữ liệu

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Nhập môn cơ sở dữ liệu

Tối ưu hoá dựa trên mô hình giá

(cid:123) Mục đích: Chọn phương án thực hiện câu hỏi

với chi phí thấp nhất ấ

ấ

(cid:123) Nhận xét:

(cid:122) Chi phí cho liệt kê các phương án trả lời câu hỏi (cid:122) Chi phí cho lượng hoá các phương án theo mô hình

giá

(cid:190) Có thể sử dụng các « mẹo » (heuristics) để giảm

không gian tìm kiếm của câu hỏi

Kết luận

(cid:123) Tối ưu hoá nhằm tìm phương án tốt nhất để

hiệ

th thực hiện một câu hỏi ột â hỏi (cid:122) Cần lưu ý: chí phí thực hiện tối ưu hoá và chi phí thực

hiện câu hỏi (cid:123) Các kỹ thuật tối ưu

(cid:122) Logic : kiểm tra điều kiện ràng buộc của các thuộc

tính/quan hệ và điều kiện lựa chọn trong câu hỏi, biến đổi tương đương các biểu thức ĐSQH

(cid:122) Vật lý : tổ chức vật lý của dữ liệu trên đĩa, mô hình giá (cid:190) Không nhất thiết phải áp dụng tất cả các kỹ thuật trên

khi thực hiện tối ưu hoá 1 câu hỏi

Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN

Bài giảng Tối ưu hóa câu hỏi - Vũ Tuyết Trinh

Tối ưu hoá câu hỏi

Xử lý câu hỏi truy vấn

Câu lệnh SQL

Biểu thức ĐSQH

Phân tích cú pháp (parser)

Biểu thức ĐSQH tối ưu

Bộ tối ưu (optimizer)

Bộ sinh mã (code generator)

Chương trình tối ưu

Tối ưu hoá

Kỹ thuật tối ưu hoá

Nội dung

Tối ưu hoá logic

Tối ưu dựa trên ngữ nghĩa

Result

WORK-IN

“Esprit”

PROJET

EMPLOYE

“30/01/70”

Tối ưu dựa trên ngữ nghĩa (2)

Tính chất của phép toán ĐSQH

2. Tính giao hoán đối với phép chọn và chiếu

Tính chất của phép toán ĐSQH (2)

Tính chất của phép toán ĐSQH (3)

(S)

(R) * σ

σ (R * S) => σ JC

C

JC CS

CR

(S)

(R) X σ

CR CR

CS CS

C C

Biến đổi biểu thức ĐSQH

Trình tự áp dụng

Bài tập

Lựa chọn cách truy nhập dữ liệu

Nested-loop-join (NLJ)

Matching

Tuple R

p

p Tuple S

SOURCE R

SOURCE S

Thực hiện như thế nào?

Thông tin về các quan hệ

Cardinality 200000 60000 80000

Record size 60 30 20

Relation WAGON TRAIN TRAFFIC (cid:123)Thông tin về các thuộc tính (cid:123)Thông tin về các thuộc tính

min -max

Attribute NW TYPE COND CAPACITY NT DATE

Cardinality 200000 200 5 400 2000 8 00

Size 20 5 15 15 10 6

Attributes NW TYPE TYPE COND CAPACITY NT NT DATE

Unique Yes N No No No No No no

Type Principal S Secondary d Secondary Secondary Principal Principal Principal

Num of pages 45 25 25 30 25 18 20 40

Relation WAGON WAGON WAGON WAGON WAGON TRAIN TRAFFIC TRAFFIC Relation

Cardinality

Record size (num of rec./page) 60(100) 30 (200) 20 (300)

Num. of pages (NP’) 1500(375) 225(60) 200(60)

Mô hình giá

Tối ưu hoá dựa trên mô hình giá

Kết luận

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ