GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
CHƯƠNG 6. XỬ LÝ VÀ TỐI ƯU CÂU TRUY VẤN
Mục đích
Trình bày các bước xử lý câu truy vấn, tối ưu logic câu truy vấn và tối ưu vật lý
câu truy vấn.
Yêu cầu
Sinh viên nắm các kỹ thuật cơ bản của tối ưu câu truy vấn và vận dụng được
trong khi thực hiện truy vấn dữ liệu trên SQL Server và có ý thức tối ưu trong quá
trình câu truy vấn dữ liệu cũng như trong khai phá dữ liệu.
1. Quá trình xử lý và tối ưu câu truy vấn.
Khi nhận được một câu hỏi của người dùng, bộ xử lí câu hỏi trước hết kiểm tra xem
câu hỏi có được viết đúng cú pháp hay không, các quan hệ và các thuộc tính trong câu hỏi
có trong CSDL hay không. Tiếp đó, nếu câu hỏi được chấp nhận, một phương án thực thi
(execution plan) cho câu hỏi được phát sinh.
Một phương án thực thi câu hỏi xác định một dãy các bước cho việc định giá câu hỏi,
trong đó mỗi bước ứng với một phép toán của đại số quan hệ cùng với chú giải về phương
pháp được dùng để định giá phép toán đó. Chẳng hạn, phép kết nối có thể được định giá
bằng các phương pháp lặp lồng, sắp xếp trộn, kết nối băm…
Mục đích của tối ưu hóa câu hỏi là tìm một phương án thực thi trong số tất cả các
phương án tương đương (theo nghĩa luôn cho cùng một kết quả), có thể có, được định giá
với chi phí nhỏ nhất. Trong hệ CSDL tập trung, chi phí cho việc định giá một câu hỏi là
tổng của chi phí nhỏ nhất. Trong hệ CSDL tập trung, chi phí cho việc định giá một câu hỏi
là tổng của chi phí I/O và chi phí CPU. Chi phí I/O (Vào/ra) do việc truyền dữ liệu giữa bộ
nhớ chính và bộ nhớ thứ cấp (thường là đĩa từ) vì trong phần lớn các ứng dụng, dữ liệu
thường quá lớn và không thể chứa hết trong bộ nhớ chính. Với phần lớn các thao tác
CSDL, chi phí I/O là chi phí có tính chi phối. Để giảm chi phí I/O thường phải sử dụng các
cấu trúc dữ liệu đặc biệt, như các cây B
+
chẳng hạn.
Hình 1 dưới đây chỉ rõ các bước khác nhau của việc xử lí một câu hỏi được viết
trong một ngôn ngữ hỏi bậc cao, chẳng hạn SQL.

Improve logical query plan
Logical query plan + sizes
{P1, P2, … }
{(P1, C1), (P2,C2) … }
Pi
statistic
s
2
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Nói chung, số các phương án thực thi tương đương đối với một câu hỏi cho trước là
rất lớn và phụ thuộc vào số m các phép toán (thao tác) trong câu hỏi và số k các phương
pháp khác nhau có thể được dùng để định giá mỗi một phép toán đó. Khi đó, số các
phương án thực thi có thể lên tới (m!).k.m. Tập tất cả các phương án thực thi tương đương
là không gian tìm kiếm cho tối ưu hóa câu hỏi.
Vì vậy, bài toán tìm phương án thực thi tối ưu (tốt nhất) là một bài toán rất khó, tốn
rất nhiều thời gian, đòi hỏi phải biết thông tin về các tệp được cài đặt ra sao, thậm chí cần
biết cả nội dung của các tệp. Đó là những thông tin thường không có sẵn đầy đủ trong thư
mục của hệ quản trị cơ sở dữ liệu (hệ QTCSDL).
Do đó, tối ưu hóa câu hỏi trong nhiều trường hợp được hiểu là tìm một phương án
thực thi câu hỏi tương đối hiệu quả, gần với tối ưu.
Xét ví dụ sau, cho hai lược đồ quan hệ R(AB) và S(CD). Giả sử ta có yêu cầu sau:
“Đưa ra thuộc tính A của các bộ thoả mãn điều kiện B=C và D=100”.
Câu hỏi được viết dưới dạng ngôn ngữ đại số quan hệ như sau:
π
A
(σ
B=C and D=100
(R
×
S))

=
D
thì số bộ lấy ra sẽ ít hơn toàn bộ số bộ của cả quạn
hệ S. Số bộ được chọn ra xong từ S mới đem kết nối với quan hệ trên R. Phép kết nối này
chỉ chọn ra bộ nào thuộc R mà có giá trị tại B bằng bộ có giá trị tại C mới được lấy ra. Như
vậy chi phí thực hiện sẽ tốt hơn lấy tích Đề - các của
SR ×
, rồi mới chọn trong kết quả
những bộ có giá trị tại B bằng giá trị tại C.
Qua ví dụ đơn giản trên đủ để cho thấy tối ưu hóa là cần thiết.
Quá trình tối ưu hóa câu hỏi thường được chia làm hai pha: tối ưu hóa logic và tối ưu
hóa vật lí. Tối ưu hóa logic cho phép viết lại câu hỏi dưới dạng chuẩn tắc đơn giản và được
tối ưu hóa về mặt logic, cóc nghĩa không tính tới các chi phí truy cập dữ liệu. Tối ưu hóa
vật lí thực hiện chọn các thuật toán tốt nhất cho các toán tử mức thấp có tính tới kích thước
dữ liệu và các đường truy cập sẵn có.
Tối ưu hóa logic được thực hiện ở mức của đại số quan hệ, trong khi tối ưu hóa vật lí
cho phép, nói riêng, thiết lập các chú giải. Tối ưu hóa vật lí cần tới một mô hình chi phí để
NTD – Khoa Tin – ĐHSP Huế
3
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
ước lượng chi phí của mỗi phương án thực thi nhằm chọn được phương án tối ưu hay gần
tối ưu.
Phần còn lại của chương được tổ chức như sau:
Mục 2: Trình bày về các mục tiêu của tối ưu hóa.
Mục 3. Dành cho việc nghiên cứu các phương pháp chính của tối ưu hóa logic nhằm
tìm câu hỏi đơn giản nhất tương đương với câu hỏi đã cho và sử dụng một phương pháp
heuristic cấu trúc lại cây đại số để xây dựng một dạng chuẩn tắc.
Mục 4. Nghiên cứu các thuật toán khác nhau truy cập vật lí tới dữ liệu bao gồm phép
chọn, phép chiếu, phép kết nối.
Mục 5. Mô tả mô hình chi phí.

NTD – Khoa Tin – ĐHSP Huế
4
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Cây đại số quan hệ cũng tương tự như cây nhị phân biểu diễn biểu thức mà các bạn đã học
ở phần cấu trúc cây nhị phân trong môn học Cấu trúc dữ liệu và Giải thuật.
Từ cây đại số, có thể tạo sinh một phương án thực thi bằng cách đi dọc theo cây, từ
lá tới gốc. Một phép toán có thể được thực hiện theo kiểu hướng tập (set oriented
execution) bao gồm việc tính tập tất cả các bộ của các quan hệ đầu vào của một toán từ
trước khi định giá toán tử đó.
Như vậy, nếu phép toán O
1
không dùng các kết quả của phép toán O
2
thì các phép
toán O
1
và O
2
có thể được thực hiện song song. Kiểu thực hiện này có thể thích hợp cho
những thuật toán có khả năng làm việc hiệu quả trên các tập (trên cơ sở của phép sắp xếp
chẳng hạn).
Một phép toán cũng có thể được thực hiện theo kiểu từng bộ một hay kiểu đường ống
(pipeline execution). Cụ thể là khởi động phép toán sớm nhất có thể, ngay khi đã có một bộ
cho ít nhất một toán hạng.
Đối với phép toán một ngôi, chỉ cần có một bộ là đủ. Như vậy, có thể thực hiện hai
phép chọn liên tiếp theo kiểu đường ống, có nghĩa là bắt đầu thực hiện phép chọn thứ hai
ngay khi có một bộ (hay một trang gồm một số bộ) được sinh bởi phép chọn thứ nhất.
Các phép toán hai ngôi, như phép hiệu r – s chẳng hạn, chỉ có thể bắt đầu sau khi đã
tính được đầy đủ toán hạng s. Như vậy, kiểu đường ống chỉ có khả năng thực hiện một
toán hạng.

Phép viết lại cho phép thu được một biểu diễn chuẩn tắc của câu hỏi, dưới dạng một
cây đại số trong đó các phép toán được sắp thứ tự và các điều kiện được viết dưới dạng
chuẩn.
Phép viết lại có thể bao gồm phép viết lại ngữ nghĩa và phép viết lại cú pháp.
3.1. Phân tích và viết lại ngữ nghĩa
Loại phân tích này nhằm xác định tính đúng đắn của câu hỏi, tìm các câu hỏi tương
đương trên cơ sở thao tác trên điều kiện của câu hỏi này nhờ vào các ràng buộc toàn vẹn.
Để thực hiện việc phân tích ngữ nghĩa của câu hỏi, có thể dùng đồ thị liên kết các
quan hệ (Relation connection graph), đồ thị các kết nối, đồ thị liên kết các thuộc tính
(Attribute connection graph).
Đồ thị liên kết các quan hệ là đồ thị trong đó:
1. Một đỉnh được kết hợp với mỗi xuất hiện của một quan hệ.
2. Một phép kết nối được biểu diễn bởi một cung giữ hai nút biểu diễn các quan hệ
được kết nối.
3. Một phép chọn được biểu diễn bởi một khuyên của nút ứng với quan hệ trên đó
phép chọn được áp dụng.
4. Phép chiếu cuối cùng được biểu diễn bởi một cung từ nút quan hệ tới một nút đặc
biệt là nút kết quả.
Đồ thị các kết nối là đồ thị liên kết các quan hệ trong đó chỉ giữ lại các nút và các
cung biểu diễn các phép kết nối giữa chúng.
Đồ thị liên kết các thuộc tính là đồ thị trong đó:
1. Một đỉnh được kết hợp với mỗi thuộc tính hay một hằng được tham chiếu (hay dẫn
trỏ).
2. Một phép kết nối được biểu diễn bởi một cung giữa các thuộc tính tham gia.
3. Một phép chọn được biểu diễn bởi một cung giữa một thuộc tính và một hằng.
Đồ thị liên kết các thuộc tính cho phép phát hiện các điều kiện trong câu hỏi có chứa
mâu thuẫn, nếu có chứa một chu trình không được thỏa mãn bởi các hằng. Nó cũng cho
phép phát hiện các câu hỏi tương đương với câu hỏi đã cho nhờ tính bắc cầu.
Hai hình vẽ dưới đây theo thứ tự các đồ thị liên kết các quan hệ và đồ thị liên kết các
thuộc tính của câu hỏi được nói ở ví dụ ở trên có biểu diễn bằng SQL như sau.

