Mengapa subquery mengurangi estimasi baris menjadi 1?

26

Pertimbangkan permintaan berikut yang dibuat namun sederhana:

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END AS ID2
FROM X_HEAP;

Saya akan memperkirakan taksiran baris terakhir untuk kueri ini sama dengan jumlah baris dalam X_HEAPtabel. Apa pun yang saya lakukan di subquery seharusnya tidak masalah untuk estimasi baris karena tidak dapat menyaring baris. Namun, pada SQL Server 2016 saya melihat estimasi baris dikurangi menjadi 1 karena subquery:

permintaan buruk

Mengapa ini terjadi? Apa yang bisa saya lakukan?

Sangat mudah untuk mereproduksi masalah ini dengan sintaks yang tepat. Berikut adalah satu set definisi tabel yang akan melakukannya:

CREATE TABLE dbo.X_HEAP (ID INT NOT NULL)
CREATE TABLE dbo.X_OTHER_TABLE (ID INT NOT NULL);
CREATE TABLE dbo.X_OTHER_TABLE_2 (ID INT NOT NULL);

INSERT INTO dbo.X_HEAP WITH (TABLOCK)
SELECT TOP (1000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM master..spt_values;

CREATE STATISTICS X_HEAP__ID ON X_HEAP (ID) WITH FULLSCAN;

db fiddle link .

Joe Obbish
sumber

Jawaban:

22

Masalah perkiraan kardinalitas (CE) ini muncul ketika:

  1. Join adalah join luar dengan predikat pass-through
  2. The selektivitas predikat pass-through diperkirakan tepat 1 .

Catatan: Kalkulator khusus yang digunakan untuk menentukan selektivitas tidak penting.


Detail

CE menghitung selektivitas gabungan luar sebagai jumlah dari:

  • The bergabung dalam selektivitas dengan predikat yang sama
  • The anti bergabung selektivitas dengan predikat yang sama

Satu-satunya perbedaan antara gabungan luar dan dalam adalah bahwa gabungan luar juga mengembalikan baris yang tidak cocok dengan predikat gabungan. Anti bergabung memberikan perbedaan ini persis. Estimasi kardinalitas untuk inner dan anti join lebih mudah daripada untuk outer join secara langsung.

Proses estimasi selektivitas bergabung sangat mudah:

  • Pertama, selektivitas SPT predikat pass-through dinilai.
    • Ini dilakukan dengan menggunakan kalkulator mana saja yang sesuai dengan keadaan.
    • Predikat adalah semuanya, termasuk IsFalseOrNullkomponen peniadaan .
  • Selektivitas gabungan bagian dalam: = 1 - SPT
  • Selektivitas anti bergabung: = SPT

Anti join merupakan baris yang akan 'melewati' join. Gabung dalam mewakili baris yang tidak akan 'melewati'. Perhatikan bahwa 'lewati' berarti baris yang mengalir melalui gabungan tanpa menjalankan sisi dalam sama sekali. Untuk menekankan: semua baris akan dikembalikan oleh gabungan, perbedaannya adalah antara baris yang menjalankan sisi dalam gabungan sebelum muncul, dan yang tidak.

Jelas, menambahkan ke harus selalu memberikan selektivitas total 1, artinya semua baris dikembalikan oleh gabungan, seperti yang diharapkan.1 - SPTSPT

Memang, perhitungan di atas bekerja persis seperti yang dijelaskan untuk semua nilai kecuali 1 .SPT

Ketika = 1, selektivitas gabungan internal dan anti gabungan diperkirakan nol, menghasilkan estimasi kardinalitas (untuk gabungan secara keseluruhan) dari satu baris. Sejauh yang saya tahu, ini tidak disengaja, dan harus dilaporkan sebagai bug.SPT


Masalah terkait

Bug ini lebih mungkin bermanifestasi daripada yang diperkirakan, karena batasan CE yang terpisah. Ini muncul ketika CASEekspresi menggunakan EXISTSklausa (seperti yang umum). Sebagai contoh query dimodifikasi berikut dari pertanyaan tersebut tidak menemukan perkiraan kardinalitas tak terduga:

-- This is fine
SELECT 
    CASE
        WHEN XH.ID = 1
        THEN (SELECT TOP (1) XOT.ID FROM dbo.X_OTHER_TABLE AS XOT) 
    END
FROM dbo.X_HEAP AS XH;

Memperkenalkan hal-hal sepele EXISTSmemang menyebabkan masalah muncul:

-- This is not fine
SELECT 
    CASE
        WHEN EXISTS (SELECT 1 WHERE XH.ID = 1)
        THEN (SELECT TOP (1) XOT.ID FROM dbo.X_OTHER_TABLE AS XOT) 
    END
FROM dbo.X_HEAP AS XH;

Menggunakan EXISTSmemperkenalkan bergabung bersama (disorot) ke rencana eksekusi:

Paket semi bergabung

Perkiraan untuk semi join baik-baik saja. Masalahnya adalah bahwa CE memperlakukan kolom probe terkait sebagai proyeksi sederhana, dengan selektivitas tetap 1:

Semijoin with probe column treated as a Project.

Selectivity of probe column = 1

Ini secara otomatis memenuhi salah satu kondisi yang diperlukan untuk masalah CE ini untuk terwujud, terlepas dari isi EXISTSklausa.


Untuk informasi latar belakang yang penting, lihat Subqueries dalam CASEEkspresi oleh Craig Freedman.

Paul White mengatakan GoFundMonica
sumber
22

Ini sepertinya perilaku yang tidak disengaja. Memang benar bahwa perkiraan kardinalitas tidak perlu konsisten pada setiap langkah rencana tetapi ini adalah rencana kueri yang relatif sederhana dan perkiraan kardinalitas akhir tidak konsisten dengan apa yang dilakukan kueri. Perkiraan kardinalitas yang rendah dapat menghasilkan pilihan yang buruk untuk tipe gabungan dan metode akses untuk tabel lain di bagian hilir dalam rencana yang lebih rumit.

Melalui coba-coba, kami dapat menemukan beberapa pertanyaan serupa yang masalahnya tidak muncul:

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT -1) 
  END AS ID2
