हम अनस्पेक्टिंग ओपनसोर्स डीबीएमएस को स्थानिक सूचकांक को तेज करते हैं

मुझे हमेशा यह पसंद आया जब हेडलाइन स्पष्ट रूप से कहती है कि आगे क्या होगा, उदाहरण के लिए, "द टेक्सास चेन्सॉ नरसंहार।" इसलिए, कटौती के तहत, हम वास्तव में DBMS में एक स्थानिक खोज जोड़ देंगे, जिसमें यह मूल रूप से नहीं था।

पृष्ठभूमि
चलो स्थानिक खोज के महत्व और उपयोगिता के बारे में सामान्य शब्दों के बिना करने की कोशिश करते हैं।
यह पूछे जाने पर कि एक एकीकृत स्थानिक खोज के साथ एक खुला DBMS लेना क्यों संभव नहीं था, तो उत्तर होगा: "यदि आप कुछ अच्छा करना चाहते हैं, तो इसे स्वयं करें" (C)। लेकिन गंभीरता से, हम यह दिखाने की कोशिश करेंगे कि अधिकांश व्यावहारिक स्थानिक समस्याओं को ओवरवॉल्टेज और विशेष लागतों के बिना पूरी तरह से साधारण डेस्कटॉप पर हल किया जा सकता है।

एक प्रयोगात्मक DBMS के रूप में हम OpenLink Virtuoso के खुले संस्करण का उपयोग करेंगे। इसके सशुल्क संस्करण में, स्थानिक अनुक्रमण उपलब्ध है, लेकिन यह पूरी तरह से अलग कहानी है। क्यों वास्तव में यह DBMS? लेखक उसे पसंद करता है। तेज, आसान, शक्तिशाली। कॉपी-रन-सब कुछ काम करता है। हम केवल नियमित उपकरण, कोई सी-प्लग या विशेष असेंबलियों का उपयोग नहीं करेंगे, केवल आधिकारिक विधानसभा और पाठ संपादक।

सूचकांक प्रकार
हम एक पिक्सेल-कोड (ब्लॉक) इंडेक्स का उपयोग करके अंकों को सूचीबद्ध करेंगे।
पिक्सेल-कोड इंडेक्स क्या है? यह व्यापक वक्र का एक समझौता संस्करण है, जो आपको 2-आयामी खोज स्थान में गलत वस्तुओं के साथ काम करने की अनुमति देता है। इस कक्षा में सभी विधियों को मिलाएं:

• किसी तरह से खोज स्थान को ब्लॉकों में विभाजित करें
• सभी ब्लॉकों की संख्या है।
• प्रत्येक अनुक्रमित वस्तु को एक या अधिक ब्लॉक संख्या दी जाती है जिसमें वह स्थित है
• खोज करते समय, सीमा को ब्लॉकों में विभाजित किया जाता है, और प्रत्येक ब्लॉक या एक नियमित पूर्णांक सूचकांक (बी-ट्री) से ब्लॉकों की एक सतत श्रृंखला के लिए, उन सभी वस्तुओं को प्राप्त किया जाता है जो उनके हैं।

सबसे प्रसिद्ध विधियाँ हैं:

