(RDB) Join को समझने के 13 तरीके

 (justinjaffray.com)
4 पॉइंट द्वारा GN⁺ 2023-07-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • relational database में inner join सिर्फ SQL syntax नहीं है; उसी structure को lookup, nested loop, logical model, type checking और algebraic perspective से अलग-अलग तरह से समझा जा सकता है
  • normalized tables में join, references को follow करके बिना duplication के store की गई जानकारी को फिर से जोड़ने का सबसे practical tool बन जाता है
  • implementation perspective से इसे row pairs पर iterate करके सिर्फ condition satisfy करने वाले combinations रखने, या column domains में दोनों relations में मौजूद value combinations चुनने के तरीके के रूप में देखा जा सकता है
  • programming model में join को flatMap, SQL LATERAL, ORM की N+1 problem का समाधान, Rust trait-based type checking, और Set monad के andThen से समझाया जा सकता है
  • mathematical रूप से graph paths, minimal model, largest permissible relation, partial order का least upper bound, और relational expression का ring product—ये सभी join की समान properties दिखाते हैं

Normalized data में join lookup बन जाता है

  • Join को सबसे practical रूप से किसी value को lookup करने या existing data में redundant information जोड़ने के काम के तौर पर देखा जा सकता है
  • उदाहरण user, country, country_code को एक ही table में store करने के तरीके से शुरू होता है
    • समान country value के लिए country_code दोहराया जाता है, जिससे duplication होता है
    • अगर data ऐसा है जो अक्सर बदलता है, तो हर जगह को साथ में update करना पड़ता है, जिससे errors और inefficiency बढ़ती है
  • Normalized form में country और country_code के relation को अलग table में अलग कर दिया जाता है, और user table सिर्फ country_id को reference करता है
  • users और countries को country_id पर INNER JOIN करने से original user, country, country_code form फिर से मिल जाता है
  • आगे की explanation यह मानती है कि same-name columns के आधार पर implicitly join किया जा रहा है, लेकिन detailed SQL syntax से सख्ती से बंधी नहीं है

Implementation perspective: rows और columns पर iterate करने वाला join

  • जब दो sets R, S और predicate p हों, join सभी r ∈ R, s ∈ S पर iterate करता है और केवल वे cases output करता है जिनमें p(r, s) true हो
    • अगर दो collections का Cartesian product सभी possible row connections है, तो join उसका वह subset है जो condition satisfy करता है
  • Column-centric view में हर column के domain को possible values का set माना जाता है और column value combinations पर iterate किया जाता है
    • अगर R(a, b) और S(b, c) हों, तो a, b, c के domains पर iterate किया जाता है
    • केवल जब (a, b) R में हो और (b, c) S में हो, तब [a, b, c] output किया जाता है

Compatible alternative realities के रूप में join

  • John और Sally का example ऐसी situation में join को समझाता है जहाँ दोनों के पास कुछ-कुछ information है और सिर्फ compatible realities बचाई जाती हैं
  • John अपने pet और stray animal के possible combinations जानता है, और Sally भी अपने pet और stray animal के possible combinations रखती है
    • जब John के पास dog हो और stray dog हो, और Sally के पास cat हो और stray mouse हो—ये दोनों एक साथ true नहीं हो सकते
    • क्योंकि दोनों को वही stray observe करना चाहिए
  • दोनों tables को stray के आधार पर join करने से John के pet·stray·Sally के pet combinations में से केवल वे cases बचते हैं जिनमें आपसी contradiction नहीं है

Programming model में join

  • flatMap वह function है जो original array के हर element के लिए नया array बनाता है और results को concatenate करता है; इसे join implement करने में use किया जा सकता है
    • SELECT * FROM r INNER JOIN s ON p को r.flatMap(x => s.filter(y => p(x, y))) के रूप में express किया जाता है
    • SQL के कुछ variants में LATERAL syntax join को flatMap form में बदल देता है
  • अगर LATERAL के right side में left columns का reference नहीं है, तो यह Cartesian product के बराबर है
    • Query decorrelation right side के column references को successive rewrites के जरिए हटाने के तरीके पर depend करता है
  • ORM में common N+1 problem को भी join से explain किया जा सकता है
    • अगर result set की हर row के लिए extra query execute की जाए, तो Postgres जैसे connection use करने वाले databases में individual queries की fixed cost बड़ी होती है
    • Database से “ये सभी lookups कर दो” कहकर request करने का result users INNER JOIN countries जैसा join है
    • Sqlite जैसे in-process databases में यह problem कम होती है

Graph paths और logical model

  • Relation दो sets को “relate” करता है, इसलिए इसे graph के रूप में देखा जा सकता है
    • users table user names के set और country_id set को connect करता है
    • country_id और two-letter country codes को connect करने वाला relation भी अलग graph के रूप में दिखाया जा सकता है
  • अगर पहले graph का right set और दूसरे graph का left set same vertex set share करते हैं, तो उन्हें merge करके देखा जा सकता है
  • Left set से शुरू होकर middle vertex के जरिए right set तक जाने वाले सभी paths list करें, तो वह दो relations का join बन जाता है
  • Formal logic में relation को predicate माना जाता है, और sentences के set को true बनाने वाले facts के set को model माना जाता है
    • अगर users(A, B) और countries(B, C, D) true हैं, तो Q(A, B, C, D) true है—ऐसा implication रखा जाता है
    • इस condition को satisfy करने वाले कई models हो सकते हैं
    • Standard result पाने के लिए condition satisfy करने वाले models में से smallest model चुना जाता है
    • यह smallest model users और country के join result जैसा ही है

Type checking के रूप में join

  • ML-style type system Prolog और Datalog से काफी मिलता-जुलता है, इसलिए इसे join की तरह express किया जा सकता है
  • Rust example में relations को traits के रूप में define किया जाता है
    • Users और CountryCode relations की भूमिका निभाते हैं
    • Smudge, Sissel, Petee, Canada, UnitedStates, CA, US concrete types के रूप में define किए जाते हैं
  • (Smudge, Canada): Users, (Canada, CA): CountryCode जैसे trait implementations relation की rows के बराबर हैं
  • (A, B, C) को join में शामिल होने के लिए (A, B): Users और (B, C): CountryCode होना चाहिए
  • test::<(Smudge, _, CA)>() type checking में succeed करता है, लेकिन test::<(Smudge, _, US)>() fail करता है क्योंकि (Canada, US): CountryCode implement नहीं किया गया है

Set monad operations के रूप में join

  • JavaScript के Some और None example optional records को combine करने के तरीके से शुरू होता है
    • अगर दो records में same country हो, तो उन्हें merge करके Some return करता है
    • अगर वे compatible नहीं हैं या value नहीं है, तो None return करता है
  • andThen optional value के अंदर की value निकालकर merge function apply करता है
  • उसी combine function को बनाए रखते हुए container को Rel में बदल दें, तो relation sets process किए जा सकते हैं
    • Rel.map सभी rows पर function apply करता है
    • Rel.andThen हर row से निकले relation को flatMap से concatenate करता है
  • users relation और countries relation पर वही combine चलाने से Smudge, Sissel, Petee के साथ country code जुड़ा हुआ join result मिलता है

Largest permissible relation और partial order का join

  • अगर दो relations R, S के सभी columns वाला तीसरा relation T नई information invent नहीं करता, तो उसे permissible define किया जाता है
    • T की किसी row को R के columns तक restrict करने पर वह row R में होनी चाहिए
    • इसी तरह S के columns तक restrict करने पर भी वह row S में होनी चाहिए
  • उदाहरण के लिए Smudge, Canada, US permissible नहीं है
    • सिर्फ country, country_code देखें तो Canada, US बनता है, लेकिन यह S में मौजूद row नहीं है
  • Empty relation भी permissible है, लेकिन largest permissible relation में Smudge-Canada-CA, Sissel-Canada-CA, Petee-United States-US शामिल हैं
  • यह largest permissible relation ही दो relations का join है
  • Partial order view में R ≤ Q को इस तरह define किया जाता है
    • Q में R के सभी columns शामिल हों
    • Q की हर row को R के columns तक restrict करने पर वह R की row बने
  • इस partial order में दो relations R, S का least upper bound R ∨ S मौजूद होता है, और यही relational join के समान अर्थ वाला join है

Ring product के रूप में join

  • Relation को algebraically भी express किया जा सकता है
    • एक row को column-value pairs के product के रूप में दिखाया जाता है
    • एक relation को कई rows के sum के रूप में दिखाया जाता है
  • उदाहरण के लिए user = Smudge और country_id = 1 को multiply करने वाला term एक row बन जाता है
  • Expression simplify करने के लिए rules जोड़े जाते हैं
    • Idempotence: [x = y][x = y] = [x = y]
    • Contradiction: [x = y][x = z] = 0 if y ≠ z
  • User relation R और country lookup relation S को multiply करके, distributive और commutative laws से expand करने पर contradictory terms गायब हो जाते हैं और सिर्फ compatible terms बचते हैं
  • बची हुई expression Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US है, और यही ठीक-ठीक दो relations का join है
  • इस तरीके को tensor contraction के रूप में भी देखा जा सकता है

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

