Ước tính tham gia máy chủ SQL sử dụng Căn chỉnh thô biểu đồ

Các thay đổi chính được thực hiện đối với Ước tính số lượng bắt đầu từ bản phát hành SQL Server 2014 được mô tả trong Sách trắng của Microsoft Tối ưu hóa kế hoạch truy vấn của bạn với Công cụ ước tính số lượng mã số SQL Server 2014 của Joe Sack, Yi Fang và Vassilis Papadimos.

Một trong những thay đổi đó liên quan đến việc ước tính liên kết đơn giản với một vị từ bình đẳng hoặc bất bình đẳng duy nhất bằng cách sử dụng biểu đồ thống kê. Trong phần ở đầu, "Tham gia các thay đổi của thuật toán ước tính", bài báo đã giới thiệu khái niệm "liên kết thô" bằng cách sử dụng các ranh giới biểu đồ tối thiểu và tối đa:

Mặc dù có khả năng ít nhất quán hơn, nhưng CE cũ có thể tạo ra các ước tính điều kiện kết hợp đơn giản tốt hơn một chút do căn chỉnh biểu đồ từng bước. CE mới sử dụng một liên kết thô. Tuy nhiên, sự khác biệt về ước tính có thể đủ nhỏ để ít có khả năng gây ra vấn đề về chất lượng kế hoạch.

Là một trong những người đánh giá kỹ thuật của bài báo, tôi cảm thấy rằng một chút chi tiết xung quanh thay đổi này sẽ hữu ích, nhưng điều đó đã không được đưa vào phiên bản cuối cùng. Bài viết này bổ sung một số chi tiết đó.

Ví dụ về căn chỉnh biểu đồ thô

Căn chỉnh thô ví dụ trong Sách trắng sử dụng phiên bản Kho dữ liệu của cơ sở dữ liệu mẫu AdventureWorks. Mặc dù có tên, cơ sở dữ liệu khá nhỏ; bản sao lưu chỉ có 22,3MB và mở rộng lên khoảng 200MB. Nó có thể được tải xuống thông qua các liên kết trên trang tài liệu Cài đặt và Cấu hình AdventureWorks.

Truy vấn mà chúng tôi quan tâm sẽ kết hợp với FactResellerSales và FactCurrencyRate bảng.

SELECT
    FRS.ProductKey,
    FRS.OrderDateKey,
    FRS.DueDateKey,
    FRS.ShipDateKey,
    FCR.DateKey,
    FCR.AverageRate,
    FCR.EndOfDayRate,
    FCR.[Date]
FROM dbo.FactResellerSales AS FRS
JOIN dbo.FactCurrencyRate AS FCR
    ON FCR.CurrencyKey = FRS.CurrencyKey;

Đây là liên kết đơn giản trên một cột duy nhất vì vậy nó đủ điều kiện để tham gia ước tính độ chọn lọc và tính chọn lọc bằng cách sử dụng căn chỉnh thô biểu đồ.

Biểu đồ

Biểu đồ chúng ta cần được liên kết với CurrencyKey trên mỗi bảng đã tham gia. Trên bản sao mới của cơ sở dữ liệu AdventureWorksDW, thống kê đã có từ trước cho FactResellerSales lớn hơn bảng dựa trên một mẫu. Để tối đa hóa khả năng tái tạo và thực hiện các phép tính chi tiết đơn giản nhất có thể (tránh chia tỷ lệ), điều đầu tiên chúng tôi sẽ làm là làm mới thống kê bằng cách sử dụng quét toàn bộ:

UPDATE STATISTICS dbo.FactCurrencyRate WITH FULLSCAN;
UPDATE STATISTICS dbo.FactResellerSales WITH FULLSCAN;

Các bảng này có lợi ích thân thiện với bản demo là tạo maxdiff nhỏ và đơn giản biểu đồ:

DBCC SHOW_STATISTICS
    (FactResellerSales, CurrencyKey)
WITH HISTOGRAM;
 
DBCC SHOW_STATISTICS
    (FactCurrencyRate, [PK_FactCurrencyRate_CurrencyKey_DateKey])
WITH HISTOGRAM;

Kết hợp các bước biểu đồ đối sánh tối thiểu

Bước đầu tiên trong căn chỉnh thô tính toán là để tìm sự đóng góp vào số lượng liên kết được cung cấp bởi bước biểu đồ phù hợp thấp nhất. Đối với biểu đồ mẫu của chúng tôi, giá trị bước phù hợp tối thiểu là trên RANGE_HI_KEY = 6 :

Số lượng tương đương ước tính cho chỉ bước được đánh dấu này là 1,713 * 1,158 = 1,983,654 hàng .

Các bước Đối sánh Còn lại

Tiếp theo, chúng ta cần xác định phạm vi biểu đồ RANGE_HI_KEY bước lên đến mức tối đa cho các trận đấu tương đương có thể có. Điều này liên quan đến việc chuyển tiếp từ mức tối thiểu đã tìm thấy trước đó cho đến khi một trong các đầu vào biểu đồ hết hàng. Các phạm vi tương đương phù hợp cho ví dụ hiện tại được đánh dấu bên dưới:

Hai phạm vi này đại diện cho các hàng còn lại có thể được mong đợi sẽ đóng góp vào số lượng tương đương.

Ước tính dựa trên tần suất thô

Câu hỏi bây giờ là làm thế nào để thực hiện một thô ước tính mức độ cơ bản tương đương của các bước được đánh dấu, sử dụng thông tin có sẵn.

Công cụ ước tính số lượng ban đầu sẽ thực hiện căn chỉnh biểu đồ từng bước chi tiết bằng cách sử dụng nội suy tuyến tính, đánh giá đóng góp liên kết của mỗi bước (giống như chúng tôi đã làm đối với giá trị bước tối thiểu trước đây) và tổng hợp đóng góp của mỗi bước để thu được ước tính tham gia đầy đủ. Mặc dù quy trình này có nhiều ý nghĩa trực quan, nhưng kinh nghiệm thực tế là cách tiếp cận chi tiết này đã bổ sung chi phí tính toán và có thể tạo ra kết quả có chất lượng thay đổi.

Công cụ ước tính ban đầu có một cách khác để ước tính số lượng liên kết khi thông tin biểu đồ hoặc không có sẵn hoặc đánh giá theo kinh nghiệm là kém hơn. Đây được gọi là ước tính dựa trên tần suất và sử dụng các định nghĩa sau:

• C - số lượng (số hàng)
• D - số lượng các giá trị riêng biệt
• F - tần suất (số hàng) cho mỗi giá trị riêng biệt
• Lưu ý C =D * F theo định nghĩa

Ảnh hưởng của một phần tương đương của quan hệ R1 và R2 đối với mỗi thuộc tính này như được hiển thị bên dưới:

• F '=F1 * F2
• D '=MIN (D1; D2) - giả sử có chứa
• C '=D' * F '(một lần nữa, theo định nghĩa)

Chúng tôi đang theo đuổi C ', bản chất của tương đương. Thay thế cho D 'và F' trong công thức và mở rộng:

• C '=D' * F '
• C '=MIN (D1; D2) * F1 * F2
• C '=MIN (D1 * F1 * F2; D2 * F1 * F2)
• bây giờ, vì C1 =D1 * F1 và C2 =D2 * F2:
• C '=MIN (C1 * F2, C2 * F1)
• cuối cùng, vì F =C / D (cũng theo định nghĩa):
• C '=MIN (C1 * C2 / D2; C2 * C1 / D1)

Lưu ý rằng C1 * C2 là tích của hai thẻ số đầu vào (phép nối Descartes), rõ ràng là giá trị tối thiểu của các biểu thức đó sẽ là biểu thức có số lượng giá trị khác biệt cao hơn:

• C '=(C1 * C2) / MAX (D1; D2)

Trong trường hợp tất cả điều này có vẻ hơi trừu tượng, một cách trực quan để suy nghĩ về ước lượng tương đương dựa trên tần số là xem xét rằng mỗi giá trị khác biệt từ một quan hệ sẽ kết hợp với một số hàng (tần suất trung bình) trong quan hệ kia. Nếu chúng ta có 5 giá trị khác biệt ở một bên và mỗi giá trị khác biệt ở bên kia xuất hiện trung bình 3 lần, thì một ước tính tương đương hợp lý (nhưng thô) là 5 * 3 =15.

Đây không phải là một bàn chải rộng như nó có thể xuất hiện. Hãy nhớ rằng số lượng bản số và giá trị riêng biệt ở trên không đến từ toàn bộ mối quan hệ, mà chỉ từ các bước so khớp trên mức tối thiểu. Do đó, ước tính thô giữa các giá trị tối thiểu và tối đa.

Tính toán tần suất

Chúng tôi có thể nhận từng tham số này từ các bước biểu đồ được đánh dấu.

• Bản chất C là tổng của EQ_ROWS và RANGE_ROWS .
• Số lượng các giá trị khác biệt D là tổng của DISTINCT_RANGE_ROWS cộng một cho mỗi bước.

Cardinality C1 của kết hợp FactResellerSales số bước là tổng của các ô được đánh dấu:

Điều này cho ra C1 =59,142 hàng.

Không có hàng phạm vi phân biệt, vì vậy các giá trị khác biệt duy nhất đến từ chính ranh giới bốn bước, cho ra D1 =4 .

Đối với bảng thứ hai:

Điều này cho ra C2 =9,632 . Một lần nữa, không có hàng phạm vi phân biệt nào, vì vậy các giá trị khác biệt đến từ ranh giới mười bước, D2 =10.

Hoàn thành Ước tính Trang bị

Bây giờ chúng ta có tất cả các số chúng ta cần cho công thức tương đương:

• C '=(C1 * C2) / MAX (D1; D2)
• C '=(59142 * 9632) / MAX (4; 10)
• C '=569655744/10
• C '= 56.965.574,4

Hãy nhớ rằng, đây là phần đóng góp của các bước biểu đồ trên ranh giới phù hợp tối thiểu. Để hoàn thành ước tính số lượng kết hợp, chúng tôi cần thêm đóng góp từ các giá trị bước phù hợp tối thiểu, là 1,713 * 1,158 = 1,983,654 hàng.

Do đó, ước tính tương đương cuối cùng là 56.965.574,4 + 1.983.654 =58.949.228,4 hàng hoặc 58.949.200 đến sáu con số quan trọng.

Kết quả này được xác nhận trong kế hoạch thực thi ước tính cho truy vấn nguồn:

Như đã lưu ý trong Sách trắng, đây không phải là một ước tính lớn. Số hàng thực tế được trả về bởi truy vấn này là 70.470.090 . Ước tính được tạo ra bởi công cụ ước tính số lượng ban đầu ("kế thừa") - sử dụng căn chỉnh biểu đồ từng bước - là 70.470.100 hàng.

Các kết quả tốt hơn thường có thể có với phương pháp tốt hơn, nhưng chỉ khi các số liệu thống kê thể hiện rất tốt phân phối dữ liệu cơ bản. Đây không chỉ là vấn đề giữ cho số liệu thống kê được cập nhật, hoặc sử dụng toàn bộ dân số quét. Thuật toán được sử dụng để đóng gói thông tin thành tối đa 201 bước biểu đồ không hoàn hảo và trong mọi trường hợp, nhiều bản phân phối dữ liệu trong thế giới thực chỉ đơn giản là không có khả năng trung thực biểu đồ như vậy. Về trung bình, mọi người sẽ thấy rằng phương pháp thô hơn cung cấp các ước tính hoàn toàn phù hợp và độ ổn định cao hơn với CE mới.

Ví dụ thứ hai

Điều này xây dựng một chút dựa trên ví dụ trước và không yêu cầu tải xuống cơ sở dữ liệu mẫu.

DROP TABLE IF EXISTS
    dbo.R1,
    dbo.R2;
 
CREATE TABLE dbo.R1 (n integer NOT NULL);
CREATE TABLE dbo.R2 (n integer NOT NULL);
 
INSERT dbo.R1
    (n)
VALUES
    (1), (2), (3), (4), (5), (6), (7), (8), (9), (10),
    (6), (6), (6), (6), (6), (6), (6), (6), (6), (6), 
    (6), (6), (6), (6), (6), (6), (6), (6), (6);
 
INSERT dbo.R2
    (n)
VALUES
    (5), (6), (7), (8), (9), (10), (11), (12), (13), (14), (15),
    (10), (10);
 
CREATE STATISTICS stats_n ON dbo.R1 (n) WITH FULLSCAN;
CREATE STATISTICS stats_n ON dbo.R2 (n) WITH FULLSCAN;

Biểu đồ hiển thị các bước tối thiểu phù hợp là:

RANGE_HI_KEY thấp nhất kết quả phù hợp là 5. Giá trị của EQ_ROWS là 1 trong cả hai, do đó, số lượng tương đương ước tính là 1 * 1 = 1 hàng .

RANGE_HI_KEY phù hợp nhất là 10. Đánh dấu các hàng biểu đồ R1 để ước tính dựa trên tần số thô:

Tính tổng EQ_ROWS và RANGE_ROWS đưa ra C1 =24 . Số hàng riêng biệt là 2 DISTINCT_RANGE_ROWS (giá trị khác biệt giữa các bước) cộng với 3 cho các giá trị khác biệt được liên kết với ranh giới từng bước, cho ra D1 =5 .

Đối với R2, tính tổng EQ_ROWS và RANGE_ROWS đưa ra C2 =7 . Số hàng riêng biệt là 2 DISTINCT_RANGE_ROWS (giá trị khác biệt giữa các bước) cộng với 3 cho các giá trị khác biệt được liên kết với ranh giới từng bước, cho ra D2 =5 .

Ước lượng tương đương C 'là:

• C '=(C1 * C2) / MAX (D1; D2)
• C '=(24 * 7) / 5
• C '= 33,6

Thêm vào 1 hàng từ so khớp bước tối thiểu đưa ra ước tính tổng cộng là 34,6 hàng cho phần tương đương:

SELECT
    R1.n,
    R2.n
FROM dbo.R1 AS R1
JOIN dbo.R2 AS R2
    ON R2.n = R1.n;

Kế hoạch thực hiện ước tính cho thấy một ước tính phù hợp với tính toán của chúng tôi:

Điều này không chính xác, nhưng công cụ ước tính số lượng thẻ "kế thừa" không tốt hơn, ước tính 15,25 hàng so với 27 hàng thực tế:

Để xử lý hoàn chỉnh, chúng tôi cũng sẽ phải thêm đóng góp cuối cùng từ các bước rỗng của biểu đồ phù hợp, nhưng điều này không phổ biến đối với các phần tương đương (thường được viết để từ chối các giá trị rỗng) và một phần mở rộng tương đối đơn giản cho người đọc quan tâm.

Lời kết

Hy vọng rằng những chi tiết trong bài viết sẽ lấp đầy một vài khoảng trống cho những ai đã từng thắc mắc về "căn chỉnh thô". Lưu ý rằng đây chỉ là một thành phần nhỏ trong bộ ước lượng cardinality. Có một số khái niệm và thuật toán quan trọng khác được sử dụng để ước tính liên kết, đáng chú ý là cách đánh giá các vị từ không liên kết và cách xử lý các phép nối phức tạp hơn. Nhiều điều thực sự quan trọng được đề cập khá kỹ trong Sách trắng.