PostgreSQL से एडवांस्ड सर्च इंजन बनाना

 (xata.io)
6 पॉइंट द्वारा GN⁺ 2023-07-13 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • PostgreSQL का full-text search अलग search engine के बिना tsvector, tsquery, @@, ts_rank, GIN index को मिलाकर search feature बनाने का तरीका है
  • Search terms और documents को lexeme यूनिट में normalize किया जाता है, और AND·OR·NOT·FOLLOWED BY जैसे operators से query को व्यक्त कर सामान्य search syntax का बड़ा हिस्सा implement किया जा सकता है
  • GIN index ने example environment में search time को 200ms से अधिक से घटाकर लगभग 4ms कर दिया, लेकिन results बढ़ने पर ts_rank की ranking और sorting cost bottleneck बन सकती है
  • Relevance tuning को title weight, vote count, rating, genre, recency जैसे signals को sort expression में जोड़कर या setweight से column weights देकर implement किया जाता है
  • Typo tolerance, faceted search, autocomplete, exact phrase search, hybrid search भी संभव हैं, लेकिन PostgreSQL में components को खुद जोड़ना पड़ता है और बड़े datasets में performance limits जांचनी पड़ती हैं

PostgreSQL full-text search का approach

  • PostgreSQL full-text search के लिए low-level components देता है, जिन्हें मिलाकर search engine की functionality बनाई जा सकती है
  • यह तरीका flexible है, लेकिन जिनका मुख्य उपयोग full-text search है, ऐसे Elasticsearch, Typesense, Meilisearch की तुलना में इसमें ज्यादा implementation work चाहिए
  • Example queries Kaggle के Wikipedia Movie Plots dataset का उपयोग करती हैं
    • इसमें 34,000 movie titles शामिल हैं
    • CSV format का size लगभग 81MB है

मुख्य components

  • PostgreSQL full-text search मुख्य रूप से इन elements पर काम करता है
    • tsvector: search target text को normalized lexeme list के रूप में store करता है
    • tsquery: normalized search query को represent करता है
    • @@: यह check करने वाला match operator कि tsquery, tsvector से match होता है या नहीं
    • ts_rank, ts_rank_cd: search results का relevance score calculate करते हैं
    • GIN index: tsvector को efficiently query करने के लिए inverted index

tsvector और search configuration

  • tsvector sorted lexeme list store करता है
    • lexeme token जैसा होता है, लेकिन यह normalized string है ताकि एक ही word के अलग-अलग forms एक में align हो जाएं
    • English configuration में uppercase को lowercase में fold किया जाता है और suffix हटाकर normalize किया जाता है
  • to_tsvector से English sentence parse करने पर “I”, “to”, “an” जैसे stop words हट जाते हैं
    • “refuse” और “Refusing” दोनों refus में convert होते हैं
    • punctuation ignore होता है
    • original text में word positions और weights भी record होते हैं
  • english search configuration की जगह simple configuration इस्तेमाल करने पर words text में जिस form में मिले हैं, उसी तरह include होते हैं
    • “refuse” और “refusing” अलग lexeme के रूप में रह जाते हैं
    • simple configuration label या tag वाली columns के लिए खास तौर पर useful है
  • PostgreSQL कई languages के built-in search configurations देता है, लेकिन CJK (Chinese·Japanese·Korean) configuration नहीं है
    • unsupported languages के लिए simple configuration व्यावहारिक रूप से अच्छा काम कर सकता है
    • हालांकि CJK के लिए यह पर्याप्त है या नहीं, यह स्पष्ट नहीं है

tsquery और query expression

  • tsquery normalized search query को represent करने वाला data type है
    • Search terms पहले से normalized lexeme होने चाहिए
    • कई search terms को AND, OR, NOT, FOLLOWED BY operators से combine किया जा सकता है
  • to_tsquery, plainto_tsquery, websearch_to_tsquery user द्वारा input text को उपयुक्त tsquery में बदलने में मदद करते हैं
    • उनका core role input text में शामिल words को normalize करना है
  • websearch_to_tsquery इस्तेमाल करने पर general search box जैसी query बनाई जा सकती है
    • darth vader को logical AND की तरह process किया जाता है, जिसमें दोनों words document में होने चाहिए
    • OR search और word exclusion भी संभव है
    • Phrase search words के क्रम से लगातार आने वाले form को express करता है
  • English configuration में “the” जैसे stop words हट जाते हैं, इसलिए कुछ phrase searches में लगभग पूरा phrase गायब हो सकता है
    • ऐसे cases में simple configuration इस्तेमाल करने पर expected results मिल सकते हैं
  • @@ operator का उपयोग यह check करने के लिए किया जाता है कि tsquery, tsvector से match करता है या नहीं

