(RDB) Join’i Anlamanın 13 Yolu

 (justinjaffray.com)
4 puan yazan GN⁺ 2023-07-04 | 1 yorum | WhatsApp'ta paylaş
  • İlişkisel veritabanlarındaki inner join, basit bir SQL söz diziminin ötesinde; sorgulama, iç içe döngüler, mantıksal model, tip denetimi ve cebir açısından aynı yapının farklı yorumları olarak görülebilir
  • Normalize edilmiş tablolarda join, referansları izleyerek tekrarsız saklanan bilgileri yeniden birleştiren en pratik araç hâline gelir
  • Uygulama açısından, satır çiftleri üzerinde dolaşıp yalnızca koşulu sağlayan kombinasyonları bırakmak ya da sütun domain’lerinde iki ilişkide de bulunan değer kombinasyonlarını seçmek olarak görülebilir
  • Programlama modelinde join; flatMap, SQL LATERAL, ORM’lerde N+1 problemi çözümü, Rust trait tabanlı tip denetimi ve Set monad’ının andThen işlemiyle açıklanabilir
  • Matematiksel olarak graf yolları, en küçük model, izin verilen en büyük ilişki, kısmi sıralamanın en küçük üst sınırı ve ilişkisel ifadelerin halka çarpımı, join’in aynı özelliklerini ortaya koyar

Normalize edilmiş veride join bir sorgulamaya dönüşür

  • Join, en pratik anlamıyla belirli bir değeri sorgulamak ya da mevcut veriye tekrarlı bilgiyi eklemek olarak görülebilir
  • Örnek, user, country, country_code değerlerini tek bir tabloda saklama yaklaşımıyla başlar
    • Aynı country değerinin her geçtiği yerde country_code tekrarlandığı için yinelenme oluşur
    • Değerleri sık değişen verilerde tüm konumları birlikte güncellemek gerektiğinden hata ve verimsizlik artar
  • Normalize edilmiş biçimde country ile country_code arasındaki ilişki ayrı bir tabloya ayrılır; kullanıcı tablosu ise yalnızca country_id değerine referans verir
  • users ve countries tabloları country_id üzerinden INNER JOIN edilirse, başlangıçtaki user, country, country_code biçimi yeniden elde edilir
  • Sonraki açıklamalar, aynı adlı sütunlara göre örtük olarak join yapıldığını varsayar; ancak ayrıntılı SQL söz dizimine sıkı sıkıya bağlı kalmaz

Uygulama açısından: satır ve sütunlar üzerinde dolaşan join

  • İki küme R, S ve bir yüklem p olduğunda join, tüm r ∈ R, s ∈ S değerleri üzerinde dolaştıktan sonra yalnızca p(r, s) doğru olanları çıktı olarak üretir
    • İki koleksiyonun Kartezyen çarpımı olası tüm satır bağlantılarıysa, join bunun içinde koşulu sağlayan alt kümedir
  • Sütun merkezli bakıldığında, her sütunun domain’i olası değerler kümesi olarak alınır ve sütun değer kombinasyonları üzerinde dolaşılır
    • R(a, b) ve S(b, c) varsa a, b, c domain’leri üzerinde dolaşılır
    • (a, b) R içinde ve (b, c) S içinde olduğunda yalnızca [a, b, c] çıktılanır

Uyumlu alternatif gerçeklikler olarak join

  • John ve Sally örneği, tarafların bilginin yalnızca bir kısmına sahip olduğu bir durumda yalnızca uyumlu gerçekliklerin bırakılması üzerinden join’i açıklar
  • John, kendi evcil hayvanı ile sokak hayvanının olası kombinasyonlarını bilir; Sally de kendi evcil hayvanı ile sokak hayvanının olası kombinasyonlarını bilir
    • John’un köpeği olduğunda sokak hayvanının köpek olması ile Sally’nin kedisi olduğunda sokak hayvanının fare olması aynı anda doğru olamaz
    • Çünkü iki kişinin aynı sokak hayvanını gözlemlemesi gerekir
  • İki tablo stray üzerinden join edilirse, John’un evcil hayvanı, sokak hayvanı ve Sally’nin evcil hayvanı kombinasyonları içinde yalnızca birbirleriyle çelişmeyen durumlar kalır

Programlama modelinde join

  • flatMap, başlangıçtaki dizinin her öğesi için yeni bir dizi oluşturup sonuçları ardışık olarak birleştiren bir fonksiyondur ve join’i uygulamak için kullanılabilir
    • SELECT * FROM r INNER JOIN s ON p, r.flatMap(x => s.filter(y => p(x, y))) olarak ifade edilir
    • SQL’in bazı varyantlarındaki LATERAL söz dizimi, join’i flatMap biçimine dönüştürür
  • LATERAL ifadesinin sağ tarafı soldaki sütunlara referans vermiyorsa Kartezyen çarpım ile eşdeğerdir
    • Sorgu decorrelation işlemi, sağ taraftaki sütun referanslarını ardışık yeniden yazımlarla kaldırma yaklaşımına dayanır
  • ORM’lerde yaygın olan N+1 problemi de join ile açıklanabilir
    • Sonuç kümesindeki her satır için ek bir sorgu çalıştırıldığında, Postgres gibi bağlantı kullanan veritabanlarında her tekil sorgunun sabit maliyeti yüksektir
    • Veritabanından “bu sorgulamaların hepsini gerçekleştir” diye istemenin sonucu, users INNER JOIN countries gibi bir join’dir
    • Sqlite gibi in-process veritabanlarında bu problem daha hafiftir

Graf yolları ve mantıksal model

  • İlişki, iki kümeyi “ilişkilendirdiği” için graf olarak görülebilir
    • users tablosu, kullanıcı adı kümesi ile country_id kümesini birbirine bağlar
    • country_id ile iki harfli ülke kodlarını bağlayan ilişki de ayrı bir graf olarak gösterilebilir
  • İlk grafın sağdaki kümesi ile ikinci grafın soldaki kümesi aynı vertex setini paylaşıyorsa bunlar tek bir graf olarak birleştirilebilir
  • Soldaki kümeden başlayıp ortadaki vertex üzerinden sağdaki kümeye giden tüm yollar listelenirse, iki ilişkinin join’i elde edilir
  • Biçimsel mantıkta ilişkiler yüklem olarak, cümleler kümesini doğru yapan olgular kümesi ise model olarak görülür
    • users(A, B) ve countries(B, C, D) doğruysa Q(A, B, C, D) doğrudur şeklinde bir çıkarım konur
    • Bu koşulu sağlayan birden fazla model olabilir
    • Standart sonucu elde etmek için koşulu sağlayan modeller arasından en küçük model seçilir
    • Bu en küçük model, users ile country tablolarının join sonucuyla aynıdır

Tip denetimi olarak join

  • ML tarzı tip sistemleri Prolog ve Datalog’a güçlü biçimde benzediği için join’e benzer şekilde ifade edilebilir
  • Rust örneğinde ilişkiler trait olarak tanımlanır
    • Users ve CountryCode ilişki rolünü üstlenir
    • Smudge, Sissel, Petee, Canada, UnitedStates, CA, US somut tipler olarak tanımlanır
  • (Smudge, Canada): Users, (Canada, CA): CountryCode gibi trait implementasyonları ilişkinin satırlarına karşılık gelir
  • (A, B, C) değerinin join’e dahil olması için (A, B): Users ve (B, C): CountryCode olmalıdır
  • test::<(Smudge, _, CA)>() tip denetiminden geçer; ancak test::<(Smudge, _, US)>(), (Canada, US): CountryCode implementasyonu olmadığı için başarısız olur

Set monad işlemi olarak join

  • JavaScript’teki Some ve None örneği, optional record’ları birleştirme yöntemiyle başlar
    • İki record aynı country değerine sahipse birleştirilip Some döndürülür
    • Uyumlu değillerse ya da değer yoksa None döndürülür
  • andThen, optional değerin içini çıkarıp birleştirme fonksiyonunu uygular
  • Aynı combine fonksiyonu korunup container Rel olarak değiştirilirse ilişki kümeleri işlenebilir
    • Rel.map, tüm satırlara fonksiyon uygular
    • Rel.andThen, her satırdan çıkan ilişkiyi flatMap ile ardışık olarak birleştirir
  • users ilişkisi ile countries ilişkisine aynı combine çalıştırıldığında, Smudge, Sissel, Petee değerlerine ülke kodu eklenmiş join sonucu elde edilir

