MySQL या PostgreSQL के लिए हैमिंग दूरी अनुकूलन?

Question

मैं MySQL डेटाबेस में phashed खोज समान छवियों को बेहतर बनाने की कोशिश कर रहा हूं। अभी मैं की तुलना pHash गिनती इस तरह आलोचनात्मक दूरी: का चयन (इंजन MyISAM)

• 20000 पंक्तियों के लिए

  SELECT * FROM images WHERE BIT_COUNT(hash^2028359052535108275) <= 4 
  

  परिणाम; क्वेरी समय < 20ms

• 100000 पंक्तियां; प्रश्न समय ~ 60ms # यह ठीक था, जब तक यह 150000 पंक्तियों तक पहुंच गया
• 300000 पंक्तियां; क्वेरी समय ~ 150ms

तो प्रश्न समय बढ़ाना तालिका में पंक्तियों की संख्या के आधार पर निर्भर करता है।

---

मैं भी stackoverflow पर पाया समाधान की कोशिश Hamming distance on binary strings in SQL

SELECT * FROM images WHERE 
BIT_COUNT(h1^11110011) + 
BIT_COUNT(h2^10110100) + 
BIT_COUNT(h3^11001001) + 
BIT_COUNT(h4^11010001) + 
BIT_COUNT(h5^00100011) + 
BIT_COUNT(h6^00010100) + 
BIT_COUNT(h7^00011111) + 
BIT_COUNT(h8^00001111) <= 4 

पंक्तियों 300000; क्वेरी समय ~ 240ms

---

मैंने डेटाबेस इंजन को PostgreSQL में बदल दिया। सफलता के बिना Translate this MySQL query to PyGreSQL । पंक्तियां 300000; क्वेरी समय ~ 18s

---

वहाँ प्रश्नों ऊपर अनुकूलन करने के लिए किसी भी समाधान है? मेरा मतलब ऑप्टिमाइज़ेशन पंक्तियों की संख्या से वंचित नहीं है।

मैं सीमित विधियों (उपकरण) इस समस्या को हल करने के लिए है। MySQL अब तक का सबसे आसान समाधान प्रतीत होता है लेकिन मैं प्रत्येक ओपन सोर्स डेटाबेस इंजन पर कोड तैनात कर सकता हूं जो रूबी के साथ समर्पित मशीन पर काम करेगा। एमएसएसक्यूएल https://stackoverflow.com/a/5930944/766217 (परीक्षण नहीं किया गया) के लिए कुछ तैयार समाधान हैं। हो सकता है कि किसी को यह पता चले कि MySQL या PostgreSQL के लिए इसका अनुवाद कैसे करें।

कृपया, कुछ कोड या अवलोकनों के आधार पर उत्तर पोस्ट करें। हम पर stackoverflow.com

धन्यवाद आलोचनात्मक अंतर के बारे में सैद्धांतिक मुद्दों का एक बहुत कुछ है!

Answer 1

जब एल्गोरिदम की दक्षता पर विचार, कंप्यूटर वैज्ञानिकों आदेश निरूपित किया जाता हे (कुछ) जहां कुछ n के एक समारोह है की अवधारणा का उपयोग, चीजों की संख्या इस मामले पंक्तियों में गणना की जा रहा है।इसलिए हम बढ़ती समय में मिलता है,:

• हे (1) - आइटम की संख्या की स्वतंत्र
• हे (लॉग (एन)) - वस्तुओं के लघुगणक के रूप में बढ़ जाती है
• हे (एन) -
• O (n^3) वस्तुओं के वर्ग के रूप में बढ़ जाती है - - आइटम के अनुपात में बढ़ जाती है (क्या है)
• O (n^2) आदि
• हे (2^n) - तेजी से बढ़ता है
• ओ (एन!) - वास्तव में बढ़ता है संख्या