• सीमित सटीकता का अच्छा पुराना इग्लू (या अन्य व्यापक वक्र )। अंतरिक्ष को एक जाली से काटा जाता है, जिसका चरण (आमतौर पर) अनुक्रमित वस्तु का चारित्रिक आकार होता है। कोशिकाओं को X ... xY ... yZ ... z ... के रूप में गिना जाता है। मानदंडों के साथ सेल नंबर को gluing द्वारा।
• HEALPix । यह नाम पदानुक्रमित समान क्षेत्र iso-Latitude Pixelisation से आता है। यह विधि एक गोलाकार सतह को विभाजित करने के लिए डिज़ाइन की गई है ताकि इग्लू के मुख्य दोष से बचने के लिए - विभिन्न अक्षांशों पर कोशिकाओं के तहत विभिन्न क्षेत्रों। गोले को 12 समान क्षेत्रों में विभाजित किया गया है, जिनमें से प्रत्येक को आगे पदानुक्रम में 4 उप-वर्गों में विभाजित किया गया है। इस विधि के लिए चित्रण लेख के शीर्षक में है।
• पदानुक्रमित त्रिकोणीय जाल ( HTM )। यह क्रमिक रूप से त्रिभुज का उपयोग करते हुए एक गोले के पास पहुंचने की योजना है, जो 8 शुरुआती लोगों से शुरू होता है, जिनमें से प्रत्येक पदानुक्रम में 4 उप त्रिकोणों में विभाजित है।
• सबसे प्रसिद्ध ब्लॉक इंडेक्स योजनाओं में से एक जीआरआईडी है। स्थानिक डेटा को एक बहुआयामी सूचकांक के विशेष मामले के रूप में माना जाता है। इस मामले में:
  
  1. ग्रिल का उपयोग करके अंतरिक्ष को टुकड़ों में काट दिया जाता है
  2. परिणामी कोशिकाओं को किसी तरह से गिना जाता है
  3. एक विशिष्ट सेल में डेटा एक साथ संग्रहीत किया जाता है
  4. विशेषता मानों को "निर्देशिका" का उपयोग करके कुल्हाड़ियों के साथ सेल नंबर में अनुवादित किया जाता है, यह माना जाता है कि यह छोटा है और मेमोरी में संग्रहीत है
  5. यदि "निर्देशिका" बड़ी है, तो इसे स्तरों में विभाजित किया जाता है एक ला ट्री
  6. बदलते समय, जाली इसके विपरीत, कोशिकाओं या स्तंभों को विभाजित या विलय कर सकती है
  Z-ऑर्डर पर आधारित 3-स्तरीय GRID का उपयोग DB2 द्वारा किया जाता है, एक 4-स्तर GRID जो हिल्बर्ट वक्र के एक संस्करण के आधार पर MS SQLServer 2008 में उपयोग किया जाता है
  

सभी minuses के साथ, जिनमें से मुख्य एक, शायद, गैर-अनुकूलन क्षमता है, एक विशिष्ट कार्य के लिए सूचकांक को अनुकूलित करने की आवश्यकता है, ब्लॉक इंडेक्स में प्लसस हैं: सादगी और सर्वाहारी। संक्षेप में, यह एक साधारण पेड़ है जिसमें अतिरिक्त सिमेंटिक लोड होता है। जब हम इंडेक्सिंग करते हैं तो हम किसी भी तरह से ज्यामिति को अंकों में बदलते हैं और इसी तरह हमें इंडेक्स को खोजने के लिए कुंजी मिलती है।
इस पत्र में, हम इसकी सरलता के कारण एक क्षैतिज स्कैन (+1 ystein ) का उपयोग करेंगे: निर्देशांक को PL / SQL का उपयोग करके सस्ते में संख्याओं में परिवर्तित किया जा सकता है। सी-प्लग को शामिल किए बिना एचटीएम या हिल्बर्ट वक्र का उपयोग करना मुश्किल होगा।

डेटा प्रकार
डॉट्स क्यों? जैसा कि पहले ही उल्लेख किया गया है, ब्लॉक इंडेक्स इंडेक्सिंग के समान हैं। इसी समय, अंक के लिए रेखापुंज तुच्छ है, और बहुभुज के लिए इसे लिखना होगा, और यह विषय का खुलासा करने के लिए बिल्कुल महत्वपूर्ण नहीं है।

वास्तव में डेटा
आगे की हलचल के बिना,

• हम शुरुआत (0,0) और चरण 1 के साथ जाली 4000X4000 के नोड्स पर अंक डालते हैं।
• हमें 16 मिलियन अंकों का एक वर्ग मिलता है।
• 10X10 के लिए ब्लॉक इंडेक्स सेल लें,
• इसलिए हमारे पास प्रत्येक 100 अंक में 400x400 सेल हैं।

