हम तेजी से देख रहे हैं, और भी तेज

मुझे क्यूए सेक्शन में एक दिलचस्प सवाल आया। इसके उत्तर ने मुझे इस लेख को प्रश्न के अधिक पूर्ण उत्तर के रूप में लिखा "उदाहरण के लिए, यैंडेक्स बाजार में, कई मापदंडों का उपयोग करके खोज कैसे व्यवस्थित करें"।

मुझे पता है कि Habré पर, और वास्तव में noSQL समाधान के कई समर्थक हैं (यह पाप के बिना नहीं है), लेकिन फिर भी मैं पहले सोच का समर्थक हूं, और उसके बाद ही कोई समाधान चुनता हूं।

तो, हमारे पास DANO में क्या है?

• हमारे पास 120 चेकबॉक्स हैं - विकल्प 1/0
• हमारे पास "हां / नहीं / कोई बात नहीं" के विकल्प के साथ 30 "रेडियो" हैं
• किस धागे की कीमत सीमा / आकार इंगित करने के लिए हमारे पास 2-3 स्लाइडर्स हैं
• हमारे पास सबसे महत्वपूर्ण बात है: डेटाबेस में 12 मिलियन रिकॉर्ड।
• हमारे पास Select है * tovar से (wifi = true) और (led = false) और (type = 3) और .... अन्य पैरामीटर्स ...; ग्राहक उन्माद के करीब रनटाइम के साथ।

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

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

चेक बॉक्स

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

पर्वतमाला

किसी भी सीमा (ऊंचाई, वजन, कमर, बस्ट वॉल्यूम) को अंतराल और संख्या में विभाजित किया जा सकता है। 256 भागों में विभाजित करें। आंकड़ा "छत से लिया गया है।" किसी भी स्थिति में, हमें $ 100 - $ 1200 की सीमा के लिए 2 नंबर मिलेंगे। यदि आप अधिकतम $ 25,500 के साथ $ 1 - $ 100 लेते हैं, तो हम अपनी सीमा को 2 के रूप में लिख सकते हैं। 12 - वास्तव में यह एक 16 बिट संख्या है। हमारे पास इस तरह की संख्या संभव रेंज की संख्या से होगी। यदि उनमें से कुछ से कम हैं, तो हम यहां रुकेंगे, अगर उनमें से 100-10000 हैं, तो सब कुछ अधिक जटिल है। हम 200-20000 बिट कुंजी के लिए पर्याप्त रूप से जल्दी से खोज नहीं कर सकते हैं। हां, और हम नहीं कर रहे हैं, हम इसे केवल md5 की गणना करते हैं, और इस प्रक्रिया को तेज करने के लिए, हम सब कुछ 128 बिट संख्या (कुछ प्रकार की दयनीय 16 बाइट्स) में भी परिवर्तित करते हैं। कई "चेकबॉक्स" के संयोजन में हमें एक और भी सटीक चयन मिलता है।

हां / नहीं / महत्वपूर्ण नहीं

ऐड के साथ इन मूल्यों को खोजने के लिए एल्गोरिदम। पैरामीटर "महत्वपूर्ण नहीं" चेकबॉक्स के साथ विकल्प के लगभग समान है, सिवाय इसके कि हम केवल इंडेक्स (और 0, जब "महत्वपूर्ण नहीं" चुनते हैं) को केवल 1 / हां लिखते हैं। दूसरे इंडेक्स में हम "महत्वपूर्ण नहीं" विकल्प के साथ 0 और किसी अन्य के साथ 1 डालेंगे।

कुल हमें 2 इंडेक्स मिलते हैं:
1 सूचकांक: 01010000001010101010001
2 इंडेक्स: 0111110111011111101110111

होमवर्क Xor के माध्यम से बनाने के लिए होगा | और | या एक अनुरोध जिसमें हम सभी तुच्छ बिट्स को अनुक्रमणिका 2 पर रीसेट करेंगे और index1 के साथ तुलना करेंगे।

इसलिए, हमने 12 मिलियन रिकॉर्ड से 0-100-500 मिलान की स्थिति पाई। यह इन रिकॉर्ड्स को पहले से ही उनकी संपूर्णता (120-बिट चेकबॉक्स फ़ील्ड, रेंज, और कई हां / नहीं / महत्वपूर्ण नहीं) में जाँच की जानी चाहिए। इस बात से सहमत हैं कि सौ लाइनों के जोड़े के बीच एक पूर्ण जाँच एक पूर्ण खोज की तुलना में बहुत तेज़ है।

....

लाभ !!!

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

एक समान एल्गोरिथ्म का उपयोग हमारे द्वारा ग्रंथों के फिल्टर में शिंगल द्वारा किया जाता है, जब चेकसम से हमें 32 बिट्स मिलते हैं, जो 128 बिट्स की तुलना में तेज़ होते हैं।
इसी तरह की तकनीक एक विशेष दस्तावेज़ भंडारण प्रणाली में काम करती है, जो माइक्रोसेकंड को 2.2Gb पाठ डेटाबेस लिंक को उन दस्तावेज़ों में खोजने की अनुमति देती है जहां खोज शब्द या वाक्यांश स्थित है। लेकिन, इसके बारे में एक और लेख में।