(RDB) 13 Cara Memahami Join

• Inner join dalam basis data relasional dapat dipahami bukan hanya sebagai sintaks SQL sederhana, tetapi sebagai struktur yang sama yang ditafsirkan berbeda dari sudut pandang kueri, nested loop, model logika, pemeriksaan tipe, dan aljabar
• Dalam tabel yang ternormalisasi, join menjadi alat paling praktis untuk mengikuti referensi dan menggabungkan kembali informasi yang disimpan tanpa duplikasi
• Dari sudut pandang implementasi, ini bisa dilihat sebagai menelusuri pasangan baris dan hanya menyisakan kombinasi yang memenuhi kondisi, atau memilih hanya kombinasi nilai yang ada di kedua relasi dari domain kolom
• Dalam model pemrograman, join dapat dijelaskan dengan flatMap, SQL LATERAL, penyelesaian masalah N+1 pada ORM, pemeriksaan tipe berbasis trait Rust, dan andThen dari monad Set
• Secara matematis, jalur graf, model minimum, relasi terbesar yang diizinkan, batas atas terkecil pada himpunan berurutan parsial, dan hasil kali ring dari ekspresi relasional semuanya menyingkap sifat join yang sama

---

Pada data yang ternormalisasi, join menjadi kueri

• Secara paling praktis, join dapat dipandang sebagai operasi untuk mengambil suatu nilai, atau menambahkan informasi redundan ke data yang sudah ada
• Contohnya dimulai dari cara menyimpan user, country, dan country_code dalam satu tabel
  • Untuk setiap nilai country yang sama, country_code akan berulang sehingga menimbulkan duplikasi
  • Jika datanya sering berubah, semua lokasi harus diperbarui bersama-sama sehingga meningkatkan risiko kesalahan dan inefisiensi
• Dalam bentuk ternormalisasi, relasi antara country dan country_code dipisahkan ke tabel lain, dan tabel pengguna hanya mereferensikan country_id
• Jika users dan countries di-INNER JOIN dengan country_id, kita bisa mendapatkan kembali bentuk asli user, country, country_code
• Penjelasan selanjutnya mengasumsikan join implisit berdasarkan kolom dengan nama yang sama, tanpa terlalu terikat secara ketat pada detail sintaks SQL

Sudut pandang implementasi: join yang menelusuri baris dan kolom

• Jika ada dua himpunan R, S dan predikat p, maka join menelusuri semua r ∈ R, s ∈ S, lalu hanya mengeluarkan kasus ketika p(r, s) bernilai benar
  • Jika hasil kali Kartesius dari dua koleksi adalah semua kemungkinan penggabungan baris, maka join adalah subset yang memenuhi kondisi tersebut
• Jika dilihat per kolom, domain setiap kolom dianggap sebagai himpunan nilai yang mungkin, lalu kombinasi nilai kolom itu ditelusuri
  • Jika ada R(a, b) dan S(b, c), maka domain a, b, c ditelusuri
  • Hanya ketika (a, b) ada di R dan (b, c) ada di S, maka [a, b, c] dikeluarkan

Join sebagai realitas alternatif yang saling kompatibel

• Contoh John dan Sally menjelaskan join sebagai cara menyisakan hanya realitas yang saling kompatibel ketika masing-masing hanya memiliki sebagian informasi
• John mengetahui kemungkinan kombinasi antara hewan peliharaannya dan hewan liar, dan Sally juga memiliki kemungkinan kombinasi antara hewan peliharaannya dan hewan liar
  • Jika John memiliki dog saat hewan liar itu dog, dan Sally memiliki cat saat hewan liar itu mouse, keduanya tidak mungkin benar secara bersamaan
  • Karena keduanya harus mengamati hewan liar yang sama
• Jika dua tabel di-join berdasarkan stray, maka hanya kombinasi pet John · stray · pet Sally yang tidak saling bertentangan yang akan tersisa

Join dalam model pemrograman