सूचकांक के लिए, इससे कोई फर्क नहीं पड़ता कि अंक सेल के अंदर कैसे स्थित हैं, लेकिन ऐसी नियमितता हमें परिणामों की शुद्धता को नियंत्रित करने की अनुमति देगी।

डेटा उत्पन्न करने के लिए, हम AWK पर इस तरह की स्क्रिप्ट का उपयोग करेंगे (इसे 'data.awk' होने दें):

BEGIN { cnt = 1; sz = 4000; # Set the checkpoint interval to 100 hours -- enough to complete most of experiments. print"checkpoint_interval (6000);"; print"SET AUTOCOMMIT MANUAL;"; for (i=0; i < sz; i++) { for (j=0; j < sz; j++) { print "insert into \"xxx\".\"YYY\".\"_POINTS\""; print " (\"oid_\",\"x_\", \"y_\") values ("cnt","i","j");"; cnt++; } print"commit work;" } print"checkpoint;" print"checkpoint_interval (60);"; exit; } 

सर्वर

• कंपनी की वेबसाइट से आधिकारिक बिल्ड लें।
  लेखक ने नवीनतम संस्करण 7.0.0 (x86_64) का उपयोग किया, लेकिन यह महत्वपूर्ण नहीं है, आप कोई अन्य ले सकते हैं।
• स्थापित करें, यदि नहीं, तो Microsoft Visual C ++ 2010 Redistributable Package (x64)
• हम प्रयोगों के लिए निर्देशिका का चयन करते हैं और संग्रह की 'डेटाबेस' से संग्रह 'बिन' और virtuoso.ini से libeay32.dll, ssleay32.dll, isql.exe, virtuoso-t.exe की प्रतिलिपि बनाते हैं।
• सर्वर को 'स्टार्ट पुण्योसो-t.exe + अग्रभूमि' का उपयोग करके शुरू करें, फ़ायरवॉल को पोर्ट खोलने की अनुमति दें
• हम 'isql localhost: 1111 dba dba' कमांड का उपयोग करके सर्वर उपलब्धता का परीक्षण करते हैं। एक कनेक्शन स्थापित करने के बाद, हम उदाहरण के लिए, परिचय देते हैं। '1 का चयन करें?' और सुनिश्चित करें कि सर्वर जीवित है।

डेटा स्कीमा
सबसे पहले, अंक तालिका बनाएं, अधिक कुछ नहीं:

 create user "YYY"; create table "xxx"."YYY"."_POINTS" ( "oid_" integer, "x_" double precision, "y_" double precision, primary key ("oid_") ); 

अब खुद सूचकांक:

 create table "xxx"."YYY"."_POINTS_spx" ( "node_" integer, "oid_" integer references "xxx"."YYY"."_POINTS", primary key ("node_", "oid_") ); 

जहाँ नोड_ स्पेस सेल का पहचानकर्ता है। ध्यान दें कि यद्यपि सूचकांक एक तालिका के रूप में बनाया गया है, दोनों फ़ील्ड प्राथमिक कुंजी में मौजूद हैं और इसलिए, एक पेड़ में पैक किए गए हैं।

अनुक्रमणिका विकल्प कॉन्फ़िगर करें:

 registry_set ('__spx_startx', '0'); registry_set ('__spx_starty', '0'); registry_set ('__spx_nx', '4000'); registry_set ('__spx_ny', '4000'); registry_set ('__spx_stepx', '10'); registry_set ('__spx_stepy', '10'); 

रजिस्ट्री_सेट सिस्टम फ़ंक्शन आपको सिस्टम रजिस्ट्री में स्ट्रिंग नाम / मूल्य जोड़े लिखने की अनुमति देता है - यह उन्हें सहायक तालिका में रखने की तुलना में बहुत तेज है और अभी भी लेनदेन द्वारा कवर किया गया है।

रिकॉर्डिंग ट्रिगर:

 create trigger "xxx_YYY__POINTS_insert_trigger" after insert on "xxx"."YYY"."_POINTS" referencing new as n { declare nx, ny integer; nx := atoi (registry_get ('__spx_nx')); declare startx, starty double precision; startx := atof (registry_get ('__spx_startx')); starty := atof (registry_get ('__spx_starty')); declare stepx, stepy double precision; stepx := atof (registry_get ('__spx_stepx')); stepy := atof (registry_get ('__spx_stepy')); declare sx, sy integer; sx := floor ((n.x_ - startx)/stepx); sy := floor ((n.y_ - starty)/stepy); declare ixf integer; ixf := (nx / stepx) * sy + sx; insert into "xxx"."YYY"."_POINTS_spx" ("oid_","node_") values (n.oid_,ixf); }; 

हम यह सब, उदाहरण के लिए, 'sch.sql' और के माध्यम से निष्पादित करते हैं

 isql.exe localhost:1111 dba dba <sch.sql 

डेटा लोड हो रहा है
योजना तैयार होने के बाद, आप डेटा भर सकते हैं।

 gawk -f data.awk | isql.exe localhost:1111 dba dba >log 2>errlog 

यह इंटेल i7-3612QM 2.1GHz पर 45 मिनट (~ 6000 प्रति सेकंड) 8 जीबी मेमोरी के साथ लेखक को ले गया।
इस सर्वर द्वारा कब्जा की गई मेमोरी का आकार लगभग 1 जीबी था, डिस्क पर डेटाबेस का आकार 540Mb था, अर्थात। ~ 34 बाइट्स प्रति बिंदु और इसके सूचकांक।
अब आपको यह सुनिश्चित करने की आवश्यकता है कि परिणाम सही है, isql में दर्ज करें

 select count(*) from "xxx"."YYY"."_POINTS"; select count(*) from "xxx"."YYY"."_POINTS_spx"; 

दोनों अनुरोधों को 16,000,000 जारी करना चाहिए।

एक गाइड के रूप में, आप यहां प्रकाशित डेटा का उपयोग कर सकते हैं :
।
वे PostgreSQL (Linux), 2.2GHz Xeon पर प्राप्त होते हैं।
एक ओर, डेटा 9 साल पहले प्राप्त किया गया था। दूसरी ओर, इस मामले में, डिस्क संचालन एक अड़चन है, और पिछली अवधि में डिस्क पर यादृच्छिक अभिगम बहुत तेजी से नहीं बढ़ा है।
और यहां हम जान सकते हैं कि वास्तविक डेटा भरने के समय के साथ स्थानिक अनुक्रमण का समय क्या है।
यह ध्यान दिया जाना चाहिए कि बाद के अनुक्रमण के साथ डेटा भरना (स्पष्ट कारणों के लिए) मक्खी पर अनुक्रमण की तुलना में बहुत तेज होता है। लेकिन हम मक्खी पर अनुक्रमण करने में अधिक रुचि रखते हैं क्योंकि व्यावहारिक उद्देश्यों के लिए, एक स्थानिक डीबीएमएस एक स्थानिक खोज इंजन की तुलना में अधिक दिलचस्प है।

और फिर भी, यह ध्यान दिया जाना चाहिए कि स्थानिक डेटा भरते समय, उनके भरने का क्रम बहुत महत्वपूर्ण है।
इस काम में और पूर्वोक्त बिंदु में दोनों खिला क्रम स्थानिक सूचकांक के संदर्भ में आदर्श (या इसके करीब) था। यदि आप डेटा मिलाते हैं, तो प्रदर्शन काफी नाटकीय रूप से गिर जाएगा, फिर चाहे आप जो भी डीबीएमएस चुनें।
यदि डेटा बेतरतीब ढंग से आता है, तो हम इसे सॉंप में जमा करने की सलाह दे सकते हैं, इसे छाँटते हुए इसे भागों में भर सकते हैं।

हम एक खोज स्थापित कर रहे हैं
ऐसा करने के लिए, हम प्रक्रियात्मक दृष्टिकोण के रूप में इस तरह के अद्भुत फीचर का उपयोग करेंगे।

 create procedure "xxx"."YYY"."_POINTS_spx_enum_items_in_box" ( in minx double precision, in miny double precision, in maxx double precision, in maxy double precision) { declare nx, ny integer; nx := atoi (registry_get ('__spx_nx')); ny := atoi (registry_get ('__spx_ny')); declare startx, starty double precision; startx := atof (registry_get ('__spx_startx')); starty := atof (registry_get ('__spx_starty')); declare stepx, stepy double precision; stepx := atof (registry_get ('__spx_stepx')); stepy := atof (registry_get ('__spx_stepy')); declare sx, sy, fx, fy integer; sx := floor ((minx - startx)/stepx); fx := floor (1 + (maxx - startx - 1)/stepx); sy := floor ((miny - starty)/stepy); fy := floor (1 + (maxy - starty - 1)/stepy); declare mulx, muly integer; mulx := nx / stepx; muly := ny / stepy; declare res any; res := dict_new (); declare cnt integer; for (declare iy integer, iy := sy; iy < fy; iy := iy + 1) { declare ixf, ixt integer; ixf := mulx * iy + sx; ixt := mulx * iy + fx; for select "node_", "oid_" from "xxx"."YYY"."_POINTS_spx" where "node_" >= ixf and "node_" < ixt do { dict_put (res, "oid_", 0); cnt := cnt + 1; } } declare arr any; arr := dict_list_keys (res, 1); gvector_digit_sort (arr, 1, 0, 1); result_names(sx); foreach (integer oid in arr) do { result (oid); } }; create procedure view "xxx"."YYY"."v_POINTS_spx_enum_items_in_box" as "xxx"."YYY"."_POINTS_spx_enum_items_in_box" (minx, miny, maxx, maxy) ("oid" integer); 

संक्षेप में, यह प्रक्रिया बहुत सरल है, यह पता लगाता है कि खोज सीमा में ब्लॉक की कौन सी कोशिकाएं खोज सीमा में आती हैं और इन कोशिकाओं की प्रत्येक पंक्ति के लिए एक उप-अनुरोध करता है, प्रविष्टियों के पहचानकर्ताओं को हैश मैप पर लिखता है, डुप्लिकेट को समाप्त करता है, और परिणामस्वरूप परिणामस्वरूप पहचानकर्ताओं का सेट देता है।
स्थानिक सूचकांक का उपयोग कैसे करें? उदाहरण के लिए, इस तरह:

 select count(*), avg(x.x_), avg(x.y_) from "xxx"."YYY"."_POINTS" as x, "xxx"."YYY"."v_POINTS_spx_enum_items_in_box" as a where a.minx = 91. and a.miny = 228. and a.maxx = 139. and a.maxy = 295. and x."oid_" = a.oid and x.x_ >= 91. and x.x_ < 139. and x.y_ >= 228. and x.y_ < 295.; 

यहां, अंकों की तालिका और पहचानकर्ताओं द्वारा प्रक्रियात्मक दृष्टिकोण से सिंथेटिक रिकॉर्ड के बीच एक जुड़ाव बनाया जाता है। यहां, प्रक्रियात्मक दृश्य एक मोटे फिल्टर के रूप में कार्य करता है जो सेल को सटीक बनाता है। इसलिए, अंतिम पंक्ति में हमने एक पतला फिल्टर लगाया।
अपेक्षित परिणाम:

• संख्या: (139 - 91) * (295 - 228) = 3216
• एक्स-औसत: (139 + 91 - 1) / 2 = 114.5 (-1 क्योंकि सही सीमा को बाहर रखा गया है)
• Y औसत: (295 + 228 - 1) / 2 = 261 (...)

इसलिए, एक ही लेन-देन के भीतर एक क्वेरी के साथ, हमने एक स्थानिक खोज की।

बेंचमार्क
अनुरोध प्रवाह तैयार करने के लिए, हम निम्नलिखित AWK स्क्रिप्ट का उपयोग करते हैं:

 BEGIN { srand(); for (i=0; i < 100; i++) { for (j=0; j < 100; j++) { startx = int(rand() * 3900); finx = int(startx + rand() * 100); starty = int(rand() * 3900); finy = int(starty + rand() * 100); print "select count(*), avg(x.x_), avg(x.y_) from"; print "\"xxx\".\"YYY\".\"_POINTS\" as x, " print "\"xxx\".\"YYY\".\"v_POINTS_spx_enum_items_in_box\" as a" print "where a.minx = "startx". and a.miny = "starty"." print " and a.maxx = "finx". and a.maxy = "finy". and" print "x.\"oid_\" = a.oid and x.x_ >= "startx". and x.x_ < "finx"." print " and x.y_ >= "starty". and x.y_ < "finy".;" } } exit; } 

जैसा कि आप देख सकते हैं, हमें यादृच्छिक आकार (0 ... 100) के यादृच्छिक स्थानों में 10,000 अनुरोध मिलते हैं। हम 4 ऐसे सेट तैयार करेंगे और तीन श्रृंखलाओं का प्रदर्शन करेंगे - एक इस्क्ल टेस्ट के साथ, 2 समानांतर और 4 समानांतर में। आठ-कोर प्रोसेसर पर, यह अधिक समांतर बनाने के लिए कोई मतलब नहीं है। प्रदर्शन को मापें।

• 1 धागा: 151 सेकंड = ~ 66 अनुरोध प्रति सेकंड प्रति थ्रेड
• 2 सूत्र: 159 सेकंड = ~ 63 ...
• 4 धागे: 182 सेकंड = ~ 55 ...

आप इन समयों की तुलना सेरेब्रोस्पाइनल ट्रैक्ट द्वारा प्राप्त दो साधारण सूचकांकों - x_ & y_ का उपयोग करके कर सकते हैं। हम इन क्षेत्रों द्वारा तालिका को अनुक्रमित करते हैं और प्रकार के प्रश्नों के साथ परीक्षणों की एक समान श्रृंखला चलाते हैं

 select count(*), avg(x.x_), avg(x.y_) from "xxx"."YYY"."_POINTS" as x where x.x_ >= 91. and x.x_ < 139. and x.y_ >= 228. and x.y_ < 295.; 

इसका परिणाम यह है: 10,000 प्रश्नों की एक श्रृंखला 417 सेकंड में पूरी होती है, हमारे पास प्रति सेकंड 24 प्रश्न हैं।

निष्कर्ष
प्रस्तुत विधि में कई कमियां हैं, जिनमें से मुख्य, जैसा कि पहले ही उल्लेख किया गया है, एक विशिष्ट कार्य के लिए इसे कॉन्फ़िगर करने की आवश्यकता है। इसका प्रदर्शन उन सेटिंग्स पर अत्यधिक निर्भर करता है जिन्हें इंडेक्स बनने के बाद बदला नहीं जा सकता। हालांकि, यह सामान्य रूप से अधिकांश स्थानिक सूचकांकों के लिए सही है।

लेकिन यहां तक ​​कि घुटने पर लिखे गए इस तरह के सूचकांक एक सभ्य प्रदर्शन देता है। इसके अलावा, चूंकि हम प्रक्रिया के पूर्ण नियंत्रण में हैं, इस आधार पर हम व्हिटर कॉम्प्लेक्स निर्माण कर सकते हैं, उदाहरण के लिए, मल्टी-टेबल इंडेक्स, जो नियमित तरीकों का उपयोग करके निर्माण करना मुश्किल है। लेकिन इसके बारे में अगली बार किसी तरह।