Bài giảng 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ệ CSDL

Thiết kế và quản trị cơ sở dữ liệu<br /> <br /> Xử lý truy vấn và<br /> hiệu năng hệ CSDL<br /> <br /> Vũ Tuyết Trinh<br /> trinhvt-fit@mail.hut.edu.vn<br /> Bộ môn Hệ thống thông tin, Viện CNTT&TT<br /> Đại học Bách Khoa Hà Nội<br /> <br /> Xử lý câu hỏi truy vấn<br /> Câu lệnh<br /> SQL<br /> <br /> Phân tích<br /> cú pháp<br /> (parser)<br /> <br /> Biểu thức<br /> ĐSQH<br /> <br /> Bộ tối ưu<br /> (optimizer)<br /> <br /> Biểu thức<br /> ĐSQH<br /> tối ưu<br /> <br /> Bộ sinh mã<br /> (code generator)<br /> <br /> Chương trình<br /> tối ưu<br /> <br /> Vũ Tuyết Trinh<br /> <br /> 1<br /> <br /> Thiết kế và quản trị cơ sở dữ liệu<br /> <br /> Cây toán tử<br /> TYPE<br /> <br /> WAGON (NW, TYPE, COND, STATION,<br /> CAPACITY, WEIGHT)<br /> TRAIN (NT, NW)<br /> <br /> <br /> Cây toán tử logic<br /> <br /> <br /> <br /> <br /> Thứ tự các phép toán<br /> <br /> NW<br /> <br /> Cây toán tử vật lý<br /> <br /> <br /> Các thuật toán thực thi phép toán<br /> <br /> WAGON<br /> (NW, TYPE...)<br /> NT =<br /> <br /> 4002<br /> <br /> TRAIN<br /> (NT, NW)<br /> <br /> Các phép toán vật lý (thuật toán)<br /> <br /> <br /> Query Blocks<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> SELECT-FROMWHERE-GROUPBYORDERBY<br /> VIEW được coi là 1<br /> block riêng rẽ<br /> <br /> Dạng cây thực thi<br /> (right-deep, bushy, …)<br /> Thứ tự kết nối<br /> <br /> <br /> <br /> Thuật toán<br /> <br /> <br /> <br /> <br /> <br /> <br /> Sort<br /> Aggregates<br /> Select<br /> Project<br /> Join<br /> <br /> <br /> <br /> <br /> Vũ Tuyết Trinh<br /> <br /> Nested Loop<br /> Sort-Merge<br /> Hash-Join<br /> <br /> 2<br /> <br /> Thiết kế và quản trị cơ sở dữ liệu<br /> <br /> Truy nhập bảng<br /> <br /> <br /> <br /> <br /> <br /> <br /> Truy nhập tuần tự (Sequential scan): đọc theo<br /> khối<br /> Truy nhập theo địa chỉ (index scan): truy nhập<br /> vào bản ghi dựa trên chỉ mục<br /> Chi phí truy nhập ?<br /> <br /> S<br /> <br /> Phép toán nhiều pha:<br /> Nested-Loops Join<br /> <br /> <br /> Nguyên tắc<br /> <br /> <br /> <br /> <br /> Matching<br /> Tuple R<br /> <br /> Đặc điểm<br /> <br /> <br /> <br /> <br /> Đọc từng bản ghi của quan<br /> hệ R (external relation) & lặp<br /> trên quan hệ S (internal<br /> relation)<br /> one-and-haft pass, nonblocking<br /> <br /> Tuple R<br /> <br /> Tuple S<br /> <br /> SOURCE<br /> R<br /> <br /> SOURCE<br /> S<br /> <br /> Chi phí ?<br /> <br /> Tuple-based NLJ, block-based NLJ, index-based NLJ<br /> <br /> Vũ Tuyết Trinh<br /> <br /> 3<br /> <br /> Thiết kế và quản trị cơ sở dữ liệu<br /> <br /> Sort Merge Join<br /> <br /> <br /> Nguyên tắc<br /> <br /> <br /> <br /> <br /> <br /> Đặc điểm<br /> <br /> <br /> <br /> <br /> Merge<br /> <br /> Sắp xếp dữ liệu đầu vào<br /> trộn dữ liệu<br /> two-pass, blocking algorithm<br /> <br /> Sort<br /> <br /> Chi phí?<br /> <br /> Sort<br /> <br /> SOURCE<br /> R<br /> <br /> SOURCE<br /> S<br /> <br /> Hash Join (HJ)<br /> <br /> <br /> Nguyên tắc<br /> <br /> <br /> <br /> <br /> <br /> Đặc điểm<br /> <br /> <br /> <br /> <br /> Tạo bảng băm trên R<br /> Đọc S và đối sánh với dữ liệu<br /> trên bảng băm<br /> <br /> Matching<br /> Hash Table R<br /> <br /> 1<br /> <br /> …<br /> <br /> n<br /> <br /> two-pass, blocking algorithm<br /> <br /> probe<br /> <br /> Chi phí ?<br /> build<br /> Tuple R<br /> <br /> Tuple S<br /> <br /> hash(Tuple R)hash(Tuple S)<br /> SOURCE<br /> R<br /> <br /> Vũ Tuyết Trinh<br /> <br /> SOURCE<br /> S<br /> <br /> 4<br /> <br /> Thiết kế và quản trị cơ sở dữ liệu<br /> <br /> Mô hình giá<br /> <br /> <br /> Chí phí thực hiện câu hỏi phụ thuộc:<br /> đọc/ghi bộ nhớ ngoài (số trang nhớ)<br /> Kích thước dữ liệu phải xử lý<br /> <br /> <br /> Chi<br /> <br /> phí truy nhập dữ liệu<br /> Đọc ghi dữ liệu<br /> xử lý<br /> Truyền thông giữa các trạm làm việc<br /> <br /> CTA = s * NBPAGES + t * NBNUPLETS (+ m * NBMESSAGES)<br /> Trọng<br /> <br /> số<br /> s = trọng số đọc/ghi dữ liệu (ví dụ = 1)<br /> t = trọng số xử lý của CPU (ví dụ = 1/3)<br /> m = trọng số truyền dữ liệu<br /> <br /> <br /> <br /> Thông tin về các quan hệ<br /> <br /> <br /> Kích thước của các quan hệ và bản ghi<br /> Relation<br /> WAGON<br /> TRAIN<br /> TRAFFIC<br /> <br /> Thông<br /> <br /> Cardinality<br /> 200000<br /> 200<br /> 5<br /> 400<br /> 2000<br /> 800<br /> <br /> Size<br /> 20<br /> 5<br /> 15<br /> 15<br /> 10<br /> 6<br /> <br /> min -max<br /> <br /> 5-45<br /> <br /> tin về các chỉ số<br /> Relation<br /> WAGON<br /> WAGON<br /> WAGON<br /> WAGON<br /> TRAIN<br /> TRAFFIC<br /> TRAFFIC<br /> <br /> Vũ Tuyết Trinh<br /> <br /> Record size<br /> 60<br /> 30<br /> 20<br /> <br /> tin về các thuộc tính<br /> Attribute<br /> NW<br /> TYPE<br /> COND<br /> CAPACITY<br /> NT<br /> DATE<br /> <br /> Thông<br /> <br /> Cardinality<br /> 200000<br /> 60000<br /> 80000<br /> <br /> Attributes<br /> NW<br /> TYPE<br /> COND<br /> CAPACITY<br /> NT<br /> NT<br /> DATE<br /> <br /> Relation<br /> <br /> Cardinality<br /> <br /> WAGON<br /> TRAIN<br /> TRAFFIC<br /> <br /> 200000<br /> 60000<br /> 80000<br /> <br /> Unique<br /> Yes<br /> No<br /> No<br /> No<br /> No<br /> No<br /> no<br /> <br /> Type<br /> Principal<br /> Secondary<br /> Secondary<br /> Secondary<br /> Principal<br /> Principal<br /> Principal<br /> <br /> Record size<br /> (num of rec./page)<br /> 60(100)<br /> 30 (200)<br /> 20 (300)<br /> <br /> Num of pages<br /> 45<br /> 25<br /> 30<br /> 25<br /> 18<br /> 20<br /> 40<br /> <br /> Num. of pages<br /> (NP’)<br /> 1500(375)<br /> 225(60)<br /> 200(60)<br /> <br /> 5<br /> <br />