Thiết kế và quản trị cơ sở dữ liệu 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 Vũ Tuyết Trinh fb.com/groups/ 1 Thiết kế và quản trị cơ sở dữ liệu Cây toán tử TYPE WAGON (NW, TYPE, COND, STATION, CAPACITY, WEIGHT) TRAIN (NT, NW)  Cây toán tử logic   Thứ tự các phép toán NW Cây toán tử vật lý  Các thuật toán thực thi phép toán WAGON (NW, TYPE...) NT = 4002 TRAIN (NT, NW) Các phép toán vật lý (thuật toán)  Query Blocks SELECT-FROMWHERE-GROUPBYORDERBY  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 Vũ Tuyết Trinh fb.com/groups/ 2 Thiết kế và quản trị cơ sở dữ liệu 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   Matching Tuple R Đặc điểm   Đọc từng bản ghi của quan hệ R (external relation) & lặp trên quan hệ S (internal relation) one-and-haft pass, nonblocking Tuple R Tuple S SOURCE R SOURCE S Chi phí ? Tuple-based NLJ, block-based NLJ, index-based NLJ Vũ Tuyết Trinh fb.com/groups/ 3 Thiết kế và quản trị cơ sở dữ liệu Sort Merge Join  Nguyên tắc Merge Sắp xếp dữ liệu đầu vào  trộn dữ liệu   Đặc điểm   two-pass, blocking algorithm Sort Chi phí? Sort SOURCE R SOURCE S 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 Matching   Đặc điểm   Hash Table R 1 … n two-pass, blocking algorithm probe Ch