Kapan dan mengapa basis data bergabung mahal?

Saya sedang melakukan penelitian ke dalam database dan saya melihat beberapa keterbatasan DB relasional.

Saya mendapatkan bahwa bergabung dengan meja besar sangat mahal, tetapi saya tidak sepenuhnya yakin mengapa. Apa yang perlu dilakukan DBMS untuk menjalankan operasi gabungan, di mana bottleneck?
Bagaimana denormalisasi dapat membantu mengatasi pengeluaran ini? Bagaimana teknik pengoptimalan lainnya (pengindeksan, misalnya) membantu?

Pengalaman pribadi dipersilakan! Jika Anda akan memposting tautan ke sumber daya, harap hindari Wikipedia. Saya sudah tahu di mana menemukannya.

Sehubungan dengan ini, saya bertanya-tanya tentang pendekatan denormalized yang digunakan oleh database layanan cloud seperti BigTable dan SimpleDB. Lihat pertanyaan ini .

Dinormalisasi untuk meningkatkan kinerja? Kedengarannya meyakinkan, tetapi tidak menahan air.

Chris Date, yang bekerja sama dengan Dr Ted Codd adalah pendukung asli model data relasional, kehabisan kesabaran dengan argumen informasi yang salah terhadap normalisasi dan secara sistematis menghancurkan mereka menggunakan metode ilmiah: ia mendapatkan database besar dan menguji pernyataan ini.

Saya pikir dia menulis itu di Relational Database Tulisan 1988-1991 namun buku ini kemudian digulung menjadi edisi enam Pengantar Sistem Basis Data , yang merupakan satu teks definitif tentang teori database dan desain, dalam edisi kedelapan saat aku menulis dan kemungkinan akan tetap di cetak selama beberapa dekade yang akan datang. Chris Date adalah seorang ahli dalam bidang ini ketika kebanyakan dari kita masih berlarian tanpa alas kaki.

Dia menemukan bahwa:

• Beberapa dari mereka memegang kasus khusus
• Semuanya gagal membayar untuk penggunaan umum
• Semuanya secara signifikan lebih buruk untuk kasus-kasus khusus lainnya

Semuanya kembali untuk mengurangi ukuran set kerja. Gabungan yang melibatkan kunci yang dipilih dengan benar dengan indeks pengaturan yang benar adalah murah, tidak mahal, karena memungkinkan pemangkasan hasil yang signifikan sebelum baris terwujud.

Mewujudkan hasilnya melibatkan pembacaan disk massal yang merupakan aspek paling mahal dari latihan dengan urutan besarnya. Sebaliknya, melakukan penggabungan secara logis membutuhkan hanya pengambilan kunci . Dalam praktiknya, bahkan nilai kunci tidak diambil: nilai hash kunci digunakan untuk perbandingan gabungan, mengurangi biaya gabungan multi-kolom dan secara radikal mengurangi biaya sambungan yang melibatkan perbandingan string. Tidak hanya akan jauh lebih cocok di cache, ada banyak pembacaan disk yang harus dilakukan.

Selain itu, pengoptimal yang baik akan memilih kondisi yang paling ketat dan menerapkannya sebelum melakukan penggabungan, sangat efektif meningkatkan selektivitas tinggi dari gabungan pada indeks dengan kardinalitas tinggi.

Memang jenis optimisasi ini juga dapat diterapkan pada basis data yang dinormalisasi, tetapi jenis orang yang ingin mendenormalisasi skema biasanya tidak memikirkan kardinalitas ketika (jika) mereka membuat indeks.

Penting untuk memahami bahwa pemindaian tabel (pemeriksaan setiap baris dalam tabel selama menghasilkan gabungan) jarang dilakukan. Pengoptimal permintaan akan memilih pemindaian tabel hanya jika satu atau lebih dari yang berikut ini berlaku.

• Ada kurang dari 200 baris dalam hubungan (dalam hal ini pemindaian akan lebih murah)
• Tidak ada indeks yang sesuai pada kolom gabungan (jika bermakna untuk bergabung pada kolom ini, mengapa mereka tidak diindeks? Perbaiki)
• Suatu jenis pemaksaan diperlukan sebelum kolom dapat dibandingkan (WTF ?! perbaiki atau pulang) LIHAT CATATAN UNTUK ADO.NET MASALAH
• Salah satu argumen perbandingan adalah ekspresi (tanpa indeks)

