Notasi Big-O dalam SQL

Basis Data, Teknologi

Selain untuk membahasakan berapa lama sebuah algoritma membutuhkan waktu untuk menyelesaikan suatu masalah, Big-O juga bisa kita pakai untuk mengukur kompleksitas waktu dari perintah dalam bahasa SQL.

Dalam pembahasan ini, indeks memiliki peran dalam pengukuran kompleksitas waktu.

a. Waktu konstan

Query akan berjalan dengan waktu konstan apabila query tersebut membutuhkan jumlah waktu yang sama tanpa bergantung pada ukuran tabel.

Contoh query

SELECT TOP 1 t.*
FROM t;

Kompleksitas waktu dari query diatas adalah konstan karena kita hanya memilih 1 baris dari tabel t. Waktu yang dibutuhkan untuk menjalankan query tidak bergantung pada ukuran tabel t.

b. Waktu linear

Query akan berjalan dengan waktu linear apabila waktu eksekusinya sebanding dengan ukuran tabel.

Hal ini karena query perlu memeriksa seluruh baris dalam tabel.

Contoh query:

SELECT i_id
FROM item;

Semakin bertambah jumlah baris pada tabel, semakin bertambah juga waktu eksekusi query.

c. Waktu logaritmik

Query akan berjalan dengan waktu logaritmik apabila waktu eksekusinya sebanding dengan nilai logaritma dari ukuran basis data.

Hal ini terjadi saat query melakukan pencarian menggunakan indeks.

Contoh query:

SELECT i_stock
FROM item
WHERE i_id = N;

Tanpa indeks, kompleksitas waktunya akan menjadi O(n)

d. Waktu quadratic

Dalam database, waktu quadratic adalah waktu eksekusi untuk sebuah query sebanding dengan kuadrat ukuran basis data.

Contoh query dengan atribut JOIN:

SELECT *
FROM item, author
WHERE item.i_a_id = author.a_id;

Untuk query diatas, kompleksitas waktu minimalnya adalah O(n log(n)), sedangkan untuk kompleksitas waktu maksimalnya adalah O(n2). Hal ini berdasarkan pada informasi indeks dari atribut JOIN.

Referensi

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *