Tối ưu hóa truy vấn trong các cơ sở dữ liệu phân tán

Ưu điểm của phương pháp động so với phương pháp tĩnh là kích thước thực sự của các quan hệ trung gian là phù hợp cho bộ xử lý truy vấn. Vì vậy, sẽ giảm thiểu xác suất cho việc lựa chọn một giải pháp tồi.

Nhược điểm của phương pháp động là các thao tác tối ưu hóa có chi phí cao, lặp lại nhiều lần cho mỗi thao tác. Vì vậy, phương pháp này sẽ rất phù hợp cho một số câu truy vấn đặc biệt.

Phần này sẽ trình bày một số thuật toán tối ưu hóa truy vấn cơ bản trong CSDL phân tán như thuật toán INGRES phân tán, thuật toán R* và một thuật toán mới, kết hợp giữa thuật toán quy hoạch động (Dynamic Programming) và thuật toán đàn kiến (Ant Colony Optimization) được gọi là DP-ACO.

2.4.1. Thuật toán D-INGRES

Thuật toán D-INGRES hay còn gọi là INGRES phân tán [11] là sự mở rộng của thuật toán INGRES tập trung, sử dụng chiến lược tối ưu động. Hàm mục tiêu của thuật toán là tối thiểu tổng chi phí và thời gian trả lời, nhưng hai mục tiêu này đối lập nhau (tăng chi phí truyền thông có thể giảm thời gian trả lời) nên hàm mục tiêu có trọng số lớn hơn cho mục tiêu này hoặc mục tiêu kia. Thuật toán tối ưu hóa truy vấn bỏ qua chi phí truyền dữ liệu tới trạm kết quả, thuật toán sử dụng phân đoạn ngang và xét cả hai kiểu mạng (mạng cục bộ và diện rộng)

Thuật toán INGRES tập trung là một thuật toán tối ưu hóa truy vấn động, chia câu truy vấn thành các truy vấn con. Ý tưởng của thuật toán như sau:

 Một câu truy vấn q có n quan hệ sẽ được phân rã thành n truy vấn con q1 q2 … qn, trong đó, mỗi qi là một truy vấn có 1 quan hệ, qi+1 sử dụng kết quả của qi.

 Hai kỹ thuật phân rã cơ bản được sử dụng là tách (detachment) và thay thế (substitution)

 Có một bộ xử lý có thể xử lý hiệu quả các truy vấn một quan hệ. Detachment: Tách câu truy vấn q thành q‟  q” dựa vào quan hệ chung là kết quả của q‟. Câu truy vấn q:

SELECT R2.A2, ...., Rn.An