Melakukan operasi lebih mahal daripada tidak melakukannya. Namun, melakukan operasi yang salah , dipaksa ke disk I / O yang tidak berguna dan kemudian membuang sampah sebelum melakukan penggabungan yang benar-benar Anda butuhkan, jauh lebih mahal. Bahkan ketika operasi "salah" dihitung dan indeks telah diterapkan dengan bijaksana, masih ada penalti yang signifikan. Menormalisasi untuk memulai bergabung - terlepas dari anomali pembaruan yang disyaratkan - adalah komitmen untuk bergabung tertentu. Jika Anda membutuhkan gabung yang berbeda , komitmen itu akan menelan biaya besar .

Jika ada yang ingin mengingatkan saya bahwa ini adalah dunia yang berubah, saya pikir Anda akan menemukan bahwa kumpulan data yang lebih besar pada perangkat keras yang lebih besar hanya melebih-lebihkan penyebaran temuan Date.

Untuk Anda semua yang bekerja pada sistem penagihan atau generator junk mail (malu pada Anda) dan dengan marah mengatur tangan ke keyboard untuk memberi tahu saya bahwa Anda tahu fakta bahwa denormalisasi lebih cepat, maaf tetapi Anda tinggal di salah satu tempat khusus case - khususnya, case di mana Anda memproses semua data, secara berurutan. Ini bukan kasus umum, dan Anda akan dibenarkan dalam strategi Anda.

Anda tidak dibenarkan menggeneralisasikannya secara keliru. Lihat bagian akhir catatan untuk informasi lebih lanjut tentang penggunaan denormalisasi yang tepat dalam skenario pergudangan data.

Saya juga ingin merespons

Bergabung hanyalah produk cartesian dengan beberapa lipgloss

Apa beban omong kosong. Pembatasan diterapkan sedini mungkin, paling membatasi dulu. Anda telah membaca teorinya, tetapi Anda belum memahaminya. Bergabung diperlakukan sebagai "produk cartesian yang predikatnya berlaku" hanya oleh pengoptimal permintaan. Ini adalah representasi simbolis (normalisasi, pada kenyataannya) untuk memfasilitasi dekomposisi simbolis sehingga optimizer dapat menghasilkan semua transformasi yang setara dan peringkat mereka berdasarkan biaya dan selektivitas sehingga dapat memilih rencana permintaan terbaik.

Satu-satunya cara Anda akan mendapatkan pengoptimal untuk menghasilkan produk kartesius adalah gagal memasok predikat: SELECT * FROM A,B

Catatan

David Aldridge memberikan beberapa informasi tambahan penting.

Memang ada berbagai strategi lain selain indeks dan pindaian tabel, dan pengoptimal modern akan menghabiskan semuanya sebelum membuat rencana eksekusi.

Saran praktis: jika dapat digunakan sebagai kunci asing, maka indekskan, sehingga strategi indeks tersedia untuk pengoptimal.

Saya dulu lebih pintar daripada pengoptimal MSSQL. Itu mengubah dua versi yang lalu. Sekarang ini biasanya mengajarkan saya . Ini, dalam arti yang sangat nyata, sistem pakar, mengkodifikasi semua kebijaksanaan banyak orang yang sangat pintar dalam domain yang cukup tertutup sehingga sistem berbasis aturan efektif.

"Bollocks" mungkin tidak bijaksana. Saya diminta untuk tidak terlalu angkuh dan diingatkan bahwa matematika tidak bohong. Ini benar, tetapi tidak semua implikasi model matematika harus diambil secara harfiah. Akar kuadrat dari angka negatif sangat berguna jika Anda dengan hati-hati menghindari memeriksa absurditasnya (pun ada) dan pastikan Anda membatalkan semuanya sebelum Anda mencoba menafsirkan persamaan Anda.

Alasan saya merespons dengan sangat kejam adalah karena pernyataan seperti yang dikatakan mengatakan itu

Bergabung adalah produk kartesius ...

Ini mungkin bukan apa yang dimaksudkan tetapi itu adalah apa yang ditulis, dan itu pasti tidak benar. Produk kartesius adalah suatu hubungan. Gabung adalah fungsi. Lebih khusus lagi, gabungan adalah fungsi yang dihargai relasi. Dengan predikat kosong, itu akan menghasilkan produk kartesius, dan memeriksa apakah itu adalah pemeriksaan kebenaran untuk mesin query basis data, tetapi tidak ada yang menulis gabungan yang tidak dibatasi dalam praktik karena mereka tidak memiliki nilai praktis di luar ruang kelas.

Saya menyebut ini karena saya tidak ingin pembaca jatuh ke dalam perangkap kuno yang membingungkan model dengan model yang dibuat. Model adalah perkiraan, sengaja disederhanakan untuk manipulasi yang mudah.

