Bài giảng Xử lý truy vấn và hiệu năng hệ cơ sở dữ liệu

1 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Xử lý truy vấn và 
hiệu năng hệ CSDL 
Vũ Tuyết Trinh 
trinhvt-fit@mail.hut.edu.vn 
Bộ môn Hệ thống thông tin, Viện CNTT&TT 
Đại học Bách Khoa Hà Nội 
Xử lý câu hỏi truy vấn 
Câu lệnh 
SQL 
Phân tích 
cú pháp 
(parser) 
Biểu thức 
ĐSQH 
Bộ tối ưu 
(optimizer) 
Biểu thức 
ĐSQH 
tối ưu 
Bộ sinh mã 
(code generator) 
Chương trình 
tối ưu 
2 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Cây toán tử 
WAGON (NW, TYPE, COND, STATION, 
 CAPACITY, WEIGHT) 
TRAIN (NT, NW) 
 Cây toán tử logic 
 Thứ tự các phép toán 
 Cây toán tử vật lý 
 Các thuật toán thực thi phép toán 
WAGON 
(NW, TYPE...) 
TRAIN 
(NT, NW) 
NW 
NT = 4002 
TYPE 
Các phép toán vật lý (thuật toán) 
 Query Blocks 
 SELECT-FROM-
WHERE-GROUPBY-
ORDERBY 
 VIEW được coi là 1 
block riêng rẽ 
 Dạng cây thực thi 
(right-deep, bushy, ) 
 Thứ tự kết nối 
 Thuật toán 
 Sort 
 Aggregates 
 Select 
 Project 
 Join 
 Nested Loop 
 Sort-Merge 
 Hash-Join 
3 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Truy nhập bảng 
 Truy nhập tuần tự (Sequential scan): đọc theo 
khối 
 Truy nhập theo địa chỉ (index scan): truy nhập 
vào bản ghi dựa trên chỉ mục 
 Chi phí truy nhập ? 
S 
Phép toán nhiều pha: 
Nested-Loops Join 
 Nguyên tắc 
 Đọc từng bản ghi của quan 
hệ R (external relation) & lặp 
trên quan hệ S (internal 
relation) 
 Đặc điểm 
 one-and-haft pass, non-
blocking 
 Chi phí ? 
SOURCE 
S 
SOURCE 
R 
Tuple R 
Tuple R 
Tuple S 
Matching 
Tuple-based NLJ, block-based NLJ, index-based NLJ 
4 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Sort Merge Join 
 Nguyên tắc 
 Sắp xếp dữ liệu đầu vào 
 trộn dữ liệu 
 Đặc điểm 
 two-pass, blocking algorithm 
 Chi phí? 
SOURCE 
S 
SOURCE 
R 
Merge 
Sort 
Sort 
Hash Join (HJ) 
 Nguyên tắc 
 Tạo bảng băm trên R 
 Đọc S và đối sánh với dữ liệu 
trên bảng băm 
 Đặc điểm 
 two-pass, blocking algorithm 
 Chi phí ? 
SOURCE 
S 
SOURCE 
R 
Tuple R Tuple S 
Hash Table R 
 1 n 
Matching 
hash(Tuple S) hash(Tuple R) 
build 
probe 
5 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Mô hình giá 
 Chí phí thực hiện câu hỏi phụ thuộc: 
 đọc/ghi bộ nhớ ngoài (số trang nhớ) 
Kích thước dữ liệu phải xử lý 
 Chi phí truy nhập dữ liệu 
Đọc ghi dữ liệu 
xử lý 
Truyền thông giữa các trạm làm việc 
CTA = s * NBPAGES + t * NBNUPLETS (+ m * NBMESSAGES) 
 Trọng số 
 s = trọng số đọc/ghi dữ liệu (ví dụ = 1) 
 t = trọng số xử lý của CPU (ví dụ = 1/3) 
 m = trọng số truyền dữ liệu 
Thông tin về các quan hệ 
 Kích thước của các quan hệ và bản ghi 
 Thông tin về các thuộc tính 
 Thông tin về các chỉ số 
