Mengapa LEFT JOIN ini berperforma jauh lebih buruk daripada LEFT JOIN LATERAL?

13

Saya memiliki tabel berikut (diambil dari database Sakila):

  • film: film_id adalah pkey
  • actor: actor_id is pkey
  • film_actor: film_id dan actor_id adalah ikon untuk film / aktor

Saya memilih film tertentu. Untuk film ini, saya juga ingin semua aktor berpartisipasi dalam film itu. Saya punya dua pertanyaan untuk ini: satu dengan LEFT JOINdan satu dengan LEFT JOIN LATERAL.

select film.film_id, film.title, a.actors
from   film
left join
  (         
       select     film_actor.film_id, array_agg(first_name) as actors
       from       actor
       inner join film_actor using(actor_id)
       group by   film_actor.film_id
  ) as a
on       a.film_id = film.film_id
where    film.title = 'ACADEMY DINOSAUR'
order by film.title;

select film.film_id, film.title, a.actors
from   film
left join lateral
  (
       select     array_agg(first_name) as actors
       from       actor
       inner join film_actor using(actor_id)
       where      film_actor.film_id = film.film_id
  ) as a
on       true
where    film.title = 'ACADEMY DINOSAUR'
order by film.title;

Saat membandingkan paket kueri, kueri pertama berkinerja lebih buruk (20x) daripada yang kedua:

 Merge Left Join  (cost=507.20..573.11 rows=1 width=51) (actual time=15.087..15.089 rows=1 loops=1)
   Merge Cond: (film.film_id = film_actor.film_id)
   ->  Sort  (cost=8.30..8.31 rows=1 width=19) (actual time=0.075..0.075 rows=1 loops=1)
     Sort Key: film.film_id
     Sort Method: quicksort  Memory: 25kB
     ->  Index Scan using idx_title on film  (cost=0.28..8.29 rows=1 width=19) (actual time=0.044..0.058 rows=1 loops=1)
           Index Cond: ((title)::text = 'ACADEMY DINOSAUR'::text)
   ->  GroupAggregate  (cost=498.90..552.33 rows=997 width=34) (actual time=15.004..15.004 rows=1 loops=1)
     Group Key: film_actor.film_id
     ->  Sort  (cost=498.90..512.55 rows=5462 width=8) (actual time=14.934..14.937 rows=11 loops=1)
           Sort Key: film_actor.film_id
           Sort Method: quicksort  Memory: 449kB
           ->  Hash Join  (cost=6.50..159.84 rows=5462 width=8) (actual time=0.355..8.359 rows=5462 loops=1)
             Hash Cond: (film_actor.actor_id = actor.actor_id)
             ->  Seq Scan on film_actor  (cost=0.00..84.62 rows=5462 width=4) (actual time=0.035..2.205 rows=5462 loops=1)
             ->  Hash  (cost=4.00..4.00 rows=200 width=10) (actual time=0.303..0.303 rows=200 loops=1)
               Buckets: 1024  Batches: 1  Memory Usage: 17kB
               ->  Seq Scan on actor  (cost=0.00..4.00 rows=200 width=10) (actual time=0.027..0.143 rows=200 loops=1)
 Planning time: 1.495 ms
 Execution time: 15.426 ms

 Nested Loop Left Join  (cost=25.11..33.16 rows=1 width=51) (actual time=0.849..0.854 rows=1 loops=1)
   ->  Index Scan using idx_title on film  (cost=0.28..8.29 rows=1 width=19) (actual time=0.045..0.048 rows=1 loops=1)
     Index Cond: ((title)::text = 'ACADEMY DINOSAUR'::text)
   ->  Aggregate  (cost=24.84..24.85 rows=1 width=32) (actual time=0.797..0.797 rows=1 loops=1)
     ->  Hash Join  (cost=10.82..24.82 rows=5 width=6) (actual time=0.672..0.764 rows=10 loops=1)
           Hash Cond: (film_actor.actor_id = actor.actor_id)
           ->  Bitmap Heap Scan on film_actor  (cost=4.32..18.26 rows=5 width=2) (actual time=0.072..0.150 rows=10 loops=1)
             Recheck Cond: (film_id = film.film_id)
             Heap Blocks: exact=10
             ->  Bitmap Index Scan on idx_fk_film_id  (cost=0.00..4.32 rows=5 width=0) (actual time=0.041..0.041 rows=10 loops=1)
               Index Cond: (film_id = film.film_id)
           ->  Hash  (cost=4.00..4.00 rows=200 width=10) (actual time=0.561..0.561 rows=200 loops=1)
             Buckets: 1024  Batches: 1  Memory Usage: 17kB
             ->  Seq Scan on actor  (cost=0.00..4.00 rows=200 width=10) (actual time=0.039..0.275 rows=200 loops=1)
 Planning time: 1.722 ms
 Execution time: 1.087 ms

Kenapa ini? Saya ingin mempelajari alasan tentang hal ini, sehingga saya dapat memahami apa yang sedang terjadi dan dapat memprediksi bagaimana kueri akan berperilaku ketika ukuran data meningkat dan keputusan mana yang akan diambil oleh perencana dalam kondisi tertentu.

Pikiranku: dulu LEFT JOIN kueri , sepertinya subquery dijalankan untuk semua film dalam basis data, tanpa memperhitungkan pemfilteran dalam kueri luar yang kami hanya tertarik pada satu film tertentu. Mengapa perencana itu tidak dapat memiliki pengetahuan itu dalam subquery?

Dalam LEFT JOIN LATERAL kueri, kami sedikit banyak 'mendorong' penyaringan ke bawah. Jadi masalah yang kami miliki di kueri pertama tidak ada di sini, karenanya kinerja yang lebih baik.

Saya kira saya terutama mencari aturan praktis, kebijaksanaan umum, ... jadi sihir perencana ini menjadi sifat kedua - jika itu masuk akal.

perbarui (1)

Menulis ulang yang LEFT JOINberikut ini juga memberikan kinerja yang lebih baik (sedikit lebih baik daripada LEFT JOIN LATERAL):

select film.film_id, film.title, array_agg(a.first_name) as actors
from   film
left join
  (         
       select     film_actor.film_id, actor.first_name
       from       actor
       inner join film_actor using(actor_id)
  ) as a
on       a.film_id = film.film_id
where    film.title = 'ACADEMY DINOSAUR'
group by film.film_id
order by film.title;

 GroupAggregate  (cost=29.44..29.49 rows=1 width=51) (actual time=0.470..0.471 rows=1 loops=1)
   Group Key: film.film_id
   ->  Sort  (cost=29.44..29.45 rows=5 width=25) (actual time=0.428..0.430 rows=10 loops=1)
     Sort Key: film.film_id
     Sort Method: quicksort  Memory: 25kB
     ->  Nested Loop Left Join  (cost=4.74..29.38 rows=5 width=25) (actual time=0.149..0.386 rows=10 loops=1)
           ->  Index Scan using idx_title on film  (cost=0.28..8.29 rows=1 width=19) (actual time=0.056..0.057 rows=1 loops=1)
             Index Cond: ((title)::text = 'ACADEMY DINOSAUR'::text)
           ->  Nested Loop  (cost=4.47..19.09 rows=200 width=8) (actual time=0.087..0.316 rows=10 loops=1)
             ->  Bitmap Heap Scan on film_actor  (cost=4.32..18.26 rows=5 width=4) (actual time=0.052..0.089 rows=10 loops=1)
               Recheck Cond: (film_id = film.film_id)
               Heap Blocks: exact=10
               ->  Bitmap Index Scan on idx_fk_film_id  (cost=0.00..4.32 rows=5 width=0) (actual time=0.035..0.035 rows=10 loops=1)
                 Index Cond: (film_id = film.film_id)
             ->  Index Scan using actor_pkey on actor  (cost=0.14..0.17 rows=1 width=10) (actual time=0.011..0.011 rows=1 loops=10)
               Index Cond: (actor_id = film_actor.actor_id)
 Planning time: 1.833 ms
 Execution time: 0.706 ms

Bagaimana kita bisa bernalar tentang ini?

pembaruan (2)

Saya melanjutkan dengan beberapa percobaan dan saya pikir aturan praktis yang menarik adalah: menerapkan fungsi agregat setinggi / selambat mungkin . Permintaan dalam pembaruan (1) mungkin berkinerja lebih baik karena kami mengumpulkan dalam permintaan luar, tidak lagi dalam permintaan dalam.