FROM dbo.X_HEAP;

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END AS ID2
FROM dbo.X_HEAP;

Kami juga dapat memunculkan lebih banyak kueri tempat masalah muncul:

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
  END AS ID2
FROM dbo.X_HEAP;

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT -1) 
  END AS ID2
FROM dbo.X_HEAP;

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END AS ID2
FROM dbo.X_HEAP;

Tampaknya ada pola: jika ada ekspresi di dalam CASEyang tidak diharapkan dieksekusi dan ekspresi hasilnya adalah subquery terhadap tabel maka estimasi baris jatuh ke 1 setelah ekspresi itu.

Jika saya menulis kueri terhadap tabel dengan indeks berkerumun aturan berubah sedikit. Kita dapat menggunakan data yang sama:

CREATE TABLE dbo.X_CI (ID INT NOT NULL, PRIMARY KEY (ID))

INSERT INTO dbo.X_CI WITH (TABLOCK)
SELECT * FROM dbo.X_HEAP;

UPDATE STATISTICS X_CI WITH FULLSCAN;

Kueri ini memiliki taksiran akhir 1000 baris:

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
  END
FROM dbo.X_CI;

Namun kueri ini memiliki taksiran akhir 1 baris:

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END
FROM dbo.X_CI;

Untuk menggali lebih jauh ini, kita dapat menggunakan tanda jejak tidak berdokumen 2363 untuk mendapatkan informasi tentang bagaimana pengoptimal kueri melakukan perhitungan selektivitas. Saya merasa terbantu untuk memasangkan flag trace dengan flag trace tanpa dokumen 8606 . TF 2363 tampaknya memberikan perhitungan selektivitas untuk pohon yang disederhanakan dan pohon setelah normalisasi proyek. Dengan mengaktifkan kedua tanda jejak, memperjelas perhitungan mana yang berlaku untuk pohon mana.

Mari kita coba untuk permintaan asli yang diposting dalam pertanyaan:

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END AS ID2
FROM X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

Berikut adalah bagian dari bagian output yang menurut saya relevan dengan beberapa komentar:

Plan for computation:

  CSelCalcColumnInInterval -- this is the type of calculator used

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID -- this is the column used for the calculation

Pass-through selectivity: 0 -- all rows are expected to have a true value for the case expression

Stats collection generated: 

  CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter) -- the row estimate after the join will still be 1000

      CStCollBaseTable(ID=1, CARD=1000 TBL: X_HEAP)

      CStCollBaseTable(ID=2, CARD=1 TBL: X_OTHER_TABLE)

...

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 1 -- no rows are expected to have a true value for the case expression

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1 x_jtLeftOuter) -- the row estimate after the join will still be 1

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter) -- here is the row estimate after the previous join

          CStCollBaseTable(ID=1, CARD=1000 TBL: X_HEAP)

          CStCollBaseTable(ID=2, CARD=1 TBL: X_OTHER_TABLE)

      CStCollBaseTable(ID=3, CARD=1 TBL: X_OTHER_TABLE_2)