• flatMap adalah fungsi yang membuat array baru untuk setiap elemen array asal lalu menggabungkan hasilnya, dan ini dapat digunakan untuk mengimplementasikan join
  • SELECT * FROM r INNER JOIN s ON p dapat dinyatakan sebagai r.flatMap(x => s.filter(y => p(x, y)))
  • Sintaks LATERAL pada beberapa varian SQL mengubah join menjadi bentuk flatMap
• Jika sisi kanan LATERAL tidak mereferensikan kolom di sisi kiri, maka hasilnya setara dengan hasil kali Kartesius
  • Decorrelation kueri bergantung pada penghapusan referensi kolom di sisi kanan melalui serangkaian penulisan ulang bertahap
• Masalah N+1 yang umum pada ORM juga dapat dijelaskan lewat join
  • Jika kueri tambahan dijalankan untuk setiap baris di himpunan hasil, maka pada basis data yang memakai koneksi seperti Postgres, biaya tetap tiap kueri individual menjadi besar
  • Hasil dari meminta basis data untuk “menjalankan semua pengambilan ini sekaligus” adalah join seperti users INNER JOIN countries
  • Pada basis data in-process seperti Sqlite, masalah ini tidak terlalu besar

Jalur graf dan model logika

• Karena relasi “menghubungkan” dua himpunan, relasi dapat dipandang sebagai graf
  • Tabel users menghubungkan himpunan nama pengguna dengan himpunan country_id
  • Relasi yang menghubungkan country_id dan kode negara dua huruf juga dapat digambarkan sebagai graf terpisah
• Jika himpunan di sisi kanan graf pertama dan himpunan di sisi kiri graf kedua berbagi vertex set yang sama, keduanya dapat dipandang sebagai satu kesatuan
• Jika kita mencantumkan semua jalur dari himpunan kiri, melalui vertex tengah, ke himpunan kanan, itulah join dari kedua relasi tersebut
• Dalam logika formal, relasi dipandang sebagai predikat, dan model adalah himpunan fakta yang membuat sekumpulan kalimat menjadi benar
  • Jika users(A, B) dan countries(B, C, D) benar, maka ada implikasi bahwa Q(A, B, C, D) benar
  • Bisa ada banyak model yang memenuhi kondisi ini
  • Untuk memperoleh hasil yang standar, dipilih model terkecil di antara model-model yang memenuhi kondisi itu
  • Model terkecil ini sama dengan hasil join users dan country

Join sebagai pemeriksaan tipe

• Sistem tipe bergaya ML sangat mirip dengan Prolog dan Datalog, sehingga dapat diekspresikan dengan cara yang mirip join
• Dalam contoh Rust, relasi didefinisikan sebagai trait
  • Users dan CountryCode berperan sebagai relasi
  • Smudge, Sissel, Petee, Canada, UnitedStates, CA, US didefinisikan sebagai tipe konkret
• Implementasi trait seperti (Smudge, Canada): Users dan (Canada, CA): CountryCode setara dengan baris dalam relasi
• Agar (A, B, C) termasuk dalam join, harus berlaku (A, B): Users dan (B, C): CountryCode
• test::<(Smudge, _, CA)>() lolos pemeriksaan tipe, tetapi test::<(Smudge, _, US)>() gagal karena (Canada, US): CountryCode tidak diimplementasikan

Join sebagai operasi monad Set

• Contoh Some dan None di JavaScript dimulai dari cara menggabungkan record opsional
  • Jika dua record memiliki country yang sama, keduanya digabung dan Some dikembalikan
  • Jika tidak kompatibel atau nilainya tidak ada, None dikembalikan
• andThen membuka nilai di dalam optional lalu menerapkan fungsi penggabungan
• Dengan tetap memakai fungsi combine yang sama, container bisa diubah menjadi Rel untuk memproses himpunan relasi
  • Rel.map menerapkan fungsi ke semua baris
  • Rel.andThen menggabungkan relasi yang dihasilkan dari tiap baris dengan flatMap
• Jika fungsi combine yang sama dijalankan pada relasi users dan countries, hasilnya adalah join dengan kode negara yang ditambahkan ke Smudge, Sissel, dan Petee

Relasi terbesar yang diizinkan dan join pada himpunan berurutan parsial

• Relasi ketiga T yang memiliki semua kolom dari dua relasi R, S didefinisikan sebagai diizinkan jika ia tidak menciptakan informasi baru
  • Jika suatu baris dari T dibatasi ke kolom milik R, maka baris itu harus ada di R
  • Dengan cara yang sama, jika dibatasi ke kolom milik S, maka baris itu juga harus ada di S
• Sebagai contoh, Smudge, Canada, US tidak diizinkan
  • Jika hanya dilihat dari country, country_code, hasilnya menjadi Canada, US, dan itu bukan baris yang ada di S
• Relasi kosong juga diizinkan, tetapi relasi terbesar yang diizinkan memuat Smudge-Canada-CA, Sissel-Canada-CA, Petee-United States-US
• Relasi terbesar yang diizinkan inilah join dari dua relasi tersebut
• Dari sudut pandang himpunan berurutan parsial, R ≤ Q didefinisikan sebagai berikut
  • Q memuat semua kolom milik R
  • Jika setiap baris Q dibatasi ke kolom milik R, hasilnya adalah baris di R
• Dalam himpunan berurutan parsial ini, terdapat batas atas terkecil R ∨ S dari dua relasi R, S, dan ini memiliki makna yang sama dengan join relasional

Join sebagai hasil kali ring

• Relasi juga dapat dinyatakan secara aljabar
  • Satu baris direpresentasikan sebagai hasil kali pasangan kolom-nilai
  • Satu relasi direpresentasikan sebagai penjumlahan dari beberapa baris
• Sebagai contoh, suku hasil kali dari user = Smudge dan country_id = 1 menjadi satu baris
• Aturan tambahan diperkenalkan untuk menyederhanakan ekspresi
  • Idempotence: [x = y][x = y] = [x = y]
  • Contradiction: [x = y][x = z] = 0 if y ≠ z
• Jika relasi pengguna R dan relasi lookup negara S dikalikan lalu dikembangkan dengan hukum distributif dan komutatif, maka suku-suku yang bertentangan akan hilang dan hanya suku yang kompatibel yang tersisa
• Ekspresi yang tersisa adalah Smudge-1-Canada-CA, Sissel-1-Canada-CA, Petee-2-United States-US, dan ini tepat sama dengan join dua relasi tersebut
• Cara ini juga dapat dipandang sebagai tensor contraction

[GN⁺]

Komentar Hacker News

• Begitu mulai memikirkan join dalam dimensi ruang, konsepnya jadi jauh lebih mudah dipahami
  Jika setiap dimensi dipisah ke tabel berbeda seperti Dim_X, Dim_Y, Dim_Z lalu diikat dengan EntityId yang sama, itu bisa dilihat sebagai cara menyusun posisi 3 dimensi suatu entitas
  Untuk membuat 3 dimensi, dibutuhkan setidaknya 2 inner join, dan dimensi nonspasial seperti waktu juga bisa diperluas dengan cara yang sama
  Jika waktu tertentu tidak dibatasi, hasilnya menjadi laporan yang memuat semua posisi yang pernah ditempati satu entitas seiring waktu
  Tipe join lain juga jadi lebih mudah dipahami sebagai variasi dari ini jika konsep skemanya sudah cukup tertanam sampai bisa “memutar” skema itu di kepala

  • Ini mengingatkan pada HyperDex. Pendekatannya adalah melakukan hashing nilai berbasis atribut ke dalam ruang hiper multidimensi untuk dipakai sebagai indeks
    https://dbdb.io/db/hyperdex
  • Ini tampaknya lebih dekat ke hipernormalisasi data. Biasanya kalau BCNF, saya mungkin cukup memakai tabel seperti EntityPosition(EntityId, X, Y, Z)
    Tetapi dari sisi menyusun potongan berbagai dimensi dan menangani agregasi, ini mengingatkan pada data warehouse
  • Saya selalu bertanya-tanya kenapa harus memakai sintaks seperti JOIN, INNER JOIN. Menuliskan tabel di FROM lalu menaruh kondisi join di klausa WHERE sebagai persamaan terasa jauh lebih jelas
    Kalau ada banyak JOIN bercampur di klausa FROM yang kompleks, itu sulit dibaca, dan membaca ekspresi kondisi yang setara di WHERE terasa lebih intuitif
  • Saya penasaran apakah semua join sebaiknya dipahami sebagai variasi dari cross join

