मैं मूल रूप से अन्य सुझाए गए दृष्टिकोणों के रूप में पार्श्व में शामिल होने के बारे में सोच रहा था (उदाहरण के लिए, इरविन ब्रैंडस्टेटर द्वारा अंतिम क्वेरी, जहां वह सरल int8 का उपयोग करता है। डेटाटाइप और सरल अनुक्रमणिका), लेकिन इसे उत्तर में लिखना नहीं चाहता था, क्योंकि मैंने सोचा था कि यह वास्तव में कुशल नहीं है। जब आप सभी netblock . को खोजने का प्रयास करते हैं वे श्रेणियां जो दी गई सीमा को कवर करती हैं, एक इंडेक्स ज्यादा मदद नहीं करता है।
मैं यहां इरविन ब्रैंडस्टेटर की क्वेरी दोहराऊंगा:
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;
जब आपके पास netblock_details पर एक इंडेक्स है, तो इस तरह:
CREATE INDEX netblock_details_ip_min_max_idx ON netblock_details
(ip_min, ip_max DESC NULLS LAST);
आप जल्दी कर सकते हैं (O(logN) . में) ) स्कैन के शुरुआती बिंदु को netblock_details . में ढूंढें तालिका - या तो अधिकतम n.ip_min जो r.ip_min . से कम है , या न्यूनतम n.ip_max जो r.ip_max . से अधिक है . लेकिन फिर आपको शेष अनुक्रमणिका/तालिका को स्कैन/पढ़ना होगा और प्रत्येक पंक्ति के लिए चेक का दूसरा भाग करना होगा और अधिकांश पंक्तियों को फ़िल्टर करना होगा।
दूसरे शब्दों में, यह इंडेक्स पहली खोज मानदंड को पूरा करने वाली शुरुआती पंक्ति को जल्दी से ढूंढने में मदद करता है:n.ip_min <= r.ip_min , लेकिन फिर आप उन सभी पंक्तियों को पढ़ना जारी रखेंगे जो इस मानदंड को पूरा करती हैं और ऐसी प्रत्येक पंक्ति के लिए दूसरी जाँच करें n.ip_max >= r.ip_max . औसतन (यदि डेटा का वितरण समान है) तो आपको netblock_details की आधी पंक्तियों को पढ़ना होगा मेज़। ऑप्टिमाइज़र n.ip_max >= r.ip_max खोजने के लिए अनुक्रमणिका का उपयोग करना चुन सकता है पहले और फिर दूसरा फ़िल्टर लागू करें n.ip_min <= r.ip_min , लेकिन आप दोनों फ़िल्टर एक साथ लागू करने के लिए इस अनुक्रमणिका का उपयोग नहीं कर सकते हैं।
अंतिम परिणाम:प्रत्येक पंक्ति के लिए routing_details . से हम netblock_details . से आधी पंक्तियों को पढ़ेंगे . 600K * 4M =2,400,000,000,000 पंक्तियाँ। यह कार्टेशियन उत्पाद से 2 गुना बेहतर है। आप इस नंबर (कार्टेशियन उत्पाद) को EXPLAIN ANALYZE के आउटपुट में देख सकते हैं प्रश्न में।
592,496 * 8,221,675 = 4,871,309,550,800
कोई आश्चर्य नहीं कि इसे अमल में लाने और क्रमबद्ध करने का प्रयास करते समय आपके प्रश्नों का डिस्क स्थान समाप्त हो जाता है।
अंतिम परिणाम प्राप्त करने के लिए समग्र उच्च स्तरीय प्रक्रिया:
-
दो तालिकाओं में शामिल हों (अभी तक का सबसे अच्छा मैच खोजे बिना)। सबसे खराब स्थिति में यह कार्टेशियन उत्पाद है, सबसे अच्छी स्थिति में यह
netblock_detailsसे लेकर सभी श्रेणियों को कवर करता हैrouting_details. से प्रत्येक श्रेणी के लिए . आपने कहा था किnetblock_details. में कई प्रविष्टियां हैंrouting_details. में प्रत्येक प्रविष्टि के लिए , 3 से लेकर लगभग 10 तक कुछ भी। इसलिए, इस जुड़ाव के परिणाम में ~6M पंक्तियाँ हो सकती हैं (बहुत अधिक नहीं) -
routing_details. द्वारा शामिल होने का परिणाम ऑर्डर/विभाजन करें श्रेणी और ऐसी प्रत्येक श्रेणी के लिएnetblock_detailsसे सर्वोत्तम (सबसे छोटी) कवरिंग श्रेणी खोजें ।
मेरा विचार क्वेरी को उलटना है। बड़े netblock_details . से सभी कवरिंग रेंज ढूंढने के बजाय प्रत्येक पंक्ति के लिए छोटे routing_details . से तालिका मैं छोटे routing_details . से सभी छोटी श्रेणियों को खोजने का सुझाव देता हूं प्रत्येक पंक्ति के लिए बड़े netblock_details . से ।
दो चरणों वाली प्रक्रिया
प्रत्येक पंक्ति के लिए बड़े netblock_details . से routing_details . से सभी श्रेणियां ढूंढें जो netblock . के अंदर हैं रेंज।
मैं प्रश्नों में निम्नलिखित स्कीमा का उपयोग करूंगा। मैंने प्राथमिक कुंजी जोड़ दी है ID दोनों टेबल पर।
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
हमें routing_details . पर अनुक्रमणिका चाहिए पर (ip_min, ip_max) . यहां मुख्य बात ip_min . पर अनुक्रमणिका है . इंडेक्स में दूसरा कॉलम होने से ip_max के मान के लिए लुकअप करने की आवश्यकता को समाप्त करने में मदद मिलती है; यह पेड़ की खोज में मदद नहीं करता है।
ध्यान दें कि लेटरल सबक्वेरी में LIMIT नहीं है . यह अभी अंतिम परिणाम नहीं है। यह क्वेरी ~ 6M पंक्तियों को वापस करनी चाहिए। इस परिणाम को अस्थायी तालिका में सहेजें। (r_ID, n_length, n_ID) पर अस्थायी तालिका में एक अनुक्रमणिका जोड़ें . n_ID अतिरिक्त लुकअप को हटाने के लिए फिर से है। हमें प्रत्येक r_ID . के लिए डेटा सॉर्ट करने से बचने के लिए एक इंडेक्स की आवश्यकता है ।
अंतिम चरण
routing_details . से प्रत्येक पंक्ति के लिए n_ID ढूंढें सबसे छोटी n_length . के साथ . अब हम पार्श्व जोड़ का उपयोग "उचित" क्रम में कर सकते हैं। यहां temp तालिका पिछले चरण सूचकांक के साथ . का परिणाम है ।
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
यहां सबक्वायरी इंडेक्स की तलाश होनी चाहिए, स्कैन नहीं। ऑप्टिमाइज़र इतना स्मार्ट होना चाहिए कि वह केवल खोज कर सके और LIMIT 1 के कारण पहला परिणाम प्राप्त कर सके। , तो आपके पास 6M पंक्ति अस्थायी तालिका में 600K अनुक्रमणिका की तलाश होगी।
मूल उत्तर (मैं इसे केवल श्रेणियों के आरेख के लिए रखूंगा):
क्या आप "धोखा" दे सकते हैं?
अगर मैं आपकी क्वेरी को सही ढंग से समझ पाया, तो प्रत्येक routing_details.range . के लिए आप सबसे छोटा netblock_details.range find खोजना चाहते हैं जो routing_details.range . को कवर करता/करती है ।
निम्नलिखित उदाहरण को देखते हुए, जहां r रूटिंग रेंज है और n1, ..., n8 नेटब्लॉक रेंज हैं, इसका सही उत्तर है 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
आपकी क्वेरी जिसमें 14 घंटे लगे दिखाता है कि इंडेक्स स्कैन में 6ms लगे, लेकिन रेंज की लंबाई के अनुसार सॉर्ट करने में 80ms का समय लगा।
इस प्रकार की खोज के साथ डेटा का कोई सरल 1D क्रम नहीं है। आप n.start . का उपयोग कर रहे हैं साथ में n.end और साथ में n.length . लेकिन, हो सकता है कि आपका डेटा उतना सामान्य नहीं है, या कुछ अलग परिणाम देना ठीक है।
उदाहरण के लिए, अगर n6 return को वापस करना ठीक था नतीजतन, यह बहुत तेजी से काम कर सकता है। n6 कवरिंग रेंज है जिसमें सबसे बड़ा start है :
n.start <= r.start AND n.end >= r.end
order by n.start desc
limit 1
या, आप n7 . के लिए जा सकते हैं , जिसका सबसे छोटा end है :
n.start <= r.start AND n.end >= r.end
order by n.end
limit 1
इस प्रकार की खोज n.start . पर सरल अनुक्रमणिका का उपयोग करेगी (या n.end ) अतिरिक्त छँटाई के बिना।
एक दूसरा, पूरी तरह से अलग दृष्टिकोण। पर्वतमाला कितनी बड़ी/लंबी हैं? यदि वे अपेक्षाकृत कम (कुछ संख्याएं) हैं, तो आप उन्हें एक श्रेणी के बजाय पूर्णांकों की एक स्पष्ट सूची के रूप में संग्रहीत करने का प्रयास कर सकते हैं। उदाहरण के लिए, श्रेणी [5-8] 4 पंक्तियों के रूप में संग्रहीत किया जाएगा:(5, 6, 7, 8) . इस भंडारण मॉडल के साथ श्रेणियों के प्रतिच्छेदन को खोजना आसान हो सकता है।
