Giáo trình Thiết kế và quản trị cơ sở dữ liệu - Chương 4: Xử lý truy vấn và hiệu năng hệ Cơ sở dữ liệu - Vũ Tuyết Trinh

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