Panduan SQL: Cara Menulis Pertanyaan dengan Lebih Baik (Bagian 2)

Artikel lanjutan Panduan SQL: Cara Menulis Query dengan Lebih Baik

Dari permintaan hingga rencana eksekusi

Mengetahui bahwa antipatterns tidak statis dan berevolusi ketika Anda tumbuh sebagai pengembang SQL, dan fakta bahwa ada banyak hal yang perlu dipertimbangkan ketika memikirkan alternatif juga berarti bahwa menghindari antipatterns dan menulis ulang permintaan bisa sangat sulit. tugas. Bantuan apa pun bisa berguna, itulah sebabnya pendekatan yang lebih terstruktur untuk optimasi kueri menggunakan beberapa alat mungkin paling efektif.

Juga harus dicatat bahwa beberapa antipatterns yang disebutkan di bagian terakhir berakar pada masalah kinerja, seperti operator AND , OR dan NOT dan ketidakhadiran mereka saat menggunakan indeks. Berpikir tentang kinerja tidak hanya membutuhkan lebih terstruktur, tetapi juga pendekatan yang lebih dalam.

Namun, pendekatan terstruktur dan mendalam ini terutama akan didasarkan pada rencana kueri, yang, seperti yang Anda ingat, adalah hasil dari kueri pertama yang diuraikan menjadi "parsing tree" atau "parse tree" dan menentukan dengan tepat algoritma mana digunakan untuk setiap operasi dan bagaimana pelaksanaannya dikoordinasikan.

Optimasi kueri

Saat Anda membaca di pendahuluan, Anda mungkin perlu memeriksa dan mengatur paket yang dikompilasi secara manual oleh optimizer. Dalam kasus seperti itu, Anda perlu menganalisis permintaan Anda lagi dengan melihat rencana permintaan.

Untuk mengakses rencana ini, Anda harus menggunakan alat yang disediakan oleh sistem manajemen basis data. Alat-alat berikut ini dapat Anda gunakan:

• Beberapa paket berisi alat yang menghasilkan representasi grafis dari rencana kueri. Perhatikan contoh berikut:
  
  
  
• Alat lain akan memberikan deskripsi tekstual dari rencana kueri. Salah satu contohnya adalah pernyataan EXPLAIN PLAN di Oracle, tetapi nama instruksi tergantung pada DBMS yang Anda gunakan. Di tempat lain Anda dapat menemukan EXPLAIN (MySQL, PostgreSQL) atau EXPLAIN QUERY PLAN (SQLite).

Harap dicatat bahwa ketika bekerja dengan PostgreSQL, Anda dapat membuat perbedaan antara EXPLAIN , di mana Anda hanya mendapatkan deskripsi yang memberi tahu bagaimana perencana bermaksud untuk mengeksekusi kueri tanpa menjalankannya, sementara EXPLAIN ANALYZE benar-benar mengeksekusi kueri dan mengembalikan analisis kepada Anda rencana permintaan yang diharapkan dan aktual. Secara umum, rencana pelaksanaan nyata adalah rencana di mana permintaan sebenarnya dieksekusi, sementara rencana pelaksanaan evaluasi menentukan apa yang akan dilakukannya tanpa memenuhi permintaan. Meskipun ini setara secara logis, rencana eksekusi sebenarnya jauh lebih berguna karena berisi informasi tambahan dan statistik tentang apa yang sebenarnya terjadi ketika permintaan dieksekusi.

Di bagian selanjutnya, Anda akan belajar lebih banyak tentang EXPLAIN dan ANALYZE , serta cara menggunakannya untuk mendapatkan informasi lebih lanjut tentang rencana kueri dan kemungkinan kinerjanya. Untuk melakukan ini, mulailah dengan beberapa contoh di mana Anda akan bekerja dengan dua tabel: one_million dan half_million .

Anda bisa mendapatkan informasi saat ini dari tabel one_million menggunakan EXPLAIN ; Pastikan untuk meletakkannya langsung di atas permintaan, dan setelah menjalankannya, itu akan mengembalikan rencana kueri kepada Anda:

 EXPLAIN SELECT * FROM one_million; QUERY PLAN ____________________________________________________ Seq Scan on one_million (cost=0.00..18584.82 rows=1025082 width=36) (1 row) 

