Ban đầu tôi đã nghĩ về phép nối bên như trong các cách tiếp cận được đề xuất khác (ví dụ:truy vấn cuối cùng của Erwin Brandstetter, trong đó anh ấy sử dụng int8 đơn giản kiểu dữ liệu và các chỉ mục đơn giản), nhưng không muốn viết nó trong câu trả lời, vì tôi nghĩ rằng nó không thực sự hiệu quả. Khi bạn cố gắng tìm tất cả netblock phạm vi bao gồm phạm vi đã cho, một chỉ mục không giúp ích nhiều.
Tôi sẽ lặp lại truy vấn của Erwin Brandstetter ở đây:
SELECT * -- only select columns you need to make it faster
FROM routing_details r
, LATERAL (
SELECT *
FROM netblock_details n
WHERE n.ip_min <= r.ip_min
AND n.ip_max >= r.ip_max
ORDER BY n.ip_max - n.ip_min
LIMIT 1
) n;
Khi bạn có một chỉ mục trên netblock_details, như sau:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
bạn có thể nhanh chóng (trong O(logN) ) tìm điểm bắt đầu của quá trình quét trong netblock_details bảng - n.ip_min tối đa nhỏ hơn r.ip_min hoặc n.ip_max tối thiểu hơn r.ip_max . Nhưng sau đó, bạn phải quét / đọc phần còn lại của chỉ mục / bảng và đối với mỗi hàng, hãy thực hiện phần thứ hai của quá trình kiểm tra và lọc ra hầu hết các hàng.
Nói cách khác, chỉ mục này giúp tìm nhanh hàng bắt đầu đáp ứng tiêu chí tìm kiếm đầu tiên:n.ip_min <= r.ip_min , nhưng sau đó bạn sẽ tiếp tục đọc tất cả các hàng đáp ứng tiêu chí này và đối với mỗi hàng như vậy, hãy thực hiện kiểm tra thứ hai n.ip_max >= r.ip_max . Trung bình (nếu dữ liệu có phân phối đồng đều), bạn sẽ phải đọc một nửa số hàng của netblock_details bàn. Trình tối ưu hóa có thể chọn sử dụng chỉ mục để tìm kiếm n.ip_max >= r.ip_max đầu tiên và sau đó áp dụng bộ lọc thứ hai n.ip_min <= r.ip_min , nhưng bạn không thể sử dụng chỉ mục này để áp dụng cả hai bộ lọc cùng nhau.
Kết quả cuối cùng:cho mỗi hàng từ routing_details chúng tôi sẽ đọc qua một nửa số hàng từ netblock_details . 600K * 4M =2.400.000.000.000 hàng, tốt hơn gấp 2 lần so với sản phẩm Descartes. Bạn có thể thấy con số này (tích Đề-các) trong đầu ra của EXPLAIN ANALYZE trong câu hỏi.
592,496 * 8,221,675 = 4,871,309,550,800
Không có gì ngạc nhiên khi các truy vấn của bạn hết dung lượng ổ đĩa khi cố gắng hiện thực hóa và sắp xếp điều này.
Quy trình cấp cao tổng thể để đi đến kết quả cuối cùng:
-
tham gia hai bảng (mà vẫn chưa tìm được bảng phù hợp nhất). Trong trường hợp xấu nhất, nó là sản phẩm Descartes, trong trường hợp tốt nhất, nó bao gồm tất cả các phạm vi từ
netblock_detailscho mỗi phạm vi từrouting_details. Bạn cho biết rằng có nhiều mục nhập trongnetblock_detailscho mỗi mục nhập trongrouting_details, bất kỳ thứ gì từ 3 đến khoảng 10. Vì vậy, kết quả của phép nối này có thể có ~ 6 triệu hàng (không quá nhiều) -
sắp xếp / phân vùng kết quả của phép nối theo
routing_detailsphạm vi và đối với mỗi phạm vi như vậy, hãy tìm phạm vi bao phủ tốt nhất (nhỏ nhất) từnetblock_details.
Ý tưởng của tôi là đảo ngược truy vấn. Thay vì tìm tất cả các phạm vi bao phủ từ netblock_details lớn hơn cho mỗi hàng từ routing_details nhỏ hơn tôi đề xuất bảng để tìm tất cả các phạm vi nhỏ hơn từ routing_details nhỏ hơn cho mỗi hàng từ netblock_details lớn hơn .
Quy trình hai bước
Đối với mỗi hàng từ netblock_details lớn hơn tìm tất cả các phạm vi từ routing_details nằm trong netblock phạm vi.
Tôi sẽ sử dụng lược đồ sau trong các truy vấn. Tôi đã thêm khóa chính ID cho cả hai bảng.
CREATE TABLE routing_details (
ID int
,ip_min int8
,ip_max int8
,asn text
,netblock text
);
CREATE TABLE netblock_details (
ID int
,ip_min int8
,ip_max int8
,name text
,country text
,source text
);
SELECT
netblock_details.ID AS n_ID
,netblock_details.ip_max - netblock_details.ip_min AS n_length
,r.ID AS r_ID
FROM
netblock_details
INNER JOIN LATERAL
(
SELECT routing_details.ID
FROM routing_details
WHERE
routing_details.ip_min >= netblock_details.ip_min
AND routing_details.ip_min <= netblock_details.ip_max
-- note how routing_details.ip_min is limited from both sides
-- this would make it possible to scan only (hopefully) small
-- portion of the table instead of full or half table
AND routing_details.ip_max <= netblock_details.ip_max
-- this clause ensures that the whole routing range
-- is inside the netblock range
) AS r ON true
Chúng tôi cần chỉ mục trên routing_details trên (ip_min, ip_max) . Điều chính ở đây là lập chỉ mục trên ip_min . Có cột thứ hai trong chỉ mục giúp loại bỏ sự cần thiết phải thực hiện tra cứu giá trị của ip_max; nó không giúp ích gì trong việc tìm kiếm trên cây.
Lưu ý rằng truy vấn con bên không có LIMIT . Nó vẫn chưa phải là kết quả cuối cùng. Truy vấn này sẽ trả về ~ 6 triệu hàng. Lưu kết quả này vào một bảng tạm thời. Thêm chỉ mục vào bảng tạm thời trên (r_ID, n_length, n_ID) . n_ID một lần nữa chỉ để loại bỏ các tra cứu bổ sung. Chúng tôi cần một chỉ mục để tránh sắp xếp dữ liệu cho từng r_ID .
Bước cuối cùng
Đối với mỗi hàng từ routing_details tìm n_ID với n_length nhỏ nhất . Bây giờ chúng ta có thể sử dụng phép nối bên theo thứ tự "thích hợp". Đây temp bảng là kết quả của bước trước với chỉ mục .
SELECT
routing_details.*
,t.n_ID
,netblock_details.*
FROM
routing_details
INNER JOIN LATERAL
(
SELECT temp.n_ID
FROM temp
WHERE temp.r_ID = routing_details.ID
ORDER BY temp.n_length
LIMIT 1
) AS t ON true
INNER JOIN netblock_details ON netblock_details.ID = t.n_ID
Ở đây truy vấn con phải là một tìm kiếm của chỉ mục, không phải quét. Trình tối ưu hóa phải đủ thông minh để chỉ thực hiện tìm kiếm và trả về kết quả tìm thấy đầu tiên vì LIMIT 1 , vì vậy bạn sẽ có 600 nghìn lượt tìm kiếm chỉ mục trong bảng tạm thời 6 triệu hàng.
Câu trả lời ban đầu (tôi sẽ giữ nó chỉ cho sơ đồ các phạm vi):
Bạn có thể "gian lận" không?
Nếu tôi hiểu đúng truy vấn của bạn, cho mỗi routing_details.range bạn muốn tìm netblock_details.range nhỏ nhất bao trùm / lớn hơn routing_details.range .
Cho ví dụ sau, trong đó r là phạm vi định tuyến và n1, ..., n8 là phạm vi netblock, câu trả lời đúng là n5 .
|---|
n1
|------------------|
n2
|---------------|
n3
|-----|
n4
|------------------|
n5
|--------------------------------------|
n6
|---------------------------|
n7
|-----|
n8
|------------|
r
start end
n.start <= r.start AND n.end >= r.end
order by n.length
limit 1
truy vấn của bạn mất 14 giờ cho thấy quá trình quét chỉ mục mất 6 mili giây, nhưng sắp xếp theo độ dài phạm vi mất 80 mili giây.
Với kiểu tìm kiếm này, không có thứ tự 1D đơn giản của dữ liệu. Bạn đang sử dụng n.start cùng với n.end và cùng với n.length . Tuy nhiên, có thể dữ liệu của bạn không chung chung như vậy hoặc bạn có thể trả về một kết quả hơi khác.
Ví dụ:nếu trả về n6 là OK do đó, nó có thể hoạt động nhanh hơn nhiều. n6 là phạm vi bao phủ có start lớn nhất :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
Hoặc, bạn có thể sử dụng n7 , có end nhỏ nhất :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
Loại tìm kiếm này sẽ sử dụng chỉ mục đơn giản trên n.start (hoặc n.end ) mà không cần phân loại thêm.
Một cách tiếp cận thứ hai, hoàn toàn khác. Phạm vi lớn / dài bao nhiêu? Nếu chúng tương đối ngắn (ít số), thì bạn có thể cố gắng lưu trữ chúng dưới dạng danh sách các số nguyên rõ ràng, thay vì một dải ô. Ví dụ:dải ô [5-8] sẽ được lưu trữ dưới dạng 4 hàng:(5, 6, 7, 8) . Với mô hình lưu trữ này, có thể dễ dàng hơn trong việc tìm các giao điểm của các dải.
