Pengoptimalan SQL keren yang tidak bergantung pada model biaya. Bagian 1

Lima pengoptimalan sederhana yang dapat diimplementasikan hanya berdasarkan metadata (yaitu batasan) dan kueri itu sendiri. Kami menawarkan kepada Anda adaptasi artikel Lukas Eder, yang dirancang bagi mereka yang memiliki pemahaman umum tentang database dan SQL, serta beberapa pengalaman praktis dengan DBMS . Pengoptimalan biaya sebenarnya adalah cara standar untuk mengoptimalkan kueri SQL dalam database modern. Inilah sebabnya mengapa sangat sulit untuk menulis algoritma kompleks secara manual dalam 3GL (bahasa pemrograman generasi ketiga) yang kinerjanya akan melebihi rencana eksekusi yang dihitung secara dinamis yang dihasilkan oleh pengoptimal modern. Hari ini kita tidak akan membahas optimasi biaya, yaitu optimasi berdasarkan model biaya database. Kami akan melihat pengoptimalan yang lebih sederhana. Yang dapat diimplementasikan hanya berdasarkan metadata (yaitu pembatasan) dan permintaan itu sendiri. Biasanya implementasinya untuk database bukanlah binomial Newton, karena, dalam hal ini, optimasi apa pun akan menghasilkan rencana eksekusi yang lebih baik, terlepas dari keberadaan indeks, volume data, dan kecondongan distribusi data. "Bukan binomial Newton" bukan berarti betapa mudahnya menerapkan optimasi, tetapi apakah hal itu harus dilakukan. Pengoptimalan ini menghilangkan pekerjaan ekstra yang tidak perlu [untuk database] ( sebagai lawan dari pekerjaan yang diperlukan dan tidak perlu, yang sudah saya tulis ).

Untuk apa pengoptimalan ini digunakan?

Kebanyakan dari mereka digunakan untuk:

• perbaikan bug dalam kueri;
• memungkinkan tampilan untuk digunakan kembali tanpa database benar-benar menjalankan logika tampilan.

Dalam kasus pertama, seseorang dapat mengatakan: “Jadi apa, lanjutkan saja dan perbaiki query SQL bodoh ini.” Tapi biarlah yang tak pernah melakukan kesalahan melempariku dengan batu dulu. Kasus kedua sangat menarik: ini memberi kita kemampuan untuk membuat pustaka tampilan dan fungsi tabel kompleks yang dapat digunakan kembali di banyak lapisan.

Basis data yang digunakan

Pada artikel ini kami akan membandingkan 10 optimasi SQL di lima DBMS yang paling banyak digunakan ( menurut peringkat database ):

• Peramal 12.2;
• MySQL 8.0.2;
• SQLServer 2014;
• PostgreSQL 9.6;
• DB2 LUW 10.5.

Peringkat lain hampir menggemakannya. Seperti biasa pada artikel kali ini saya akan menanyakan database Sakila . Berikut daftar sepuluh jenis optimasi tersebut:

1. penutupan transitif;
2. predikat mustahil dan panggilan tabel yang tidak perlu;
3. menghilangkan GABUNG;
4. penghapusan predikat “tidak berarti”;
5. proyeksi dalam subkueri EXISTS;
6. penggabungan predikat;
7. set yang terbukti kosong;
8. kendala PERIKSA;
9. koneksi refleksif yang tidak perlu;
10. Predikat pushdown

Hari ini kita akan membahas hal. 1-3, di bagian kedua - 4 dan 5, dan di bagian 3 - 6-10.

1. Penutupan transitif

Mari kita mulai dengan sesuatu yang lebih sederhana: penutupan transitif . Ini adalah konsep sepele yang berlaku untuk banyak operasi matematika, seperti operator persamaan. Dalam hal ini dapat dirumuskan sebagai berikut: jika A = B dan B = C, maka A = C.

Tidak sulit, bukan? Namun hal ini memiliki beberapa implikasi menarik bagi pengoptimal SQL. Mari kita lihat sebuah contoh. Mari kita ekstrak semua film dengan ACTOR_ID = 1:

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE a.actor_id = 1;

Hasilnya adalah sebagai berikut:

FIRST_NAME      LAST_NAME  FILM_ID
PENELOPE        GUINESS    1
PENELOPE        GUINESS    23
PENELOPE        GUINESS    25
PENELOPE        GUINESS    106
PENELOPE        GUINESS    140
PENELOPE        GUINESS    166
...

