Bài giảng Nhập môn cơ sở dữ liệu - Bài 6: Tối ưu hoá câu hỏi

Tối ưu hoá câu hỏi

Vũ Tuyết Trinh

trinhvt@it-hut.edu.vn

Bộ môn Các hệ thống thông tin, Khoa Công nghệ thông tin

Đạ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

Biểu thức

ĐSQH

tối ưu

Bộ tối ưu

(optimizer)

Bộ sinh mã

(code generator)

Chương trình

tối ưu

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Tối ưu hoá

{ Biến đổi biểu thức ĐSQH để tìm 1 biểu thức

hiệu quả

{ Tối ưu dựa trên cấu trúc và nội dung của dữ

liệu

{ Nâng cao hiệu quả thực hiện câu hỏi trên 1 hay

nhiều tiêu chí: thời gian, sử dụng bộ nhớ, ...

{

L

ư

u ý:

z Không nhất thiết phải tìm biểu thức tối ưu nhất

z Chú ý tới tài nguyên sử dụng cho tối ưu

Kỹ thuật tối ưu hoá

{ 2 kỹ thuật chính

TYPE

z

T

ố

i

ư

u logic (rewriting)

z Tối ưu vật lý (access methods)

{ Mục đích của các kỹ thuật tối ưu

z Giảm số bản ghi

z Giảm kích thước bản ghi

NW

{ Ví dụ

WAGON

(NW, TYPE...)

WAGON (NW, TYPE, COND, STATION,

CAPACITY, WEIGHT)

TRAIN (NT, NW)

NT

=

4002

TRAIN

(NT, NW)

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Nội dung

9 Giới thiệu chung

{ Tối ưu logic

{ Tối ưu vật lý

{ Mô hình giá

Tối ưu hoá logic

{ Sử dụng các phép biến đổi tương đương để tìm

ra biểu thức ĐSQH tốt

{ Gồm 2 giai đoạn

z Biến đổi dựa trên ngữ nghĩa

z

Bi

ế

n

đổ

i d

ự

a trên tính ch

ấ

t c

ủ

a các phép toán

Đ

SQH

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Tối ưu dựa trên ngữ nghĩa

{ Mục đích:

z Dựa trên các ràng buộc dữ liệu để xác định các biểu

thức tương đương

z Viết lại câu hỏi trên khung nhìn dựa trên các định

nghĩa của khung nhìn

{ Ví dụ

EMPLOYEE (FirstName, LastName, SSN, Birthday,

Adrresse, NoDept)

DEPARTEMENT (DNO, DName, SSNManager)

PROJECT (PNO, PName, PLocation, DNo)

WORK-IN (ESSN, PNO, Heures)

EMPLOYEE (Name, SSN, Birthday, Adrresse, NoDept)

DEPARTEMENT (DNO, DName, SSNManager)

PROJECT (PNO, PName, PLocation, DNo)

WORK-IN (ESSN, NoProj, Heures)

Tên của các nhân viên sinh sau ngày 30/01/70 và làm việc cho dự án

"Esprit"

Result

=

EMPLOYEE.

SSN

WORK-IN.ESSN

Name

WORK-IN

=

WORK-IN.

PNO

PROJECT.PNO

NoProj = PNO

ESSN=SSN

“Esprit”

PROJET

PName = “Esprit”

>

EMPLOYEE.

Birthday

EMPLOYE

“30/01/70”

Birthday > “30/01/70

Đồ thị kết nối các quan hệ

Đồ thị kết nối các thuộc tính

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Tối ưu dựa trên ngữ nghĩa (2)

{ Loại bỏ các đồ thị con không liên kết trong đồ

thị kết nối các quan hệ

{ Kiểm tra mâu thuẫn trong đồ thị kết nối các

thuộc tính

{

Bi

ến đổ

i câu h

ỏ

i t

ương đương

Tính chất của phép toán ĐSQH

A ~ tập các thuộc tính, C ~ biểu thức điều kiện

1. Phép chiếu và phép chọn

Π (R) => Π (Π (R) nếu A ⊆ A1

A

A A1

σ

(R) => σ (σ (R)) nếu C = C1^C2

C

C1 C2

2. Tính giao hoán đối với phép chọn và chiếu

nếu các thuộc tính của C2 thuộc A1

σ

(σ (R))

σ

(σ (R))

C2 C1

=>

Π

(σ (R))

σ

(Π (R))

=>

C1 C2

(Π (R))

A1 C2

C2 A1

σ

Π

(σ (R))

=>

Π

(Π (R))

Π

(R)

C1 A2

A2 C1

=>

A1 A2

A1

nếu A1 ⊆ A2

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Tính chất của phép toán ĐSQH (2)

3. Tính giao hoán và kết hợp của các phép toán

∗, ∩, ∪, −, x

R X S => S X R

R * S => S * R

R ∩ S => S ∩ R

R

∪

S => S

∪

R

(R X S) X T => R X (S X T)

(R ∩ S) ∩ T => R ∩ (S ∩ T)

(R ∪ S) ∪ T => R ∪ (S ∪ T)

(R * S) * T => R * (S * T)

C1 C2 C1 C2

chỉ nếu

Attr(C2) ⊆ Attr(S) U Attr(T)

Tính chất của phép toán ĐSQH (3)

4. Tính phân phối σ và Π trên các phép toán *, ∩,

∪

, -, X

Nếu C = (CR ^ CS) và nếu Attr(CR) ⊆ R và Attr(CS) ⊆ S thì :

σ

(R * S) => σ (R) *

σ

(S)

JC

C

CR

CS

(S)

σ

(R X S) => σ

(R) X

CR

σ

C

CS

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Biến đổi biểu thức ĐSQH

T1

_________________________________________________________________

T2 (R[Y]) [Z] R[Z] n u Z ⊆ Y

_________________________________________________________________

R: F1 ∧ F2 ∧ ... Fn

((...(R:F1) : F2 ):...):Fn

T3

(R[Y]) :F (X)

(R :F(X)) [Y] n u X ⊆ Y

(R: F(X)) [Y]

(R[X ∪ Y]) : F(X) ) [Y] n u X ⊄ Y

_________________________________________________________________

T4 (R(X) x S(Y)) : F(Z) (R(X):F) x S(Y) n u Z ⊆ X

(R(X) x S(Y)) : F(Z1)∧ F(Z2) (R(X):F(Z1)) x (S(Y): F(Z2))

n u Z1 ⊆ X và Z2 ⊆ Y

_________________________________________________________________

T5

_________________________________________________________________

T6 (R - S): F (R:F) - S

_________________________________________________________________

T7 (R(X) x S(Y))[Z] R[X ∩ Z] x S[Y ∩ Z]

_________________________________________________________________

T8 (R ∪ S) [Z] (R[Z]) ∪ (S[Z])

(R ∪ S): F

(R:F) ∪ (S:F)

_________________________________________________________________

Trình tự áp dụng

{ Khai triển phép lựa chọn dựa trên nhiều điều

ki

ệ

n: T1

{ Hoán vị phép chọn với tích đề-các, hợp, trừ: T3,

T4, T5, T6

{ Hoán vị phép chiếu với tích đề-các, hợp : T2,

T7, T8

{ Nhóm các điều kiện chọn bởi T1 và áp dụng T2

để loại các phép chiếu dư thừa

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Bài tập

Lựa chọn cách truy nhập dữ liệu

{ Giả thiết

TYPE

z TRAIN : có chỉ số trên

NT

z WAGON : có chỉ số

trên NW

{ Thực hiện phép kết

NW

nối

z Lựa chọn 1 giải thuật.

WAGON

(NW, TYPE...)

z Lựa chọn cách truy

NT

=

4002

nhập các quan hệ

TRAIN

(NT, NW)

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Relation S

Nested-loop-join (NLJ)

{ Nguyên tắc

z Duyệt 1 lần trên quan hệ

ngoài R & lặp trên quan hệ

trong S

Matching

Tuple R

{ Các mở rộng của thuật toán

z Tuple-based NLJ, block-

based NLJ, index-based NLJ

Tuple R

Tuple S

SOURCE

R

SOURCE

S

Thực hiện như thế nào?

TYPE

NW

=

WAGON

(NW, TYPE...)

NT

4002

TRAIN

(NT, NW)

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Thông tin về các quan hệ

{ Kích thước của các quan hệ và bản ghi

Relation

WAGON

TRAIN

Cardinality

200000

Record size

60

30

20

60000

TRAFFIC

80000

{

Thông tin v

ề

các thu

ộ

c tính

Attribute

NW

Cardinality

200000

200

Size

20

5

min -max

TYPE

COND

CAPACITY

NT

5

400

2000

800

15

10

6

5-45

DATE

{Thông tin về các chỉ số

Relation

WAGON

TRAIN

TRAFFIC

Relation

Attributes

NW

TYPE

COND

CAPACITY

NT

DATE

Cardinality

Unique

Yes

No

no

Type

Num of pages

Principal

Secondary

Principal

45

25

30

25

18

20

40

Record size

(num of rec./page)

Num. of pages

(NP’)

WAGON

TRAIN

TRAFFIC

200000

60000

80000

60(100)

30 (200)

20 (300)

1500(375)

225(60)

200(60)

Mô hình giá

{

Chí phí thực hiện câu hỏi phụ thuộc:

z đọc/ghi bộ nhớ ngoài (số trang nhớ

)

zKích thước dữ liệu phải xử lý

{Chi phí truy nhập dữ liệu

zĐọc ghi dữ liệu

zxử lý

z

Truy

ền thông giữa các trạm làm việc

CTA = σ * NBPAGES + τ ∗ NBNUPLETS (+ µ ∗ NBMESSAGES)

{Trọng số

{σ = trọng số đọc/ghi dữ liệu (ví dụ = 1)

{τ = trọng số xử lý của CPU (ví dụ = 1/3)

{µ = trọng số truyền dữ liệu

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Tối ưu hoá dựa trên mô hình giá

{ Mục đích: Chọn phương án thực hiện câu hỏi

với chi phí thấp nhất

{ Nhận xét:

z Chi phí cho liệt kê các phương án trả lời câu hỏi

z Chi phí cho lượng hoá các phương án theo mô hình

giá

¾ Có thể sử dụng các « mẹo » (heuristics) để giảm

không gian tìm kiếm của câu hỏi

Kết luận

{ Tối ưu hoá nhằm tìm phương án tốt nhất để

th

ự

c hi

ện mộ

t câu h

ỏ

i

z Cần lưu ý: chí phí thực hiện tối ưu hoá và chi phí thực

hiện câu hỏi

{ Các kỹ thuật tối ưu

z Logic : kiểm tra điều kiện ràng buộc của các thuộc

tính/quan hệ và điều kiện lựa chọn trong câu hỏi, biến

đổi tương đương các biểu thức ĐSQH

z Vật lý : tổ chức vật lý của dữ liệu trên đĩa, mô hình giá

¾ Không nhất thiết phải áp dụng tất cả các kỹ thuật trên

khi thực hiện tối ưu hoá 1 câu hỏi

ũ Tuyết Trinh, b/m Các hệ thống thông tin,

Bài giảng Nhập môn cơ sở dữ liệu - Bài 6: Tối ưu hoá câu hỏi - Vũ Tuyết Trinh