GIN index और search performance

  • GIN का मतलब Generalized Inverted Index है, और यह complex values के अंदर शामिल element values खोजने वाली queries के लिए design किया गया index type है
  • GIN text search के अलावा JSON queries के लिए भी इस्तेमाल हो सकता है
  • Searchable कई columns को मिलाकर एक tsvector column बनाया जा सकता है, और उस column पर GIN index create किया जा सकता है
  • Example environment में GIN index ने search time को 200ms से अधिक से घटाकर लगभग 4ms कर दिया

Ranking और relevance calculation

  • अच्छी search experience के लिए results को relevance के आधार पर sort करना चाहिए
  • PostgreSQL दो predefined ranking functions देता है: ts_rank और ts_rank_cd
    • दोनों functions search term frequency को consider करते हैं
    • ts_rank_cd matching lexemes के बीच proximity को भी reflect करता है
  • Relevance application के nature पर बहुत depend करती है
    • Default ranking function starting point जैसा है, और जरूरत के अनुसार custom ranking function बनाया जा सकता है या उसे दूसरे factors के साथ combine किया जा सकता है
  • ts_rank को हर result की search column access करनी पड़ती है
    • अगर WHERE condition में बहुत सारी rows match होती हैं, तो PostgreSQL को ranking calculation और sorting के लिए उन सभी rows को visit करना पड़ता है
    • Example environment में एक query 5~7ms में return हुई, लेकिन darth OR vader जैसी query जिसमें 1,000 से ज्यादा results rank करने थे, उसमें लगभग 80ms लगे

Relevance tuning

  • Word frequency-based relevance अच्छा default है, लेकिन data में frequency से ज्यादा important signals हो सकते हैं
  • Movie dataset में relevance में ये signals reflect किए जा सकते हैं
    • Title में match हुए results को description या plot में match हुए results से ज्यादा important मानना
    • Rating या vote count के आधार पर ज्यादा popular movies को promote करना
    • अगर user comedy पसंद करता है, तो comedy movies को ऊपर रखना
    • पुराने titles की तुलना में latest titles को ज्यादा relevant मानना
  • Dedicated search engines अलग-अलग columns या fields को ranking पर असर डालने के लिए configure करने की capability देते हैं

Numbers, dates, exact values पर आधारित boosting

  • PostgreSQL दूसरे columns पर आधारित boosting सीधे provide नहीं करता, लेकिन ranking आखिरकार एक sort expression है, इसलिए custom signals जोड़े जा सकते हैं
  • Vote count reflect करने के लिए ranking score में vote count-based boost जोड़ने के तरीके से implement किया जा सकता है
    • Example में impact को gradual बनाने के लिए log का उपयोग किया गया
    • 0.01 coefficient से booster को ranking score जैसी scale पर align किया गया
  • Vote count एक निश्चित level पर होने पर ही rating को boost करने वाला अधिक complex function भी बनाया जा सकता है
  • अगर किसी खास genre को ऊपर लाना हो, तो valueBooster जैसा function इस्तेमाल किया जा सकता है जो value के किसी specific column value से match होने पर ही coefficient return करे

Column weights

  • tsvector के lexemes में weight लगाया जा सकता है
  • PostgreSQL A, B, C, D चार weights support करता है
    • A सबसे ज्यादा weight है
    • D सबसे कम और default value है
  • setweight function का उपयोग करके tsvector column बनाते समय weights control किए जा सकते हैं
  • Title column को higher weight देने पर, search term title में शामिल वाली movies results के top पर आती हैं और ranking score भी बढ़ता है
  • Weight classes सिर्फ चार हैं, यह limitation है, और weight tsvector calculate करते समय apply करना पड़ता है

