Sorting of Query Processing

SDBL

SORTING of query processing

Start!

Kelompok 6

M. Thaufan Delviyoga 201401088

Ammar Wahyudi 201401095

M. Farhan Ramadhan 201401093

Dimas Dafa Abipraya 171401071

Pengertian Sorting

Sorting merupakan proses pengurutan sekumpulan data dalam suatu urutan tertentu.Sorting dipakai untuk :

• Membantu proses pencarian (searching)
• Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.

+ inf

External Sorting

Penyortiran eksternal biasanya menggunakan strategi gabungan sortir hibrida. Pada fase pengurutan, potongan data yang cukup kecil untuk muat di memori utama dibaca, disortir, dan ditulis ke file sementara. Pada fase penggabungan, sub-file yang diurutkan digabungkan menjadi satu file yang lebih besar.

External Sorting adalah istilah untuk kelas algoritma pengurutan yang dapat menangani sejumlah besar data. Penyortiran eksternal diperlukan ketika data yang diurutkan tidak sesuai dengan memori utama perangkat komputasi (biasanya RAM) dan sebaliknya, harus berada di memori eksternal yang lebih lambat (biasanya hard drive).

Kapan Melakukan External Sorting?

• Ketika data yang belum disortir terlalu besar untuk diurutkan di memori internal komputer.
• Saat menggunakan perangkat penyimpanan sekunder, contoh tape disk.
• Ketika data berukuran besar.
• Untuk melakukan permintaan berdasarkan kueri.
• Untuk memilih elemen duplikat.
• Saat kita perlu mengambil input yang besar dari user.

External Sort-Merge

Biarkan M menunjukkan ukuran memori (dalam halaman).1. Buat run yang diurutkan sebagai berikut. misal i = 0. lakukan hingga akhir relasi:

• Baca M blok relasi ke dalam memori
• Urutkan blok dalam memori
• Tulis data yang diurutkan : Ri; increment i.

2. Gabungkan run; misalkan untuk saat ini i<M. Dalam satu langkah penggabungan, gunakan i blok memori untuk buffer input, dan 1 blokuntuk buffer keluaran. Lakukan sampai semua halaman buffer input kosong:

• Pilih record pertama dalam urutan sortir dari masing-masing buffer
• Tulis record ke output
• Hapus record dari halaman buffer; jika halaman buffer kosong, baca blok berikutnya (jika ada) dari run ke buffer.

Contoh Sort Merge

Cost Analysis

• Akses disk untuk pembuatan run awal serta di setiap passadalah 2br (kecuali untuk lulus akhir, yang tidak menuliskan hasil)

• Jumlah total pass gabungan yang diperlukan: [ logM−1(br/M) ]

Jadi jumlah total akses disk untuk penyortiran eksternal: br(2[logM−1(br/M) + 1)

+ info

Data dan analitik adalah kunci untuk pengambilan keputusan bisnis yang cerdas. Namun, dalam membuat keputusan tersebut penting untuk memahami apa itu data, cara mengumpulkan, memproses, dan mengelolanya sehingga bisa menjadi insight yang bernilai

- Wahyudi

Thanks!