Perlambatan besar ke permintaan SQL Server untuk menambahkan wildcard (atau atas)

Saya punya kebun binatang 20 juta hewan yang saya lacak di database SQL Server 2005 saya. Sekitar 1% dari mereka berkulit hitam dan sekitar 1% dari mereka adalah angsa. Saya ingin mendapatkan detail dari semua angsa hitam dan karenanya, tidak ingin membanjiri halaman hasil yang saya lakukan:

select top 10 * 
from animal 
where colour like 'black'  
and species like 'swan'

(Ya, secara tidak sengaja bidang-bidang tersebut adalah freetext tetapi keduanya diindeks). Ternyata kami tidak memiliki hewan seperti permintaan mengembalikan set kosong dalam sekitar 300 milidetik. Itu akan menjadi sekitar dua kali lebih cepat jika saya menggunakan '=' daripada 'suka' tetapi saya memiliki firasat yang terakhir akan menyelamatkan saya dari mengetik.

Ternyata kepala zookeeper berpikir dia mungkin telah memasukkan beberapa angsa sebagai 'kehitaman' jadi saya memodifikasi kueri sesuai:

select top 10 * 
from animal  
where colour like 'black%' 
and species like 'swan'

Ternyata tidak ada satupun dari mereka (dan sebenarnya tidak ada hewan 'hitam%' kecuali yang 'hitam') tetapi permintaan sekarang membutuhkan waktu sekitar 30 detik untuk kembali kosong.

Sepertinya itu hanya kombinasi 'top' dan 'like%' yang menyebabkan masalah

select count(*) 
from animal  
where colour like 'black%' 
and species like 'swan'

mengembalikan 0 dengan sangat cepat, dan bahkan

select * 
from animal 
where colour like 'black%' 
and species like 'swan'

kembali kosong dalam sepersekian detik.

Apakah ada yang tahu mengapa 'top' dan '%' harus berkonspirasi untuk menyebabkan hilangnya kinerja yang dramatis, terutama dalam hasil yang kosong?

EDIT: Hanya untuk memperjelas, saya tidak menggunakan indeks FreeText, saya hanya bermaksud bahwa bidang tersebut adalah freetext pada titik masuk, yaitu tidak dinormalisasi dalam database. Maaf atas kebingungan, kata-kata yang buruk di pihak saya.

Ini adalah keputusan pengoptimal berbasis biaya.

Perkiraan biaya yang digunakan dalam pilihan ini tidak benar karena mengasumsikan kemandirian statistik antara nilai dalam kolom yang berbeda.

Ini mirip dengan masalah yang dijelaskan dalam Row Goals Gone Rogue di mana bilangan genap dan ganjil berkorelasi negatif.

Mudah direproduksi.

CREATE TABLE dbo.animal(
    id int IDENTITY(1,1) NOT NULL PRIMARY KEY,
    colour varchar(50) NOT NULL,
    species varchar(50) NOT NULL,
    Filler char(10) NULL
);

/*Insert 20 million rows with 1% black and 1% swan but no black swans*/
WITH T
     AS (SELECT TOP 20000000 ROW_NUMBER() OVER (ORDER BY @@SPID) AS RN
         FROM   master..spt_values v1,
                master..spt_values v2,
                master..spt_values v3)
INSERT INTO dbo.animal
            (colour,
             species)
SELECT CASE
         WHEN RN % 100 = 1 THEN 'black'
         ELSE CAST(RN % 100 AS VARCHAR(3))
       END,
       CASE
         WHEN RN % 100 = 2 THEN 'swan'
         ELSE CAST(RN % 100 AS VARCHAR(3))
       END
FROM   T 

/*Create some indexes*/
CREATE NONCLUSTERED INDEX ix_species ON  dbo.animal(species);
CREATE NONCLUSTERED INDEX ix_colour ON  dbo.animal(colour);

Sekarang coba

SELECT TOP 10 *
FROM   animal
WHERE  colour LIKE 'black'
       AND species LIKE 'swan' 

Ini memberikan rencana di bawah ini yang dihitung biayanya 0.0563167.

Paket tersebut dapat melakukan gabungan gabungan antara hasil dari dua indeks pada idkolom. ( Lebih detail dari algoritma gabungan gabung di sini ).

Gabung bergabung membutuhkan kedua input untuk dipesan oleh kunci bergabung.

Indeks nonclustered dipesan oleh (species, id)dan (colour, id)masing - masing (indeks nonunique non clustered selalu memiliki locator baris ditambahkan ke akhir kunci secara implisit jika tidak ditambahkan secara eksplisit). Permintaan tanpa wildcard melakukan pencarian kesetaraan ke species = 'swan'dan colour ='black'. Karena setiap pencarian hanya mengambil satu nilai persis dari kolom terkemuka, baris yang cocok akan dipesan oleh idkarena itu, rencana ini dimungkinkan.