Typo tolerance और fuzzy search

  • PostgreSQL tsvector और tsquery इस्तेमाल करते समय fuzzy search या typo tolerance सीधे support नहीं करता
  • Query side में typo होने की assumption के तहत इसे इन तरीकों से implement किया जा सकता है
    • Content से सभी lexemes को अलग table में index करना
    • Query के हर word के लिए similarity या Levenshtein distance से candidate words search करना
    • मिले हुए words शामिल करने के लिए query modify करना
    • Modified query से search execute करना
  • Example में search engines द्वारा fuzzy search में इस्तेमाल किए जाने वाले तरीके के कारण Levenshtein distance का उपयोग किया गया
  • Candidate word list मिलने के बाद query को इस तरह adjust करना होता है कि वे सभी words शामिल हों

Faceted search

  • Faceted search खासकर e-commerce sites में users को search scope को बार-बार narrow करने के लिए व्यापक रूप से इस्तेमाल होता है
  • PostgreSQL में categories को manually define करके और उन्हें search की WHERE condition में जोड़कर इसे implement किया जा सकता है
  • Existing data के आधार पर algorithmically categories बनाने का तरीका भी संभव है
    • Example में movie year के आधार पर “Decade” facet बनाया गया
    • हर decade के match count को भी calculate करके parentheses में दिखाया जा सकता है
  • कई facets को एक query में लाने के लिए CTEs combine किए जा सकते हैं
  • यह तरीका small-to-medium datasets में अच्छा काम कर सकता है, लेकिन बहुत बड़े datasets में धीमा हो सकता है

PostgreSQL search engine का scope और limitations

  • PostgreSQL के full-text search components को मिलाकर काफी advanced search engine बनाया जा सकता है
  • PostgreSQL-based search joins और ACID transactions भी साथ में support करता है
    • ये ऐसी capabilities हैं जो आम तौर पर दूसरे search engines में नहीं होतीं
  • आगे कवर किए जा सकने वाले advanced search topics ये हैं
    • Suggestions और autocomplete
    • Exact phrase matching
    • pg-vector के साथ combined hybrid search
  • ये features PostgreSQL से संभव हैं, लेकिन components को खुद combine करना पड़ता है
  • कुछ cases में बहुत बड़े datasets पर performance degrade हो सकती है
  • अगला लेख part 2 PostgreSQL में search implement करने और infrastructure में Elasticsearch जोड़कर data sync करने की तुलना करता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-07-13