Dalam hal ini, Anda melihat bahwa biaya permintaan adalah 0.00..18584.82 , dan jumlah baris adalah 1025082 . Lebar jumlah kolom adalah 36 .

Selain itu, Anda dapat memperbarui statistik menggunakan ANALYZE .

 ANALYZE one_million; EXPLAIN SELECT * FROM one_million; QUERY PLAN ____________________________________________________ Seq Scan on one_million (cost=0.00..18334.00 rows=1000000 width=37) (1 row) 

Selain EXPLAIN dan ANALYZE , Anda juga bisa mendapatkan runtime sebenarnya dengan EXPLAIN ANALYZE :

 EXPLAIN ANALYZE SELECT * FROM one_million; QUERY PLAN ___________________________________________________________ Seq Scan on one_million (cost=0.00..18334.00 rows=1000000 width=37) (actual time=0.015..1207.019 rows=1000000 loops=1) Total runtime: 2320.146 ms (2 rows) 

Kerugian menggunakan EXPLAIN ANALYZE adalah bahwa kueri benar-benar dieksekusi, jadi berhati-hatilah dengan ini!

Sejauh ini, semua algoritma yang telah Anda lihat adalah Seq Scan ( Seq Scan Sekuensial) atau Pemindaian Tabel Penuh: ini adalah pemindaian yang dilakukan dalam database di mana setiap baris tabel yang dipindai dibaca dalam urutan serial dan kolom yang ditemukan diperiksa untuk kepatuhan dengan kondisi atau tidak. Dalam hal kinerja, pemindaian berurutan jelas bukan rencana eksekusi terbaik karena Anda masih melakukan pemindaian tabel penuh. Namun, ini tidak terlalu buruk ketika tabel tidak pas di memori: membaca berurutan cukup cepat bahkan pada disk yang lambat.

Anda akan belajar lebih banyak tentang ini nanti ketika kita berbicara tentang pemindaian indeks.

Namun, ada algoritma lain. Ambil, misalnya, paket permintaan ini untuk koneksi:

 EXPLAIN ANALYZE SELECT * FROM one_million JOIN half_million ON (one_million.counter=half_million.counter); QUERY PLAN _________________________________________________________________ Hash Join (cost=15417.00..68831.00 rows=500000 width=42) (actual time=1241.471..5912.553 rows=500000 loops=1) Hash Cond: (one_million.counter = half_million.counter) -> Seq Scan on one_million (cost=0.00..18334.00 rows=1000000 width=37) (actual time=0.007..1254.027 rows=1000000 loops=1) -> Hash (cost=7213.00..7213.00 rows=500000 width=5) (actual time=1241.251..1241.251 rows=500000 loops=1) Buckets: 4096 Batches: 16 Memory Usage: 770kB -> Seq Scan on half_million (cost=0.00..7213.00 rows=500000 width=5) (actual time=0.008..601.128 rows=500000 loops=1) Total runtime: 6468.337 ms 

Anda melihat bahwa pengoptimal kueri memilih Hash Join sini! Ingat operasi ini, karena Anda akan memerlukannya untuk mengevaluasi kompleksitas waktu permintaan Anda. Untuk saat ini, perhatikan bahwa tidak ada indeks di half_million.counter , yang kami tambahkan dalam contoh berikut:

 CREATE INDEX ON half_million(counter); EXPLAIN ANALYZE SELECT * FROM one_million JOIN half_million ON (one_million.counter=half_million.counter); QUERY PLAN ________________________________________________________________ Merge Join (cost=4.12..37650.65 rows=500000 width=42) (actual time=0.033..3272.940 rows=500000 loops=1) Merge Cond: (one_million.counter = half_million.counter) -> Index Scan using one_million_counter_idx on one_million (cost=0.00..32129.34 rows=1000000 width=37) (actual time=0.011..694.466 rows=500001 loops=1) -> Index Scan using half_million_counter_idx on half_million (cost=0.00..14120.29 rows=500000 width=5) (actual time=0.010..683.674 rows=500000 loops=1) Total runtime: 3833.310 ms (5 rows) 

Anda melihat bahwa dengan membuat indeks, pengoptimal kueri sekarang telah memutuskan untuk menggunakan Merge join saat memindai Index Scan Indeks.