Operator rencana kueri mengeksekusi dari kiri ke kanan . Dengan operator kiri meminta baris dari anak-anaknya, yang pada gilirannya meminta baris dari anak - anak mereka (dan seterusnya hingga simpul daun tercapai). The TOPiterator akan berhenti meminta setiap baris lebih dari anaknya setelah 10 telah diterima.

SQL Server memiliki statistik pada indeks yang mengatakan bahwa 1% dari baris cocok dengan masing-masing predikat. Ini mengasumsikan bahwa statistik ini independen (yaitu tidak berkorelasi baik positif atau negatif) sehingga rata-rata setelah diproses 1.000 baris yang cocok dengan predikat pertama, akan ditemukan 10 yang cocok dengan yang kedua dan dapat keluar. (rencana di atas sebenarnya menunjukkan 987 daripada 1.000 tetapi cukup dekat).

Faktanya karena predikat berkorelasi negatif, rencana aktual menunjukkan bahwa semua 200.000 baris yang cocok perlu diproses dari masing-masing indeks tetapi ini dimitigasi sampai batas tertentu karena nol baris yang bergabung juga berarti nol pencarian benar-benar diperlukan.

Dibandingkan dengan

SELECT TOP 10 *
FROM   animal
WHERE  colour LIKE 'black%'
       AND species LIKE 'swan' 

Yang memberikan rencana di bawah ini yang dihitung biayanya 0.567943

Penambahan wildcard trailing sekarang telah menyebabkan pemindaian indeks. Biaya paket ini masih cukup rendah meskipun untuk pemindaian pada tabel 20 juta baris.

Menambahkan querytraceon 9130menunjukkan beberapa informasi lebih lanjut

SELECT TOP 10 *
FROM   animal
WHERE  colour LIKE 'black%'
       AND species LIKE 'swan'       
OPTION (QUERYTRACEON 9130)  

Dapat dilihat bahwa SQL Server menganggap hanya perlu memindai sekitar 100.000 baris sebelum menemukan 10 yang cocok dengan predikat dan TOPdapat berhenti meminta baris.

Sekali lagi ini masuk akal dengan asumsi independensi sebagai 10 * 100 * 100 = 100,000

Akhirnya mari kita coba dan paksa rencana persimpangan indeks

SELECT TOP 10 *
FROM   animal WITH (INDEX(ix_species), INDEX(ix_colour))
WHERE  colour LIKE 'black%'
       AND species LIKE 'swan' 

Ini memberikan rencana paralel bagi saya dengan perkiraan biaya 3,4625

Perbedaan utama di sini adalah bahwa colour like 'black%'predikat sekarang dapat cocok dengan berbagai warna. Ini berarti baris indeks yang cocok untuk predikat itu tidak lagi dijamin untuk disortir sesuai urutan id.

Misalnya indeks pencarian like 'black%'mungkin mengembalikan baris berikut

+------------+----+
|   Colour   | id |
+------------+----+
| black      | 12 |
| black      | 20 |
| black      | 23 |
| black      | 25 |
| blackberry |  1 |
| blackberry | 50 |
+------------+----+

Dalam setiap warna id akan dipesan tetapi id di berbagai warna mungkin tidak.

Akibatnya SQL Server tidak lagi dapat melakukan persimpangan indeks gabungan gabung (tanpa menambahkan operator pengurutan blokir) dan ia memilih untuk melakukan hash bergabung. Hash Join memblokir pada input build jadi sekarang biayanya mencerminkan fakta bahwa semua baris yang cocok perlu diproses dari input build daripada mengasumsikan hanya perlu memindai 1.000 seperti pada rencana pertama.

Input probe bukan pemblokiran dan masih salah memperkirakan bahwa ia akan dapat berhenti memeriksa setelah memproses 987 baris dari itu.

(Info lebih lanjut tentang Non-blocking vs iterator pemblokiran di sini)

Mengingat peningkatan biaya baris perkiraan tambahan dan hash bergabung dengan pemindaian clustered index parsial terlihat lebih murah.

Dalam praktiknya tentu saja pemindaian indeks berkerumun "parsial" tidak parsial sama sekali dan perlu dilakukan pemotongan keseluruhan 20 juta baris daripada 100 ribu yang diasumsikan ketika membandingkan rencana.

Meningkatkan nilai TOP(atau menghapus seluruhnya) akhirnya menemui titik kritis di mana jumlah baris yang diperkirakan akan dipindai oleh pemindaian CI perlu membuat rencana itu terlihat lebih mahal dan kembali ke rencana persimpangan indeks. Bagi saya cut off point antara dua rencana adalah TOP (89)vs TOP (90).

Untuk Anda mungkin berbeda karena tergantung seberapa lebar indeks berkerumun itu.

Menghapus TOPdan memaksa pemindaian CI

SELECT *
FROM   animal WITH (INDEX = 1)
WHERE  colour LIKE 'black%'
       AND species LIKE 'swan' 

Dibebankan pada 88.0586pada mesin saya untuk tabel contoh saya.

Jika SQL Server sadar bahwa kebun binatang tidak memiliki angsa hitam dan perlu melakukan pemindaian penuh alih-alih hanya membaca 100.000 baris, rencana ini tidak akan dipilih.

Saya sudah mencoba statistik multi-kolom animal(species,colour)dan animal(colour,species)dan menyaring statistik, animal (colour) where species = 'swan'tetapi tidak ada yang membantu meyakinkan bahwa angsa hitam tidak ada dan TOP 10pemindaian perlu memproses lebih dari 100.000 baris.

Ini disebabkan oleh "asumsi inklusi" di mana SQL Server pada dasarnya mengasumsikan bahwa jika Anda mencari sesuatu itu mungkin ada.

Pada 2008+ ada flag jejak terdokumentasi 4138 yang mematikan tujuan baris. Efek dari ini adalah bahwa rencana dihitung biayanya tanpa asumsi bahwa TOPakan memungkinkan operator anak untuk mengakhiri lebih awal tanpa membaca semua baris yang cocok. Dengan jejak bendera ini di tempat saya secara alami mendapatkan rencana persimpangan indeks yang lebih optimal.

SELECT TOP 10 *
FROM   animal
WHERE  colour LIKE 'black%'
       AND species LIKE 'swan'
OPTION (QUERYTRACEON 4138)       

Paket ini sekarang benar biaya untuk membaca 200 ribu baris penuh di kedua indeks mencari tetapi lebih dari biaya pencarian kunci (diperkirakan 2 ribu vs aktual 0. TOP 10Akan membatasi ini hingga maksimum 10 tetapi bendera jejak mencegah ini diperhitungkan) . Meski demikian, paket ini biayanya jauh lebih murah daripada pemindaian CI penuh sehingga dipilih.

Tentu saja rencana ini mungkin tidak akan optimal untuk kombinasi yang sangat umum. Seperti angsa putih.

Indeks gabungan pada animal (colour, species)atau idealnya animal (species, colour)akan memungkinkan kueri menjadi jauh lebih efisien untuk kedua skenario.

Untuk menggunakan indeks komposit yang paling efisien, LIKE 'swan'perlu diubah juga = 'swan'.

Tabel di bawah ini menunjukkan predikat pencarian dan predikat residual yang ditunjukkan dalam rencana eksekusi untuk keempat permutasi.

+----------------------------------------------+-------------------+----------------------------------------------------------------+----------------------------------------------+
|                 WHERE clause                 |       Index       |                         Seek Predicate                         |              Residual Predicate              |
+----------------------------------------------+-------------------+----------------------------------------------------------------+----------------------------------------------+
| colour LIKE 'black%' AND species LIKE 'swan' | ix_colour_species | colour >= 'black' AND colour < 'blacL'                         | colour like 'black%' AND species like 'swan' |
| colour LIKE 'black%' AND species LIKE 'swan' | ix_species_colour | species >= 'swan' AND species <= 'swan'                        | colour like 'black%' AND species like 'swan' |
| colour LIKE 'black%' AND species = 'swan'    | ix_colour_species | (colour,species) >= ('black', 'swan')) AND colour < 'blacL'    | colour LIKE 'black%' AND species = 'swan'    |
| colour LIKE 'black%' AND species = 'swan'    | ix_species_colour | species = 'swan' AND (colour >= 'black' and colour <  'blacL') | colour like 'black%'                         |
+----------------------------------------------+-------------------+----------------------------------------------------------------+----------------------------------------------+

Mendapati hal ini menarik, saya melakukan pencarian dan menemukan Q / A ini. Bagaimana (dan mengapa) TOP mempengaruhi rencana eksekusi?

Pada dasarnya, menggunakan TOP mengubah biaya operator yang mengikutinya (dengan cara nontrivial), yang menyebabkan rencana overal berubah juga (alangkah baiknya jika Anda memasukkan ExecPlans dengan dan tanpa TOP 10), yang cukup banyak mengubah pelaksanaan overal dari kueri.

Semoga ini membantu.

Sebagai contoh, saya mencobanya pada database dan: -Ketika tidak ada top dipanggil, paralelisme digunakan -Dengan TOP, paralelisme tidak digunakan

Jadi, sekali lagi, menunjukkan rencana eksekusi Anda akan memberikan lebih banyak info.

Semoga harimu menyenangkan

Saya percaya ini mungkin karena sifat dasar MSSQL 2005 dan cara pengoptimal kueri memutuskan rencana eksekusi mana yang paling efisien.

Jika Anda menggunakan variabel SQL, itu harus 'menipu' pengoptimal kueri agar menggunakan pencocokan hash alih-alih bersarang loop yang akan menghasilkan tingkat paralelisme yang jauh lebih tinggi.

Mencoba:

DECLARE @topn INT = 10
SELECT TOP (@topn) *
FROM    animal
WHERE   colour LIKE 'black%' 
AND species LIKE 'swan'