Mục lục
Bối cảnh
I. Cách phân chia dữ liệu trong Doris
1.1 Phân vùng
1.2 Phân桶
II. Các phương thức Join
2.1 Tổng quan
2.2 Broadcast Join
2.3 Shuffle Join
2.4 Bucket Shuffle Join
2.5 Colocation Join
2.6 So sánh bốn phương thức Shuffle
III. Tối ưu Runtime Filter Join
3.1 Tổng quan Runtime Filter
3.2 Nguyên lý Runtime Filter Join
3.3 Các loại Runtime Filter
3.3.1 IN
3.3.2 Bloom Filter
3.3.3 MinMax
IV. Tối ưu Join Reorder
4.1 Tổng quan Join Reorder
4.2 Thuật toán Join Reorder
V. Điều chỉnh Join
5.1 Khuyến nghị điều chỉnh Join
5.2 Phương pháp điều chỉnh Join
5.3 Trường hợp thực tế điều chỉnh
Bối cảnh
Hiểu biết về các phương pháp tối ưu hóa trong Doris và nguyên lý thực thi của chúng, cung cấp cơ sở lý thuyết cho việc đọc mã nguồn.
I. Cách phân chia dữ liệu trong Doris
Trước khi giới thiệu nhiều phương thức Join và nguyên lý tối ưu hóa trong Doris, hãy xem lại cơ chế phân chia dữ liệu và đa bản sao tablet của Doris. Doris hỗ trợ hai lớp phân chia dữ liệu, lớp đầu tiên là Range Partition, lớp thứ hai là Hash Bucket (Tablet). Bảng dữ liệu của Doris theo quy tắc phân vùng và phân桶 được cắt nhỏ thành nhiều phân đoạn dữ liệu (Tablet, còn gọi là phân桶 Bucket) lưu trữ trên các node BE khác nhau, mỗi tablet có nhiều bản sao (mặc định là 3 bản sao). Dữ liệu giữa các Tablet không có giao điểm và được lưu trữ độc lập về mặt vật lý. Tablet là đơn vị lưu trữ vật lý nhỏ nhất cho các thao tác di chuyển, sao chép dữ liệu.
Hình ảnh dưới đây minh họa mối quan hệ giữa Table, Partition, Bucket (Tablet):
- Giả sử Table được phân chia theo Range theo trường date, thu được N Partition
- Mỗi Partition được chia thành M Bucket (Tablet) cùng một cách Hash
- Về mặt logic, Bucket 1 có thể chứa dữ liệu được phân chia từ N Partition, ví dụ như Tablet 11, Tablet 21, Tablet N1 trong hình dưới
1.1 Phân vùng
Là khái niệm logic, phân vùng được sử dụng để chia dữ liệu thành các khoảng khác nhau, chủ yếu để chia một bảng thành các đơn vị quản lý khác nhau theo khóa phân vùng. Khi truy vấn, thông qua cắt giảm phân vùng, có thể giảm lượng dữ liệu quét, tối ưu hóa đáng kể hiệu suất truy vấn.
1.2 Phân桶
Là khái niệm vật lý, StarRocks thường sử dụng thuật toán Hash làm thuật toán phân桶. Trong cùng một phân vùng, dữ liệu có cùng giá trị băm của khóa phân桶 sẽ được chia vào cùng một tablet (phân đoạn dữ liệu), tablet được lưu trữ với nhiều bản sao dư thừa, là đơn vị nhỏ nhất cho cân bằng dữ liệu và phục hồi, dữ liệu được nhập và truy vấn cuối cùng đều được chuyển đến bản sao tablet liên quan.
II. Các phương thức Join
2.1 Tổng quan
Là cơ sở dữ liệu MPP phân tán, trong quá trình Join cần thực hiện Shuffle dữ liệu, dữ liệu cần được chia nhỏ và điều phối để đảm bảo kết quả Join cuối cùng là chính xác.
Hiện tại, Doris hỗ trợ 4 phương thức Join: Broadcast Join, Shuffle Join, Bucket Shuffle Join và Colocate Join. Độ linh hoạt và tính ứng dụng của 4 phương thức này giảm dần, yêu cầu về phân bố dữ liệu ngày càng nghiêm ngặt hơn, nhưng hiệu suất tính toán Join lại ngày càng tốt hơn nhờ giảm thiểu chi phí mạng.
Việc chọn phương thức Join là một trong những yếu tố được xem xét trong giai đoạn tạo kế hoạch phân tán của FE. Khi FE tạo kế hoạch phân tán, thứ tự ưu tiên lựa chọn là: Colocate Join -> Bucket Shuffle Join -> Broadcast Join -> Shuffle Join. Rõ ràng, Colocate và Bucket Shuffle là những thứ khó có thể gặp. Khi không thể sử dụng chúng, Doris sẽ tự động thử thực hiện Broadcast Join (bảng lớn join bảng nhỏ), nếu bảng nhỏ được đánh giá là quá lớn thì sẽ tự động chuyển sang Shuffle Join.
Tuy nhiên, người dùng cũng có thể sử dụng Hint rõ ràng để buộc sử dụng kiểu Join mong muốn, ví dụ:
SELECT k1 FROM bang1 JOIN [BUCKET] bang2 ON bang1.k1 = bang2.k2 GROUP BY bang2.k2;
2.2 Broadcast Join
SELECT * FROM bangA,bangB WHERE bangA.cot=bangB.cot
Bằng cách gửi toàn bộ dữ liệu của bảng B đến các máy của bảng A, thực hiện thao tác Join trên máy của bảng A, so với Shuffle join tiết kiệm được việc Shuffle dữ liệu của bảng A, nhưng dữ liệu của bảng B được phát sóng toàn bộ, phù hợp với tình huống bảng B là bảng nhỏ.
Như hình dưới đây, theo phân bố dữ liệu, truy vấn lập kế hoạch có 3 HashJoinNode thực thi cho bảng A, cần gửi toàn bộ bảng B đến 3 HashJoinNode, chi phí mạng là 3B, chi phí bộ nhớ cũng là 3B.
- Ưu điểm: chi phí mạng 3B
- Nhược điểm: chiếm dụng nhiều bộ nhớ (mỗi BE đều cần đặt bảng B trong bộ nhớ), chi phí bộ nhớ 3B
Do chiếm dụng nhiều bộ nhớ, nếu dữ liệu của bảng B đủ lớn, thì không thể thực hiện Broadcast Join (phù hợp với bảng lớn join bảng nhỏ), vì vậy Doris đã giới thiệu Shuffle Join
2.3 Shuffle Join
<