Sekarang mari kita coba untuk permintaan serupa yang tidak memiliki masalah. Saya akan menggunakan ini:

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT -1) 
  END AS ID2
FROM dbo.X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

Output debug pada bagian paling akhir:

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 1

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1000 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_HEAP)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

      CStCollConstTable(ID=4, CARD=1) -- this is different than before because we select a constant instead of from a table

Mari kita coba kueri lain yang menyajikan perkiraan baris buruk:

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
  END AS ID2
FROM dbo.X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

Pada akhir perkiraan kardinalitas turun menjadi 1 baris, sekali lagi setelah Selektivitas pass-through = 1. Estimasi kardinalitas dipertahankan setelah selektivitas 0,501 dan 0,499.

Plan for computation:

 CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 0.501

...

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 0.499

...

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 1

Stats collection generated: 

  CStCollOuterJoin(ID=12, CARD=1 x_jtLeftOuter) -- this is associated with the ELSE expression

      CStCollOuterJoin(ID=11, CARD=1000 x_jtLeftOuter)

          CStCollOuterJoin(ID=10, CARD=1000 x_jtLeftOuter)

              CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_HEAP)

              CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

          CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

      CStCollBaseTable(ID=4, CARD=1 TBL: X_OTHER_TABLE)

Mari kita kembali ke kueri serupa lainnya yang tidak memiliki masalah. Saya akan menggunakan ini:

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END AS ID2
FROM dbo.X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

Dalam output debug tidak pernah ada langkah yang memiliki selektivitas pass-through dari 1. Perkiraan kardinalitas tetap pada 1000 baris.

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 0.499

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1000 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_HEAP)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

      CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

End selectivity computation

Bagaimana dengan kueri ketika melibatkan tabel dengan indeks berkerumun? Pertimbangkan kueri berikut dengan masalah taksiran baris:

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END
FROM dbo.X_CI
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

Akhir dari hasil debug mirip dengan apa yang telah kita lihat:

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_CI].ID

Pass-through selectivity: 1

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_CI)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

      CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

Namun, permintaan terhadap CI tanpa masalah memiliki output yang berbeda. Menggunakan kueri ini:

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
  END
FROM dbo.X_CI
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

Hasil dalam berbagai kalkulator digunakan. CSelCalcColumnInIntervaltidak lagi muncul:

Plan for computation:

  CSelCalcFixedFilter (0.559)

Pass-through selectivity: 0.559

Stats collection generated: 

  CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

      CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_CI)

      CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

...

Plan for computation:

  CSelCalcUniqueKeyFilter

Pass-through selectivity: 0.001

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1000 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_CI)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

      CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE)

Sebagai kesimpulan, kami tampaknya mendapatkan taksiran baris yang buruk setelah subquery dalam kondisi berikut:

  1. The CSelCalcColumnInIntervalselektivitas kalkulator digunakan. Saya tidak tahu persis kapan ini digunakan tetapi tampaknya muncul lebih sering ketika tabel dasar adalah tumpukan.

  2. Selektivitas pass-through = 1. Dengan kata lain, salah satu CASEekspresi diharapkan dievaluasi menjadi false untuk semua baris. Tidak masalah jika CASEekspresi pertama bernilai true untuk semua baris.

  3. Ada bagian luar yang bergabung CStCollBaseTable. Dengan kata lain, CASEekspresi hasil adalah subquery terhadap tabel. Nilai konstan tidak akan berfungsi.

Mungkin dalam kondisi tersebut, pengoptimal kueri tidak sengaja menerapkan selektivitas pass-through ke estimasi baris tabel luar alih-alih untuk pekerjaan yang dilakukan pada bagian dalam loop bersarang. Itu akan mengurangi estimasi baris menjadi 1.

Saya dapat menemukan dua solusi. Saya tidak dapat mereproduksi masalah saat menggunakan APPLYalih-alih subquery. Output dari jejak bendera 2363 sangat berbeda dengan APPLY. Inilah satu cara untuk menulis ulang kueri asli dalam pertanyaan:

SELECT 
  h.ID
, a.ID2
FROM X_HEAP h
OUTER APPLY
(
SELECT CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END
) a(ID2);

pertanyaan bagus 1

Legacy CE juga muncul untuk menghindari masalah.

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END AS ID2
FROM X_HEAP
OPTION (USE HINT('FORCE_LEGACY_CARDINALITY_ESTIMATION'));

pertanyaan bagus 2

Sebuah item yang menghubungkan disampaikan untuk masalah ini (dengan beberapa detail yang Paulus Putih disediakan dalam jawabannya).

Joe Obbish
sumber