Cut-off untuk pemilihan strategi join table-scan dapat bervariasi di antara mesin basis data. Hal ini dipengaruhi oleh sejumlah keputusan implementasi seperti tree-node fill-factor, ukuran nilai kunci dan seluk-beluk algoritma, tetapi secara umum indeks kinerja tinggi memiliki waktu eksekusi k log n + c . Istilah C adalah overhead tetap yang sebagian besar terbuat dari waktu setup, dan bentuk kurva berarti Anda tidak mendapatkan hasil (dibandingkan dengan pencarian linier) sampai n ada dalam ratusan.

Terkadang denormalisasi adalah ide yang bagus

Denormalisasi adalah komitmen terhadap strategi bergabung tertentu. Seperti yang disebutkan sebelumnya, ini mengganggu strategi bergabung lainnya . Tetapi jika Anda memiliki ember ruang disk, pola akses yang dapat diprediksi, dan kecenderungan untuk memproses banyak atau semuanya, maka mengkompilasi gabungan bisa sangat bermanfaat.

Anda juga dapat mengetahui jalur akses yang biasanya digunakan operasi Anda dan melakukan prakompilasi semua gabungan untuk jalur akses tersebut. Ini adalah premis di belakang gudang data, atau setidaknya ketika dibangun oleh orang-orang yang tahu mengapa mereka melakukan apa yang mereka lakukan, dan bukan hanya demi kepatuhan kata kunci.

Gudang data yang dirancang dengan baik diproduksi secara berkala oleh transformasi massal dari sistem pemrosesan transaksi yang dinormalisasi. Pemisahan operasi dan basis data pelaporan ini memiliki efek yang sangat diinginkan untuk menghilangkan bentrokan antara OLTP dan OLAP (pemrosesan transaksi online yaitu entri data, dan pemrosesan analitis online yaitu pelaporan).

Poin penting di sini adalah bahwa selain dari pembaruan berkala, gudang data hanya dibaca . Ini membuat saya mempermasalahkan masalah pembaruan anomali.

Jangan membuat kesalahan dengan melumpuhkan basis data OLTP Anda (database tempat entri data terjadi). Mungkin lebih cepat untuk penagihan berjalan tetapi jika Anda melakukannya, Anda akan mendapatkan pembaruan anomali. Pernah mencoba membuat Reader's Digest berhenti mengirim barang kepada Anda?

Ruang disk saat ini murah, jadi hancurkan diri Anda. Tetapi denormalising hanya bagian dari cerita untuk gudang data. Keuntungan kinerja yang jauh lebih besar berasal dari nilai-nilai digulung yang telah diperhitungkan: total bulanan, hal semacam itu. Itu selalu tentang mengurangi set kerja.

Masalah ADO.NET dengan tipe ketidakcocokan

Misalkan Anda memiliki tabel SQL Server yang berisi kolom indeks tipe varchar, dan Anda menggunakan AddWithValue untuk melewatkan parameter yang membatasi kueri pada kolom ini. String C # adalah Unicode, jadi tipe parameter yang disimpulkan adalah NVARCHAR, yang tidak cocok dengan VARCHAR.

VARCHAR ke NVARCHAR adalah konversi pelebaran sehingga terjadi secara implisit - tetapi mengucapkan selamat tinggal pada pengindeksan, dan semoga berhasil mencari tahu mengapa.

"Hitung hit disk" (Rick James)

Jika semuanya di-cache dalam RAM, JOINsagak murah. Artinya, normalisasi tidak memiliki banyak penalti kinerja .

Jika skema "dinormalisasi" menyebabkan JOINsbanyak disk, tetapi skema "denormalized" yang setara tidak harus mengenai disk, maka denasionalisasi memenangkan persaingan kinerja.

Komentar dari penulis asli: Mesin database modern sangat baik mengatur pengurutan akses untuk meminimalkan kesalahan cache selama operasi gabungan. Sementara di atas, sementara benar, mungkin salah dikartikan sebagai menyiratkan bahwa bergabung tentu mahal pada data besar. Hal ini akan menyebabkan pengambilan keputusan yang buruk di pihak pengembang yang tidak berpengalaman.

Apa yang gagal dicatat oleh kebanyakan komentator adalah beragamnya metodologi bergabung yang tersedia dalam RDBMS yang kompleks, dan para penyangkal selalu mengabaikan biaya yang lebih tinggi untuk memelihara data yang dinormalisasi. Tidak setiap gabung didasarkan pada indeks, dan database memiliki banyak algotitma dan metodologi yang dioptimalkan untuk bergabung yang dimaksudkan untuk mengurangi biaya gabung.