• Sudut pandang ke-0 adalah bahwa “join adalah operator dalam aljabar relasional”
  https://en.m.wikipedia.org/wiki/Relational_algebra
  Natural join R ⋈ S adalah himpunan kombinasi tuple yang memiliki nama atribut bersama yang sama, dan merupakan operasi relasional yang berpadanan dengan logical AND
⋈ bisa dipandang sebagai hasil kali Kartesius yang memfilter baris-baris yang tidak boleh masuk ke hasil melalui predikat, dan banyak bagian SQL jadi lebih mudah dipahami dari sudut pandang ini

  • Dalam penafsiran fungsional teori relasional, join adalah komposisi fungsi, jadi agak mengejutkan sudut pandang itu tidak dibahas
  • Penjelasan “nested loop atas baris” sudah mencakup sudut pandang cross product + predikat

• Sudah beberapa hari saya mencari materi tentang implementasi eksekusi/perencanaan query, tetapi sulit menemukan materi implementasi soal predikat, indeks yang ada, dan join
  Hasil pencarian Google tercemar oleh materi penggunaan
  Sejauh ini yang saya temukan hanya materi dari CMU Database Group, dan itu sangat bagus

  • Ada buku gratis 700 halaman tentang topik ini: “Building Query Compilers”
    https://pi3.informatik.uni-mannheim.de/~moer/querycompiler.p...
    Kuliah TUM “Database Systems on Modern CPU Architectures” juga mungkin membantu, dan materi tahun 2020 punya rekaman kuliah lengkap
    https://db.in.tum.de/teaching/ss20/moderndbs/?lang=en
  • Saya tidak yakin ini sedalam yang Anda inginkan, tetapi ringkasan optimisasi dan dokumen query planner SQLite layak dibaca
    https://www.sqlite.org/optoverview.html
    https://www.sqlite.org/queryplanner.html
  • Dalam situasi seperti ini, sering disarankan untuk membaca dokumentasi dan source code Postgres. Source code-nya juga cukup enak dibaca
    https://www.postgresql.org/docs/current/planner-optimizer.ht...
  • Ini topik yang cukup khusus, jadi sulit menemukan buku teks yang bagus, dan banyak bergantung pada seberapa dalam Anda ingin masuk serta bagian mana yang Anda minati
    Eksekusi query dan perencanaan query pada praktiknya hampir merupakan hal yang terpisah
    Untuk makalah optimisasi join, menurut saya makalah Selinger yang asli masih yang terbaik
    https://courses.cs.duke.edu/compsci516/cps216/spring03/paper...
    Memang tidak mendukung outer join dan teknik yang lebih efisien sudah muncul, tetapi bagi siapa pun yang melihat optimizer keluarga System R, makalah itu masih terasa familier
    src/backend/optimizer/README milik Postgres juga berisi banyak hal yang sulit ditemukan di tempat lain
    Kuliah Andy Pavlo dari CMU nyaris menjadi satu-satunya materi online yang benar-benar menjelaskan hal ini, dan PDF “Building Query Compilers”, meski tidak lengkap, memuat makalah inti Moerkotte dkk., jadi layak dibaca kalau ingin membuat implementasi modern
    Mencari indeks yang bisa diterapkan biasanya tidak terlalu sulit karena cukup melihat apakah ada sargable predicate, tetapi estimasi selektivitas itu sulit, dan estimasi selektivitas setelah join termasuk masalah tersulit dalam optimizer
    Misalnya, jika ada A=x AND B=y AND C=z dan hanya tersedia informasi selektivitas/kardinalitas untuk indeks (A,B) dan (B,C), memperkirakan selektivitas gabungan dari ketiga kondisi itu bukan masalah yang sederhana
    Bahkan ada makalah yang menuntut solver untuk “second-order cone programming” demi menyelesaikan ini
  • Saya mencoba menambahkan relational algebra di depan kata kunci lalu mencari query planning, dan sekilas pun terlihat hasil yang lebih banyak mengarah ke implementasi