Sekarang mari kita lihat rencana untuk mengeksekusi query ini dalam kasus Oracle DBMS:

--------------------------------------------------------------
| Id  | Operation                    | Name          | Rows  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT             |               |       |
|   1 |  NESTED LOOPS                |               |    19 |
|   2 |   TABLE ACCESS BY INDEX ROWID| ACTOR         |     1 |
|*  3 |    INDEX UNIQUE SCAN         | PK_ACTOR      |     1 |
|*  4 |   INDEX RANGE SCAN           | PK_FILM_ACTOR |    19 |
--------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("A"."ACTOR_ID"=1)
   4 - access("FA"."ACTOR_ID"=1)

Bagian tentang predikat sangat menarik di sini. Predikat ACTOR_ID = 1, karena penutupan transitif, berlaku untuk tabel ACTOR dan tabel FILM_ACTOR. Jika:

• A.ACTOR_ID = 1 (из предиката WHERE) и…
• A.ACTOR_ID = FA.ACTOR_ID (из предиката ON)
  То:
• FA.ACTOR_ID = 1

Untuk pertanyaan yang lebih kompleks, ini menghasilkan beberapa hasil yang sangat bagus. Secara khusus, keakuratan estimasi kardinalitas meningkat secara signifikan, karena dimungkinkan untuk memilih estimasi berdasarkan nilai konstanta tertentu dari predikat, dan bukan, misalnya, jumlah rata-rata film berdasarkan aktor, seperti pada kueri berikut (mengembalikan hasil yang sama):

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE first_name = 'PENELOPE'
AND last_name = 'GUINESS'

Rencananya:

----------------------------------------------------------------------------
| Id  | Operation                            | Name                | Rows  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                     |       |
|   1 |  NESTED LOOPS                        |                     |     2 |
|*  2 |   TABLE ACCESS BY INDEX ROWID BATCHED| ACTOR               |     1 |
|*  3 |    INDEX RANGE SCAN                  | IDX_ACTOR_LAST_NAME |     3 |
|*  4 |   INDEX RANGE SCAN                   | PK_FILM_ACTOR       |    27 |
----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("A"."FIRST_NAME"='PENELOPE')
   3 - access("A"."LAST_NAME"='GUINESS')
   4 - access("A"."ACTOR_ID"="FA"."ACTOR_ID")

Seperti yang Anda lihat, jumlah baris dalam tabel FILM_ACTOR terlalu tinggi, sedangkan NESTED LOOP terlalu rendah. Berikut adalah beberapa nilai menarik:

SELECT count(*) FROM film_actor WHERE actor_id = 1;
SELECT avg(c) FROM (
  SELECT count(*) c FROM film_actor GROUP BY actor_id
);

Hasil:

19
27.315

Dari sinilah perkiraan tersebut berasal. Jika database mengetahui bahwa kita sedang membicarakan ACTOR_ID = 1, maka database dapat mengumpulkan statistik jumlah film untuk aktor tersebut . Jika tidak (karena mekanisme pengumpulan statistik standar tidak mengkorelasikan FIRST_NAME/LAST_NAME dengan ACTOR_ID), maka kita akan mendapatkan jumlah rata-rata film untuk semua aktor . Kesalahan yang sederhana dan tidak penting dalam kasus khusus ini, namun dalam kueri yang kompleks, kesalahan tersebut dapat menyebar lebih jauh, terakumulasi, dan mengarahkan lebih jauh ke dalam kueri (yang lebih tinggi dalam rencana) ke pilihan GABUNG yang salah. Jadi kapan pun Anda bisa, rancang gabungan dan predikat sederhana Anda untuk memanfaatkan penutupan transitif. Database lain apa yang mendukung fitur ini?

DB2

Ya!

Explain Plan
-----------------------------------------------------------
ID | Operation              |                 Rows | Cost
 1 | RETURN                 |                      |   13
 2 |  NLJOIN                |              27 of 1 |   13
 3 |   FETCH ACTOR          |     1 of 1 (100.00%) |    6
 4 |    IXSCAN PK_ACTOR     |   1 of 200 (   .50%) |    0
 5 |   IXSCAN PK_FILM_ACTOR | 27 of 5462 (   .49%) |    6