Perhatikan perbedaan antara pemindaian indeks dan pemindaian tabel penuh atau pemindaian berurutan: yang pertama, juga disebut "pemindaian tabel," memindai data atau halaman indeks untuk menemukan catatan yang sesuai, sedangkan yang kedua memindai setiap baris tabel.

Anda melihat bahwa runtime keseluruhan telah menurun dan kinerja harus lebih baik, tetapi ada dua pemindaian indeks, yang membuat memori lebih penting di sini, terutama jika tabel tidak cocok dengan itu. Dalam kasus seperti itu, Anda harus terlebih dahulu melakukan pemindaian indeks penuh, yang dilakukan menggunakan pembacaan berurutan cepat dan bukan masalah, tetapi kemudian Anda memiliki banyak operasi pembacaan acak untuk memilih baris berdasarkan nilai indeks. Ini adalah operasi baca acak yang biasanya beberapa urutan besarnya lebih lambat daripada yang berurutan. Dalam kasus ini, pemindaian tabel lengkap memang terjadi lebih cepat daripada pemindaian indeks penuh.

Kiat: Jika Anda ingin mempelajari lebih lanjut tentang MENJELASKAN atau mempertimbangkan contoh secara lebih rinci, coba baca Penjelasan Pemahaman Guillaume Lelarge.

Kompleksitas Waktu dan Big O

Sekarang setelah Anda meninjau rencana kueri secara singkat, Anda dapat mulai menggali lebih dalam dan memikirkan kinerja dalam istilah yang lebih formal menggunakan teori kompleksitas komputasi. Ini adalah bidang ilmu komputer teoretis, yang, antara lain, berfokus pada klasifikasi masalah komputasi tergantung pada kompleksitasnya; Masalah komputasi ini mungkin berupa algoritme, tetapi juga kueri.

Namun, untuk pertanyaan, mereka tidak perlu diklasifikasikan menurut kompleksitasnya, tetapi lebih tergantung pada waktu yang dibutuhkan untuk menyelesaikannya dan mendapatkan hasil. Ini disebut kompleksitas waktu, dan Anda dapat menggunakan notasi O besar untuk merumuskan atau mengukur jenis kompleksitas ini.

Dengan penunjukan O besar, Anda mengekspresikan runtime dalam hal seberapa cepat itu tumbuh relatif terhadap input, karena input menjadi besar secara sewenang-wenang. Notasi O besar mengecualikan koefisien dan anggota dari urutan yang lebih rendah, sehingga Anda dapat fokus pada bagian penting dari waktu eksekusi kueri Anda: laju pertumbuhannya. Ketika diekspresikan dengan cara ini, membuang koefisien dan syarat-syarat dari orde yang lebih rendah, mereka mengatakan bahwa kompleksitas waktu dijelaskan secara asimptotik. Ini berarti bahwa ukuran input masuk hingga tak terhingga.

Dalam bahasa database, kompleksitas menentukan berapa lama waktu yang dibutuhkan untuk menyelesaikan kueri saat ukuran tabel data dan oleh karena itu database tumbuh.

Harap dicatat bahwa ukuran basis data Anda meningkat tidak hanya dari peningkatan jumlah data dalam tabel, tetapi fakta bahwa ada indeks juga memainkan peran dalam ukuran.

Memperkirakan kompleksitas waktu dari rencana kueri Anda

Seperti yang Anda lihat sebelumnya, rencana eksekusi, antara lain, menentukan algoritma mana yang digunakan untuk setiap operasi, yang memungkinkan Anda untuk secara logis mengekspresikan setiap waktu eksekusi kueri sebagai fungsi dari ukuran tabel yang termasuk dalam rencana kueri, yang disebut fungsi kompleksitas. Dengan kata lain, Anda dapat menggunakan notasi O besar dan rencana eksekusi untuk mengevaluasi kompleksitas dan kinerja kueri.

Di bagian berikut, Anda akan mendapatkan gambaran umum dari empat jenis kompleksitas waktu, dan Anda akan melihat beberapa contoh bagaimana kompleksitas waktu kueri dapat bervariasi tergantung pada konteks di mana ia dieksekusi.

Petunjuk: indeks adalah bagian dari cerita ini!

Namun, harus dicatat bahwa ada berbagai jenis indeks, rencana eksekusi yang berbeda, dan implementasi yang berbeda untuk database yang berbeda, sehingga kesulitan sementara yang tercantum di bawah ini sangat umum dan dapat bervariasi tergantung pada pengaturan tertentu.

O (1): Waktu Konstan

Mereka mengatakan bahwa suatu algoritma bekerja dalam waktu yang konstan jika membutuhkan jumlah waktu yang sama terlepas dari ukuran data input. Ketika datang ke permintaan, itu akan dieksekusi dalam waktu yang konstan jika jumlah waktu yang sama diperlukan terlepas dari ukuran tabel.

Jenis kueri ini tidak terlalu umum, tetapi ini adalah salah satu contohnya:

 SELECT TOP 1 t.* FROM t 

Kompleksitas waktu adalah konstan, karena satu baris arbitrer dipilih dari tabel. Oleh karena itu, lamanya waktu seharusnya tidak tergantung pada ukuran tabel.

Waktu Linier: O (n)

Mereka mengatakan bahwa algoritma bekerja dalam waktu linier, jika waktu eksekusi berbanding lurus dengan ukuran data input, yaitu, waktu meningkat secara linier dengan ukuran data input. Untuk database, ini berarti bahwa waktu eksekusi akan berbanding lurus dengan ukuran tabel: saat jumlah baris dalam tabel bertambah, waktu eksekusi permintaan meningkat.

Contohnya adalah permintaan dengan WHERE untuk kolom yang tidak terindeks: pemindaian tabel penuh atau Seq Scan akan diperlukan, yang akan mengarah pada kompleksitas waktu O (n). Ini berarti bahwa setiap baris harus dibaca untuk menemukan baris dengan pengenal yang diinginkan (ID). Anda tidak memiliki batasan sama sekali, jadi Anda harus menghitung setiap baris, bahkan jika baris pertama cocok dengan kondisi tersebut.

Pertimbangkan juga contoh kueri berikut, yang akan memiliki kompleksitas O (n) jika tidak ada indeks pada bidang i_id :

 SELECT i_id FROM item; 

• Penjelasan sebelumnya juga berarti bahwa kueri lain, seperti kueri untuk menghitung jumlah baris COUNT (*) FROM TABLE; akan memiliki kompleksitas waktu O (n) , karena pemindaian tabel penuh akan diperlukan karena jumlah baris belum disimpan untuk tabel. Kalau tidak, kompleksitas waktu akan mirip dengan O (1) .
  

Runtime linier terkait erat dengan runtime paket yang memiliki gabungan tabel. Berikut ini beberapa contohnya:

• Gabung hash memiliki kompleksitas yang diharapkan dari O (M + N) .Gabung hash klasik untuk menggabungkan dua tabel secara internal terlebih dahulu mempersiapkan tabel hash dari tabel yang lebih kecil. Entri tabel hash terdiri dari atribut koneksi dan stringnya. Tabel hash diakses dengan menerapkan fungsi hash ke atribut koneksi. Setelah tabel hash dibangun, tabel besar dipindai, dan baris yang sesuai dari tabel yang lebih kecil ditemukan dengan mencari tabel hash.
• Gabungan gabungan biasanya memiliki kompleksitas O (M + N), tetapi akan sangat bergantung pada indeks kolom gabungan dan, jika tidak ada indeks, apakah baris diurutkan menurut kunci yang digunakan dalam gabungan:
  • Jika kedua tabel diurutkan berdasarkan tombol yang digunakan dalam gabungan, maka kueri akan memiliki kompleksitas waktu O (M + N).
  • Jika kedua tabel memiliki indeks untuk kolom yang bergabung, maka indeks sudah mendukung kolom ini dalam urutan dan penyortiran tidak diperlukan. Kesulitannya adalah O (M + N).
  • Jika tidak ada tabel yang memiliki indeks pada kolom yang terhubung, Anda harus mengurutkan kedua tabel terlebih dahulu, sehingga kompleksitasnya akan terlihat seperti O (M log M + N log N).
  • Jika hanya satu dari tabel yang memiliki indeks pada kolom yang terhubung, maka hanya tabel yang tidak memiliki indeks yang harus diurutkan sebelum langkah bergabung terjadi, sehingga kerumitan akan terlihat seperti O (M + N log N).
