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
1
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
l
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
NW
WAGON (NW, TYPE...)
(cid:123) Ví dụ Ví d WAGON (NW, TYPE, COND, STATION, CAPACITY, WEIGHT)
NT = 4002
TRAIN (NT, NW)
TRAIN (NT, NW)
Vũ Tuyết Trinh, b/m Các hệ thống thông tin, khoa CNTT, ĐHBKHN
2
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
3
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
4
Đồ 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
5
(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
g
p
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
6
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
7
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
ố
NT
(cid:122) WAGON : có chỉ số
trên NW
(cid:123) Thực hiện phép kết
NW
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
8
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
NW
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
9
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
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
10
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
11