अंतिम 2 प्रभावी रूप से एन (80+) की उचित संख्या के लिए असम्पीबल हैं।

केवल सबसे महत्वपूर्ण अवधि के मामलों के बाद से इस बड़े के लिए हावी n इसलिए n^2 और 65 * n^2 + 787 * n + 4,656,566 दोनों हे मन में (एन^2)

असर कर रहे हैं यह है कि एक गणितीय निर्माण और वास्तविक डेटा का उपयोग कर वास्तविक हार्डवेयर पर वास्तविक सॉफ़्टवेयर के साथ एक एल्गोरिदम लेता है, अन्य चीजों से काफी प्रभावित हो सकता है (उदाहरण के लिए ओ (एन^2) मेमोरी ऑपरेशन ओ (एन) डिस्क ऑपरेशन से कम समय ले सकता है)।

आपकी समस्या के लिए, आपको प्रत्येक पंक्ति के माध्यम से चलाने और BIT_COUNT(hash^2028359052535108275) <= 4 की गणना करने की आवश्यकता है। यह एक ओ (एन) ऑपरेशन है।

बी-पेड़ इंडेक्स पुनर्प्राप्ति एक ओ (लॉग (एन)) ऑपरेशन के बाद से एक सूचकांक का उपयोग करके इसे सुधारने का एकमात्र तरीका है।

हालांकि, क्योंकि आपका कॉलम फ़ील्ड किसी फ़ंक्शन के भीतर निहित है, उस कॉलम पर एक अनुक्रमणिका का उपयोग नहीं किया जा सकता है। आपके पास 2 संभावनाएं हैं:

1. यह एक SQL सर्वर समाधान है और मुझे नहीं पता कि यह MySQL के लिए पोर्टेबल है या नहीं। फॉर्मूला BIT_COUNT(hash^2028359052535108275) के साथ अपनी तालिका में एक सतत गणना कॉलम बनाएं और उस पर एक अनुक्रमणिका डालें। यह नहीं उपयुक्त होगा यदि आपको बिट मास्क बदलने की आवश्यकता है।
2. BIT_COUNT फ़ंक्शन का उपयोग किए बिना bitwise अंकगणित करने का एक तरीका बनाएं।

Answer 2

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

यह InnoDB है, और मेरे पास बहुत कम इंडेक्स हैं।

अगर कोई इसे तेज़ी से बना सकता है, तो मैं आपकी सराहना करूंगा।

SELECT *, BIT_COUNT(pHash3^42597524) + BC2 AS BC3 
FROM ( 
    SELECT *, BIT_COUNT(pHash2^258741369) + BC1 AS BC2 
    FROM ( 
     SELECT *, BIT_COUNT(pHash1^5678910) + BC0 AS BC1 
     FROM ( 
      SELECT `Key`, pHash0, pHash1, pHash2, pHash3, BIT_COUNT(pHash0^1234567) as BC0 
      FROM files 
      WHERE BIT_COUNT(pHash0^1234567) <= 3 
     ) AS BCQ0 
     WHERE BIT_COUNT(pHash1^5678910) + BC0 <= 3 
    ) AS BCQ1 
    WHERE BIT_COUNT(pHash2^258741369) + BC1 <= 3 
    ) AS BCQ2 
WHERE BIT_COUNT(pHash3^42597524) + BC2 <= 3 

यह समकक्ष क्वेरी है, लेकिन व्युत्पन्न तालिकाओं के बिना। इसका वापसी समय लगभग 3 गुना लंबा है।

SELECT `Key`, pHash0, pHash1, pHash2, pHash3 
FROM Files 
WHERE BIT_COUNT(pHash0^1234567) + BIT_COUNT(pHash1^5678910) + BIT_COUNT(pHash2^258741369) + BIT_COUNT(pHash3^42597524) <=3 

ध्यान में रखते हुए कि पहले के पहले हैम मूल्य कम है, तेज़ी से यह चल जाएगा।