Pemrosesan Kueri Terdistribusi

Pemrosesan kueri terdistribusi mengevaluasi kueri atas data yang tersebar di banyak node, memanfaatkan paralelisme untuk kecepatan dan meminimalkan komunikasi jaringan yang mendominasi biaya dalam pengaturan terdistribusi.

Definition

Pemrosesan kueri terdistribusi adalah dekomposisi, optimasi, dan eksekusi kueri atas data yang terletak di beberapa situs atau partisi, di mana rencana harus mengoordinasikan pekerjaan di seluruh node dan meminimalkan komputasi serta transfer data antar-node.

Scope

Topik ini mencakup bagaimana kueri berjalan di seluruh data yang dipartisi dan direplikasi: bentuk-bentuk paralelisme (terpartisi, berpipa, dan independen); strategi gabungan paralel dan terdistribusi seperti gabungan repartisi dan siaran; teknik pengurangan komunikasi seperti semijoin; dan perluasan optimasi berbasis biaya untuk memperhitungkan transfer jaringan dan penempatan data. Ini membahas bagaimana kueri logis didekomposisi dan dijadwalkan di seluruh node. Ini tidak termasuk keputusan penempatan data dan protokol komit untuk transaksi terdistribusi.

Core questions

• Bentuk paralelisme apa (terpartisi, berpipa, independen) yang dapat dimanfaatkan oleh rencana terdistribusi?
• Bagaimana gabungan dieksekusi ketika input dipartisi di seluruh node?
• Bagaimana semijoin mengurangi jumlah data yang dikirim antar situs?
• Bagaimana optimasi berubah ketika biaya jaringan mendominasi?
• Bagaimana penempatan data memengaruhi rencana mana yang paling murah?

Key concepts

• paralelisme terpartisi
• paralelisme berpipa
• paralelisme independen
• gabungan repartisi (shuffle)
• gabungan siaran
• pengurangan semijoin
• biaya komunikasi
• lokalisasi data

Key theories

Paralelisme dalam eksekusi kueri

Rencana terdistribusi memanfaatkan paralelisme terpartisi (operator yang sama berjalan pada partisi data yang terpisah), paralelisme berpipa (operator dalam rantai berjalan secara bersamaan), dan paralelisme independen (sub-rencana yang tidak terkait berjalan sekaligus) untuk mengurangi waktu respons.

Gabungan terdistribusi dan paralel

Gabungan atas data yang dipartisi menggunakan repartisi (mengocok kedua input berdasarkan kunci gabungan) atau menyiarkan input kecil ke semua node; pemilihan di antara keduanya bergantung pada ukuran relasi dan partisi yang ada.

Semijoin dan minimalisasi komunikasi

Semijoin mengurangi relasi hanya ke tupel yang dapat cocok sebelum mengirimkannya melalui jaringan, memotong biaya komunikasi; teknik ini merupakan inti dari prosesor kueri terdistribusi awal seperti SDD-1.

Clinical relevance

Pemrosesan kueri terdistribusi adalah apa yang memungkinkan sistem analitik menjawab kueri atas data yang jauh lebih besar daripada yang dapat ditampung oleh satu mesin, dan teknik untuk meminimalkan lalu lintas jaringan serta memaksimalkan paralelisme secara langsung menentukan kecepatan gudang data skala besar dan mesin kueri.

History

Pemrosesan kueri terdistribusi awal dipelopori dalam sistem SDD-1 sekitar tahun 1980, yang memperkenalkan pengurangan komunikasi berbasis semijoin. Basis data paralel tanpa-bagi (shared-nothing) pada tahun 1980-an dan 1990-an, yang disurvei oleh DeWitt dan Gray, menetapkan gabungan repartisi dan siaran serta taksonomi paralelisme yang masih digunakan oleh mesin kueri terdistribusi modern.

Key figures

• Philip Bernstein
• David DeWitt
• M. Tamer Özsu
• Patrick Valduriez

Seminal works

• bernstein1981
• dewitt1992
• ozsu2011

Frequently asked questions

Mengapa biaya jaringan sangat penting dalam pemrosesan kueri terdistribusi?

Dalam basis data terdistribusi, sumber daya paling lambat dan paling banyak diperebutkan biasanya adalah jaringan antar node. Mengirim hasil perantara yang besar antar node dapat mendominasi total waktu kueri, sehingga pengoptimal dan teknik seperti semijoin berfokus pada transfer data sesedikit mungkin, bahkan dengan biaya komputasi lokal tambahan.

Kapan gabungan siaran digunakan sebagai pengganti gabungan repartisi?

Gabungan siaran mengirimkan salinan satu input ke setiap node dan efisien ketika input tersebut kecil. Gabungan repartisi (shuffle) mendistribusikan ulang kedua input berdasarkan kunci gabungan di seluruh node dan digunakan ketika kedua relasi berukuran besar. Pengoptimal membandingkan biaya komunikasi siaran versus pengocokan untuk memilih.