Nền
Ở chế độ hàng truyền thống kế hoạch thực thi, SQL Server có thể giới thiệu toán tử Bitmap như một phần của việc thực hiện sớm giảm kết nối bán phần trước một phép băm song song hoặc phép hợp nhất. Bitmap được xây dựng từ đầu vào bản dựng và được sử dụng để lọc các hàng trên đầu vào của đầu dò trước khi chúng đến được kết nối. Tôi đã viết về chế độ hàng ảnh bitmap trước đây và chúng cũng được đề cập trong tài liệu.
Bài viết này nói về chế độ hàng loạt bitmap, có cách triển khai rất khác. Đã có những cải tiến lớn kể từ lần xuất hiện đầu tiên của công cụ thực thi chế độ hàng loạt trong SQL Server 2012. Các chi tiết đưa ra ở đây áp dụng cho SQL Server 2017 - phiên bản được phát hành gần đây nhất tại thời điểm viết bài. Các tính năng cụ thể cho các phiên bản trước đó sẽ được đề cập nội tuyến khi chúng ta cùng tìm hiểu.
Trình tối ưu hóa Truy vấn
Toán tử tham gia duy nhất có thể chạy ở chế độ hàng loạt là tham gia băm. Trình tối ưu hóa truy vấn quyết định xem tham gia băm chế độ hàng loạt (nối tiếp hoặc song song) có nên có một bitmap hay không. Trình tối ưu hóa đánh giá mức độ hữu ích tiềm năng của một bitmap bằng cách tính toán tính chọn lọc của một kết nối bán giả định của các đầu vào tham gia băm trên (các) khóa tham gia.
Một phép nối bán phần có ý nghĩa, bởi vì chức năng của lọc bitmap là loại bỏ các hàng từ phía thăm dò không tồn tại ở phía xây dựng. Nếu độ chọn lọc ước tính của kết hợp bán là 0,75 hoặc ít hơn, trình tối ưu hóa coi việc sử dụng bộ lọc bitmap ở chế độ hàng loạt là đáng giá. Nói cách khác, một bitmap được chỉ định nếu phép tính kết nối bán chỉ ra rằng 25% hoặc nhiều hơn các hàng phía đầu dò sẽ bị loại bỏ bởi bitmap.
Tính chọn lọc của phép nối bán chính xác chỉ được sử dụng để xác định xem phép nối băm có nên có một bitmap hay không. Ước tính độ chọn lọc phía đầu dò (có thể nhìn thấy như một hiệu ứng đối với ước tính số lượng) được sửa đổi để phản ánh thực tế rằng bitmap thường không hoàn hảo trong việc loại bỏ các hàng không đủ tiêu chuẩn. Điều này đặc biệt xảy ra khi bitmap được triển khai bằng bộ lọc Bloom, có thể tạo ra kết quả dương tính giả (các hàng phía đầu dò vượt qua bộ lọc, nhưng không kết hợp với phía bản dựng).
Làm tròn độ chọn lọc
Bộ tối ưu hóa tính đến độ không đảm bảo này bằng cách làm tròn độ chọn lọc bán nối thành lũy thừa mười. Nó thực hiện điều này bằng cách lấy logarit cơ số 10 trước khi làm tròn. Ví dụ:độ chọn lọc bán nối là 0,316 cung cấp nhật ký 10 giá trị dưới -0,5 theo tỷ lệ, được làm tròn xuống -1. Độ chọn lọc phía đầu dò thu được là 10 =0,1. Ngược lại, độ chọn lọc bán nối là 0,317 cho một nhật ký 10 giá trị chỉ trên -0,5, được làm tròn thành 0. Do đó, độ chọn lọc phía đầu dò là 10 =1 (tất cả các hàng đều vượt qua). Các khả năng chọn lọc bitmap phía đầu dò do chuỗi tính toán này là 1, 0,1, 0,01, 0,001, v.v. Lưu ý rằng một bitmap vẫn có thể được sử dụng khi độ chọn lọc ước tính được làm tròn lên 1 (tất cả các hàng đều vượt qua vị từ).
Các toán tử và ước tính bản số
Không có Bitmap riêng biệt toán tử cho phép tham gia băm chế độ hàng loạt. Thay vào đó, toán tử tham gia băm có một Trình tạo bitmap thuộc tính (được đặt thành đúng), hoặc thuộc tính bị thiếu (không được đặt thành sai). Sự khác biệt này giữa chế độ hàng và thực thi chế độ hàng loạt làm cho việc xem một bitmap đang được tạo ít dễ dàng hơn hay không, nhưng nó phản ánh chính xác hơn quy trình cơ bản:Trong thực thi chế độ hàng, Bitmap toán tử điền bitmap khi các hàng chảy qua nó, từng hàng một, trước khi đến đầu vào xây dựng tham gia băm. Nói cách khác, bitmap và bảng băm được xây dựng đồng thời trong quá trình thực thi chế độ hàng. Ở chế độ hàng loạt, bảng băm được tạo đầy đủ trước khi tạo bitmap (sẽ sớm có thêm thông tin về điều này).
Trình tối ưu hóa truy vấn không thực hiện các lựa chọn dựa trên chi phí về vị trí của bộ lọc bitmap chế độ hàng loạt ở phía thăm dò của phép nối băm. Nó chỉ đơn giản giả định rằng tính chọn lọc của bitmap sẽ áp dụng cho tất cả các toán tử con ở phía thăm dò. Trong thực tế, bitmap chỉ được đẩy xuống phía đầu dò khi một kế hoạch thực thi cuối cùng duy nhất đã được trình tối ưu hóa chọn. Nếu không thể đẩy toàn bộ bitmap xuống một toán tử lá, thì các ước lượng về bản số sẽ trông hơi lạ. Đây là sự đánh đổi có thể được cải thiện trong tương lai.
Công cụ thực thi
Trong khi trình tối ưu hóa quyết định liệu bitmap chế độ tham gia băm có nên được sử dụng hay không, công cụ thực thi chế độ hàng loạt quyết định loại của bitmap để sử dụng trong thời gian chạy. Quyết định này được thông báo bởi thông tin thống kê thu thập được về các khóa tham gia bên bản dựng trong quá trình xây dựng bảng băm. Như đã đề cập trước đây, trái ngược với thực thi chế độ hàng, băm chế độ hàng loạt tham gia hoàn toàn vào việc xây dựng bảng băm trước, trước khi thực hiện một chuyển riêng qua bảng băm để xây dựng bitmap.
Bản đồ bit đơn giản
Có hai loại bitmap tham gia băm chế độ hàng loạt chính. Đ đơn giản bitmap chứa một bit cho mỗi phạm vi giá trị phía xây dựng liền kề. Ví dụ:một bitmap đơn giản một byte có khả năng cho biết tám giá trị mặt dựng liền kề có hiện diện hay không. Các giá trị bao gồm từ 0 đến 7 có thể được mã hóa thành bitmap bằng cách đặt bit tương ứng. Giá trị 5 sẽ đặt bit 5, có giá trị vị trí là 2. Chúng ta có thể mã hóa tập {1, 5, 7} là 2 + 2 + 2 =2 + 32 + 128 =162 =10100010 2 . Một dải giá trị không bắt đầu bằng 0 có thể được mã hóa theo cùng một cách bằng cách bù trừ tất cả các giá trị bằng giá trị nhỏ nhất có trong tập hợp (mà chúng tôi biết từ thống kê bảng băm).
Một bitmap đơn giản có lợi thế là lưu trữ chính xác thông tin về các giá trị phía bản dựng thực sự hiện diện, với chi phí yêu cầu bộ nhớ tỷ lệ với phạm vi giá trị hiện tại.
Bản đồ Bit phức tạp
Loại bitmap thứ hai là bộ lọc Bloom. Điều này đặt một hoặc nhiều bit trong cấu trúc bitmap tùy theo kết quả của việc áp dụng một hoặc nhiều hàm băm cho mỗi giá trị bên dựng. Chúng tôi kiểm tra các kết quả phù hợp bằng cách áp dụng các hàm băm giống nhau cho mỗi giá trị phía thăm dò. Nếu bất kỳ hàm băm nào xác định một bit chưa được đặt, chúng tôi có thể chắc chắn rằng giá trị thăm dò hiện tại không xuất hiện ở phía bản dựng.
Vì bộ lọc Bloom là một cấu trúc xác suất, chúng tôi có thể không lọc ra một số giá trị thăm dò không có kết quả phù hợp phía xây dựng (dương tính giả), nhưng chúng tôi sẽ không bao giờ lọc ra giá trị hiện có (âm tính giả). Nói cách khác, bộ lọc Bloom cho chúng ta biết “có thể là một kết quả phù hợp” hoặc “chắc chắn không phải là một kết quả phù hợp”. Tỷ lệ xác thực sai có thể được giảm bớt bằng cách sử dụng nhiều bit hơn cho mỗi khóa (bitmap lớn hơn) hoặc nhiều hàm băm hơn. Để rõ ràng hơn, bộ lọc Bloom có thể tạo ra bộ lọc chính xác, nhưng nó cũng có thể không.
Bộ lọc Bloom cung cấp một giải pháp thay thế hiệu quả về không gian và thời gian khi một bitmap đơn giản không khả thi do yêu cầu về không gian. Việc triển khai chế độ hàng loạt SQL Server của bộ lọc Bloom được tối ưu hóa cho các kiến trúc bộ nhớ đệm CPU hiện đại và được gọi nội bộ là bitmap phức tạp . Các bitmap phức tạp đã hỗ trợ nhiều cột nối và tất cả các kiểu dữ liệu ở chế độ hàng loạt kể từ SQL Server 2014.
Lựa chọn bitmap
SQL Server có chọn một đơn giản hay không hoặc phức tạp (Bộ lọc nở hoa) bitmap phụ thuộc vào phạm vi giá trị bên dựng (từ thống kê bảng băm). Có một cảnh báo quan trọng đối với từ “phạm vi” ở đó, điều này sẽ được giải thích trong phần tiếp theo. Trong khi đó, đây là cách công cụ thực thi chọn loại bitmap:
- Một bitmap nhỏ đơn giản được sử dụng khi phạm vi giá trị là 2 (8,388,608) trở xuống. Đây là số bit trong 1MB.
- Khi phạm vi giá trị lớn hơn 2 nhưng nhỏ hơn hoặc bằng 2 (8MB), công cụ thực thi sẽ chọn giữa bitmap đơn giản lớn và một bitmap phức tạp bằng cách tính toán bộ nhớ cần thiết cho mỗi tùy chọn và chọn tùy chọn nhỏ hơn. Một ảnh bitmap đơn giản lớn có thể có kích thước lên đến 8MB. Kích thước của một bitmap phức tạp phụ thuộc vào số lượng bit trên mỗi khóa cần thiết để thể hiện đầy đủ dữ liệu. Các giá trị khác biệt hơn thường có nghĩa là một bitmap phức tạp lớn hơn.
- Nếu phạm vi giá trị vượt quá 2 bit, thì bitmap phức tạp được sử dụng.
Giới thiệu về phạm vi giá trị
Phạm vi của các giá trị được đề cập ở trên dựa trên nhị phân nội bộ đại diện của dữ liệu. Ví dụ:smallint giá trị 128 và 255 có thể được biểu thị dưới dạng 0x0080 và 0x00FF , đưa ra một dải 0x7F (127) giá trị nhị phân. Phạm vi này sẽ hoạt động tốt với một bitmap đơn giản nhỏ.
Mặt khác, datetime các giá trị “1900-01-01” và “1900-01-02” có thể được biểu thị bằng 8 byte dưới dạng 0x0000000100000000 và 0x0000000200000000 (bốn byte cho ngày và bốn byte cho dấu tích sau nửa đêm). Biểu diễn được phân đoạn này cung cấp một phạm vi nhị phân là 0x0100000000 (4,294,967,296) cho hai giá trị ví dụ đó, quá lớn để phù hợp với một bitmap đơn giản (thậm chí là một giá trị lớn). Các kiểu dữ liệu có biểu diễn nhị phân phức tạp (ví dụ:hoán đổi byte) thường sẽ không hoạt động tốt với các bitmap đơn giản.
Một điều phức tạp nữa là dữ liệu chế độ hàng loạt được chuẩn hóa - được chuyển đổi sang bố cục nhị phân hoạt động tốt với các lệnh được vector hóa - và luôn có kích thước 64 bit. Các giá trị không thể vừa với 64 bit được lưu trữ "ngoài hàng", với một con trỏ 64 bit trong hàng. Nhân tiện, bố cục nhị phân này không giống như được báo cáo bằng cách chuyển đổi T-SQL sang kiểu nhị phân.
Tuy nhiên, bố cục chuẩn hóa đủ tương tự cho các kiểu số nguyên (ví dụ:integer và bigint ) rằng các bitmap đơn giản vẫn hữu ích cho các phạm vi của các kiểu dữ liệu này. Các loại khác có biểu diễn nhị phân giống số nguyên (ví dụ:money và date ) cũng phù hợp.
Một ví dụ khác:Tập hợp integer các giá trị trong phạm vi từ 1 đến 8,388,608 sẽ chỉ vừa với một bitmap đơn giản nhỏ 1MB, sử dụng một bit cho mỗi giá trị số nguyên có thể có trong phạm vi. Phạm vi này có thể có độ chênh lệch cố định, do đó, phạm vi số nguyên từ 10.000.000 đến 18.388.607 cũng sẽ phù hợp (với mức bù là mười triệu). Lưu ý rằng số của các giá trị hiện tại không quan trọng, chỉ là phạm vi. Hai giá trị 0 và 8,388,607 sẽ lấp đầy dải bitmap đơn giản nhỏ cũng như tập hợp tất cả các giá trị có thể có giữa hai điểm cực trị đó.
Các bảng trong phạm vi
Khi công cụ thực thi chế độ hàng loạt quyết định xây dựng một đơn giản lớn bitmap hoặc phức tạp bitmap cho phép nối băm, nó cũng xây dựng một bảng phạm vi. Nó không xây dựng một bảng phạm vi cho nhỏ các bitmap đơn giản.
Bảng phạm vi là một cấu trúc 128KB có kích thước cố định được tạo thành từ 8.192 cặp giá trị 8 byte xác định một phạm vi giá trị (thấp, cao) có trong bảng băm. Một bảng phạm vi có thể được xây dựng trên bất kỳ kiểu dữ liệu nào tương thích với việc thực thi chế độ hàng loạt. Trong quá trình quét bảng băm đã hoàn thành, mỗi lô dữ liệu được sử dụng để điền vào bitmap và bảng phạm vi.
Đối với mỗi giá trị trong lô, một hàm băm được sử dụng để định vị một nhóm (cặp giá trị phạm vi) trong bảng phạm vi. Nếu nhóm hiện không được sử dụng, giá trị được lưu trữ ở cả giá trị 8 byte thấp và cao. Nếu thùng đã được sử dụng thì thay vào đó, thùng tiếp theo sẽ được lấp đầy (và cứ tiếp tục như vậy cho đến khi tìm được thùng rỗng).
Nếu bảng phạm vi trở nên đầy một phần ba (2.730 trong số 8.192 nhóm được sử dụng), các mục đã sử dụng sẽ được sao chép ra ngoài, phạm vi nhóm được tăng gấp đôi, khi đó các giá trị đã lưu được nhập lại theo cách giống như trước (mặc dù hàm băm tính đến kích thước thùng mới). Mọi nhóm chồng chéo đều được hợp nhất và quá trình nhân đôi tiếp tục cho đến khi số lượng nhóm đã sử dụng giảm xuống dưới 2.730. Ví dụ:hai nhóm ban đầu chứa ‘phạm vi’ (1-1) và (2-2) có thể hợp nhất thành một nhóm phạm vi (1-2) sau khi phạm vi đầu tiên nhân đôi.
Sau khi tất cả các lô dữ liệu bảng băm đã được xử lý vào bảng phạm vi, quá trình hợp nhất nhóm cuối cùng sẽ được thực hiện, sau đó, một nhanh chóng tại chỗ đặt các nhóm theo thứ tự giá trị. Điều này cho phép tìm kiếm nhị phân xác định một nhóm phạm vi được cung cấp một giá trị quan tâm cụ thể.
Kết quả thực của tất cả hoạt động này là tạo ra một tập hợp lên đến 2.730 phạm vi khác nhau mô tả dữ liệu trong bảng băm (ngoài bitmap lớn đơn giản hoặc phức tạp).
Sử dụng Bảng Phạm vi
Bảng phạm vi được sử dụng khi bộ lọc bitmap tham gia băm được đẩy xuống một toán tử quét cột cửa hàng thăm dò. Mỗi phân đoạn trong cột có siêu dữ liệu danh mục về các giá trị dữ liệu tối thiểu và tối đa có trong phân đoạn. Công cụ thực thi có thể sử dụng thông tin này để tìm kiếm nhị phân bảng phạm vi bitmap cho một kết quả phù hợp. Nếu không tìm thấy kết quả phù hợp nào, công cụ thực thi có thể bỏ qua hoàn toàn phân đoạn.
Việc tối ưu hóa thời gian chạy này cũng xảy ra đối với việc đọc trước, do đó, công cụ thậm chí có thể tránh đọc các phân đoạn vào bộ nhớ mà nó biết sẽ bị bộ lọc bảng phạm vi loại bỏ. Bất kỳ phân đoạn nào không bị loại bỏ bởi bảng phạm vi vẫn được lọc bằng cách sử dụng bitmap. Sự kết hợp này dẫn đến số lượng hàng tối đa bị loại bỏ càng sớm càng tốt.
Mặc dù một bảng phạm vi không được xây dựng cho một bitmap đơn giản nhỏ, nhưng cấu trúc đó cũng có thể được sử dụng để loại bỏ phân đoạn vì phạm vi giá trị đã biết (bao gồm bất kỳ độ lệch nào). Nó đủ nhỏ để không đáng để phân chia nó thành các phạm vi phụ bằng cách sử dụng bảng phạm vi.
Khi bitmap không được đẩy xuống quá trình quét tại kho hàng, nó vẫn có thể được đánh giá như một bộ lọc chế độ hàng loạt thông thường để đạt được mức giảm bán nối trước khi tham gia băm. Điều này kém hiệu quả hơn nhiều so với việc loại bỏ hoặc lọc phân đoạn trong quá trình quét tại kho hàng, nhưng nó vẫn tốt hơn so với việc lọc tại chính tham gia băm.
Bitmap và Dữ liệu Nén
Việc áp dụng bitmap chế độ tham gia băm vào dữ liệu cột như một phần của quá trình quét có thể tạo ra hiệu suất rất tốt, nhưng nó yêu cầu dữ liệu phân đoạn không tinh khiết phải được giải nén trước khi bitmap có thể được áp dụng. Việc giải nén này có thể được thực hiện một cách hiệu quả bằng cách sử dụng hướng dẫn của SIMD, nhưng nó vẫn còn phải làm việc thêm.
SQL Server 2016 đã giới thiệu khả năng tạo bitmap cho các vị từ chung trên dữ liệu phân đoạn được mã hóa từ điển. Vị từ được đánh giá dựa trên các mục từ điển để tạo ra một mới bitmap nhỏ với mỗi bit được thiết lập chỉ ra một mục từ điển thỏa mãn vị từ. Việc áp dụng bitmap này có thể cực kỳ nhanh chóng, đặc biệt nếu bitmap vừa với một thanh ghi SIMD. SQL Server vẫn có thể sử dụng SIMD nếu bitmap không phù hợp, nhưng việc thu thập bit từ bitmap trong bộ nhớ kém hiệu quả hơn một chút so với trường hợp trong thanh ghi.
Tối ưu hóa năm 2016 này có thể được áp dụng cho bất kỳ vị từ được đẩy vào quá trình quét trong kho lưu trữ, bao gồm một ‘vị từ’ bitmap được tạo bởi một phép nối băm ngược dòng. Nói một cách rõ ràng, SQL Server lấy bitmap tham gia băm và tạo một bitmap mới (nhỏ hơn nhiều) bằng cách sử dụng các mục từ điển. Bitmap mới này được áp dụng cho dữ liệu phân đoạn trước khi giải nén. Việc tối ưu hóa có thể được theo dõi bằng sự kiện mở rộng column_store_expression_filter_bitmap_set . Khi một bitmap từ điển được sử dụng, thành viên sự kiện filter_on_compressed_data_type thành viên sẽ được nhập. Thông thường, điều này sẽ chứa giá trị RAWBITMAP . Một tối ưu hóa khác tồn tại để chuyển đổi bitmap từ điển được nén thành bộ lọc so sánh nếu bitmap từ điển đại diện cho một phạm vi giá trị liền kề duy nhất. Trong trường hợp đó, bạn sẽ thấy thứ gì đó khác ngoài RAWBITMAP (ví dụ:LTGT để nhỏ hơn / lớn hơn so với so sánh).
Sự kiện Mở rộng và Cờ theo dõi
Khả năng tổng hợp để biên dịch các bộ lọc đẩy xuống (bao gồm cả bitmap được tạo bởi phép kết hợp băm ở chế độ hàng loạt) trong quá trình quét cột tại kho thành một bitmap có thể bị vô hiệu hóa với cờ theo dõi mức phiên 9361. Có thể tắt tối ưu hóa bitmap dữ liệu nén cụ thể với phiên cờ theo dõi cấp 9362. Việc chuyển đổi bitmap từ điển với một phạm vi liền kề duy nhất thành một bộ lọc so sánh có thể bị vô hiệu hóa với cờ theo dõi 9363. Đáng tiếc là không có cờ theo dõi xây dựng bán lẻ nào báo cáo thông báo thông tin về bitmap chế độ hàng loạt hoặc bộ lọc đẩy xuống biên dịch.
Có một vài sự kiện mở rộng tạo ra thông tin về bitmap chế độ tham gia băm. Những thứ hữu ích nhất là:
-
query_execution_column_store_segment_scan_started -
query_execution_column_store_segment_scan_finished -
column_store_expression_filter_bitmap_set -
column_store_segment_eliminate
Khi bitmap chế độ tham gia băm băm được đẩy xuống quá trình quét tại kho hàng, sự kiện “đã bắt đầu” báo cáo BITMAP_SIMPLE hoặc BITMAP_COMPLEX dưới dạng filter_type . Nó không phân biệt giữa các bitmap đơn giản nhỏ và lớn, cũng như không báo cáo bất cứ điều gì về bảng phạm vi. Siêu dữ liệu sự kiện mở rộng chứa các giá trị khác cho column_store_filter_type bao gồm BITMAP_SIMPLE_LARGE trong số những thứ khác, nhưng sự kiện mở rộng hiện không tạo ra kết quả này khi một bitmap đơn giản lớn được sử dụng. Có lẽ điều này sẽ được sửa chữa trong một bản phát hành trong tương lai.
Cờ theo dõi toàn cục 646 có thể được sử dụng để báo cáo thông tin về loại bỏ phân đoạn được kích hoạt bởi bảng phạm vi (hoặc một bitmap đơn giản nhỏ). Nó báo cáo thông tin tương tự cho phân đoạn loại bỏ sự kiện mở rộng. Tất cả các cờ theo dõi được đề cập trong phần này là không có tài liệu và không được hỗ trợ.
Kết luận
Ảnh bitmap ở chế độ hàng loạt có thể cực kỳ hiệu quả khi đúng loại dữ liệu (tối đa 64 bit và giống như số nguyên) được sử dụng và bitmap có thể được đẩy xuống quá trình quét cột tại kho, đặc biệt nếu dữ liệu phân đoạn sử dụng tính năng nén RLE (lưu trữ thuần túy) hoặc nếu bitmap có thể được biên dịch thành một bitmap khác trên dữ liệu từ điển.
Sẽ rất tốt nếu các kế hoạch thực thi báo cáo thông tin chi tiết hơn về bitmap tham gia băm - ít nhất là cho biết loại bitmap đã được tạo. Hiện tại, chúng tôi chỉ có Trình tạo bitmap tài sản và một số sự kiện mở rộng để làm việc. Điều này làm cho việc phân tích kế hoạch chi tiết khó hơn một chút so với bình thường, do hiệu suất đạt được rất lớn có thể đạt được bằng cách tận dụng tất cả các tối ưu hóa thông minh được tích hợp trong công cụ thực thi cho dữ liệu cột và tham gia băm chế độ hàng loạt.
Các bản trình diễn, hình ảnh minh họa và thảo luận thêm về những điểm chính được thảo luận trong bài viết này có sẵn trên trang web cá nhân của tôi tại Bản trình diễn Bitmap Chế độ Hàng loạt.