Predicate Information
 4 - START (Q2.ACTOR_ID = 1)
      STOP (Q2.ACTOR_ID = 1)
 5 - START (1 = Q1.ACTOR_ID)
      STOP (1 = Q1.ACTOR_ID)

Omong-omong, jika Anda menyukai rencana eksekusi keren seperti ini, lihat skrip Markus Winand .

MySQL

Sayangnya, rencana eksekusi MySQL tidak cocok untuk analisis semacam ini. Predikat itu sendiri hilang dari informasi keluaran:

ID  SELECT TYPE  TABLE  TYPE   REF    ROWS
------------------------------------------
1   SIMPLE       a      const  const  1
1   SIMPLE       fa     ref    const  19

Namun fakta bahwa const ditentukan dua kali di kolom REF menunjukkan bahwa kedua tabel mencari nilai konstan. Pada saat yang sama, rencana kueri dengan FIRST_NAME/LAST_NAME terlihat seperti ini:

ID  SELECT TYPE  TABLE  TYPE   REF         ROWS
-----------------------------------------------
1   SIMPLE       a      ref    const       3
1   SIMPLE       fa     ref    a.actor_id  27

Dan seperti yang Anda lihat, REF sekarang mereferensikan kolom dari predikat GABUNG. Skor kardinalitasnya hampir sama dengan di Oracle. Jadi ya, MySQL juga mendukung penutupan transitif.

PostgreSQL

Ya!

QUERY PLAN
------------------------------------------------------------------------------------
Nested Loop  (cost=4.49..40.24 rows=27 width=15)
  ->  Seq Scan on actor a  (cost=0.00..4.50 rows=1 width=17)
        Filter: (actor_id = 1)
  ->  Bitmap Heap Scan on film_actor fa  (cost=4.49..35.47 rows=27 width=4)
        Recheck Cond: (actor_id = 1)
        ->  Bitmap Index Scan on film_actor_pkey  (cost=0.00..4.48 rows=27 width=0)
              Index Cond: (actor_id = 1)

SQLServer

Ya!

|--Nested Loops(Inner Join)
     |--Nested Loops(Inner Join)
     |    |--Index Seek (SEEK:([a].[actor_id]=(1)))
     |    |--RID Lookup
     |--Index Seek (SEEK:([fa].[actor_id]=(1)))

Ringkasan

Semua database kami mendukung penutupan transitif. Namun tunggu saja #6 di artikel bagian selanjutnya. Ada kasus penutupan transitif yang kompleks yang tidak semua database dapat menanganinya.

2. Predikat yang tidak mungkin dan panggilan tabel yang tidak perlu

Ini adalah optimasi yang sangat bodoh, tapi mengapa tidak? Jika pengguna menulis predikat yang mustahil, lalu mengapa repot-repot mengeksekusinya? Berikut beberapa contohnya:

-- "Очевидный"
SELECT * FROM actor WHERE 1 = 0
-- "Хитрый"
SELECT * FROM actor WHERE NULL = NULL

Kueri pertama jelas tidak akan pernah memberikan hasil apa pun, tetapi pernyataan yang sama berlaku untuk kueri kedua. Lagi pula, meskipun NULL IS NULL selalu TRUE, hasil perhitungan NULL = NULL adalah NULL, yang menurut logika tiga nilai setara dengan FALSE. Ini cukup jelas, jadi mari kita langsung mencari tahu database mana yang melakukan pengoptimalan ini.

DB2

Ya!

Explain Plan
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0

Seperti yang Anda lihat, akses ke tabel ACTOR sepenuhnya dikecualikan dari paket. Ini hanya berisi operasi GENROW, yang menghasilkan baris nol. Sempurna.

MySQL

Ya!

ID  SELECT TYPE  TABLE   EXTRAS
-----------------------------------------
1   SIMPLE         Impossible WHERE

Kali ini, MySQL berbaik hati memberi tahu kami tentang klausa WHERE yang mustahil. Terima kasih! Hal ini membuat analisis menjadi lebih mudah, terutama dibandingkan dengan database lainnya.

Peramal

Ya!

---------------------------------------------------------------
| Id  | Operation          | Name  | Starts | E-Rows | A-Rows |
---------------------------------------------------------------
|   0 | SELECT STATEMENT   |       |      1 |        |      0 |
|*  1 |  FILTER            |       |      1 |        |      0 |
|   2 |   TABLE ACCESS FULL| ACTOR |      0 |    200 |      0 |
---------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(NULL IS NOT NULL)