Hal yang sama tampaknya berlaku jika kita menulis ulang di LEFT JOIN LATERALatas sebagai berikut:

select film.film_id, film.title, array_agg(a.first_name) as actors
from   film
left join lateral
  (
       select     actor.first_name
       from       actor
       inner join film_actor using(actor_id)
       where      film_actor.film_id = film.film_id
  ) as a
on       true
where    film.title = 'ACADEMY DINOSAUR'
group by film.film_id
order by film.title;

 GroupAggregate  (cost=29.44..29.49 rows=1 width=51) (actual time=0.088..0.088 rows=1 loops=1)
   Group Key: film.film_id
   ->  Sort  (cost=29.44..29.45 rows=5 width=25) (actual time=0.076..0.077 rows=10 loops=1)
     Sort Key: film.film_id
     Sort Method: quicksort  Memory: 25kB
     ->  Nested Loop Left Join  (cost=4.74..29.38 rows=5 width=25) (actual time=0.031..0.066 rows=10 loops=1)
           ->  Index Scan using idx_title on film  (cost=0.28..8.29 rows=1 width=19) (actual time=0.010..0.010 rows=1 loops=1)
             Index Cond: ((title)::text = 'ACADEMY DINOSAUR'::text)
           ->  Nested Loop  (cost=4.47..19.09 rows=200 width=8) (actual time=0.019..0.052 rows=10 loops=1)
             ->  Bitmap Heap Scan on film_actor  (cost=4.32..18.26 rows=5 width=4) (actual time=0.013..0.024 rows=10 loops=1)
               Recheck Cond: (film_id = film.film_id)
               Heap Blocks: exact=10
               ->  Bitmap Index Scan on idx_fk_film_id  (cost=0.00..4.32 rows=5 width=0) (actual time=0.007..0.007 rows=10 loops=1)
                 Index Cond: (film_id = film.film_id)
             ->  Index Scan using actor_pkey on actor  (cost=0.14..0.17 rows=1 width=10) (actual time=0.002..0.002 rows=1 loops=10)
               Index Cond: (actor_id = film_actor.actor_id)
 Planning time: 0.440 ms
 Execution time: 0.136 ms

Di sini, kami bergerak array_agg()ke atas. Seperti yang Anda lihat, rencana ini juga lebih baik daripada yang asli LEFT JOIN LATERAL.

Yang mengatakan, saya tidak yakin apakah aturan praktis yang diciptakan sendiri ini ( menerapkan fungsi agregat setinggi / selambat mungkin ) benar dalam kasus lain.

informasi tambahan

Biola: https://dbfiddle.uk/?rdbms=postgres_10&fiddle=4ec4f2fffd969d9e4b949bb2ca765ffb

Versi: PostgreSQL 10.4 pada x86_64-pc-linux-musl, dikompilasi oleh gcc (Alpine 6.4.0) 6.4.0, 64-bit

Lingkungan: Docker: docker run -e POSTGRES_PASSWORD=sakila -p 5432:5432 -d frantiseks/postgres-sakila. Harap dicatat bahwa gambar pada hub Docker sudah usang, jadi saya melakukan build secara lokal terlebih dahulu: build -t frantiseks/postgres-sakilasetelah kloning repositori git.

Definisi tabel:

film

 film_id              | integer                     | not null default nextval('film_film_id_seq'::regclass)
 title                | character varying(255)      | not null

 Indexes:
    "film_pkey" PRIMARY KEY, btree (film_id)
    "idx_title" btree (title)

 Referenced by:
    TABLE "film_actor" CONSTRAINT "film_actor_film_id_fkey" FOREIGN KEY (film_id) REFERENCES film(film_id) ON UPDATE CASCADE ON DELETE RESTRICT

aktor

 actor_id    | integer                     | not null default nextval('actor_actor_id_seq'::regclass)
 first_name  | character varying(45)       | not null

 Indexes:
    "actor_pkey" PRIMARY KEY, btree (actor_id)

 Referenced by:
    TABLE "film_actor" CONSTRAINT "film_actor_actor_id_fkey" FOREIGN KEY (actor_id) REFERENCES actor(actor_id) ON UPDATE CASCADE ON DELETE RESTRICT

film_actor

 actor_id    | smallint                    | not null
 film_id     | smallint                    | not null

 Indexes:
    "film_actor_pkey" PRIMARY KEY, btree (actor_id, film_id)
    "idx_fk_film_id" btree (film_id)
 Foreign-key constraints:
    "film_actor_actor_id_fkey" FOREIGN KEY (actor_id) REFERENCES actor(actor_id) ON UPDATE CASCADE ON DELETE RESTRICT
    "film_actor_film_id_fkey" FOREIGN KEY (film_id) REFERENCES film(film_id) ON UPDATE CASCADE ON DELETE RESTRICT

Data: ini dari database sampel Sakila. Pertanyaan ini bukan kasus kehidupan nyata, saya menggunakan database ini sebagian besar sebagai database sampel pembelajaran. Saya telah diperkenalkan ke SQL beberapa bulan yang lalu dan saya mencoba untuk memperluas pengetahuan saya. Ini memiliki distribusi berikut:

select count(*) from film: 1000
select count(*) from actor: 200
select avg(a) from (select film_id, count(actor_id) a from film_actor group by film_id) a: 5.47
Orns Jelly
sumber
1
Satu hal lagi: semua informasi penting harus masuk ke pertanyaan (termasuk tautan biola Anda). Tidak ada yang ingin membaca semua komentar nanti (atau mereka akan dihapus oleh moderator yang sangat cakap).
Erwin Brandstetter
Fiddle ditambahkan ke pertanyaan!
Jelly Orn

Jawaban:

7

Pengaturan tes

Pengaturan asli Anda di biola menyisakan ruang untuk perbaikan. Saya terus menanyakan pengaturan Anda karena suatu alasan.

  • Anda memiliki indeks ini di film_actor:

    "film_actor_pkey" PRIMARY KEY, btree (actor_id, film_id)  
    "idx_fk_film_id" btree (film_id)

    Yang sudah cukup membantu. Tetapi untuk mendukung permintaan khusus Anda, Anda akan memiliki indeks multikolom aktif (film_id, actor_id), kolom dalam urutan ini. Solusi praktis: ganti idx_fk_film_iddengan indeks di (film_id, actor_id)- atau buat PK (film_id, actor_id)untuk tujuan tes ini, seperti yang saya lakukan di bawah ini. Lihat:

    Dalam read-only (atau sebagian besar, atau umumnya ketika VACUUM dapat mengikuti kegiatan menulis) juga membantu untuk membuat indeks aktif (title, film_id)untuk memungkinkan hanya scan-indeks. Kasing uji saya sekarang sangat dioptimalkan untuk kinerja membaca.

  • Ketik ketidakcocokan antara film.film_id( integer) dan film_actor.film_id( smallint). Sementara itu berfungsi itu membuat pertanyaan lebih lambat dan dapat menyebabkan berbagai komplikasi. Juga membuat kendala FK lebih mahal. Jangan pernah melakukan ini jika itu bisa dihindari. Jika Anda tidak yakin, memilih integerlebih smallint. Meskipun smallint dapat menghemat 2 byte per bidang (sering dikonsumsi oleh bantalan pelurusan) ada lebih banyak komplikasi daripada dengan integer.

  • Untuk mengoptimalkan kinerja tes itu sendiri, buat indeks dan batasan setelah memasukkan banyak baris secara massal. Secara substansial lebih lambat untuk menambahkan tupel secara bertahap ke indeks yang ada daripada membuatnya dari awal dengan semua baris yang ada.

Tidak terkait dengan tes ini:

  • Urutan berdiri sendiri ditambah default kolom alih-alih kolom yang lebih sederhana dan lebih dapat diandalkan serial(atau IDENTITY). Jangan.

  • timestamp without timestampbiasanya tidak dapat diandalkan untuk kolom seperti last_update. Gunakan timestamptzsebagai gantinya. Dan perhatikan bahwa kolom default tidak mencakup "pembaruan terakhir", secara tegas.

  • Pengubah panjang dalam character varying(255)menunjukkan bahwa test case tidak dimaksudkan untuk memulai Postgres karena panjang ganjil tidak ada gunanya di sini. (Atau penulis tidak mengerti.)