İzin verilen en büyük ilişki ve kısmi sıralamanın join’i

  • İki ilişki R, S içindeki tüm sütunlara sahip üçüncü bir ilişki T, yeni bilgi icat etmiyorsa izin verilebilir olarak tanımlanır
    • T içindeki herhangi bir satır R sütunlarıyla sınırlandığında bu satır R içinde bulunmalıdır
    • Aynı şekilde S sütunlarıyla sınırlandığında da bu satır S içinde bulunmalıdır
  • Örneğin Smudge, Canada, US izin verilebilir değildir
    • Yalnızca country, country_code açısından bakıldığında Canada, US olur; ancak bu S içinde olmayan bir satırdır
  • Boş ilişki de izin verilebilirdir; ancak izin verilen en büyük ilişki Smudge-Canada-CA, Sissel-Canada-CA, Petee-United States-US değerlerini içerir
  • Bu izin verilen en büyük ilişki, iki ilişkinin join’idir
  • Kısmi sıralama açısından R ≤ Q şu şekilde tanımlanır
    • Q, R içindeki tüm sütunları içerir
    • Q içindeki her satır R sütunlarıyla sınırlandığında R satırı olur
  • Bu kısmi sıralamada iki ilişki R, S için en küçük üst sınır olan R ∨ S vardır; bu da ilişkisel join ile aynı anlama gelen join’dir

Halka çarpımı olarak join

  • İlişkiler cebirsel olarak da ifade edilebilir
    • Tek bir satır, sütun-değer çiftlerinin çarpımı olarak gösterilir
    • Tek bir ilişki, birden fazla satırın toplamı olarak gösterilir
  • Örneğin user = Smudge ile country_id = 1 değerlerinin çarpımı olan terim tek bir satır olur
  • İfadeyi sadeleştirmek için kurallar eklenir
    • Idempotence: [x = y][x = y] = [x = y]
    • Contradiction: [x = y][x = z] = 0 if y ≠ z
  • Kullanıcı ilişkisi R ile ülke lookup ilişkisi S çarpılıp dağılım ve değişme yasalarıyla açıldığında, çelişen terimler kaybolur ve yalnızca uyumlu terimler kalır
  • Kalan ifade Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US olur; bu da tam olarak iki ilişkinin join’idir
  • Bu yöntem tensor contraction olarak da görülebilir

İlgili okumalar

1 yorum

 
GN⁺ 2023-07-04
Hacker News görüşleri

  • join kavramını uzamsal boyutlar üzerinden düşünmeye başlayınca anlamak çok daha kolaylaştı
    Her boyutu Dim_X, Dim_Y, Dim_Z gibi ayrı tablolarda tutup aynı EntityId ile bağlayınca, bunu tek bir varlığın 3 boyutlu konumunu oluşturmak gibi görmek mümkün
    3 boyut oluşturmak için en az 2 inner join gerekir; zaman gibi uzamsal olmayan boyutlar da aynı şekilde genişletilebilir
    Belirli bir zamanı kısıtlamazsanız, bu bir varlığın zaman içinde bulunduğu tüm konumları içeren bir rapora dönüşür
    Diğer join türleri de, şemayı zihninizde “döndürebilecek” kadar kavradığınızda bu varyasyon üzerinden daha kolay anlaşılır hale geliyor

    • Bu bana HyperDex'i hatırlattı. Değerleri öznitelik tabanlı olarak çok boyutlu hiperspace içine hash'leyip indeksleme için kullanıyor
      https://dbdb.io/db/hyperdex
    • Bu daha çok verinin aşırı normalizasyonu gibi görünüyor. Genelde BCNF ise bunu doğrudan EntityPosition(EntityId, X, Y, Z) gibi bir tabloda tutardım
      Yine de farklı boyut parçalarını birleştirme ve agregasyonlarla uğraşma tarafı veri ambarı dünyasını çağrıştırıyor
    • Neden JOIN, INNER JOIN gibi sözdizimleri kullandığımızı hep merak etmişimdir. Tabloları FROM içinde listeleyip join koşullarını WHERE bölümünde denklem gibi yazmak bana çok daha açık geliyor
      Karmaşık FROM bölümlerinde birden çok JOIN karışınca okumak zorlaşıyor; eşitlik koşullarını WHERE içinde okumak daha sezgisel geliyor
    • Tüm join'leri aslında cross join'in bir varyasyonu olarak anlamak doğru mu diye merak ediyorum
    1. bakış açısı şu: “join, ilişkisel cebirin bir operatörüdür”
      https://en.m.wikipedia.org/wiki/Relational_algebra
      Doğal join R ⋈ S, ortak öznitelik adları aynı olan tuple kombinasyonlarının kümesidir ve mantıksal AND'ye karşılık gelen ilişkisel işlemdir
      ⋈, sonuca girmemesi gereken satırları bir yüklemle filtreleyen Kartezyen çarpım olarak görülebilir; SQL'in büyük bir kısmı bu açıdan bakınca iyi anlaşılıyor
    • İlişki teorisinin işlevsel yorumunda join bir fonksiyon bileşimi, bu bakış açısının atlanmış olması şaşırtıcı
    • “Satırlar üzerinde nested loop” açıklamasının içinde zaten cross product + predicate bakışı var

  • Birkaç gündür query execution / planning implementation materyali arıyorum ama yüklem, mevcut indeksler ve join gibi uygulama tarafına dair kaynak bulmak zor
    Google arama sonuçları kullanım odaklı içeriklerle kirlenmiş durumda
    Şimdiye kadar yalnızca CMU Database Group materyallerini bulabildim; onlar da gerçekten mükemmel

    • Bu konuda 700 sayfalık ücretsiz bir kitap var: “Building Query Compilers”
      https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
      TUM'un “Database Systems on Modern CPU Architectures” dersi de yardımcı olabilir; 2020 materyallerinde tam video dersler de var
      https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
    • Aradığınız derinliğe uyar mı bilmiyorum ama SQLite'ın optimizasyon genel bakışı ve query planner belgeleri bakmaya değer
      https://www.sqlite.org/optoverview.html
      https://www.sqlite.org/queryplanner.html
    • Böyle durumlarda sık sık Postgres dokümantasyonu ve kaynak kodunu okumayı öneririm. Kaynak kodu da oldukça okunabilir
      https://www.postgresql.org/docs/current/planner-optimizer.ht...
    • Bu oldukça uzmanlık isteyen bir konu; iyi bir ders kitabı bulmak zor ve ne kadar derine inmek istediğinize ve hangi kısımla ilgilendiğinize göre değişiyor
      Query execution ve query planning aslında neredeyse ayrı konular
      Join optimizasyonu makaleleri arasında hâlâ orijinal Selinger makalesinin en iyisi olduğunu düşünüyorum
      https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
      Outer join desteği yok ve daha verimli teknikler geliştirildi, ama System R tarzı optimizer'lara bakan biri için hâlâ çok tanıdık geliyor
      Postgres'in src/backend/optimizer/README dosyasında da başka yerde zor bulunacak çok şey var
      CMU'dan Andy Pavlo'nun dersleri, bu konuları internette anlatan neredeyse tek kaynak sayılır; “Building Query Compilers” PDF'i eksik olsa da Moerkotte ve diğerlerinin temel makalelerini içerdiğinden modern uygulamalar için bakmaya değer
      Uygulanabilir indeksleri bulmak genelde sargable predicate olup olmadığına bakılarak yapılabildiği için çok zor değil, ama seçicilik tahmini zordur ve join sonrasındaki seçicilik tahmini optimizer'ın en zor problemlerinden biridir
      Örneğin A=x AND B=y AND C=z varsa ve yalnızca (A,B), (B,C) indekslerinin seçicilik / cardinality bilgileri varsa, üç koşulun birlikte seçiciliğinin nasıl tahmin edileceği hiç de basit değildir
      Bunu çözmek için “second-order cone programming” çözücüsü gerektiren makaleler bile var
    • Arama sorgusunun başına relational algebra ekleyip query planning aratınca, kabaca bakınca bile uygulama tarafına dönük daha fazla sonuç çıkıyor
    1. yöntem çoklu join ve buna “en kötü durumda optimal join” de deniyor, ama isim pek iyi değil
      Bu, tabloları ikişer ikişer join’leyip sürekli ara sonuçlar üretmek yerine, 3 veya daha fazla tabloyu ara sonuç olmadan birlikte join’lemek anlamına geliyor
      İlgili blog yazısı ve kısa video https://relational.ai/blog/dovetail-join adresinde, orijinal makale ise https://dl.acm.org/doi/pdf/10.1145/3180143 adresinde
      RelationalAI'da çalışıyorum; akademide yaklaşık 10 yıldır araştırılan bu yeni join algoritmasını biz ve birkaç başka yeni veritabanı şirketi pazara taşıyoruz
    • Justin’in WCOJ tanıtım yazısı da oldukça iyi
      https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
    • Girdiyi olumsuzlayıp, yani kümenin tümleyenine çevirirseniz, join’deki AND, NOR olur ve Tetris bundan yararlanır
      En kötü durum sınırı, durumsuz/streaming WCOJ’a kıyasla daha da sıkılaşmıyor, ancak gerçek veriler çoğu zaman çok daha küçük box certificate’lara sahip oluyor
      Dovetail join’in özyinelemeli sorguları, yani yalnızca çıktı ilişkisini belirtip ara ilişkileri motorun kendisinin yönettiği keyfi datalog’u destekleyip desteklemediğini görmedim
      Bu tür sorguları destekleyip desteklemediğini merak ediyorum

  • İlişkisel modelin inceliklerini özellikle uygulama seviyesi geliştiricilere gösteren bu tür yazılar daha fazla olmalı
    Fonksiyonel programlama bakış açısından yapılan açıklama ve inceleme de kısa ve ikna edici

  • N+1 problemini öğretmek için bir fırsat daha kaçırılmış gibi görünüyor
    Cluster edilmemiş bir indekse join yapmak da hâlâ N+1’dir; sadece ağ ve disk arasında gidip gelen N+1 değil, disk üzerindeki N+1’dir

    • “Benim ilgilendiğim X problemini ele almalıydı, o zaman yazı uzasa da sorun olmazdı” deniyormuş gibi geliyor

  • Inner join, koşullu bir Kartezyen çarpımdır

    • Kartezyen çarpım oluşturup sonra koşulla filtrelemek ile, koşulu doğrudan üretmek arasında büyük performans farkı vardır
      Eşitlik join koşuluna sahip inner join’ler koşulu doğrudan üretir; eşitsizlik join koşulları ise gerçek değerlendirme gerektirir

  • Güzel bir açıklama. “Doğru yöntem tabloları normalize etmektir” sözü işlemsel veritabanları için doğru, ancak veri ambarlarında belli ölçüde denormalizasyon yaygın biçimde kabul görüyor

  • Normalizasyon örneğini görünce, tabloları string yerine sayısal birincil anahtarların daha hızlı olduğunu düşünerek tasarladığımız günleri hatırladım
    Sonra anlamsız id alanları ortaya çıkıyordu ve aslında istediğiniz benzersiz değeri elde etmek için join gerekiyordu
    Bir gün, iki tabloda aynı benzersiz anahtarı kullanmanın join sayısını azaltabileceğini fark ettim; basitti ama etkiliydi

    • Yine de her tabloda benzersiz bir id alanı bulundurmayı seviyorum. Loglama için yardımcı oluyor ve birden fazla alandan oluşan “gerçek” anahtarla uğraşmak gerekmiyor
      Bunun yerine string değerler üzerinde benzersiz indeks tutuyor ve daha da önemlisi bütünlük kısıtlarını oraya koyuyorum
      Anlamlı string’lerle dolu tablolar, sayısal id ya da UUID’lerle dolu tablolardan çok daha okunaklıdır