• Cara ke-14 adalah multi-join, juga disebut “join optimal kasus terburuk”, tetapi namanya kurang bagus
  Artinya, alih-alih menggabungkan tabel dua per dua sambil terus membuat hasil antara, 3 tabel atau lebih digabungkan sekaligus tanpa hasil antara
  Ada tulisan blog terkait dan video singkat di https://relational.ai/blog/dovetail-join, dan makalah aslinya ada di https://dl.acm.org/doi/pdf/10.1145/3180143
  Saya bekerja di RelationalAI, dan algoritme join baru ini, yang telah diteliti di dunia akademik selama sekitar 10 tahun, sedang kami dan beberapa perusahaan database rintisan lain bawa ke pasar

  • Tulisan pengantar Justin tentang WCOJ juga cukup bagus
    https://justinjaffray.com/a-gentle-ish-introduction-to-worst...
  • Jika input dinegasikan, yaitu diubah menjadi komplemen himpunan, maka AND pada join menjadi NOR, dan Tetris memanfaatkan hal ini
    Batas kasus terburuk tidak menjadi lebih ketat daripada WCOJ stateless/streaming, tetapi data nyata sering kali memiliki sertifikat kotak yang jauh lebih kecil
    Saya belum melihat apakah dovetail join mendukung kueri rekursif, yaitu datalog arbitrer di mana hanya relasi output yang ditentukan dan relasi antara ditangani sendiri oleh mesin
    Saya penasaran apakah kueri semacam itu didukung

• Perlu lebih banyak tulisan seperti ini yang menunjukkan nuansa model relasional terutama kepada pengembang level aplikasi
  Penjelasan dan penelusuran dari sudut pandang pemrograman fungsional juga ringkas dan meyakinkan

• Sepertinya kesempatan lain untuk mengajarkan masalah N+1 terlewatkan
  Melakukan join ke indeks yang tidak terklaster juga tetap N+1, hanya saja N+1 di atas disk, bukan N+1 yang bolak-balik lewat jaringan dan disk

  • Terdengar seperti, “Saya harus membahas masalah X yang saya minati, dan kalau begitu artikelnya boleh jadi lebih panjang”

• Join internal adalah perkalian Kartesius dengan syarat

  • Ada perbedaan performa besar antara membuat perkalian Kartesius lalu menyaringnya dengan syarat, dan langsung menghasilkan syaratnya
    Join internal dengan kondisi equi-join langsung menghasilkan syaratnya, sedangkan kondisi non-equi join memerlukan evaluasi nyata

• Penjelasannya bagus. Pernyataan bahwa “cara yang benar adalah menormalkan tabel” benar untuk database transaksional, tetapi di data warehouse, tingkat denormalisasi tertentu diterima luas

• Contoh normalisasi itu mengingatkan saya pada masa ketika saya merancang tabel karena mengira kunci utama numerik lebih cepat daripada string
  Akibatnya muncul id yang tidak bermakna, dan untuk mendapatkan nilai unik yang sebenarnya diinginkan, perlu join
  Suatu hari saya menyadari bahwa memakai kunci unik yang sama di dua tabel bisa mengurangi join, dan itu sederhana tetapi efektif

  • Meski begitu, saya tetap suka punya field id unik di setiap tabel. Itu membantu untuk logging dan membuat saya tidak perlu memikirkan kunci “sebenarnya” yang terdiri dari beberapa field
    Sebagai gantinya, saya memasang indeks unik pada nilai string, dan yang lebih penting, menaruh batasan integritas di sana
    Tabel yang penuh string bermakna jauh lebih mudah dibaca daripada tabel yang penuh id numerik atau UUID