Pertimbangkan kasus uji yang diaudit dalam biola:

db <> biola di sini - membangun biola Anda, dioptimalkan dan dengan permintaan tambahan.

Terkait:

Pengaturan pengujian dengan 1000 film dan 200 aktor memiliki validitas terbatas. Permintaan paling efisien memakan waktu <0,2 ms. Waktu perencanaan lebih dari waktu pelaksanaan. Tes dengan 100rb atau lebih baris akan lebih terbuka.

Mengapa hanya mengambil nama depan penulis? Setelah Anda mengambil beberapa kolom, Anda sudah memiliki situasi yang sedikit berbeda.

ORDER BY titletidak masuk akal saat memfilter untuk satu judul WHERE title = 'ACADEMY DINOSAUR'. Mungkin ORDER BY film_id?

Dan untuk runtime total lebih baik digunakan EXPLAIN (ANALYZE, TIMING OFF)untuk mengurangi (berpotensi menyesatkan) kebisingan dengan overhead sub-waktu.

Menjawab

Sulit untuk membentuk aturan praktis yang sederhana, karena kinerja total tergantung pada banyak faktor. Pedoman yang sangat mendasar:

  • Menggabungkan semua baris dalam sub-tabel membawa lebih sedikit overhead tetapi hanya membayar ketika Anda benar-benar membutuhkan semua baris (atau bagian yang sangat besar).

  • Untuk memilih beberapa baris (pengujian Anda!), Berbagai teknik kueri menghasilkan hasil yang lebih baik. Di situlah LATERALmasuk. Ini membawa lebih banyak overhead tetapi hanya membaca baris yang diperlukan dari sub-tabel. Kemenangan besar jika hanya sebagian kecil (sangat) diperlukan.

Untuk kasus uji khusus Anda, saya juga akan menguji konstruktor ARRAY di LATERALsubquery :

SELECT f.film_id, f.title, a.actors
FROM   film
LEFT   JOIN LATERAL (
   SELECT ARRAY (
      SELECT a.first_name
      FROM   film_actor fa
      JOIN   actor a USING (actor_id)
      WHERE  fa.film_id = f.film_id
      ) AS actors
   ) a ON true
WHERE  f.title = 'ACADEMY DINOSAUR';
-- ORDER  BY f.title; -- redundant while we filter for a single title 

Sementara hanya menggabungkan satu array dalam subquery lateral, konstruktor ARRAY sederhana berkinerja lebih baik daripada fungsi agregat array_agg(). Lihat:

Atau dengan subquery berkorelasi rendah untuk kasus sederhana:

SELECT f.film_id, f.title
     , ARRAY (SELECT a.first_name
              FROM   film_actor fa
              JOIN   actor a USING (actor_id)
              WHERE  fa.film_id = f.film_id) AS actors
FROM   film f
WHERE  f.title = 'ACADEMY DINOSAUR';

Atau, pada dasarnya, hanya 2x LEFT JOINlalu agregat :

SELECT f.film_id, f.title, array_agg(a.first_name) AS actors
FROM   film f
LEFT   JOIN film_actor fa USING (film_id)
LEFT   JOIN actor a USING (actor_id)
WHERE  f.title = 'ACADEMY DINOSAUR'
GROUP  BY f.film_id;

Tiga ini tampaknya tercepat di biola diperbarui saya (perencanaan + waktu eksekusi).

Upaya pertama Anda (hanya sedikit dimodifikasi) biasanya tercepat untuk mengambil semua atau sebagian besar film , tetapi tidak untuk pilihan kecil:

SELECT f.film_id, f.title, a.actors
FROM   film f
LEFT   JOIN (         
   SELECT fa.film_id, array_agg(first_name) AS actors
   FROM   actor
   JOIN   film_actor fa USING (actor_id)
   GROUP  by fa.film_id
   ) a USING (film_id)
WHERE  f.title = 'ACADEMY DINOSAUR';  -- not good for a single (or few) films!

Tes dengan kardinalitas yang jauh lebih besar akan lebih terbuka. Dan jangan menyamaratakan hasil dengan ringan, ada banyak faktor untuk kinerja total.

Erwin Brandstetter
sumber