कोड सर्च इतना कठिन क्यों है

 (blog.val.town)
1 पॉइंट द्वारा GN⁺ 2024-04-12 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Val Town सर्च Postgres ILIKE आधारित substring search है, इसलिए ranking लगभग नहीं के बराबर है, और multi-word queries भी कमजोर हैं, इसलिए सुधार की मांग बहुत है
  • natural language search के stopword removal, stemming, lemmatization जैसे नियम कोड के variable names, function names और token boundaries को बिगाड़ सकते हैं
  • Postgres Full Text Search इन्फ्रास्ट्रक्चर को सरल रख सकता है, लेकिन पिछले प्रोजेक्ट्स में scalability समस्याएँ थीं, और Val Town भी single-node Postgres की सीमाओं को परख रहा है
  • soft launch किया गया v2 search pg_trgrm आधारित trigram search का उपयोग करता है, लेकिन regex search के विपरीत free-form queries की ranking को मनचाहे स्तर तक लाना कठिन है
  • Elasticsearch, Meilisearch, Zoekt, ParadeDB जैसे विकल्प मौजूद हैं, लेकिन अलग इन्फ्रास्ट्रक्चर, operations का बोझ, और hosting support की उपलब्धता अभी भी चयन की सीमाएँ हैं

Val Town सर्च जहाँ अटक गया

  • Val Town search अभी Postgres के ILIKE का उपयोग करता है
    • यह substring search तरीका है, जिसमें अगर search term कोड के अंदर शामिल हो तो वह result में दिखाई देता है
    • ranking लगभग नहीं है, और multi-word queries का सही समर्थन नहीं है
  • बेहतर search, Val Town में सबसे अधिक माँगी गई सुविधाओं में से एक है
  • सुधार का काम चल रहा है, लेकिन अभी तक requirements के मुताबिक समाधान नहीं मिला है
  • अब तक सामने आए constraints ये हैं
    • मुख्यधारा के search solutions natural language के लिए डिज़ाइन किए गए हैं
    • जिन बड़ी कंपनियों को code search चाहिए, वे अपने search systems में बहुत समय और पैसा लगाती हैं
    • Val Town के पास पहले से बहुत data है, इसलिए ऐसा समाधान चाहिए जो अच्छी तरह scale करे
    • database को scale करने के बजाय अलग search service का उपयोग करने पर infra और complexity के बीच trade-off महत्वपूर्ण हो जाता है

natural language search के नियम कोड पर क्यों फिट नहीं बैठते

  • सामान्य full-text search (FTS) settings डिफ़ॉल्ट रूप से English जैसी natural language के लिए algorithms देती हैं
    • stopword removal: “the”, “it” जैसे बहुत सामान्य शब्दों को indexing से पहले हटा दिया जाता है
    • stemming: “running” को “run” में बदल दिया जाता है, ताकि “runs” खोजने पर भी मिल सके
    • lemmatization: “excellent” खोजने पर “great” वाला document भी मिल सके, इसके लिए synonyms को अधिक सामान्य शब्द से बदला जा सकता है
  • वही नियम कोड पर लागू करने से अर्थ बिगड़ जाता है
    • TypeScript में the stopword नहीं, बल्कि खोजने लायक valid variable name हो सकता है
    • कोड में word boundaries, natural language से अलग होती हैं
    • function names पर stemming लगाने से meaningful results की उम्मीद करना कठिन है
  • Postgres to_tsvector('english', ...) natural language वाक्यों को index करते समय मूल पाठ को काफी बदल देता है
    • I am writing this example sentence बदलकर 'exampl':5 'sentenc':6 'write':3 जैसा हो जाता है
  • कोड में tokenization की समस्या और ज़्यादा स्पष्ट होती है
    • function stringifyNumber(a: number): string { return a.toString() } को 'a.tostring':7 'function':1 'number':4 'return':6 'string':5 'stringifynumb':2 की तरह index किया जाता है
    • function जैसे शब्द बचे रहते हैं, लेकिन a.toString() में . डिफ़ॉल्ट word boundary नहीं है, इसलिए यह दो tokens में नहीं बंटता

Postgres Full Text Search के फायदे और सीमाएँ

  • Postgres Full Text Search extension देता है, और Val Town के hosting provider Render भी इसे support करता है
  • Val Town अब तक Postgres का सक्रिय रूप से उपयोग करता आया है, और Postgres को documentation और hosting support के लिहाज़ से मजबूत technology माना जाता है
  • छोटी टीमों के लिए infra को जितना हो सके उतना सरल रखना महत्वपूर्ण होता है, इसलिए अगर Postgres से काम हो जाए तो उसे चुनने की प्रेरणा मजबूत रहती है
  • लेकिन FTS इस्तेमाल करने वाले पिछले projects में performance और scalability समस्याएँ आई थीं
    • Observable आखिरकार Elasticsearch पर चला गया
    • Val Town के पास बहुत सारे vals हैं, और वह single-node Postgres cluster की सीमाओं को परख रहा है
  • code search में FTS के सफल उपयोग के उदाहरण ढूँढना कठिन है, इसलिए इसे पहली पसंद के बजाय backup option की तरह रखा गया है

pg_trgrm आधारित v2 search प्रयोग

  • Val Town ने soft launch किया हुआ v2 search algorithm, Postgres के pg_trgrm पर आधारित है
    • pg_trgrm Postgres में trigram search implement करता है
  • code search में trigram के सफल उदाहरण पहले से मौजूद हैं
    • Russ Cox की 2012 की पोस्ट में Google Code Search द्वारा trigram index और special regex implementation के उपयोग का ज़िक्र है
    • GitHub का नया code search system भी trigram search का उपयोग करता है
    • Sourcegraph के पास Google से आगे बढ़ाया गया trigram-based search tool है
  • Val Town का Postgres pg_trgrm approach, Stephen Gutekanst की Postgres आधारित local repository indexing पोस्ट से काफी प्रभावित है
  • implementation में search text वाले column पर GIN index और gin_trgm_ops लगाया जाता है
  • pg_trgrm regex search के लिए अच्छा समाधान है, लेकिन Val Town के अधिकांश searches की तरह अधिक free-form queries पर यह उतना उपयुक्त नहीं है
    • search ranking के लिए word_similarity का उपयोग किया जा रहा है
    • algorithm को reasonable ranking के करीब tune करना बहुत कठिन काम है

search engine विकल्प और operational trade-offs

  • समीक्षा के दायरे में standalone search services और Postgres extensions दोनों शामिल हैं
    • Meilisearch: standalone, Rust, 41k stars
    • Typesense: standalone, C++, 17k stars
    • Zoekt: standalone, Go, 406 stars
    • ParadeDB: Postgres extension, Rust, 3.2k stars
    • Sonic: standalone, Rust, 19.4k stars
  • code-specific tools मौजूद हैं, लेकिन उनमें से अधिकांश private हैं
    • GitHub search उत्कृष्ट है, लेकिन यह dedicated team और वास्तविक time budget का नतीजा है
  • Sourcegraph द्वारा maintain किया गया Zoekt fork दिलचस्प है, लेकिन बहुत niche है और बड़े नए infra investment की मांग करता है
  • Elasticsearch अंततः अपरिहार्य समाधान बन सकता है
    • इसमें code-specific handling नहीं है, लेकिन इसे लगभग अनंत स्तर तक customize किया जा सकता है
    • Java memory tuning सीखना, application में पहली persistent disk storage लाना, और data के अतिरिक्त source of truth को manage करना बोझिल है
    • Elasticsearch Cloud maintenance का बोझ कम कर सकता है
  • Meilisearch Elasticsearch के विकल्प के रूप में promising लगता है
    • इसका Rust-based होना आकर्षक है
    • इसकी self-comparison post scalability से ज़्यादा latency पर ज़ोर देती दिखती है, इसलिए infra burden वास्तव में कम होगा या नहीं, यह स्पष्ट नहीं है
  • ParadeDB Elasticsearch की तरह काम करता है, लेकिन “सिर्फ Postgres” होना इसकी खास अपील है
    • हालांकि Render पर अभी यह extension इस्तेमाल नहीं किया जा सकता

जब छोटी टीम search infra चुनती है तो बोझ क्यों बढ़ता है

  • code search, English search की तुलना में अधिक कठिन है
  • छोटी टीमों में infra को सरल रखना, development environment setup को आसान बनाना, और data को एक ही जगह रखना स्वाभाविक प्राथमिकता होती है
  • Val Town ऐसे विकल्पों में जल्दबाज़ी में बंधना नहीं चाहता जिन्हें लगातार maintenance चाहिए
  • मझोली और बड़ी कंपनियों में सिर्फ search “service” ही नहीं, search “team” भी होती है — इसके पीछे वजह है

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

1 टिप्पणियां

 
GN⁺ 2024-04-12
Hacker News की राय

  • Sourcegraph में यह मौजूद है, और बड़े पैमाने की प्रोसेसिंग की ज़रूरत होना स्वाभाविक है, लेकिन अगर आप किसी प्रोडक्ट में पहली बार code search जोड़ रहे हैं, तो शुरुआत से indexing से शुरू न करें; जब तक उसकी सीमा न आ जाए, तब तक on-the-fly search की सिफारिश है
    अगर सिर्फ पहले N नतीजे ही ढूँढने हों, तो पूरी चीज़ को अंत तक स्कैन किए बिना भी result buffer भरा जा सकता है, इसलिए यह उम्मीद से ज़्यादा लंबे समय तक चल जाता है। जो लोग ऐसी चीज़ें बना रहे हैं, उनसे, Val Town के लोगों से भी, खुशी से बात करना चाहूँगा

    • जब indexed search की ज़रूरत पड़े, तो Zoekt मेरे हिसाब से सबसे अच्छा तरीका है
      पहले Sourcegraph ने Zoekt का maintenance संभाला था, और Livegrep तथा Hound उस scale पर कई मायनों में भारी पड़ रहे थे जिसे हम index करना चाहते थे। पुराने और डगमगाते OpenGrok deployment से Zoekt पर जाने के बाद indexing performance और search performance/usability दोनों में बड़ा फर्क आया। Sourcegraph, Zoekt द्वारा दिए गए code search के ऊपर उससे कहीं अधिक परिष्कृत फीचर जोड़ता है
    • यह हैरानी की बात थी कि indexing के बिना भी काफ़ी दूर तक जाया जा सकता है
      उदाहरण के लिए GritQL(https://github.com/getgrit/gritql) के बारे में भी मैं हमेशा सोचता था कि speed के लिए आखिरकार indexing चाहिए होगी, लेकिन अब तक वह पूरी तरह on-the-fly search से काफ़ी अच्छी तरह चल रहा है
    • मैं कई समस्याओं पर यही तरीका लागू करता हूँ। पहले सबसे कम state रखने वाला simple approach अपनाता हूँ, और तभी बदलता हूँ जब यह साबित हो जाए कि speed के लिए memory की दिशा में झुकना पड़ेगा
      cache न हो तो चीज़ों को सही बनाए रखना कहीं ज़्यादा सरल होता है
    • वास्तव में पर्याप्त scale और प्रतिनिधि workload आने के बाद ही उपयुक्त indexing approach चुनना कहीं बेहतर होता है
    • time-series database बना रहे किसी व्यक्ति ने disk block को compress करके रखा था और stream के रूप में decompress करते हुए search किया
      जो चीज़ें L2 cache में फिट हो जाती हैं, वे सचमुच बहुत तेज़ चलती हैं

  • code search वाकई कठिन है, और एक अच्छा code search platform जीवन को बहुत आसान बना देता है
    अगर मैं Google छोड़ूँ, तो internal code search सबसे ज़्यादा याद आएगा। blaze target ढूँढना, guice binding वगैरह, हर workflow के साथ यह इतना अच्छी तरह integrated है कि इसके बिना काम करने की कल्पना करना मुश्किल है। जब भी GitHub search इस्तेमाल करता हूँ, इसकी कीमत और ज़्यादा समझ में आती है; इसलिए नहीं कि GitHub search खराब है, बल्कि इसलिए कि एक general-purpose code search platform बनाना मूल रूप से कहीं अधिक कठिन है

    • छोड़ने के बाद, Google के code search काम पर आधारित Livegrep इस्तेमाल किया जा सकता है
      मैं अभी व्यक्तिगत रूप से इसका उपयोग नहीं कर रहा, लेकिन यह बेहतरीन लगता है और ज़्यादातर ज़रूरतें पूरी कर देगा। https://github.com/livegrep/livegrep
    • guice binding layer फीचर अच्छा है, लेकिन UI और बेहतर हो सकता है
      अच्छा होगा अगर search box से ही सीधे provider या usage location मिल सके

  • बुनियादी code search skills नए डेवलपर्स को आम तौर पर स्पष्ट रूप से नहीं सिखाई जातीं, लेकिन यह शुरुआती दौर में ज़रूर सीखने वाली मुख्य क्षमता लगती है
    सुझाया गया flow यह है कि पहले Ctrl+F जैसी हर जगह चलने वाली search सीखें, फिर ripgrep(https://github.com/BurntSushi/ripgrep) पर जाएँ। यह कोई optional चीज़ नहीं, बल्कि सचमुच शानदार और आसानी से खोजा जा सकने वाला tool है, और terminal खुला रखना भी शुरुआती लोगों के लिए उल्टा फायदेमंद है। अगर संभव हो तो एक शक्तिशाली command-line editor भी सीखना अच्छा है; पहले मैं Emacs की सिफारिश करता, लेकिन अब vim का basic version सुझाऊँगा जो लगभग हर जगह installed मिलता है। क्योंकि उसी window में grep भी कर सकते हैं और edit भी। इसके बाद grep -r, grep -ri, grep -ril जैसे विकल्पों से वह व्यवहार पुराने grep में भी सीखें जो ripgrep डिफ़ॉल्ट रूप से देता है, और अंत में जब ripgrep की सीमाएँ सामने आएँ तो असली indexed, dedicated code search tool पर जाएँ

    • VSCode की search सुविधा भी ripgrep का उपयोग करती है, इसलिए यह एक अच्छा शुरुआती बिंदु है
    • GitHub भी उन repositories तक code search करने के लिए बेहतरीन tool है जिन्हें आपने अभी clone नहीं किया है, चाहे वे public repos हों या organization repos
    • यह जानने की जिज्ञासा है कि Git repository खोजते समय speed के अलावा ripgrep को git grep पर क्या फ़ायदा मिलता है

  • यह हैरानी की बात है कि hound(https://github.com/hound-search/hound) का ज़िक्र नहीं हुआ
    मुझे लगा था कि इस क्षेत्र के open source समाधानों में यह अग्रणी है। मैं Wikimedia instance(https://codesearch.wmcloud.org/search/) का उपयोग करता रहा हूँ और कुल मिलाकर संतुष्ट हूँ

    • Hound ने search results पर कोई ऊपरी सीमा न रखने का दिलचस्प विकल्प चुना
      https://codesearch.wmcloud.org/search/?q=test&files=&exclude... मेरे मामले में 13 सेकंड लेकर 55MB JSON response बनाता है, और फिर उसे DOM में render करने में भी कुछ सेकंड और लगते हैं। neogrok में इस्तेमाल होने वाले Zoekt JSON API में search response size limit की सही ज़रूरत थी, इसलिए यह सुनिश्चित करना पड़ा: https://github.com/sourcegraph/zoekt/pull/615

  • IDE और developer tools बनाने वाले लोग बहुत पहले से मानते रहे हैं कि सही code search करने के लिए compiler platform को खोलना पड़ता है
    क्योंकि ज़रूरी कामों का बड़ा हिस्सा आखिरकार compiler द्वारा उपयोग किए जाने वाले internal representation को फिर से बनाना ही होता है। अच्छा code search refactoring support, auto-complete, और आम IDE features की नींव भी है। बेशक यह कहना जितना आसान है, करना उतना नहीं; इसलिए compiler बनाने वाली तरफ़ tools अक्सर पीछे छूट जाते थे, और JetBrains ने भी Kotlin के शुरुआती दौर में यही गलती की थी। अब Kotlin 2.0 में incremental compilation जैसी support को आसान बनाने के लिए इसका कुछ सुधार किया जा रहा है। Rust community ने भी कुछ साल पहले IDE-friendliness बढ़ाने के लिए बड़ा प्रयास करते हुए यही समझ हासिल की थी। IBM ने पुराने Eclipse में यह काम सही ढंग से किया था, और उसके बाद से कोई उसे ठीक से पकड़ नहीं पाया। IntelliJ लगभग 2–3 orders of magnitude धीमा था, इसलिए फ़र्क seconds और milliseconds का हो जाता था। Eclipse में Java के लिए एक बहुत तेज़ incremental compiler था जो syntax errors होने पर भी कुछ हद तक compile कर सकता था, और IDE का code representation उसी compiler से जुड़ा हुआ था। अगर आप typo डालकर कुछ code तोड़ देते थे, तो पूरे codebase में समस्या वाले files तुरंत लाल underline के साथ दिख जाते थे, और typo ठीक करते ही बिना देरी गायब हो जाते थे। यह तभी संभव है जब files और syntax tree के बीच mapping हो, और Eclipse incremental compiler से जुड़ा होने की वजह से यह कर पाता था। IntelliJ यह नहीं कर पाता, इसलिए rebuild से पहले normal/broken state के बारे में सक्रिय रूप से भ्रम पैदा करता है, और internal state disk से mismatch होने पर बहुत सारे fake errors दिखाता है। Run करने पर कुछ seconds की compile delay होती है, और तभी पता चलता है कि IDE ने जिसे runnable बताया था, वह गलत था। Eclipse में compiler और internal state साझा होने की वजह से यह सब तुरंत और साफ़-साफ़ होता था। कमियाँ और परेशान करने वाले bugs भी बहुत थे, लेकिन वह feature याद आता है

    • बेशक Microsoft का Roslyn (.NET compiler) अपवाद है
      https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov...
      https://ericlippert.com/2012/06/08/red-green-trees/
      Roslyn SDK से tools बनाकर देखे हैं, और वह सच में बहुत अच्छा था
    • Eclipse का Java incremental compiler वाकई कमाल का है, लेकिन Maven और Gradle जैसे external build systems के साथ integration और कई languages की बेहतर support के कारण आखिरकार लोग IntelliJ की तरफ़ चले गए
    • Eclipse में अब भी सब कुछ तुरंत और बिना किसी अस्पष्टता के होता है
      बहुत से लोग दूसरे IDE पर switch न करने की यही मुख्य वजह है

  • लगता है GitHub ने पहले a.toString() को दो tokens में तोड़ने जैसी “fix” की थी, और वह काफ़ी परेशान करने वाली थी
    GitHub IDE-जैसी find-usages क्षमता को बेहतर बना रहा है, लेकिन अभी भी यह perfect नहीं है, इसलिए कभी-कभी छूट गए usages ढूँढने के लिए "foo.bar()" जैसी text search करनी पड़ती है। लेकिन इस तरह की stemming behavior की वजह से foo और bar का अलग-अलग ज़िक्र जहाँ-जहाँ हुआ है, सब मिल जाता है और results बेवजह बहुत बढ़ जाते हैं

  • Zoekt को यूँ ही नज़रअंदाज़ करना समझ में नहीं आता
    यह ठीक इसी काम के लिए बनाया गया था, और दूसरे विकल्पों की तुलना में कोई बड़ा नया infrastructure burden भी नहीं है। Server भी single binary है, indexer भी single binary, इसलिए इससे ज़्यादा simple होना मुश्किल है। Elasticsearch की तुलना में Zoekt से ज़्यादा डरने की कोई वजह नहीं दिखती

  • हाल में देखे गए code search approaches में सबसे दिलचस्प चीज़ों में से एक septum है: https://github.com/pyjarrett/septum
    मेरा मानना है कि सही code search बनाते समय सबसे मुश्किल हिस्सा उचित मात्रा में surrounding context लाना होता है, और septum इस समस्या को file-level पर हल करने की कोशिश करने वाला tool है। एक और चीज़ जिसका ज़िक्र न होना चौंकाने वाला है, वह stack-graphs (https://github.com/github/stack-graphs) है, जो पूरे codebase में symbol relationships को incrementally resolve करने की कोशिश करता है। यह GitHub की cross-file precise indexing को चलाता है और conceptually भी सही लगता है, लेकिन open source version को चलाने में दिक्कतें आईं

  • Oracle में USER/ALL/DBA_SOURCE views होते हैं, और database में लोड किया गया सारा PL/SQL (SQL/PSM) code वहाँ दिखाई देता है
    अगर जानबूझकर obfuscate न किया गया हो, तो सब plain text में दिखता है। इसमें owner, object name, LINE[NUMBER], TEXT[VARCHAR2(4000)] columns होते हैं, और stored source code पर LIKE या regexp_like() इस्तेमाल किया जा सकता है। जिज्ञासा है कि EnterpriseDB ने इसे Postgres के अंदर implement किया है या extension के रूप में देता है। चूँकि ज़्यादातर SQL/PSM वैसे भी Oracle से आया है, इसलिए यह चाहना स्वाभाविक feature है। https://en.wikipedia.org/wiki/SQL/PSM

  • कहा गया कि “GitHub search शानदार है”, लेकिन क्या सच में?
    ज़्यादातर मामलों में यह लगभग बेकार लगता है, और clone करने के बाद ripgrep इस्तेमाल करना कहीं ज़्यादा असरदार है। हो सकता है असली समस्या search से ज़्यादा उसका भयानक UX हो