Relation Cardinality Record size 
WAGON 200000 60 
TRAIN 60000 30 
TRAFFIC 80000 20 
Attribute Cardinality Size min - max 
NW 200000 20 
TYPE 200 5 
COND 5 15 
CAPACITY 400 15 5 - 45 
NT 2000 10 
DATE 8 00 6 
Relation Attributes Unique Type Num of pages 
WAGON NW Yes Principal 45 
WAGON TYPE No Secondary 25 
WAGON COND No Secondary 30 
WAGON CAPACITY No Secondary 25 
TRAIN NT No Principal 18 
TRAFFIC NT No Principal 20 
TRAFFIC DATE no Principal 40 
Relation Cardinality Record size 
(num of rec./page) 
Num. of pages 
(NP’) 
WAGON 200000 60(100) 1500(375) 
TRAIN 60000 30 (200) 225(60) 
TRAFFIC 80000 20 (300) 200(60) 
6 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Tối ưu 
 Đặt vấn đề: Cho 1 câu truy vấn, các cây toán tử thực 
thi nào sẽ được xem xét ? 
 Không gian tìm kiếm 
 Chiến lược tìm kiếm 
 Ước lượng giá cho các kế hoạch thực thi 
 Lý tưởng: tìm ra kế hoạch thực thi tốt nhất 
 Thực tế: Tránh kế hoạch thực thi tồi 
Bộ tối ưu 
Rewriter 
Planner 
Method-Structure 
Space 
Algebraic 
Space 
Size-Distribution 
Estimator 
Cost Model 
7 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Query: R1 R2 R3 R4 R5 
R3 R2 
R4 
R1 
R5 
Optimal Plan: 
R3 R2 
R4 
R1 
R5 
Optimal Plan: 
Optimal plan for joining R3, R2, R4 
Query: R1 R2 R3 R4 R5 
Optimal plan for 
joining R3, R2, R4, 
R1 
8 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
R3 R1 
R2 
R2 R3 
R1 
Optimal 
for joining R1, R2, R3 
Sub-Optimal 
for joining R1, R2, R3 
{ R1 } { R2 } { R3 } { R4 } 
{ R1, R2 } { R1, R3 } { R1, R4 } { R2, R3 } { R2, R4 } { R3, R4 } 
{ R1, R2, R3 } { R1, R2, R4 } { R1, R3, R4 } { R2, R3, R4 } 
{ R1, R2, R3, R4 } 
R2 
R3 
R4 
R1 
Cây toán tử tối ưu 
Tiến trình tối ưu 
9 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Các lý do dẫn đến hiệu năng thực 
thi truy vấn chậm 
 Đòi hỏi nhiều phép truy nhập đĩa 
 Không sử dụng index 
 Cấu trúc CSDL không hợp lý 
 Các giao dịch dư thừa, lồng nhau 
Ví dụ 
 Employee(ssnum, name, manager, dept, salary, 
numfriends) 
 Clustering index : ssnum 
 Non clustering indexes (i) name (ii) dept 
 Student(ssnum, name, degree_sought, year) 
 Clustering index :ssnum 
 Non clustering index :name 
 Tech(dept, manager, location) 
 Clustering index : dept 
10 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Các kỹ thuật viết lại truy vấn 
 Sử dụng Index 
 Loại bỏ DISTINCTs 
 Xem xét câu truy vấn lồng nhau 
 Điều kiện kết nối 
 Mệnh đề having 
 Sử dụng view 
 Khung nhìn lưu trữ (Materialized views) 
Sử dụng Index 
 Một số trường hợp index không được sử 
dụng 
 Biểu thức toán học 
WHERE salary/12 >= 4000; 
 Hàm tính toán trên xâu 
SELECT * FROM employee 
WHERE SUBSTR(name, 1, 1) = „G‟; 
 So sánh các trường không cùng kiểu 
 So sánh với giá trị rỗng 
11 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Hạn chế sử dụng DISTINCTs 
 Ví dụ 
 SELECT distinct ssnum 
FROM employee 
WHERE dept = „information systems‟ 
 có thể loại bỏ distinct 
Hạn chế sử dụng DISTINCTs 
 Ví dụ 
 SELECT DISTINCT ssnum 
FROM employee, tech 
WHERE employee.dept = tech.dept 
 Có cần sử dụng DISTINCT? 
12 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Employee(ssnum, name, manager, dept, salary, numfriends) 
Student(ssnum, name, degree_sought, year) 
Tech(dept, manager, location) 
 SELECT ssnum 