Bagaimanapun, biaya bergabung tergantung pada jenisnya dan beberapa faktor lainnya. Tidak perlu mahal sama sekali - beberapa contoh.

• Gabung hash, di mana data massal disamakan, memang sangat murah, dan biaya hanya menjadi signifikan jika tabel hash tidak dapat di-cache dalam memori. Tidak diperlukan indeks. Partisi-partisi antara set data yang digabungkan dapat sangat membantu.
• Biaya gabungan semacam-didorong didorong oleh biaya semacam itu daripada gabungan - metode akses berbasis indeks hampir dapat menghilangkan biaya semacam itu.
• Biaya gabungan loop bersarang pada indeks didorong oleh ketinggian indeks b-tree dan akses dari blok tabel itu sendiri. Ini cepat, tetapi tidak cocok untuk sambungan massal.
• Gabung loop bersarang berdasarkan cluster jauh lebih murah, dengan logika IO lebih sedikit diperlukan per baris bergabung - jika tabel bergabung keduanya di cluster yang sama maka bergabung menjadi sangat murah melalui colocation dari baris bergabung.

Basis data dirancang untuk bergabung, dan mereka sangat fleksibel dalam cara mereka melakukannya dan umumnya sangat berkinerja kecuali jika mereka salah dalam mekanisme join.

Saya pikir seluruh pertanyaan didasarkan pada premis yang salah. Bergabung di meja besar belum tentu mahal. Faktanya, melakukan penggabungan secara efisien adalah salah satu alasan utama basis data relasional ada . Bergabung pada set besar sering mahal, tetapi sangat jarang Anda ingin bergabung dengan seluruh isi tabel besar A dengan seluruh isi tabel besar B. Sebaliknya, Anda menulis kueri sehingga hanya baris - baris penting dari setiap tabel yang digunakan dan set aktual yang disimpan oleh join tetap lebih kecil.

Selain itu, Anda memiliki efisiensi yang disebutkan oleh Peter Wone, sehingga hanya bagian-bagian penting dari setiap catatan yang perlu ada dalam memori sampai hasil akhir ditetapkan. Selain itu, dalam kueri besar dengan banyak penggabungan, Anda biasanya ingin memulai dengan set tabel yang lebih kecil dan bekerja hingga yang besar, sehingga set yang disimpan dalam memori tetap sekecil mungkin selama mungkin.

Ketika dilakukan dengan benar, gabungan biasanya merupakan cara terbaik untuk membandingkan, menggabungkan, atau memfilter data dalam jumlah besar.

Kemacetan hampir selalu disk I / O, dan bahkan lebih khusus - disk I / O acak (sebagai perbandingan, pembacaan berurutan cukup cepat dan dapat di-cache dengan strategi read depan).

Bergabung dapat meningkatkan pencarian acak - jika Anda melompat membaca sebagian kecil dari sebuah meja besar. Namun, pengoptimal kueri mencari itu dan akan mengubahnya menjadi pemindaian tabel berurutan (membuang baris yang tidak dibutuhkan) jika dianggap lebih baik.

Tabel denormalized tunggal memiliki masalah yang sama - barisnya besar, dan kurang pas di satu halaman data. Jika Anda membutuhkan baris yang terletak jauh dari yang lain (dan ukuran baris yang besar membuatnya terpisah jauh) maka Anda akan memiliki I / O yang lebih acak. Sekali lagi, pemindaian tabel mungkin terpaksa untuk menghindari ini. Tapi, kali ini, pemindaian tabel Anda harus membaca lebih banyak data karena ukuran baris yang besar. Tambahkan ke fakta bahwa Anda menyalin data dari satu lokasi ke beberapa lokasi, dan RDBMS memiliki lebih banyak untuk dibaca (dan cache).

Dengan 2 tabel, Anda juga mendapatkan 2 indeks berkerumun - dan umumnya dapat mengindeks lebih banyak (karena lebih sedikit memasukkan / memperbarui overhead) yang dapat membuat Anda meningkatkan kinerja secara drastis (terutama, sekali lagi, karena indeks (relatif) kecil, cepat untuk membaca dari disk (atau murah untuk di-cache), dan kurangi jumlah baris tabel yang perlu Anda baca dari disk).

Tentang satu-satunya overhead dengan bergabung berasal dari mencari tahu baris yang cocok. Sql Server menggunakan 3 jenis gabungan, terutama berdasarkan ukuran dataset, untuk menemukan baris yang cocok. Jika pengoptimal memilih tipe gabungan yang salah (karena statistik yang tidak akurat, indeks yang tidak memadai, atau hanya bug pengoptimal atau casing tepi) pengoptimal dapat secara drastis mempengaruhi waktu kueri.

• Gabung loop jauh lebih murah untuk (setidaknya 1) dataset kecil.
• Penggabungan gabung membutuhkan jenis kedua dataset terlebih dahulu. Jika Anda bergabung pada kolom yang diindeks, maka indeks sudah diurutkan dan tidak ada pekerjaan lebih lanjut yang perlu dilakukan. Kalau tidak, ada beberapa CPU dan memori overhead dalam penyortiran.
• Gabung hash membutuhkan memori (untuk menyimpan hashtable) dan CPU (untuk membangun hash). Sekali lagi, ini cukup cepat dalam kaitannya dengan disk I / O. Namun , jika tidak ada cukup RAM untuk menyimpan hashtable, Sql Server akan menggunakan tempdb untuk menyimpan bagian dari hashtable dan baris yang ditemukan, dan kemudian hanya memproses bagian dari hashtable pada suatu waktu. Seperti halnya semua disk, ini cukup lambat.

Dalam kasus optimal, ini tidak menyebabkan disk I / O - dan dapat diabaikan dari perspektif kinerja.

Semua dalam semua, paling buruk - itu sebenarnya harus lebih cepat untuk membaca jumlah yang sama dari data logis dari x bergabung tabel, seperti itu dari satu tabel denormalized karena disk lebih kecil membaca. Untuk membaca jumlah data fisik yang sama , mungkin ada sedikit overhead.

Karena waktu kueri biasanya didominasi oleh biaya I / O, dan ukuran data Anda tidak berubah (minus beberapa overhead baris yang sangat kecil) dengan denormalisasi, tidak ada banyak manfaat yang bisa didapat dengan hanya menggabungkan tabel bersama. Jenis denormalisasi yang cenderung meningkatkan kinerja, IME, adalah caching nilai yang dihitung alih-alih membaca 10.000 baris yang diperlukan untuk menghitungnya.

Urutan di mana Anda bergabung dengan tabel sangat penting. Jika Anda memiliki dua set data, coba buat kueri dengan cara sehingga yang terkecil akan digunakan terlebih dahulu untuk mengurangi jumlah data yang harus dikerjakan kueri.

Untuk beberapa database itu tidak masalah, misalnya MS SQL memang tahu urutan bergabung yang tepat sebagian besar waktu. Untuk beberapa (seperti IBM Informix) pesanan membuat semua perbedaan.

Memutuskan apakah akan mendenormalisasi atau menormalkan adalah proses yang cukup mudah ketika Anda mempertimbangkan kelas kompleksitas dari join. Sebagai contoh, saya cenderung mendesain basis data saya dengan normalisasi ketika kueri adalah O (k log n) di mana k relatif terhadap besaran keluaran yang diinginkan.

Cara mudah untuk mendenormalisasi dan mengoptimalkan kinerja adalah dengan memikirkan bagaimana perubahan pada struktur normalisasi Anda memengaruhi struktur denormalisasi Anda. Namun dapat menjadi masalah karena mungkin memerlukan logika transaksional untuk bekerja pada struktur yang didenormalized.

Perdebatan untuk normalisasi dan denormalisasi tidak akan berakhir karena masalahnya sangat luas. Ada banyak masalah di mana solusi alami membutuhkan kedua pendekatan.

Sebagai aturan umum, saya selalu menyimpan struktur yang dinormalisasi dan cache denormalized yang dapat direkonstruksi. Akhirnya, cache ini menyelamatkanku untuk menyelesaikan masalah normalisasi di masa depan.

Menguraikan apa yang dikatakan orang lain,

Bergabung hanyalah produk cartesian dengan beberapa lipgloss. {1,2,3,4} X {1,2,3} akan memberi kita 12 kombinasi (nXn = n ^ 2). Himpunan yang dihitung ini bertindak sebagai referensi tentang kondisi yang diterapkan. DBMS menerapkan kondisi (seperti di mana kiri dan kanan adalah 2 atau 3) untuk memberi kami kondisi yang cocok. Sebenarnya ini lebih dioptimalkan tetapi masalahnya sama. Perubahan ukuran set akan meningkatkan ukuran hasil secara eksponensial. Jumlah memori dan siklus CPU yang dikonsumsi semuanya dipengaruhi oleh istilah eksponensial.

Ketika kita mendenormalisasi, kita menghindari perhitungan ini sama sekali, berpikir memiliki lengket berwarna, melekat pada setiap halaman buku Anda. Anda dapat menyimpulkan informasi tanpa menggunakan referensi. Hukuman yang kami bayar adalah bahwa kami mengkompromikan esensi DBMS (organisasi data yang optimal)