Hacker News की रायें

  • इसे Elasticsearch की सुविधाओं की नकल करने वाले तरीके से करने की कोशिश नहीं करनी चाहिए
    2000 के दशक में मैंने MySQL 3.x से image EXIF data parse करके 3-स्तरीय classification system और counts को index करने वाला search engine बनाया था। यह ऐसा काम था जिसे कई महंगे vendors भी ठीक से नहीं कर पाए थे, और Autonomy तो top-level classification भी नहीं कर पाया था
    6 हफ्तों तक ऐसी नाजुक SQL लिखते हुए, जिसमें सिर्फ SELECT columns का order बदलने से भी performance बदल जाती थी, किसी तरह सफलता मिली, लेकिन मैं इसे दोबारा नहीं करना चाहूंगा। Databases मूल रूप से बड़े पैमाने पर समान हो सकते हैं, लेकिन search engines कहीं ज्यादा आगे बढ़ चुके हैं
    बौद्धिक जिज्ञासा के लिए इसे आजमाया जा सकता है, लेकिन search सिर्फ tokenize करके खत्म हो जाने वाली चीज नहीं है। जल्द ही faceted navigation, multilingual support, automatic synonyms, "Did you mean" spelling suggestions, large-scale performance जैसी जरूरतें आने लगेंगी और आप खुद को dead end में फंसा लेंगे। मानसिक स्वास्थ्य के लिए search engine इस्तेमाल करना बेहतर है, और PG और ES sync के लिए ZomboDB या PGSync जैसे tools भी हैं

    • इस thread में दो अलग-अलग चर्चाएं मिली हुई हैं। अगर आप customer-facing search engine बना रहे हैं, तो Elasticsearch जैसे मजबूत tool का उपयोग करके wheel को फिर से reinvent न करना सही है
      दूसरी तरफ, अगर data analysts या developers किसी बड़े database के text columns को LIKE/ILIKE से अधिक flexible तरीके से search करना चाहते हैं, तो उसी database के अंदर full-text search index/table बनाकर 90% तक पहुंचना ज्यादा आसान और तेज हो सकता है

  • भाग 2 में Postgres vs Elasticsearch तुलना का इंतजार है। हमारी कंपनी की एक application object CRUD के लिए PG और search के लिए Elastic इस्तेमाल करती है, लेकिन दो data stores को sync करने की मेहनत को हमने पूरी तरह कम आंका था, और अब सच में Elasticsearch हटाने पर विचार कर रहे हैं

    • पहले मैंने जो तरीका इस्तेमाल किया था वह था Elasticsearch को ऐसा target मानना जिसे कभी भी rebuild किया जा सके
      हर 5 मिनट में cron DB में ऐसे index-target objects ढूंढता था जिनका last_modified_at > last_indexing_started_timestamp हो, उन्हें Elasticsearch में index करता था, और फिर last_indexing_started_timestamp को sync शुरू होने के समय से update कर देता था। इस तरह run के शुरू और खत्म होने के बीच modify हुए objects अगले run में पकड़े जाते थे
      अगर Elasticsearch rebuild करना हो, तो last indexing time खाली करके शुरुआत से फिर sync कर दें; इससे self-healing संभव हो जाता है और sync drift नहीं होता
    • पिछली नौकरी में हमने similar setup इस्तेमाल किया था और यह खास मुश्किल नहीं था। जब भी PG की entity update होती, message भेजकर asynchronously ES में replicate करते थे, और ES side PG से ID द्वारा lookup करके data भरती थी
      async कामों में हमेशा की तरह monitoring और retries चाहिए होते हैं, लेकिन ES stable और तेज था, इसलिए दिक्कतें कम थीं। हालांकि consistency requirements ढीली थीं—PG की latest state reasonable time में ES तक पहुंच जाए तो काफी था—इसलिए requirements अलग हों तो बात अलग हो सकती है
    • हम भी Postgres को CRUD और Elastic को search के लिए इस्तेमाल करते हुए similar रास्ते पर गए, लेकिन दो stores के sync के अलावा सीमित manpower और experience के साथ stable Elastic cluster चलाने को भी कम आंका
      Postgres full-text search में indexes और query weights जोड़ने की तरफ shift करने के बाद, update triggers और बेहद तेज search queries के जरिए हमें जो चाहिए था वह सब Postgres के अंदर ही संभल गया
    • क्या आपने zombodb इस्तेमाल किया है? [https://www.zombodb.com/]
    • मैंने किया है; काफी experience होने के बावजूद यह मुश्किल काम था, और कुछ results तो और खराब भी थे। ज्यादातर similar थे और सिर्फ बहुत थोड़े बेहतर निकले
      कुल मिलाकर यह सफल रहा और operational burden बहुत घट गया, इसलिए लगाए गए engineering time की भरपाई अच्छी तरह हो गई, लेकिन इसे हल्के में शुरू करने वाला काम नहीं है
      जरूरत के हिसाब से materialized views, normal views, triggers बेहतर हो सकते हैं। Built-in text search शायद आपके use case में fit न बैठे, और alternative बनाना हमेशा बहुत मुश्किल हो ऐसा भी नहीं है

  • realistic load पर p50/p99 lookup time के बिना इसे साबित मानना मुश्किल है। जो search engine results लौटाने में 1 मिनट लेता है वह "advanced" नहीं है, और Postgres जैसे relational database में भी paper पर तो यह निश्चित रूप से संभव है

    • लेखक के तौर पर, Elasticsearch से तुलना करने वाला follow-up post plan में है, लेकिन शायद benchmark करने की कोशिश नहीं करूंगा। क्योंकि कोई भी realistic scenario बनाऊं, वह हर किसी के use case से बिल्कुल match नहीं करेगा
      मैं broadly सहमत हूं, और large scale पर—मसलन कुछ million records से ऊपर—शायद यह approach नहीं अपनाऊंगा। मुख्य रुचि यह थी कि features को कितना replicate किया जा सकता है
      छोटे search use cases में maintain करने के लिए कम infrastructure होता है, और strong consistency, joins जैसे फायदे मिलते हैं। Xata में हम छोटे scale पर Postgres इस्तेमाल करने और फिर minimal breaking changes के साथ Elasticsearch पर जाने वाले smooth transition पर भी विचार कर रहे हैं
    • जब मैंने एक पूर्व Google employee का interview लिया था, तो उन्होंने बताया कि वे पहले देखे गए search terms के सभी search results cache करते थे और index update करते समय cached results को भी साथ में update करते थे
      उस नजरिए से fast search results खुद में इतने चौंकाने वाले नहीं हैं। Background jobs से cached results लगातार update रखे जा सकते हैं और request आने पर उन्हें सीधे serve किया जा सकता है। ऐसी caching और response time actual search result calculation speed से अलग चीज लगती है
    • realistic load पर p50/p99 मांगने में समस्या है। जब बहुत से लोग असल में search नहीं कर रहे हों, तो search engine का वास्तविक real-world load कैसे बनाया जा सकता है? Random search terms से hit करना realistic नहीं है
      कुछ लोग slow connections इस्तेमाल करते हैं, और earthquake जैसे कुछ search terms किसी खास region में ही अचानक spike कर सकते हैं
      अगर search terms बहुत random हों, तो cache में results नहीं होंगे और performance actual से खराब दिखेगी; और अगर वे पर्याप्त random न हों, तो actual से बेहतर दिखेगी
    • Lucene, यानी Elasticsearch और Solr जिस foundation का इस्तेमाल करते हैं, वह inverted index है, और article का GIN भी वही तरीका इस्तेमाल करता है
      इसलिए ES आदि के फायदे कई nodes में horizontal scaling या main index के ऊपर रखी जाने वाली extra features में हैं
    • मैं Postgres full-text search इस्तेमाल कर रहा हूं और यह अच्छी तरह काम करता है। हालांकि query में rows की ranking कैसे करनी है, यह पता होना चाहिए
      सिर्फ ts_rank इस्तेमाल करें तो perfect है, लेकिन आम तौर पर आप ranking को दूसरे relevance metrics से adjust करना चाहेंगे। अगर आप यह limitation हल कर लें कि उस metric को primary ranking criterion नहीं बनाया जा सकता, तो results indexed normal DB table query जितने fast होते हैं

  • किशोर उम्र में, जब मुझे search engines और databases दोनों की अच्छी समझ नहीं थी, तब मैंने इन्हें शुरू से बनाकर देखा था। मैं देखना चाहता था कि मैं कितनी दूर जा सकता हूं, और कितनी तेजी से कितने relevant search results लौटा सकता हूं
    एक basic database और search engine जल्दी बनाना amateur programmers के लिए भी काफी आसान है। अगर आप basic computer science algorithms और operating system/hardware का उपयोग समझते हैं, तो एक-दो महीने में बना सकते हैं
    high-level language में भी speed खराब नहीं थी, और 2003 के laptop पर करीब 250K QPS मिल रहा था। sharding करने पर scalability भी कोई बड़ी समस्या नहीं है। storage और lookup से ज्यादा indexing, locking, consistency जटिल हैं
    असली बड़ी समस्या search की subjectivity है। जब सवाल यह हो कि लोग सच में क्या खोजना चाहते हैं, जब मुझे खुद नहीं पता कि मैं क्या खोज रहा हूं तो कैसे खोजूं, system का दुरुपयोग करने वालों को कैसे रोकूं, और complex queries व datasets को कैसे संभालूं—तब कठिनाई कई orders of magnitude बढ़ जाती है

    • 250K RPS काफी बड़ा लगता है, क्योंकि SQLite भी आज ऐसा नहीं कर पाता। inverted index शायद और महंगा होगा, और RocksDB भी करीब 130K RPS देता है—वह आंकड़ा भी शायद मेरे laptop से ज्यादा मजबूत hardware पर है, या मेरा environment गलत है
      जानना चाहूंगा कि क्या आपने सच में general-purpose database इस्तेमाल किया था और क्या वह आंकड़ा सही है। इन engines से आगे निकलने के लिए आपने कौन-सी techniques इस्तेमाल कीं?
    • search engine बनाते समय सबसे बड़ी समस्या QPS नहीं, बल्कि index किए जाने वाले dataset का size है। अगर search structure single machine की memory में फिट हो जाए, तो latency लगभग 0 के करीब होती है और practically infinite QPS दिया जा सकता है
      उससे बड़ा होते ही creative solutions चाहिए होते हैं, और वहीं से कई trade-offs सामने आते हैं
    • जानना चाहूंगा कि यह कहीं open source के रूप में उपलब्ध है या नहीं

  • Postgres के अंदर search करने में कई समस्याओं में से एक यह है कि search CPU-heavy काम है, और धीरे-धीरे GPU इस्तेमाल करने की दिशा में भी जा रहा है। आदर्श रूप से database का CPU core data model के transactional updates के लिए बचाकर रखना चाहेंगे
    मैंने कई बार देखा है कि ES और Solr clusters reindexing के दौरान 10+ nodes पर 100% पर चल रहे होते हैं, या सामान्य समय में भी 10+ nodes पर 30–50% CPU इस्तेमाल करते हैं। इसके मुकाबले database, उदाहरण के लिए AWS L/XL instance पर 50–100GB data और करीब 30% CPU usage वाला हो सकता है
    अगर search CPU को पूरा main DB में ले आएं, तो अब DB को shard करना पड़ेगा। फिर भी side projects में search, recursive joins, vectors आदि के लिए PG extensions मजेदार और सरल लगते हैं

    • क्या read-only replica पर search करके यह हल नहीं हो सकता?

  • मैंने पहले इसे असल में करके देखा था और काफी तेज बनाया था
    https://austingwalters.com/fast-full-text-search-in-postgres...
    मौजूदा website https://askhn.ai है

  • ऐसी techniques को pgvector के साथ जोड़ दें, तो embeddings से related content भी खोज सकते हैं। यह काफी जादू जैसा लगा

    • क्या आप इसे थोड़ा और detail में समझा सकते हैं या कोई reference material बता सकते हैं?
    • यह दिलचस्प है कि Vespa जैसी चीज इस्तेमाल कर सकने के बावजूद लोग ऐसे hacky रास्ते पर जाते हैं। performance, relevance, scalability और developer experience के लिहाज से मुझे लगता है Vespa कई orders of magnitude बेहतर है

  • वैसे यह "Dark" Vader नहीं, Darth Vader है। बचपन में मैं भी "Dark" समझता था

    • French जैसी कुछ translations में सच में Dark Vador है, इसलिए वह "गलती" आम हो गई
    • लेख में वह हिस्सा इतना खटका कि बाकी content पर ध्यान नहीं दे पाया। Yoda quote जानते हुए भी कोई अब तक Dark Vader कैसे कह सकता है?

  • बहुत अच्छा और स्पष्ट लेख है। SQLite भी standard plugin के रूप में advanced indexing features और stemming देता है
    English के लिए SQLite भी अच्छा काम करता है

    • SQLite के साथ किए गए experiments का material मिला
      https://github.com/daitangio/knowledge
      एक बार आजमाकर देखना चाहिए। काफी powerful है
    • सोच रहा हूं कि क्या FDW से भी यह किया जा सकता है। अगर सिर्फ search किए जाने वाले data को replicate करें, तो write workers ज्यादा नहीं होंगे, इसलिए medium-scale data पर यह अच्छा चल सकता है

  • लेख अच्छा है, लेकिन PostgreSQL fuzzy search support नहीं करता, यह हिस्सा आंशिक रूप से गलत है। pg_trgm extension और GIN trigram indexes इस लेख के examples जैसे fuzzy search use cases support करते हैं
    https://www.postgresonline.com/article_pfriendly/169.html
    query काफी तेज हो सकती है, लेकिन इसकी कीमत memory usage और updates के दौरान बढ़े हुए work time के रूप में चुकानी पड़ती है