• Untuk nested joins, kompleksitasnya biasanya O (MN). Gabung ini efektif ketika satu atau kedua tabel sangat kecil (misalnya, kurang dari 10 catatan), yang merupakan situasi yang sangat umum ketika mengevaluasi kueri, karena beberapa subquery ditulis untuk mengembalikan hanya satu baris.

Ingat: gabungan bersarang adalah gabungan yang membandingkan setiap catatan dalam satu tabel dengan setiap catatan di yang lain.

Waktu Logaritma: O (log (n))

Dikatakan bahwa suatu algoritma bekerja dalam waktu logaritma jika waktu eksekusi proporsional dengan logaritma ukuran input; Untuk permintaan, ini berarti bahwa mereka akan dieksekusi jika waktu eksekusi sebanding dengan logaritma ukuran database.

Kompleksitas waktu logaritmik ini valid untuk rencana kueri tempat Index Scan atau indeks berkerumun dipindai. Indeks berkerumun adalah indeks di mana level indeks akhir berisi baris aktual tabel. Indeks berkerumun mirip dengan indeks lain: itu didefinisikan dalam satu atau lebih kolom. Mereka membentuk kunci indeks. Kunci pengelompokan adalah kolom kunci dari indeks pengelompokan. Memindai indeks berkerumun pada dasarnya adalah operasi membaca DBMS Anda untuk satu baris atau baris dari atas ke bawah dalam indeks berkerumun.

Pertimbangkan contoh permintaan berikut, di mana ada indeks untuk i_id dan yang biasanya menghasilkan kompleksitas O (log (n)):

 SELECT i_stock FROM item WHERE i_id = N; 

Perhatikan bahwa tanpa indeks, kompleksitas waktu adalah O (n).

Waktu Quadratic: O (n ^ 2)

Dipercaya bahwa algoritma dieksekusi dalam waktu kuadratik, jika waktu eksekusi sebanding dengan kuadrat ukuran input. Sekali lagi, untuk basis data, ini berarti waktu eksekusi kueri sebanding dengan kuadrat ukuran basis data.

Contoh kemungkinan kueri kompleksitas waktu kuadratik adalah sebagai berikut:

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

Kompleksitas minimum mungkin O (n log (n)), tetapi kompleksitas maksimum mungkin O (n ^ 2) berdasarkan informasi indeks atribut koneksi.

Untuk meringkas, Anda juga dapat melihat pada lembar contekan berikut untuk mengevaluasi kinerja permintaan berdasarkan kompleksitas waktu dan efektivitasnya:

Penyetelan SQL

Dengan adanya rencana eksekusi query dan kompleksitas waktu, Anda dapat lebih lanjut menyesuaikan kueri SQL Anda. Anda dapat mulai dengan memfokuskan pada poin-poin berikut:

• Ganti pindaian tabel penuh yang tidak perlu dengan pindaian indeks;
• Pastikan bahwa urutan bergabung optimal diterapkan.
• Pastikan indeks digunakan secara optimal. Dan
• Caching scan teks lengkap dari tabel kecil (cache tabel kecil scan tabel penuh.) Digunakan.

Penggunaan SQL lebih lanjut

Selamat! Anda telah sampai pada akhir artikel ini, yang hanya memberi Anda sedikit melihat kinerja query SQL. Saya harap Anda memiliki lebih banyak informasi tentang antipatterns, optimizer kueri, dan alat yang dapat Anda gunakan untuk menganalisis, mengevaluasi, dan menafsirkan kompleksitas rencana kueri Anda. Namun, masih banyak yang harus Anda temukan! Jika Anda ingin tahu lebih banyak, baca buku "Sistem Manajemen Basis Data" oleh R. Ramakrishnan dan J. Gehrke.

Akhirnya, saya tidak ingin menyangkal StackOverflow dari Anda dalam kutipan ini:

Antipattern favorit saya tidak memeriksa permintaan Anda.

Namun, itu berlaku ketika:

• Kueri Anda menyediakan lebih dari satu tabel.
• Anda berpikir bahwa Anda memiliki desain yang optimal untuk permintaan tersebut, tetapi jangan mencoba memverifikasi asumsi Anda.
• Anda menerima permintaan kerja pertama, tidak tahu seberapa dekat dengan optimal.