Kita melihat bahwa rencananya masih menyebutkan akses ke tabel ACTOR, dan jumlah baris yang diharapkan masih 200, tetapi ada juga operasi pemfilteran (FILTER) dengan Id=1, yang tidak akan pernah ada TRUE. Karena Oracle tidak menyukai tipe data SQL Boolean standar , Oracle menampilkan NULL IS NOT NULL dalam rencana, bukan hanya FALSE. Oh ya... Tapi serius, perhatikan predikat itu. Saya memiliki kesempatan untuk men-debug rencana eksekusi dengan subpohon 1000 baris dan nilai biaya yang sangat tinggi, hanya untuk menemukan fakta bahwa seluruh subpohon "dipotong" oleh filter NULL IS NOT NULL. Sedikit mengecewakan, saya beritahu Anda.

PostgreSQL

Ya!

QUERY PLAN
-------------------------------------------
Result  (cost=0.00..0.00 rows=0 width=228)
  One-Time Filter: false

Sudah lebih baik. Tidak ada panggilan tabel ACTOR yang mengganggu dan predikat FALSE kecil yang rapi.

SQLServer?

Ya!

|--Constant Scan

SQL Server menyebutnya sebagai " pemindaian konstan ", yang merupakan pemindaian di mana tidak terjadi apa-apa - mirip dengan DB2. Semua database kami dapat mengecualikan predikat yang mustahil:

3. Hilangkan GABUNG

Di bagian sebelumnya, kita mengamati akses tabel yang tidak diperlukan dalam kueri tabel tunggal. Namun apa jadinya jika JOIN tidak memerlukan salah satu dari beberapa akses tabel? Saya sudah menulis tentang menghilangkan GABUNG di postingan sebelumnya dari blog saya . Mesin SQL dapat menentukan, berdasarkan jenis kueri dan keberadaan kunci utama dan asing, apakah GABUNG tertentu benar-benar diperlukan dalam kueri tertentu, atau apakah menghilangkannya tidak akan memengaruhi semantik kueri. Dalam ketiga contoh berikutnya, JOIN tidak diperlukan. Gabungan ...-ke-satu dalam dapat dihilangkan dengan memiliki kunci asing NOT NULL. Sebagai gantinya:

SELECT first_name, last_name
FROM customer c
JOIN address a ON c.address_id = a.address_id

Basis data dapat melakukan hal berikut:

SELECT first_name, last_name
FROM customer c

INNER JOIN bertipe "...-to-one" dapat diganti jika ada kunci asing yang dapat dibatalkan. Kueri di atas berfungsi jika kunci asing tunduk pada batasan NOT NULL. Jika tidak, misalnya seperti pada permintaan ini:

SELECT title
FROM film f
JOIN language l ON f.original_language_id = l.language_id

maka JOIN masih bisa dihilangkan, namun harus menambahkan predikat NOT NULL seperti ini:

SELECT title
FROM film
WHERE original_language_id IS NOT NULL

OUTER JOIN tipe "...-to-one" dapat dihapus jika ada kunci unik. Alih-alih ini:

SELECT first_name, last_name
FROM customer c
LEFT JOIN address a ON c.address_id = a.address_id

Basis data, sekali lagi, dapat melakukan hal berikut:

SELECT first_name, last_name
FROM customer c

... meskipun tidak ada kunci asing untuk CUSTOMER.ADDRESS_ID. Koneksi luar yang unik (DISTINCT OUTER JOIN) dari tipe "...-to-many" dapat dihapus. Alih-alih ini:

SELECT DISTINCT first_name, last_name
FROM actor a
LEFT JOIN film_actor fa ON a.actor_id = fa.actor_id

Basis data dapat melakukan hal berikut:

SELECT DISTINCT first_name, last_name
FROM actor a

Semua contoh ini telah dipelajari secara rinci di artikel sebelumnya, jadi saya tidak akan mengulanginya sendiri, tetapi hanya akan merangkum segala sesuatu yang dapat dihilangkan oleh berbagai database: Sayangnya, tidak semua database bisa menyelesaikan semua jenis koneksi. DB2 dan SQL Server adalah pemimpin yang tak terbantahkan di sini! Bersambung