queries).
Định nghĩa
NTD – Khoa Tin – ĐHSP Huế
R S
S.D=100
R.B=S.C
k
q
A
7
R.
B
S.
D
10
0
=
R.
B
R.
B
S.
C
=
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Hai câu hỏi là tương đương nếu và chỉ nếu chúng cho cùng kết quả với mọi thể hiện
(ngoại diên) có thể của cơ sở dữ liệu.
Từ việc nghiên cứu đồ thị liên kết các thuộc tính có thể phát hiện ra các câu hỏi
tương đương.
Thực vậy, mọi cặp thuộc tính (A

1
∧ I
2
∧… ∧I
n
∧ Q’→Q
(Các kiến thức về biểu diễn tri thức trong Trí tuệ nhân tạo giúp bạn về Q’ đơn giản
hơn Q, I
1
∧ I
2
∧… ∧I
n
∧ Q’→Q … là gì).
Ta minh họa các phép biến đổi ngữ nghĩa qua một số ví dụ đơn giản.
Xét cơ sở dữ liệu về việc cung cấp hàng hóa, gồm 3 quan hệ sau:
S(S#, SNAME, CITY, STATUS)
P(P#, PNAME, COLOR, ADDR, WEIGHT)
SP(S#, P#, QTY)
Với S#, P# lần lượt là mã số của nhà cung cấp hàng hóa và hàng hóa.
SNAME, PNAME lần lược là tên nhà cung cấp và tên mặt hàng.
CITY là địa chỉ của nhà cung cấp và ADDR là địa chỉ lưu trữ của mặt hàng.
Trước hết hãy xét biểu thức sau:
Π
P#
(SP

S)
Phép kết nối ở đây là phép kết nối tự nhiên trên thuộc tính S# là thuộc tính chung của
hai quan hệ S và SP. Mặt khác vì S# là một khóa ngoại của quan hệ SP và là khóa của quan

n
,
các quan hệ hằng được xác định từ k - bộ của các quan hệ (r
1
,r
2
, ,r
n
) trong đó r
i
là quan hệ
trên lược đồ R
i
và thay thế r
i
vào R
i
khi đánh giá biểu thức.
Hai biểu thức E
1
và E
2
được gọi là tương đương viết tắt là E
1
≡E
2
nếu chúng biểu
diễn cùng một ánh xạ, nghĩa là nếu thay thế cùng các quan hệ cho tên các lược đồ tương
ứng ở hai biểu thức cho ra cùng một kết quả.
Với cách hiểu tương đương trên ta đưa ra một số qui tắc chuyển dịch đại số quan hệ

2121

≡
)()(
321321
EEEEEE
∗∗≡∗∗
)()(
321321
EEEEEE
××≡××
Các qui tắc liên quan đến phép chọn và chiếu
(3) Dãy các phép chiếu
Nếu dãy các thuộc tính A
1
, ,A
n
nằm trong dãy các thuộc tính B
1
, ,B
m
thì:
)())((
21
21
21
EE
n
m
n

m
không nằm trong A
1
, ,A
n
thì:
))(())((
1
221
1 21
EE
FAAABmBAAAFAnAA
nn
σσ
⋅⋅⋅⋅⋅⋅
Π≡ΠΠ
(6) Giao hoán phép chọn và phép tích Đề - các
Nếu tất cả các thuộc tính trong F là các thuộc tính của E
1
thì:
2121
)()( EEEE
FF
×≡×
σσ
Nếu F = F
1
∧ F
2
, với F

FFF
×≡×
σσσ
(7) Giao hoán phép chọn và một phép hợp
)()()(
2121
EEEE
FFF
σσσ
∪≡∪
(8) Giao hoán phép chọn và một phép hiệu
)()()(
2121
EEEE
FFF
σσσ
−≡−
(9) Giao hoán giữa phép chọn và kết nối tự nhiên
)(*)()*(
2121
EEEE
FFF
σσσ
≡
(10) Giao hoán một phép chiếu và một phép tích Đề các
A
1
, ,A
n
là tập thuộc tính bao gồm B

⋅⋅⋅
Π∪Π≡∪Π
Lưu ý rằng phép chọn với phép giao; phép chiếu với phép hiệu lại không có tính giao
hoán, hãy cho một phản ví du.
Phép chứng minh của các qui tắc trên có thể tham khảo trong [5]
3.2.3. Tối ưu hóa trên cơ sở đại số
Sau đây là 6 chiến lược tối ưu hoá câu hỏi tổng quát [5].
- Thực hiện phép chọn càng sớm càng tốt.
Việc làm này nhằm làm giảm số bộ tham gia vào biểu thức, vì vậy làm giảm đi kích
cỡ của kết quả trung gian, nên chi phí truy cập bộ nhớ, cũng như lưu trữ cũng ít đi.
- Tổ hợp một số phép chọn với tích Đề - các thành phép kết nối.
NTD – Khoa Tin – ĐHSP Huế
10
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Vì phép kết nối, nhất là kết nối bằng chi phí thực hiện "rẻ" hơn phép tích Đề-các.
- Tổ hợp các chuỗi phép toán một ngôi như phép chọn và chiếu.
Nhằm làm giảm đi số phép toán.
- Tìm các biểu thức con chung trong một biểu thức
Nếu kết quả của một biểu thức con chung (biểu thức xuất hiện nhiều lần) là một quan
hệ không lớn và có thể đọc nó từ bộ nhớ thứ cấp với ít thời gian thì nên tính toán biểu thức
đó trước. Thường là đưa các kết quả của các biểu thức con chung đó thành một view.
Nhờ các biểu thức con chung này ta có thể phân rã câu hỏi thành các câu hỏi con đơn
giản hơn, vấn đề này sẽ được bàn trong phần tiếp theo.
- Xử lý các tệp trước
Hai vấn đề xử lý quan trọng cần thực hiện trước khi thực hiện các câu hỏi, cũng như
bất cứ công việc khai thác dữ liệu nào là: sắp xếp trước và thiết lập các tệp chỉ số cho các
tệp dữ liệu. Lúc này rõ ràng việc thực hiện các câu hỏi sẽ dễ dàng, nhanh chóng hơn.
- Đánh giá trước khi thực hiện tính toán
Khi lựa chọn trình tự thực hiện các phép tính trong một biểu thức, hoặc lựa chọn
một trong hai đối số của phép tính hai ngôi cần tính toán xem chi phí thực hiện các phép

với ∀i.
Thí dụ
Xét CSDL quản lý tư liệu với các quan hệ sau:
BOOKS(TITLE, AUTHOR, PNAME,LC_NO): quan hệ sách
PUBLISHERS(NAME, PADDR, PCITY, CARD_NO): quan hệ nhà xuất bản.
NTD – Khoa Tin – ĐHSP Huế
11
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
BORROWERS(NAME, ADDR, CITY, CARD_NO): quan hệ độc giả.
LOANS(CARD_NO, LC_NO, DATE): quan hệ sổ mượn
Trong đó các thuộc tính là:
PNAME: Tên nhà sản xuất.
LC_NO: Số thư viện.
PADDR:Địa chỉ của nhà sản xuất.
PCITY: Thành phố nơi có nhà sản xuất
CARD_NO: Số thẻ của độc giả
ADDR: Địa chỉ độc giả DATE
CITY: Thành phố nơi độc giả ở
DATE: Ngày mượn sách
Để lưu trữ thông tin về sách, có thể giả thiết thêm rằng, có một khung nhìn XLOANS
bao gồm một số thông tin bổ sung về sách được mượn. XLOANS là kết nối tự nhiên của
quan hệ BOOKS,BORROWERS , và LOANS và nó có thể được định nghĩa là:
))(( BOOKSBORROWERSLOANS
FS
××
σπ
Trong đó:
)_._.()_._.( NOLCLOANSNOLCBOOKSNOCARDLOANSNOCARDBORROWERSF
=∧==



NTD – Khoa Tin – ĐHSP Huế
12
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
BOOKS

×BORROWERS
LOANS
Nguyên tắc tối ưu hóa là tách phép chọn F thành hai phép phép chọn với các điều
kiện tương ứng:
BOOKS.LC_NO=LOANS.LC_NO và
BORROWERS.CARD_NO=LOANS.CARD_NO
Sau đó chúng ta di chuyển ba phép chọn càng xuống thấp càng tốt. Phép chọn
))((
2002.03.08
BOOKSBORROWERSLOANS
DATE
××
<
σ
có thể thay bằng:
(
BOOKSBORROWERSLOANS
DATE
××
<
))(

π

↓

NOLCLOANSNOLCBOOKS
−=−

σ

↓

×
BOOKSNOLCLOANSNOCARDBORROWERS _._.
=
σ×

BORROWERS2002.03.08
<

NOLCLOANSNOLCBOOKSTITLE _.,.,
−
π
Để áp dụng cho BOOKS và
NOLCLOANS _.
π
thì áp dụng cho toán hạng bên trái của tích
Đề - các bên trên cây kết quả trên.
Phép chiếu sau tương tác với phép chọn bên dưới nó nhờ qui tắc (5) mở rộng tạo ra
chuỗi:

NOLCLOANS
−
.
π

NOCARDLOANSNOCARDBORROWERS
−=−

σNOCARDLOANSNOCARDBORROWERSNOLCLOAN −−− .,.,.
π
Phép chiếu cuối cùng được chuyển cho tích Đề - các nhờ qui tắc (10) và chuyển một
phần cho phép chọn
2002.03.08
<
DATE
σ

.
π
NTD – Khoa Tin – ĐHSP Huế
14
BOOKS
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn

↓

×NOCARDBORROWERS
−
.
πNOLCLOANS _.
πBORROWERS

2002.03.08
<
DATE
σ

LOANS

Where TAU.TTU_TAU= 4002
Và:
Selec KIEUTOA
From TOA
Where TOA.TTU_TOA= T1.TTU_TOA
Dưới đây sẽ trình bày một cách tổng quát vấn đề và sẽ nghiên cứu vì sao có thể tạo ra
được các câu hỏi con như trên.
Trong SQL các câu hỏi thường gặp là câu hỏi có dạng tổng quát:
Select A
1
, ,A
n
From R
1
, ,R
n
Where F
1
and F
2

Với F
1
, F
2
là các mệnh đề chọn hoặc mệnh đề kết nối.
Một câu hỏi là tách được với một biến (quan hệ) tách X
m
, nếu có thể biểu diễn dưới
dạng:

đều có chứa biến X
m
, những biến còn lại chỉ có mặt nhiều nhất là một lần ở trong hai biểu
thức thành phần.
Sử dụng các khái niệm đồ thị liên kết quan hệ và đồ thị liên kết thuộc tính, để biểu
diễn câu hỏi, ta có thể nhận ra các thành phần có thể tách được của các câu hỏi.
Ví dụ: Xét CSDL quản lý đường sắt, gồm các quan hệ sau:
Quan hệ đường:DUONG (TTU_DG, GA)
Quan hệ tàu: TAU (TTU_TAU, TTU_TOA)
Quan hệ hiện trạng: HTR (TTU_TAU, TTU_DG, TTU_NG)
Ở đây:
TTU_TOA: Thứ tự TOA; TTU_DG: Thứ tự đường; GA: Tên ga; TTU_TAU: Thứ
tự tàu; TTU_NG: Ngày khởi hành.
Với câu hỏi: Hãy cho danh sách các toa khởi hành từ ga HUẾ vào ngày 05.01.02.
Q
0
Selec TTU_TOA
NTD – Khoa Tin – ĐHSP Huế
16
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
From DUONG, TAU, HTR
Where (DUONG.GA = “HUE" )
And (HTR.TTU_NG = ‘05.01.02’)
And (DUONG.TTU_DG = HTR.TTU_DG)
And (HTR.TTU_TAU = TAU.TTU_TAU)
Câu hỏi trên có thể tách thành thành bốn câu hỏi con Q
1
, Q
2
, Q

2
.TTU-DG
Q
4
Select TTU-TOA
From TAU, T
3

Where TAU.TTU-TAU= T
3
.TTU-TAU
Bạn hãy vẽ đồ thị liên kết quan hệ và liên kết thuộc tính cho câu hỏi Q
0
để nhận ra kỹ
thuật tách câu hỏi trên.
Các câu hỏi Q
1
, Q
2
có thể thực hiện một cách độc lập và theo một thứ tự bất kỳ, thâm
chí có thể song song. Điều này thực sự có lợi nếu cơ sở dữ liệu được xử lý trên các Server
có thể thực hiện song song hay trên các máy trạm trong thời gian máy trạm rỗi.
Nhận xét:
Nguyên tắc của phép tách là chia đồ thi đồ thị nối thành các đồ thị con riêng biệt
được nối với nhau bởi một cầu (một cung được gọi là cầu, nếu loại nó ra đồ thị thì số miền
liên thông của đồ thị sẽ tăng lên một) và mỗi đồ thị con tương ứng với một câu hỏi con có
thể được tách.
Trong phép tách trên, câu hỏi Q
3
và Q

Ví dụ
Ta có CSDL quản lý việc sản xuất và uống rượu gồm các sau:
Uống(Ten, NR,SL) với Ten: Tên người uống; NR: Số hiệu rượu; SL: Số lượng.
Sảnxuất( SX, TênSX, Vùng) với SX: Mã người sản xuất; TenSX: Tên người sản
xuất; Vùng: khu vực sản xuất rượu.
Rượu(NR, tên rượu, năm, độ) với năm: Năm sản xuất
Hàng(NR, SX).
Giả sử có câu hỏi:"Tìm tên người uống rượu sản xuất tại vùng Đá Bạc vào năm 2000,
độ rượu nhỏ hơn 45 độ".
Với SQL câu trả lời sẽ như sau:
SELECT Uống.Tên
FROM Uống, Sảnxuất, rượu, hàng
WHERE (Rượu.Năm=2000) and (Rượu.độ<45) and (Sản
xuất.Vùng='Đá Bạc') and
(Sản xuất.SX=Hàng.SX) and (Rượu.NR=Hàng.NR) and
(Hàng.NR=Uống.NR).
Câu hỏi trên có thể thay thế cho tối ưu hơn như sau:
Bước 1: Hạn chế
SELECT Rượu.NR INTO T1
NTD – Khoa Tin – ĐHSP Huế
18
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
WHERE (Rượu.Độ<45) and (Rượu.Năm=2000)
Và
SELECT Sản xuất.SX INTO T2
WHERE (Sản xuất. Vùng='Đá Bạc')
Sau khi tách câu hỏi như trên, lúc này câu hỏi ban đầu sẽ là
SELECT Uống.Tên
FROM Uống, T1, T2, Hàng
WHERE (T2.SX=Hàng.SX) and (T1.NR=Hàng.NR) and

ngôi. Phép viết lại là một tiếp cận cũng đã có tính tới ít nhiều việc sắp thứ tự các phép toán
mà không cần tới ước lượng kích thước kết quả của các phép kết nối. Cách tiếp cận đó rõ
ràng không đủ để thu được một phương án thực thi với chi phí nhỏ nhất vì nó không cho
phép sắp thứ tự các toán tử một cách tối ưu cũng như không cho phép chọn các thuật toán
tối ưu cho mỗi phép toán.
4. Các toán tử vật lí.
Trước khi nói tới tối ưu hóa vật lí, cần phải hiểu về các thuật toán truy cập các bảng
(quan hệ). Các thuật toán này thực hiện các toán tử của đại số quan hệ và là trung tâm của
mô tơ trong hệ quản trị CSDL chịu trách nhiệm thực thi các phương. Dưới đây, chúng ta
tập trung vào các phép chọn, chiếu và phép kết nối.
4.1. Các thống kê của CSDL.
Để thảo luận về các kĩ thuật định giá các phép toán quan hệ, cần phải dùng đến
những thống kê của CSDL được lưu giữ trong thư mục hệ thống. Để minh họa, chúng ta
tóm tắt một số thống kê chính được lưu giữ trong hai sản phẩm thương mại: DB2 và
Ingres.
Sau đây là một vài thống kê chính có trong DB2.
Với mỗi bảng (quan hệ) cơ sở:
- Số bộ (lực lượng) của bảng.
- Số trang được chiếm giữ bởi bảng.
- Phần của “không gian bảng” (table space) được chiếm giữ bởi bảng đó.
Với mỗi cột của bảng cơ sở:
- Số các giá trị phân biệt trong cột.
- Giá trị lớn thứ hai trong cột.
- Giá trị nhỏ thứ hai trong cột.
- Chỉ với các cột có chỉ mục, mười giá trị xuất hiện nhiều nhất trong cột và
số lần xuất hiện của chúng.
Với mỗi chỉ mục:
- Một chỉ dẫn cho biết đó là một “chỉ mục dồn cụm” (clustering index) hay
không (tức chỉ mục được dùng để dồn cụm vật lí đặt cạnh nhau trên đĩa đối với các
dữ liệu có quan hệ logic với nhau).

trang. Chẳng hạn sự khác nhau giữa một thao tác I/O đọc/ghi 10 trang với thao tác I/O
đọc/ghi 500 trang.
Trong môi trường nhiều người dùng, thường khó biết được số thực sự các thao tác
I/O. Chẳng hạn, hãy xét X trang dữ liệu được lưu trữ trong không gian nhớ liên tiếp (tuần
tự). Khi đó X trang này có thể được đọc vào bằng một thao tác I/O nếu đó là yêu cầu I/O
duy nhất và bộ nhớ đệm đủ lớn để lưu giữ chúng. Tuy nhiên cũng vẫn X trang đó, có thể
đọc vào, sử dụng nhiều thao tác I/O khi có nhiều yêu cầu I/O đồng thời (tương tranh). Ví
dụ vừa nêu cũng minh họa rằng, trong môi trường đa người dùng, khó có thể biết được số
I/O cho trang ngẫu nhiên. Thực vậy, nếu X trang trên có thể được đọc bởi một thao tác I/O
thì chỉ cần một trang ngẫu nhiên I/O. Tuy nhiên, nếu cần tới nhiều thao tác I/O thì phải tốn
nhiều trang ngẫu nhiên I/O.
Như vậy cả hai phương án đều có thể dẫn tới sự không chính xác. Ta sẽ dùng phương
pháp thứ nhất để tiến hành phân tích, trừ khi phương pháp thứ hai có tác động rõ rệt tới
chiến lược xử lí, và trong trường hợp đó, ta sẽ dùng cả hai phương pháp.
Trong việc phân tích chi phí I/O, để đơn giản, ta sẽ bỏ qua chi phí của việc đưa ra kết
quả của một định giá, vì mục đích của việc phân tích chi phí là để tìm ra một phương án
thực thi hiệu quả nhất. Còn kích thước của kết quả cuối cùng không phụ thuộc vào chiến
lược được sử dụng, nên việc bỏ qua chi phí của việc đưa ra kết quả không ảnh hưởng gì tới
việc tìm chiến lược hiệu quả nhất.
4.2. Định giá phép chọn.
NTD – Khoa Tin – ĐHSP Huế
21
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Xét phép chọn σ
Aopa
(R), trong đó A là một thuộc tính, a là một hằng thuộc Dom (A),
op ∈{=, ≠, <, ≤, >, ≥)
Nếu op là ≠ thì hầu hết các bộ của R sẽ thỏa điều kiện chọn, và trong trường hợp này,
quét toàn bộ quan hệ dường như là cách tốt nhất để định giá phép chọn hơn là dùng bất kì
cấu trúc chỉ mục nào. Dưới đây ta sẽ giả sử rằng op không là ≠.

Gọi k là số bộ của R thỏa điều kiện “A op a”. Khi đó k được ước lượng là n. S
A opa
(R). Chi phí cho việc định giá phép chọn σ
A opa
(R) được phân tích như sau:
Trường hợp 1: Đường truy cập nhanh không có sẵn hoặc không dùng. Có hai trường
hợp nhỏ.
a. Các bộ của quan hệ được lưu trữ theo các giá trị đã được sắp của A. Trong trường
hợp này, có thể dùng thuật toán tìm kiếm nhị phân. Chi phí CPU sẽ là O(logn + k), còn chi
phí I/O sẽ là O(logN + [k/n.N]), trong đó N là số trang cần thiết để lưu giữ các bộ của R,
còn [k/n.N] là số trang cần để lưu giữ k bộ thỏa điều kiện chọn.
b. Các bộ không được lưu trữ theo các giá trị được sắp xếp của A. Trong trường hợp
này, cần phải quét tuần tự tất cả các bộ của R. Chi phí CPU là O(n), còn chi phí I/O là
O(N).
Trường hợp 2: Có sử dụng đường truy cập nhanh. Có hai trường hợp nhỏ.
a. Các bộ của quan hệ được lưu trữ theo các giá trị được sắp của A. Đây là trường
hợp khi đường truy cập nhanh là chỉ mục được dồn cụm. Vì tất cả cá bộ được chọn được
lưu trữ cùng nhau và phải mất một số không đổi các bước (như đã được chỉ rõ trong phần
NTD – Khoa Tin – ĐHSP Huế
22
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
“Tổ chức vật lí của CSDL”, một B
+
cây thường có độ cao không quá 3 hay 4 mức) để tìm
bộ được chọn thứ nhất khi sử dụng đường truy cập nhanh, chi phí CPU sẽ là O(k), còn chi
phí CPU là O([k/n.N]).
b. Các bộ không được lưu trữ theo các giá trị được sắp của A. Đây là trường hợp khi
đường truy câp nhanh là một chỉ mục không dồn cục. Vì mỗi bộ được chọn có thể tìm
được sau một số không đổi các phép so sánh khi dùng chỉ mục, chi phí CPU sẽ là O(n).
4.3. Định giá phép chiếu.

nối) phép kết nối là phép toán tốn kém nhất và cũng được nghiên cứu nhiều nhất. Trong
mục này, sẽ giới thiệu một số thuật toán quen biết để định giá phép kết nối. Để đơn giản,
ta chỉ xét phép kết nối “bằng” của hai quan hệ R và S dạng R

R.A=S.B
S, trong đó n và m
theo thứ tự là số bộ của R và S, còn N và M là kích thước tính theo trang của chúng.
Không giảm tổng quát, giả thiết là quan hệ nhỏ hơn, có nghĩa M ≤ N.
4.4.1. Kết nối chu trình lồng nhau.
Thuật toán này tiến hành so sánh mỗi bộ của R trực tiếp với mọi bộ của S để tìm các
bộ sánh hợp:
for mỗi bộ x trong R do
for mỗi bộ y trong S do
if x[A] = y [B] then return
(x,y)
Theo sự cài đặt trên, R được dùng trong chu trình ngoài và được gọi là quan hệ
ngoài, và tương tự, S được gọi là quan hệ trong.
NTD – Khoa Tin – ĐHSP Huế
23
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
Như sẽ thấy, việc chọn quan hệ nào làm quan hệ ngoài/trong là có ý nghĩa đối với
việc tối ưu hóa chi phí I/O, nếu mục tiêu tối ưu là làm cực tiểu số trang I/O. Với thuật toán
này, chi phí CPU luôn là O(n.m). (6.2)
Để định giá chi phí I/O, thuật toán trên cần sửa đổi như sau để thể hiện rõ sự làm
việc theo trang. Gọi K là kích thước (theo trang) của bộ nhớ đệm sẵn có cho phép kết nối.
Rõ ràng, cần có K ≥ 3 vì bộ nhớ đệm cần giữ ít nhất một trang cho mỗi quan hệ R và S, và
một trang để tích lũy kết quả. Trong sự phân tích dưới đây, K được dùng để kí hiệu số
trang của bộ nhớ đệm hiện có cho hai quan hệ kết nối, không tính trang của bộ nhớ đệm
cho kết quả ra.
Trước hết xét trường hợp đặc biệt với K = 2. Khi R là quan hệ ngoài và S là quan hệ

≤ N và K
2
≤ M. Khi R là quan hệ ngoài và S là quan hệ trong, ta có thuật toán sau:
for mỗi K
1
trang P của R do
for mỗi K
2
trang Q của S do
for mỗi bộ x trong P do
for mỗi bộ y trong Q do
if x[A] = y [B] then return (x,y)
Vì R chỉ phải đọc một lần; với K
1
trang đầu tiên của R, phải đọc toàn bộ quan hệ S,
và với mỗi K
1
trang tiếp sau của R (có tất cả (N/K
1
 - 1) những nhóm K
1
trang của R như
vậy), chỉ phải đọc M – K
2
trang của S, do có cùng kĩ thuật quét qua lại. Chi phí I/O là:
NTD – Khoa Tin – ĐHSP Huế
24
GT CSDL – Chương 6. Xử lý và tối ưu câu truy vấn
N + M + ([N/K
1

tóm tắt như sau:
Nếu tiêu chuẩn tối ưu hóa là làm cực tiểu số trang I/O thì dùng quan hệ nhỏ hơn làm
quan hệ ngoài, và để cho quan hệ ngoài sử dụng số trang đệm nhiều theo sự cần thiết, tức
bằng với min {M, K – 1}.
Tuy nhiên, nếu tiêu chuẩn tối ưu hóa là làm cực tiểu số thao tác I/O lúc ban đầu (lúc
khởi đầu) thì có thể dùng một chiến lược cấp phát bộ nhớ đệm khác như sau. Chú ý là mỗi
thao tác I/O có thể đọc K
1
trang của R hay K
2
trang của S. Do đó, R có thể được đọc vào
với [N/K
1
] thao tác I/O. Tương tự, S có thể được đọc vào với [M/K
2
] thao tác I/O. Khi R
được dùng làm quan hệ ngoài, R cần được đọc vào một lần; với K
1
trang đầu của R, S cần
được quét vào một lần; với mỗi một trong số ([N/K
1
] – 1) nhóm K
1
trang của R, sẽ tiết
kiệm được một thao tác I/O khi đọc S theo kĩ thuật quét qua lại. Do đó, khi R được dùng
làm quan hệ ngoài, số các thao tác I/O cần thiết là:
[N/K
1
] + [M/K
2