Bài giảng Thiết kế và quản trị cơ sở dữ liệu - 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