FROM employee, tech 
WHERE employee.manager = tech.manager 
 SELECT ssnum, tech.dept 
FROM employee, tech 
WHERE employee.manager = tech.manager 
 SELECT student.ssnum 
FROM student, employee, tech 
WHERE student.name = employee.name 
 AND employee.dept = tech.dept; 
 23 
Truy vấn lồng nhau 
 SELECT ssnum FROM employee 
WHERE salary > (select avg(salary) 
 from employee) 
 SELECT ssnum FROM employee 
WHERE dept in (select dept from tech) 
 SELECT ssnum 
 FROM employee e1 
WHERE salary = 
 (SELECT avg(e2.salary) 
 FROM employee e2,tech 
 WHERE e2.dept = e1.dept AND 
 e2.dept = tech.dept) 
13 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Viết lại truy vấn lồng nhau 
SELECT ssnum 
FROM employee 
WHERE dept in (select dept 
 from tech) 
SELECT ssnum 
FROM employee, tech 
WHERE employee.dept = tech.dept 
Truy vấn lồng nhau với các phép 
toán tập hợp 
 Ví dụ 
 SELECT avg(salary) 
FROM employee 
WHERE manager in (select manager from tech) 
 SELECT avg(salary) 
FROM employee, tech 
WHERE employee.manager = tech.manager 
 So sánh 2 câu truy vấn trên 
14 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Truy vấn lồng có kết nối 
 Ví dụ 
SELECT ssnum 
FROM employee e1 
WHERE salary = (SELECT avg(e2.salary 
 FROM employee e2, tech 
 WHERE e2.dept = e1.dept 
 and e2.dept = tech.dept); 
 INSERT INTO temp 
SELECT avg(salary) as avsalary, employee.dept 
FROM employee, tech 
WHERE employee.dept = tech.dept 
GROUP BY employee.dept; 
 SELECT ssnum 
FROM employee, temp 
WHERE salary = avsalary 
 AND employee.dept = temp.dept 
SELECT ssnum 
FROM employee e1 
WHERE numfriends = COUNT(SELECT e2.ssnum 
 FROM employee e2, tech 
 WHERE e2.dept = tech.dept 
 AND e2.dept = e1.dept); 
 INSERT INTO temp 
SELECT COUNT(ssnum) as numcolleagues, 
employee.dept 
FROM employee, tech 
WHERE employee.dept = tech.dept 
GROUP BY employee.dept; 
 SELECT ssnum 
FROM employee, temp 
WHERE numfriends = numcolleagues 
 AND employee.dept = temp.dept; 
Employee(ssnum, name, manager, dept, salary, numfriends) 
Student(ssnum, name, degree_sought, year) 
Tech(dept, manager, location) 
15 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Điều kiện kết nối 
 Kết nối trên trường dữ liệu có clustering 
indexes. 
 Kết nối trên trường dữ liệu kiểu số “tốt hơn” là 
trên trường dữ liệu kiểu xâu ký tự 
Sử dụng khung nhìn 
 CREATE VIEW techlocation 
AS 
SELECT ssnum, tech.dept, 
 location 
FROM employee, tech 
WHERE 
 employee.dept = 
tech.dept; 
 SELECT location 
FROM techlocation 
WHERE ssnum = 43253265; 
 SELECT location 
FROM employee, tech 
WHERE 
 employee.dept = 
tech.dept 
 AND ssnum = 
43253265; 
16 
Thiết kế và quản trị cơ sở dữ liệu 
Vũ Tuyết Trinh 
Lưu trữ khung nhìn 
 Materialized views: 
 CREATE MATERIALIZED VIEW VendorOutstanding 
BUILD IMMEDIATE 
REFRESH COMPLETE 
ENABLE QUERY REWRITE 
AS 
SELECT orders.vendor, sum(orders.quantity*item.price) 
FROM orders,item 
WHERE orders.itemnum = item.itemnum 
group by orders.vendor; 
 Các tham số 
 BUILD immediate/deferred 
 REFRESH complete/fast 
 ENABLE QUERY REWRITE 
 Lợi ích: 
 Tự động cập nhật các dữ liệu tính toán 
 Sử dụng bởi bộ tối ưu truy vấn 
32