FROM R1, R2,..., Rn WHERE P1(R1.A1')

AND P2(R1.A1, R2.A2,...., Rn.An)

Dựa vào quan hệ chung R1, q được tách thành: q': SELECT R1.A1 INTO R1'

FROM R1 WHERE P1(R1.A1')

q": SELECT R2.A2,...., Rn.An FROM R1', R2,..., Rn

WHERE P2(R‟1.A1, R2.A2,..., Rn.An)

Ví dụ 2.15: Xét câu truy vấn q1: “Tên của các nhân viên làm dự án CAD/CAM” biểu diễn dưới dạng SQL như sau:

SELECT NV.TenNV FROM NV, PC, DA

WHERE NV.MNV = PC.MNV

and PC.MDA = DA.MDA

and DA.TenDA = “CAD/CAM”

Tách q1 thành q11 q‟:

q11: SELECT DA.MDA into TG1 FROM DA

WHERE DA.TenDA = “CAD/CAM”

q‟: SELECT NV.TenNV FROM NV, PC, TG1

WHERE NV.MNV = PC.MNV

and PC.MDA = TG1.MDA

Tiếp tục tách q‟ thành q12  q13:

q12:

SELECT	PC.MNV into TG2
	FROM	PC, TG1
	WHERE	PC.MDA = TG1.MDA
q13:	SELECT FROM	NV.TenNV NV, TG2
	WHERE	NV.MNV = TG2.MNV

Có thể bạn quan tâm!

Xem toàn bộ 103 trang tài liệu này.

q1 đã được phân tách thành q11  q12  q13, trong đó q11 là truy vấn có 1 quan hệ, q12 và q13 là truy vấn đa quan hệ không thể phân tách hay được gọi là truy vấn không thể rút gọn.

Tuple Substitution: cho phép chuyển một truy vấn không thể rút gọn q thành nhiều truy vấn có 1 quan hệ.

 Chọn một quan hệ R1 trong q để thay thế bộ giá trị.

 Với mỗi bộ giá trị trong R1, thay thế các thuộc tính của R1 trong truy vấn q bằng các giá trị thực của chúng bằng cách tạo ra một tập các truy vấn con q‟ với n - 1 quan hệ.

q(R1, R2,…., Rn) được thay thế bằng {q‟(t1i, R2, …., Rn), t1i  R1}

Tiếp tục xét Ví dụ 2.15: Giả sử TG2 chỉ có hai bộ giá trị {E1, E2}. q13 sẽ được viết lại thành q131 và q132 là các truy vấn có một quan hệ như sau:

q131: SELECT NV.TenNV FROM NV

WHERE NV.MaNV = “E1” q132: SELECT NV.TenNV

FROM NV

WHERE NV.MaNV = “E2”

Để phù hợp với môi trường phân tán, thuật toán INGRES tập trung đã được mở rộng tạo thành thuật toán INGRES phân tán: Tách mỗi truy vấn qithành các truy vấn con thực hiện trên các phân mảnh, chỉ áp dụng với phân mảnh ngang. Mục

đích chính của thuật toán này là giảm tổng chi phí hoặc thời gian trả lời. Một trạm cụ thể trong hệ thống phân tán mà thuật toán được thực thi gọi là trạm chủ (master) và là nơi câu truy vấn được khởi tạo. Thuật toán hoạt động như sau:

Với một truy vấn đã cho, tất cả các truy vấn có một quan hệ có thể được tách đầu tiên và được xử lý cục bộ. Sau đó thuật toán rút gọn sẽ được áp dụng cho truy vấn gốc và sẽ tạo ra hai loại truy vấn con: Truy vấn con không thể rút gọn và các truy vấn có một quan hệ. Rút gọn là kỹ thuật tách riêng tất cả các truy vấn không thể rút gọn và truy vấn có một quan hệ từ câu truy vấn gốc bằng kỹ thuật phân rã. Do các truy vấn có một quan hệ đã được xử lý cục bộ nên không cần chú ý đến chúng. Giả sử rằng, kỹ thuật rút gọn tạo ra một dãy các câu truy vấn không thể rút gọn q1  q2 ....  qn , trong đó có ít nhất một quan hệ chung giữa hai truy vấn con liên tiếp.

Dựa vào dãy các câu truy vấn không thể rút gọn và kích thước của mỗi phân mảnh, một truy vấn con trong danh sách sẽ được chọn, gọi là qi, có ít nhất hai quan hệ. Trong quá trình xử lý truy vấn con qi, ban đầu chiến lược tốt nhất được xác định cho truy vấn con. Chiến lược này được biểu diễn bởi một danh sách các cặp (F,S), trong đó F đại diện cho một phân mảnh được chuyển tới trạm xử lý S. Sau khi chuyển tất cả các phân mảnh tới trạm xử lý tương ứng, truy vấn con qi cuối cùng được thực thi. Thủ tục này được lặp lại với tất cả các truy vấn không thể rút gọn trong dãy q1  q2 ....  qn và thuật toán kết thúc.

Thuật toán được thể hiện như sau:

Thuật toán INGRES phân tán (D-INGRES) [10]

Input: MRQ: Câu truy vấn có nhiều quan hệ. Output: Kết quả của câu truy vấn con cuối cùng. Begin

For mỗi ORQi có thể tách ra in MRQ do {ORQi là truy vấn một biến} Run(ORQi); (1)

MRQ„_list  REDUCE (MRQ) {MRQ„ chứa n truy vấn không thể rút gọn}

(2)

While n ≠ 0 do (3)

{Chọn truy vấn không thể rút gọn tiếp theo liên quan đến mảnh nhỏ

nhất}

MRQ„  SELECT_QUERY (MRQ„_list); (3.1)

{Xác định mảnh để truyền và trạm xử lý cho MRQ„}

Fragment-site-list  SELECT_STRATEGY (MRQ„) (3.2)

{Chuyển các mảnh đã chọn đến trạm xử lý đã chọn} For mỗi cặp (F,S) trong Fragment-site-list do

Chuyển mảnh F tới trạm xử lý S; (3.3) Thực thi MRQ„; (3.4)

n  n-1;

{kết quả đầu ra là kết quả của MRQ„ cuối cùng}

End.

Thuật toán trên được mô tả như sau:

Bước 1: Tách riêng tất cả các truy vấn có một quan hệ từ câu truy vấn MRQ và chạy ở trạm cục bộ giống thuật toán INGRES tập trung.

Bước 2: Áp dụng kỹ thuật rút gọn với MRQ sẽ tạo ra một danh sách n truy vấn con không thể rút gọn được (Bỏ qua tất cả các truy vấn con có một quan hệ vì chúng đã được xử lý ở các trạm cục bộ)

Bước 3: Áp dụng cho các truy vấn con không thể rút gọn trong danh sách

trên.

Bước 3.1: Chọn một truy vấn con không thể rút gọn liên quan đến mảnh nhỏ nhất.

Bước 3.2: Xác định chiến lược tốt nhất để xử lý câu truy vấn đã chọn. Chiến lược này gồm các cặp giá trị (F, S), F đại diện cho một mảnh, S đại diện cho trạm xử lý

Bước 3.3: Với mỗi cặp (F,S), chuyển mảnh F đến trạm xử lý S

Bước 3.4: Thực thi câu truy vấn đã chọn. Nếu còn truy vấn trong danh sách truy vấn con không thể rút gọn, thuật toán quay lại bước 3 và thực hiện bước lặp tiếp theo, ngược lại thuật toán kết thúc.

Kết quả đầu ra là kết quả xử lý câu truy vấn cuối cùng trong danh sách các câu truy vấn con không thể rút gọn.

Đặc điểm của thuật toán INGRES phân tán là tìm kiếm giới hạn trong không gian giải pháp, một quyết định tối ưu hoá thu được ở mỗi bước mà không cần quan tâm đến tầm quan trọng của quyết định đó tối ưu tổng thể. Tối ưu hoá câu truy vấn động có lợi vì kích thước chính xác của kết quả trung gian được biết.

2.4.2. Thuật toán R*

Thuật toán tối ưu hóa truy vấn phân tán của R* là một sự mở rộng quan trọng của các kỹ thuật đã phát triển cho bộ tối ưu System R[10]. Vì vậy, nó sử dụng cách tiếp cận biên dịch trong đó thực hiện việc tìm kiếm vét cạn tất cả các chiến lược khác nhau để chọn một chiến lược với chi phí thấp nhất. Thuật toán xử lý truy vấn R* chỉ giải quyết các quan hệ như các đơn vị cơ bản. Biên dịch truy vấn là một nhiệm vụ phân tán trong R* được phối hợp bởi trạm chủ, tại đó truy vấn được bắt đầu.

Mục tiêu của thuật toán R* là giảm tổng chi phí, bao gồm chi phí xử lý cục bộ và chi phí truyền thông. Thuật toán R* sử dụng cách tìm kiếm toàn diện, thực hiện tìm kiếm vét cạn tất cả các chiến lược có thể để tìm ra chiến lược tốt nhất với chi phí nhỏ nhất. Thuật toán không hỗ trợ việc phân mảnh hoặc bản sao, vì vậy, nó chỉ giải quyết các quan hệ như các đơn vị cơ bản. Thuật toán này lựa chọn một trạm làm trạm chủ, câu truy vấn được khởi tạo từ trạm này. Bộ tối ưu truy vấn trên trạm chủ này có thể đưa ra tất cả các quyết định giữa các trạm như trạm nào được chọn để thực hiện, mảnh nào sẽ được sử dụng và phương thức truyền dữ liệu. Các trạm vệ tinh (apprentice sites) là các trạm khác lưu trữ các quan hệ liên quan trong câu truy vấn, có thể đưa ra các quyết định cục bộ còn lại và tạo ra các kế hoạch truy nhập cục bộ để thực thi câu truy vấn. Thuật toán được thực hiện như sau:

Thuật toán R*:

Input: QT: Cây truy vấn của câu truy vấn có n quan hệ. Output: strat: Chiến lược thực thi tối ưu (có chi phí nhỏ nhất) Begin

For mỗi quan hệ Ri thuộc QT do (1)

For mỗi đường truy cập APij tới Ri do

Tính chi phí của APij;

best_APi  APij có chi phí nhỏ nhất;

For mỗi thứ tự (Ri1, Ri2,...,Rin) do {i= 1,...., n!} (2) Xây dựng chiến lược (...((best APi1 Ri2) Ri3) … Rin); Tính chi phí của chiến lược này;

strat  Chiến lược có chi phí tốt nhất; (3)

For mỗi trạm k chứa một quan hệ trong QT do (4)

LSk Chiến lược cục bộ (chiến lược, k); {Xác định chiến lược tối ưu cục

bộ LSk tại trạm k}

Send (LSk, trạm k);

End.

Trong thuật toán này, dựa vào các thống kê về cơ sở dữ liệu và công thức được sử dụng để ước lượng kích thước của các kết quả trung gian và thông tin của đường truy nhập, bộ tối ưu hóa sẽ xác định thứ tự kết nối, các thuật toán nối (nested-loop hay merge - join) và đường truy nhập cho mỗi phân mảnh. Ngoài ra, nó cũng xác định các trạm chứa các kết quả nối và phương thức truyền dữ liệu giữa các trạm. Để thực hiện kết nối giữa hai quan hệ, sẽ có 3 trạm tham gia, đó là trạm chứa quan hệ đầu tiên, trạm chứa quan hệ thứ 2 và trạm chứa kết quả. Hai kỹ thuật truyền dữ liệu giữa các trạm:

- Chuyển toàn bộ (Ship-whole): Toàn bộ quan hệ sẽ được chuyển tới trạm kết nối và được lưu trữ trong một quan hệ tạm thời trước khi thực hiện phép kết

nối. Kỹ thuật này yêu cầu dữ liệu truyền lớn nhưng số lượng thông báo nhỏ hơn và tốt hơn với các quan hệ nhỏ.

- Tìm về khi cần (Fetch – as – needed): Kỹ thuật này giống với phép nối nửa của một quan hệ trong với một nút ngoài. Quan hệ ngoài được quét tuần tự, từng bộ giá trị kết nối sẽ được gửi tới trạm của quan hệ trong. Những bộ giá trị của quan hệ trong phù hợp với giá trị của quan hệ ngoài sẽ được chọn và được gửi tới trạm chứa quan hệ ngoài. Kỹ thuật này phù hợp với quan hệ lớn hơn và phép kết nối có tính chọn lọc tốt.

Với kỹ thuật Fetch – as – needed sẽ có 4 chiến lược nối R S, với R là quan hệ ngoài, S là quan hệ trong. Ký hiệu: LT là thời gian xử lý cục bộ, CT là chi phí truyền thông, s là số trung bình các bộ của S phù hợp với một bộ của R.

( ⋉ )

( )

+ Chiến lược 1: Chuyển toàn bộ quan hệ ngoài tới trạm chứa quan hệ trong.

Tổng chi phí là:

Total_cost = LT( gọi card(R) bộ từ R) + CT (size (R))

+ LT( gọi s bộ từ S)* card (R)

+ Chiến lược 2: Chuyển quan hệ trong tới trạm của quan hệ ngoài. Trường hợp này, các bộ của quan hệ trong không thể kết nối khi chúng đến nên cần được lưu trong một quan hệ T tạm thời. Vì vậy ta có:

Total_cost = LT(gọi card(S) bộ từ S)

+ CT(size(S))

+ LT(lưu card(S) bộ trong T)

+ LT(gọi card(R) bộ từ R)

+ LT(gọi s bộ từ T)*card(R)

+ Chiến lược 3: Tìm các bộ của quan hệ trong khi cần đối với mỗi bộ của quan hệ ngoài. Trường hợp này, với mỗi bộ của R, giá trị thuộc tính kết nối A được gửi tới trạm của S. Sau đó, s phù hợp với các bộ của S được gọi và gửi tới trạm của R để được kết nối khi chúng đến. Vì vậy ta có: