Tentang Query
Sebuah query adalah sebuah ekspresi bahasa yang menggambarkan data yang akan didapatkan kembali dari sebuah database. Dalam hubungannya dengan optimisasi query, seringkali diasumsikan bahwa query-query tersebut dinyatakan dalam sebuah dasar-dasar isi dan sekumpulan cara orientasi, yang memberikan optimizer pilihan-pilihan diantara alternatif prosedur-prosedur evaluasi. Query dapat digunakan pada beberapa keadaan. Kebanyakan aplikasi nyatanya adalah permintaan-permintaan secara langsung dari user yang memerlukan informasi tentang bentuk maupun isi dari database. Apabila permintaan user terbatas pada sekumpulan query-query standar, maka query-query tersebut dapat dioptimisasi secara manual oleh pemrograman prosedur-prosedur pencarian gabungan dan membatasi input dari user pada sebuah ukuran menu
Sebuah query yang diekspresikan dalam sebuah bahasa query tingkat tinggi seperti SQL mula-mula harus dibaca, diuraikan dan disahkan (scanning, parsing, validating) . Query tersebut kemudian dibentuk menjadi sebuah struktur data yang biasa disebut dengan query tree. Dan kemudian DBMS (Database Manajemen Sistem) harus merencanakan sebuah strategi eksekusi untuk mendapatkan kembali hasil dari query dari file-file database. Tahapan-tahapan proses dari sebuah query di dalam sebuah sistem database . Berikut penjelasan dari masing-masing tahapan :
Scanner melakukan identifikasi (pengenalan) token-token seperti SQL keywords, attribute, dan relation name. Proses ini disebut dengan scanning.
Query Parser mengecek kevalidan query dan kemudian menterjemahkannya ke dalam sebuah bentuk internal yaitu ekspresi relasi aljabar atau parse tree. Proses ini disebut dengan parsing.
Query Optimizer memeriksa semua ekspresi-ekspresi aljabar yang sama untuk query yang diberikan dan memilih salah satu dari ekspresi tersebut yang terbaik yang memiliki perkiraan termurah. Dengan kata lain, tugas dari query optimizer adalah menghasilkan sebuah rencana eksekusi. Proses ini disebut dengan optimisasi query.
Code Generator atau Interpreter mentransformasikan rencana akses yang dihasilkan oleh optimizer ke dalam kode-kode. Setelah itu, kode-kode tersebut dikirimkan ke dalam query processor untuk dijalankan.
Query Processor melakukan eksekusi query untuk mendapatkan hasil query yang diinginkan.
Pemrosesan terhadap query di dalam suatu basis data dilakukan dengan menggunakan bahasa query (query language) Bahasa query formal basis data relasional adalah bahasa untuk meminta informasi dari basis data. Pemrosesan query merujuk pada sejumlah aktivitas yang dilakukan untuk pengambilan data dari sebuah basis data untuk memenuhi permintaan data/informasi dari pemakai. Bahasa query relasional formal merupakan bahasa yang digunakan basis data, dengan SQL dikonversi menjadi bahasa relasional formal sehingga dapat diterapkan sekumpulan informasi untuk memperoleh query paling efisien.
Membicarakan tentang query, sangat erat hubungannya dengan cara penulisan query tersebut ke dalam sebuah bentuk bahasa yang mudah dimengerti. Pada umumnya, bahasa query yang digunakan untuk mengekspresikan sebuah pernyataan dari query adalah SQL (Structure Query Language). SQL adalah sebuah bahasa database yang luas yang memiliki statementstatement (pernyataan) untuk definisi data, query dan update data (memperbaharui data). SQL mempunyai satu statement dasar untuk mendapatkan kembali informasi dari sebuah database.
Optimasi Query adalah suatu proses untuk menganalisa query untuk menentukan sumber-sumber apa saja yang digunakan oleh query tersebut dan apakah penggunaan dari sumber tersebut dapat dikurangi tanpa merubah output. Atau bisa juga dikatakan bahwa optimasi query adalah sebuah prosedur untuk meningkatkan strategi evaluasi dari suatu query untuk membuat evaluasi tersebut menjadi lebih efektif. Optimasi query mencakup beberapa teknik seperti transformasi query ke dalam bentuk logika yang sama, memilih jalan akses yang optimal dan mengoptimumkan penyimpanan data. Tujuan dari optimasi query adalah menemukan jalan akses yang termurah untuk meminimumkan total waktu pada saat proses sebuah query. Untuk mencapai tujuan tersebut, maka diperlukan optimizer untuk melakukan analisa query dan untuk melakukan pencarian jalan akses. Optimizer query akan membuat informasi statistik yang tersimpan dalam katalog DBMS untuk memperkirakan besarnya biaya dari sebuah rencana query. Optimisasi query merupakan bagian dasar dari sebuah sistem database dan juga merupakan suatu proses untuk menghasilkan rencana akses yang efisien dari sebuah query di dalam sebuah database. Secara tidak langsung, sebuah rencana akses merupakan sebuah strategi yang nantinya akan dijalankan untuk sebuah query, untuk mendapatkan kembali operasi-operasi yang apabila dijalankan akan menghasilkan database record query. Ada tiga aspek dasar yang ditetapkan dan mempengaruhi optimisasi query, yaitu : search space, cost model dan search strategy.
Search space adalah sekumpulan rencana-rencana akses yang sama secara logika yang dapat digunakan untuk mengevaluasi sebuah query. Semua rencanarencana dalam search space query mengembalikan hasil yang sama biarpun beberapa rencana lebih efisien dibandingkan dengan rencana yang lainnya.
Cost model menandakan sebuah harga untuk tiap rencana dalam search space. Harga dari rencana tersebut adalah sebuah perkiraan dari sumber-sumber yang digunakan pada saat rencana dijalankan, dimana harga yang lebih rendah, merupakan yang terbaik dari rencana-rencana yang ada.
Search strategy adalah sebuah perincian dari rencana-rencana mana dalam search space yang akan diperiksa. Apabila search space-nya kecil, maka strategi yang dapat diteruskan adalah menghitung dan mengevaluasi setiap rencana. Meskipun kebanyakan search space bahkan untuk query-query yang sederhana adalah sangat besar, akan tetapi query optimizer selalu memerlukan aturan heuristik untuk mengontrol nomer dari rencana-rencana yang akan diperiksa
Bagaimana mengukur biaya sebuah query?
Biaya query sangat dipengaruhi oleh dua hal, yaitu proses secara lokal dan transmisi data antar lokasi, karena berkaitan dengan fungsi biaya. Proses perhitungan diperlukan untuk menghasilkan biaya query yang akurat secara parsial. Karakteristik relasi secara lokal harus diketahui dalam optimisasi waktu. Beberapa diantaranya adalah kardinalitas dari relasi secara lokal, banyaknya byte dalam nilai atribut, dan nilai selectivity factor yang terdapat dalam relasi diperlukan. Optimisasi proses pengolahan data secara global dengan cara menggunakan metoda secara lokal, dalam pelaksanaannya adalah mengoperasikan atas kedua proses, yaitu memproses data lokal dan memproses data secara lokal yang datang dari lokasi lain. Besar biaya untuk optimisasi lokal pada umumnya didasarkan pada banyaknya akses dari memori sekunder, ukuran buffers dan ukuran operand. Data yang akan dioperasikan secara lokal dan tambahan struktur data lokal seperti indek, hash tabel akan dapat mempercepat proses secara lokal.
- Operasi Select
Operasi Select (o) Biaya operasi select untuk metode akses tertentu adalah sebagai berikut
- Operasi Project
Dari operasi diatas, operasi project dengan algoritma sorting memiliki biaya[10] :
(NTuples+ SRTuples) + (NPages * 4) + SRTuples
Keterangan :
NTuples : Jumlah tuple dalam relasi
SRTuple : Ukuran tuple hasil relasi setelah dioperasi
NPages : .Jumlah page dalarn relasi.
-Operasi Join
a. Page Oriented Nested Loops Join
Biaya Operasi :
TotalCost=M+M*N
Keterangan :
M : Cost scanning relasi R
N : Cost scanning relasi S
b. Sort merge Join
Biaya Operasifl0] ;
- Kedua tabel terurut :
TotalCost = M+N {2)
- Kedua tabel belum terurut :
Total Cost = (M + N) + (Sorting R + Sorting S)
Keterangan :
Sorting R = O (M Log M)
Sorting S = O(N Log N)
c. Hybrid Hash Join
Biaya Operasi :
Total Cost = 3(M + N)
Evaluation of exspression
Terdapat dua macam cara untuk mengevaluasi entire expression tree, yaitu materialization dan pipelining. Materialization mengevaluasi 1 operasi pada satu waktu, dimulai pada level yang paling rendah kemudian dilanjutkan ke atasnya. Cost untuk menulis result pada disk dan membaca kembali cenderung besar. Sedangkan pipelining mengevaluasi banyak operasi secara bersamaan, melewati hasil satu opeasi ke berikutnya.pipelining jauh lebih murah dari pada materialisasi, karena tidak perlu untuk menyimpan sementara hubungan ke disk.
MATERIALIZATION
Dalam metode ini, kueri dipecah menjadi kueri individual dan kemudian hasilnya digunakan untuk mendapatkan hasil akhir. Untuk lebih spesifik, misalkan ada persyaratan untuk mencari siswa yang sedang belajar di kelas 'DESIGN_01'.
Di sini kita dapat mengamati dua pertanyaan: yang pertama adalah memilih CLASS_ID dari 'DESIGN_01' dan yang lainnya adalah memilih rincian siswa dari CLASS_ID yang diambil pada permintaan pertama. DBMS juga melakukan hal yang sama. Ini memecah kueri menjadi dua seperti yang disebutkan di atas. Setelah rusak, itu mengevaluasi kueri pertama dan menyimpannya di tabel sementara di memori. Data tabel sementara ini kemudian akan digunakan untuk mengevaluasi kueri kedua. Ini adalah contoh dari kueri dua tingkat dalam metode materialisasi. Kita dapat memiliki sejumlah level dan begitu banyak tabel sementara.
Meskipun metode ini terlihat sederhana, biaya untuk evaluasi jenis ini selalu lebih mahal. Butuh waktu untuk mengevaluasi dan menulis ke dalam tabel sementara, kemudian mengambil dari tabel dan kueri sementara ini untuk mendapatkan tingkat hasil berikutnya dan seterusnya. Oleh karena itu biaya evaluasi dalam metode ini adalah:
Cost = cost of individual SELECT + cost of write into temporary table
PIPELINING
Dalam metode ini, DBMS tidak menyimpan record ke dalam tabel sementara. Sebagai gantinya, ini membuat kueri setiap kueri dan hasilnya akan diteruskan ke kueri berikutnya untuk diproses dan seterusnya. Ini akan memproses kueri satu demi satu dan masing-masing akan menggunakan hasil kueri sebelumnya untuk pemrosesannya. Dalam contoh di atas, CLASS_ID dari DESIGN_01 diteruskan ke tabel STUDENT untuk mendapatkan detail siswa.
Terdapat 2 jenis pipelining
Demand Driven or Lazy evaluation
Dalam metode ini, hasil kueri tingkat yang lebih rendah tidak diteruskan ke tingkat yang lebih tinggi secara otomatis. Ini akan diteruskan ke level yang lebih tinggi hanya jika diminta oleh level yang lebih tinggi. Dalam metode ini, ia mempertahankan nilai hasil dan status dengannya dan itu akan ditransfer ke tingkat berikutnya hanya jika diminta. Dalam contoh kami di atas, CLASS_ID untuk DESIGN_01 akan diambil, tetapi tidak akan diteruskan ke kueri STUDENT hanya jika diminta. Setelah mendapat permintaan, itu diteruskan ke permintaan siswa dan kueri itu akan diproses.
Producer Driven or Eager Pipelining
Dalam metode ini, kueri tingkat yang lebih rendah dengan bersemangat meneruskan hasil ke kueri tingkat yang lebih tinggi. Itu tidak menunggu kueri tingkat yang lebih tinggi untuk meminta hasil. Dalam metode ini, kueri tingkat yang lebih rendah membuat buffer untuk menyimpan hasil dan kueri tingkat yang lebih tinggi menarik hasil untuk digunakan. Jika buffer penuh, maka kueri tingkat yang lebih rendah menunggu kueri tingkat yang lebih tinggi untuk mengosongkannya. Oleh karena itu, ini juga disebut sebagai pipelining PULL dan PUSH.