1 टिप्पणियां

 
GN⁺ 2023-07-04
Hacker News की राय

  • Join को spatial dimension के रूप में सोचना शुरू किया तो समझना बहुत आसान हो गया
    Dim_X, Dim_Y, Dim_Z की तरह हर dimension को अलग table में रखकर उन्हें उसी EntityId से जोड़ें, तो इसे किसी entity की 3D position बनाने जैसा देखा जा सकता है
    3 dimensions बनाने के लिए कम-से-कम 2 inner joins चाहिए, और time जैसी non-spatial dimension को भी इसी तरह extend किया जा सकता है
    अगर किसी specific time को restrict न करें, तो यह एक ऐसी report बन जाती है जिसमें किसी entity की time के साथ रही सभी positions होती हैं
    दूसरे join types भी, अगर schema को दिमाग में “rotate” कर सकने लायक concept पकड़ लें, तो इसी variation के रूप में समझना आसान हो जाता है

    • HyperDex याद आता है। यह attribute के आधार पर values को multi-dimensional hyperspace में hash करके index में इस्तेमाल करता है
      https://dbdb.io/db/hyperdex
    • यह data की hyper-normalization जैसा लगता है। आम तौर पर BCNF हो तो शायद बस EntityPosition(EntityId, X, Y, Z) जैसी table रखी जाएगी
      हालांकि कई dimensions के pieces को मिलाने और aggregation संभालने के मामले में data warehouse वाली तरफ ध्यान जाता है
    • JOIN, INNER JOIN जैसी syntax क्यों इस्तेमाल होती है, यह हमेशा सवाल रहा है। FROM में tables list करके WHERE clause में join condition को equation की तरह लिखना कहीं ज्यादा clear लगता है
      complex FROM clause में कई JOIN मिले हों तो पढ़ना मुश्किल हो जाता है, और equivalent conditional expressions को WHERE में पढ़ना ज्यादा intuitive है
    • क्या इसे इस तरह समझना चाहिए कि सभी joins cross join के variants हैं?

  • शून्यवां नजरिया यह है कि “join relational algebra का operator” है
    https://en.m.wikipedia.org/wiki/Relational_algebra
    natural join R ⋈ S उन tuple combinations का set है जिनमें common attribute names समान होते हैं, और यह logical AND से मेल खाने वाला relational operation है
    ⋈ को Cartesian product की तरह देखा जा सकता है, जो predicate से उन rows को filter करता है जिन्हें result में नहीं आना चाहिए, और SQL का बड़ा हिस्सा इस दृष्टिकोण से अच्छी तरह समझ आता है

    • relational theory की functional interpretation में join function composition है, इसलिए यह perspective छूट जाना हैरानी की बात है
    • “rows पर nested loop” वाली explanation के अंदर cross product + predicate का perspective शामिल है

  • कई दिनों से query execution/planning implementation पर material ढूंढ रहा हूं, लेकिन predicates, existing indexes, joins जैसी implementation-side चीजों पर material आसानी से नहीं मिल रहा
    Google search results usage material से भरे पड़े हैं
    अब तक मुझे सिर्फ CMU Database Group का material मिला है, और वह शानदार है

    • इस topic पर 700-page की free book है: “Building Query Compilers”
      https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
      TUM का “Database Systems on Modern CPU Architectures” course भी मददगार हो सकता है, और 2020 material में पूरी video lectures हैं
      https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
    • पता नहीं यह आपकी चाही depth से match करेगा या नहीं, लेकिन SQLite का optimization overview और query planner docs देखने लायक हैं
      https://www.sqlite.org/optoverview.html
      https://www.sqlite.org/queryplanner.html
    • ऐसे मामलों में अक्सर Postgres documentation और source पढ़ने की सलाह देता हूं। source भी काफी readable है
      https://www.postgresql.org/docs/current/planner-optimizer.ht...
    • यह काफी specialized topic है, इसलिए अच्छी textbook ढूंढना कठिन है, और यह इस पर depend करता है कि आप कितनी गहराई में जाना चाहते हैं और किस हिस्से में interested हैं
      query execution और query planning असल में लगभग अलग-अलग चीजें हैं
      join optimization paper के लिए मूल Selinger paper अब भी सबसे अच्छा लगता है
      https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
      यह outer joins support नहीं करता और ज्यादा efficient techniques भी आ चुकी हैं, लेकिन System R family optimizers देखने वालों के लिए इसे पढ़ना अब भी familiar लगेगा
      Postgres का src/backend/optimizer/README भी ऐसे कई contents देता है जो दूसरी जगह मुश्किल से मिलते हैं
      CMU के Andy Pavlo lectures online इस content को explain करने वाले लगभग इकलौते resources में से हैं, और “Building Query Compilers” PDF अधूरा है, लेकिन इसमें Moerkotte वगैरह के key papers शामिल हैं, इसलिए modern implementation करनी हो तो देखने लायक है
      applicable indexes ढूंढना आम तौर पर यह देखने भर से हो जाता है कि sargable predicate है या नहीं, इसलिए मुश्किल नहीं है, लेकिन selectivity estimation कठिन है, और join के बाद selectivity estimation optimizer की सबसे कठिन problems में से एक है
      जैसे अगर A=x AND B=y AND C=z हो और (A,B), (B,C) indexes की selectivity/cardinality information ही हो, तो तीनों conditions की overall selectivity कैसे estimate करें—यह भी आसान problem नहीं है
      इसे solve करने के लिए “second-order cone programming” solver मांगने वाले papers भी हैं
    • search term के आगे relational algebra जोड़कर query planning search किया, तो मोटे तौर पर देखने पर भी implementation-side results ज्यादा मिले

  • 14वां तरीका multi-join है, और इसे “worst-case optimal join” भी कहा जाता है, लेकिन यह नाम खास अच्छा नहीं है
    दो-दो tables को join करते हुए लगातार intermediate results बनाने के बजाय, इसका मतलब है 3 या उससे अधिक tables को बिना intermediate result के साथ में join करना
    संबंधित blog post और छोटा video https://relational.ai/blog/dovetail-join पर हैं, और मूल paper https://dl.acm.org/doi/pdf/10.1145/3180143 पर है
    मैं RelationalAI में काम करता/करती हूं, और academia में करीब 10 साल तक research हुए इस नए join algorithm को हम और कुछ अन्य नई database companies market में ला रहे हैं

    • Justin का WCOJ introduction भी काफी अच्छा है
      https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
    • input को negation, यानी set complement में बदल दें तो join का AND NOR बन जाता है, और Tetris इसी बात का फायदा उठाता है
      worst-case bound stateless/streaming WCOJ से ज्यादा tight नहीं होता, लेकिन real data के पास अक्सर काफी छोटे box certificates होते हैं
      मैंने नहीं देखा कि Dovetail join recursive queries, यानी arbitrary datalog जहां सिर्फ output relation specify किया जाता है और intermediate relations engine खुद संभालता है, को support करता है या नहीं
      जिज्ञासा है कि क्या यह ऐसी queries support करता है

  • relational model की बारीकियां मुख्य रूप से application-level developers को दिखाने वाले ऐसे और articles होने चाहिए
    functional programming के नजरिए से explanation और exploration भी concise और convincing है

  • लगता है N+1 problem सिखाने का एक और मौका चूक गया
    non-clustered index पर join करना भी अब भी N+1 ही है; बस यह network और disk के बीच आने-जाने वाला N+1 नहीं, बल्कि disk पर N+1 है

    • यह कुछ ऐसा सुनाई देता है कि “उन्हें मेरी रुचि वाले X problem को cover करना चाहिए था, और फिर article लंबा हो जाता तो भी ठीक था”

  • inner join एक condition वाला Cartesian product है

    • Cartesian product बनाकर फिर condition से filter करने और condition को सीधे generate करने के बीच performance में बड़ा फर्क है
      equality join condition वाला inner join condition को सीधे बनाता है, और non-equality join condition में actual evaluation की जरूरत होती है

  • अच्छी explanation है। “सही तरीका tables को normalize करना है” वाली बात transactional database में सही है, लेकिन data warehouse में कुछ हद तक denormalization व्यापक रूप से स्वीकार की जाती है

  • normalization example देखकर वह समय याद आ गया जब मैं सोचता/सोचती था कि numeric primary keys strings से तेज होती हैं और उसी हिसाब से tables design करता/करती था
    तब बेअर्थ id बन जाते थे, और असल में चाहिए होने वाली unique value पाने के लिए join की जरूरत पड़ती थी
    एक दिन समझ आया कि दो tables में वही unique key इस्तेमाल करने से joins घट सकते हैं, और यह simple लेकिन बहुत effective था

    • फिर भी मुझे हर table में unique id field रखना पसंद है। यह logging में मदद करता है और कई fields वाली “असली” key की चिंता नहीं करनी पड़ती
      इसके बजाय string value पर unique index रखता/रखती हूं, और उससे भी अहम, integrity constraint उसी पर लगाता/लगाती हूं
      meaningful strings से भरी table, numeric id या UUID से भरी table की तुलना में कहीं ज्यादा readable होती है