-
Notifications
You must be signed in to change notification settings - Fork 5
4.2. HASH JOIN (KẾT NỐI BĂM)
Thuật toán này nhằm khắc phục những điểm yếu của của phép kết nối lồng nhau, thay vì phải duyệt nhiều cây B-tree khi thực hiện câu truy vấn trong (inner query), hash join đưa các bản ghi của một bảng thuộc phép kết nối vào bảng băm theo trường được join, nhờ vậy việc duyệt mỗi hàng của bảng còn lại diễn ra rất nhanh. Cách tiếp cận trong việc tinh chỉnh hash join yêu cầu đánh chỉ mục hoàn toàn khác so với kết nối lồng nhau. Cũng có thể làm tăng hiệu năng của hash join bằng cách chọn ít cột hơn để băm– đây là một thách thức cho hầu hết các công cụ ORM
MẸO
Việc đánh chỉ mục cho vị từ độc lập trong mệnh đề where giúp cải thiện hiệu năng của thuật toán hash join
Quan sát ví dụ sau: Lấy ra doanh số bán hàng từ bảng sales trong 6 tháng gần nhất tương ứng với từng nhân viên
SELECT *
FROM sales s
JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
AND s.employee_id = e.employee_id )
WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH
Trường sale_date là vị từ độc lập trong mệnh đề where – nghĩa là nó chỉ tham chiếu đến 1 bảng và không thuộc các vị từ kết nối
------------------------------------------------------------ | Id | Operation | Name | Rows | Bytes | Cost | ------------------------------------------------------------ | 0 | SELECT STATEMENT | | 49244 | 59M | 12049| |* 1 | HASH JOIN | | 49244 | 59M | 12049| | 2 | TABLE ACCESS FULL| EMPLOYEES | 10000 | 9M | 478 | |* 3 | TABLE ACCESS FULL| SALES | 49244 | 10M | 10521| ------------------------------------------------------------
Predicate Information (identified by operation id):
--------------------------------------------------
1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
AND "S"."EMPLOYEE_ID" ="E"."EMPLOYEE_ID")
3 - filter("S"."SALE_DATE">TRUNC(SYSDATE@!)
-INTERVAL'+00-06' YEAR(2) TO MONTH)
Bước đầu tiên, quét toàn bộ bảng employees và đưa vào bảng băm. Bảng băm sử dụng vị từ nối như khóa. Tiếp theo, quét toàn bộ bảng sales và loại bỏ những bản ghi không thỏa mãn điều kiện SALE_DATE. Với những bản ghi còn lại trong bảng sales, database truy cập bảng băm lấy ra các bản ghi tương ứng trong bảng employees.
Mục đính duy nhất của bảng băm là hoạt động như một cấu trúc bộ nhớ tạm thời để tránh việc truy cập vào bảng EMPLOYEE nhiều lần (Vì việc truy cập vào ổ cứng lưu bảng tốn thời gian hơn). Vì tất cả các bản ghi được nạp vào bảng băm nên ta không cần đánh chỉ mục cho các bản ghi đó. Không có điều kiện nào được sử dụng trên bảng EMPLOYEE, câu truy vấn cũng không có bất kỳ vị từ độc lập nào trên bảng này
QUAN TRỌNG
Việc đánh chỉ mục cho các vị từ kết nối không làm tăng hiệu năng của hash join
Điều này không có nghĩa là không thể đánh chỉ mục trong hash join. Các vị từ độc lập có thể được đánh chỉ mục. Có những 1 số các điều kiện được áp dụng trong suốt 1 trong 2 thao tác truy cập bảng.Trong ví dụ ở trên, đó là trường lọc sale_date
CREATE INDEX sales_date ON sales (sale_date);
Sau đây là kế hoạch thực thi sử dụng chỉ mục trên trường sale_date
-------------------------------------------------------------- | Id | Operation | Name | Bytes| Cost| -------------------------------------------------------------- | 0 | SELECT STATEMENT | | 59M| 3252| |* 1 | HASH JOIN | | 59M| 3252| | 2 | TABLE ACCESS FULL | EMPLOYEES | 9M| 478| | 3 | TABLE ACCESS BY INDEX ROWID| SALES | 10M| 1724| |* 4 | INDEX RANGE SCAN | SALES_DATE| | | --------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("S"."SUBSIDIARY_ID"="E"."SUBSIDIARY_ID"
AND "S"."EMPLOYEE_ID" ="E"."EMPLOYEE_ID" )
4 - access("S"."SALE_DATE" > TRUNC(SYSDATE@!)
-INTERVAL'+00-06' YEAR(2) TO MONTH)
Việc đánh chỉ mục trong hash join là đối xứng, trái ngược với kết nối lồng nhau. Nghĩa là thứ tự kết nối không ảnh hưởng tới việc đánh chỉ mục. Chỉ mục SALES_DATE có thể được dùng để nạp bảng băm nếu thứ tự kết nối bị đảo ngược.
CHÚ Ý
Đánh chỉ mục trong hash join không phụ thuộc vào thứ tự kết nối
Một cách tiếp cận khác để tối ưu hóa hiệu năng hash join là tối thiểu kịch thước bảng băm. Cách này hoạt động bởi hash join được tối ưu chỉ thỏa mãn nếu toàn bộ bảng băm được nạp vào trong bộ nhớ. Vì vậy, bộ tối ưu sẽ tự động sử dụng bảng có kích thước nhỏ hơn của phép kết nối để tiến hành băm. Trong kế hoạch thực thi ở trên, bảng EMPLOYEES cần 9MB và nó nhỏ hơn.
Có thể giảm kịch thước bảng băm bằng việc thay đổi câu truy vấn, ví dụ thêm một điều kiện vào mệnh đề where để database giảm số lượng các bản ghi cần nạp. Với ví dụ ở trên, có thể thêm một thuộc tính DEPARTMENT vào bảng sales. Điều này làm tăng hiệu năng của hash join ngay cả khi không đánh chỉ mục trên trường DEPARTMENT bởi vì database không cần lưu các nhân viên không có sales trong bảng băm.
Khi thu gọn kích thước bảng băm, điều quan trọng không phải số lượng các hàng mà là dung lượng bộ nhớ nó chiếm. Trong thực tế, cũng có thể giảm kích thước bảng băm bằng việc chọn ít cột hơn – chỉ những thuộc tính thực sự cần thiết.
SELECT s.sale_date, s.eur_value
, e.last_name, e.first_name
FROM sales s
JOIN employees e ON (s.subsidiary_id = e.subsidiary_id
AND s.employee_id = e.employee_id )
WHERE s.sale_date > trunc(sysdate) - INTERVAL '6' MONTH
Phương pháp này hiếm khi có lỗi bởi việc loại bỏ sai 1 cột có thể nhanh chóng đưa ra một thông báo lỗi. Tuy nhiên, có thể giảm đáng kể kích thước bảng băm, trong trường hợp này là từ 9MB xuống còn 234KB. Giảm 97%.
-------------------------------------------------------------- | Id | Operation | Name | Bytes| Cost| -------------------------------------------------------------- | 0 | SELECT STATEMENT | | 2067K| 2202| |* 1 | HASH JOIN | | 2067K| 2202| | 2 | TABLE ACCESS FULL | EMPLOYEES | 234K| 478| | 3 | TABLE ACCESS BY INDEX ROWID| SALES | 913K| 1724| |* 4 | INDEX RANGE SCAN | SALES_DATE| | 133| --------------------------------------------------------------
CHÚ Ý
Chọn ít cột hơn để cải thiện hiệu năng hash join
Mặc dù có vẻ như đơn giản khi loại bỏ một vài cột trong câu lệnh SQL. Nhưng đó là một thách thức lớn khi sử dụng công cụ ánh xạ quan hệ đối tượng (Object Relational Mapping - ORM). Vì khả năng xử lý dữ liệu trên từng phần của đối tượng rất hạn chế.
Ví dụ tiếp theo cho thấy một số khả năng.
JAVA
JPA định nghĩa FetchType.LAZY trong chú thích @Basic. Nó có thể áp dụng trên các lớp thuộc tính:
@Column(name="junk")
@Basic(fetch=FetchType.LAZY)
private String junk;
Chiến lược LAZY (lazily fetch): Trong lần lấy dữ liệu đầu tiên (ví dụ: nạp một thực thể) chỉ một phần dữ liệu được nạp (một số thuộc tính của thực thể), phần dữ liệu còn lại sẽ được nạp sau đó khi cần thiết bằng cách gọi phương thức tương ứng của đối tượng (các thuộc tính còn lại của thực thể)
Hibernate 3.6 thực hiện nạp dữ liệu theo kiểu Lazy trong thời gian trình điều khiển biên dịch. Trình điều khiển bổ xung code vào các lớp được biên dịch, các code này là mặc định sẽ nạp dữ liệu theo kiểu Lazy. Phương pháp này là hoàn toàn trong suốt đối với ứng dụng nhưng nó nảy sinh vấn đề “N+1 problems” (đã được định nghĩa ở phần Nester Loops Join): mất một lệnh select cho mỗi bản ghi và thuộc tính. Sẽ vô cùng nguy hiểm vì JPA không kiểm soát code lúc chạy nên nó không thể nạp thêm dữ liệu bổ sung khi cần thiết (do Lazy chỉ nạp một phần).
Ngôn ngữ HQL (Hibernate’s native query language) có thể giải quyết được vấn đề này với mệnh đề FETCH ALL PROPERTIES:
select s from Sales s FETCH ALL PROPERTIES
inner join fetch s.employee e FETCH ALL PROPERTIES
where s.saleDate >:dt
Mệnh đề FETCH ALL PROPERTIES bắt buộc Hibernate nạp toàn bộ dữ liệu của thực thể ngay cả khi sử dụng nhãn LAZY.
Một lựa chọn khác là chỉ tải duy nhất các cột đã chọn bằng cách sử dụng DTOs (data transport objects) thay cho các thực thể. Phương pháp này có cách thức hoạt động như nhau trong HQL và JPQL, bạn cần cài đặt một đối tượng trong câu truy vấn.
select new SalesHeadDTO(s.saleDate , s.eurValue
,e.firstName, e.lastName)
from Sales s
join s.employee e
where s.saleDate > :dt
Câu truy vấn chọn những dữ liệu được yêu cầu và trả về một đối tượng SalesHeadDTO – một đối tượng Java, không phải thực thể.
PERL
Framework DBIx::Class được dùng để ánh xạ các hàng trong cơ sở dữ liệu quan hệ thành đối tượng. Việc kế thừa từ lớp này không gây ra vấn đề aliasing (dữ liệu trong bộ nhớ có thể được truy cập bởi các tên biểu tượng – symbolic name khác nhau gây khó khăn trong việc phân tích và tối ưu chương trình). Lớp cookbook nằm trong framework DBIx::Class hỗ trợ phương pháp này. Lược đồ sau đây định nghĩa lớp Sales trên hai cấp độ:
package UseTheIndexLuke::Schema::Result::SalesHead;
use base qw/DBIx::Class::Core/;
__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/sale_id employee_id subsidiary_id
sale_date eur_value/);
__PACKAGE__->set_primary_key(qw/sale_id/);
__PACKAGE__->belongs_to('employee', 'Employees',
{'foreign.employee_id' => 'self.employee_id'
,'foreign.subsidiary_id' => 'self.subsidiary_id'});
package UseTheIndexLuke::Schema::Result::Sales;
use base qw/UseTheIndexLuke::Schema::Result::SalesHead/;
__PACKAGE__->table('sales');
__PACKAGE__->add_columns(qw/junk/);
Lớp Sales được kế thừa từ SalesHead và thêm vào một thuộc tính bị thiếu. Bạn có thể sử dụng cả 2 lớp nếu cần.Chú ý: việc cài đặt trong lớp được kế thừa cũng là bắt buộc.
Có thể lấy thông tin toàn bộ nhân viên bảng Employee bằng cách chọn các cột như đoạn mã sau:
my @sales =
$schema->resultset('SalesHead')
->search($cond
,{ join => 'employee'
,'+columns' => ['employee.first_name'
,'employee.last_name']
}
);
Không thể nạp chỉ những cột được chọn từ bảng gốc – SaleHead trong trường hợp này DBIx::Class 0.008192 tạo ra mệnh đề SQL sau. Nó lấy tất các cột từ bảng SALES và lấy các thuộc tính từ EMPLOYEES:
SELECT me.sale_id,
me.employee_id,
me.subsidiary_id,
me.sale_date,
me.eur_value,
employee.first_name,
employee.last_name
FROM sales me
JOIN employees employee
ON( employee.employee_id = me.employee_id
AND employee.subsidiary_id = me.subsidiary_id)
WHERE(sale_date > ?)
PHP Version 2 của framework Doctrine hỗ trợ việc chọn thuộc tính trong thời điểm runtime. Tuy nhiên bạn cần phải chọn cột khóa chính một cách rõ ràng:
$qb = $em->createQueryBuilder();
$qb->select('partial s.{sale_id, sale_date, eur_value},'
. 'partial e.{employee_id, subsidiary_id, '
. 'first_name , last_name}')
->from('Sales', 's')
->join('s.employee', 'e')
->where("s.sale_date > :dt")
->setParameter('dt', $dt, Type::DATETIME);
Câu lệnh SQL được tạo ra chứa các cột yêu cầu cùng SUBSIDIARY_ID và EMPLOYEE_ID từ bảng SALES.
SELECT
s0_.sale_id AS sale_id0,
s0_.sale_date AS sale_date1,
s0_.eur_value AS eur_value2,
e1_.employee_id AS employee_id3,
e1_.subsidiary_id AS subsidiary_id4,
e1_.first_name AS first_name5,
e1_.last_name AS last_name6,
s0_.subsidiary_id AS subsidiary_id7,
s0_.employee_id AS employee_id8
FROM sales s0_
INNER JOIN employees e1_
ON s0_.subsidiary_id = e1_.subsidiary_id
AND s0_.employee_id = e1_.employee_id
WHERE s0_.sale_date > ?
Đối tượng trả về là tương thích với các đối tược đã được nạp đầy đủ, nhưng các cột còn thiếu vẫn chưa được khởi tạo. Việc truy cập chúng không đưa ra ngoại lệ
CẢNH BÁO
MySQL không hỗ trợ hash join