Pembaruan lambat di meja besar dengan subquery

Dengan SourceTablememiliki catatan> 15MM dan Bad_Phrasememiliki catatan > 3K, kueri berikut ini membutuhkan waktu hampir 10 jam untuk berjalan di SQL Server 2005 SP4.

UPDATE [SourceTable] 
SET 
    Bad_Count=
             (
               SELECT 
                  COUNT(*) 
               FROM Bad_Phrase 
               WHERE 
                  [SourceTable].Name like '%'+Bad_Phrase.PHRASE+'%'
             )

Dalam bahasa Inggris, kueri ini menghitung jumlah frasa berbeda yang tercantum dalam Bad_Phrase yang merupakan substring bidang Namedalam SourceTabledan kemudian menempatkan hasil itu di bidang Bad_Count.

Saya ingin beberapa saran tentang cara menjalankan kueri ini dengan lebih cepat.

Sementara saya setuju dengan komentator lain bahwa ini adalah masalah yang mahal secara komputasi, saya pikir ada banyak ruang untuk perbaikan dengan mengubah-ubah SQL yang Anda gunakan. Sebagai ilustrasi, saya membuat kumpulan data palsu dengan nama 15MM dan frase 3K, menjalankan pendekatan lama, dan menjalankan pendekatan baru.

Skrip lengkap untuk menghasilkan kumpulan data palsu dan mencoba pendekatan baru

TL; DR

Di komputer saya dan kumpulan data palsu ini, pendekatan asli memakan waktu sekitar 4 jam untuk dijalankan. Pendekatan baru yang diusulkan membutuhkan waktu sekitar 10 menit , peningkatan yang cukup besar. Berikut ini ringkasan singkat dari pendekatan yang diusulkan:

• Untuk setiap nama, buat substring mulai dari setiap karakter offset (dan ditutup pada panjang frasa buruk terpanjang, sebagai pengoptimalan)
• Buat indeks berkerumun di substring ini
• Untuk setiap frasa buruk, lakukan pencarian ke substring ini untuk mengidentifikasi kecocokan apa pun
• Untuk setiap string asli, hitung jumlah frasa buruk berbeda yang cocok dengan satu atau beberapa substring dari string itu

Pendekatan asli: analisis algoritmik

Dari rencana UPDATEpernyataan asli , kita dapat melihat bahwa jumlah pekerjaan sebanding secara linear dengan jumlah nama (15MM) dan jumlah frasa (3K). Jadi, jika kita gandakan jumlah nama dan frasa sebanyak 10, waktu keseluruhan akan menjadi ~ 100 kali lebih lambat.

Permintaan sebenarnya sebanding dengan panjang namejuga; sementara ini sedikit tersembunyi dalam rencana kueri, ia datang melalui "jumlah eksekusi" untuk mencari ke dalam spool tabel. Dalam rencana aktual, kita dapat melihat bahwa ini terjadi bukan hanya sekali per name, tetapi sebenarnya sekali per karakter offset dalam name. Jadi pendekatan ini adalah O ( # names* # phrases* name length) dalam kompleksitas run-time.

Pendekatan baru: kode

Kode ini juga tersedia dalam pastebin lengkap tetapi saya telah menyalinnya di sini untuk kenyamanan. Pastebin juga memiliki definisi prosedur lengkap, yang mencakup variabel @minIddan @maxIdyang Anda lihat di bawah untuk menentukan batas-batas batch saat ini.

-- For each name, generate the string at each offset
DECLARE @maxBadPhraseLen INT = (SELECT MAX(LEN(phrase)) FROM Bad_Phrase)
SELECT s.id, sub.sub_name
INTO #SubNames
FROM (SELECT * FROM SourceTable WHERE id BETWEEN @minId AND @maxId) s
CROSS APPLY (
    -- Create a row for each substring of the name, starting at each character
    -- offset within that string.  For example, if the name is "abcd", this CROSS APPLY
    -- will generate 4 rows, with values ("abcd"), ("bcd"), ("cd"), and ("d"). In order
    -- for the name to be LIKE the bad phrase, the bad phrase must match the leading X
    -- characters (where X is the length of the bad phrase) of at least one of these
    -- substrings. This can be efficiently computed after indexing the substrings.
    -- As an optimization, we only store @maxBadPhraseLen characters rather than
    -- storing the full remainder of the name from each offset; all other characters are
    -- simply extra space that isn't needed to determine whether a bad phrase matches.
    SELECT TOP(LEN(s.name)) SUBSTRING(s.name, n.n, @maxBadPhraseLen) AS sub_name 
    FROM Numbers n
    ORDER BY n.n
) sub
-- Create an index so that bad phrases can be quickly compared for a match
CREATE CLUSTERED INDEX IX_SubNames ON #SubNames (sub_name)

-- For each name, compute the number of distinct bad phrases that match
-- By "match", we mean that the a substring starting from one or more 
-- character offsets of the overall name starts with the bad phrase
SELECT s.id, COUNT(DISTINCT b.phrase) AS bad_count
INTO #tempBadCounts
FROM dbo.Bad_Phrase b
JOIN #SubNames s
    ON s.sub_name LIKE b.phrase + '%'
GROUP BY s.id

-- Perform the actual update into a "bad_count_new" field
-- For validation, we'll compare bad_count_new with the originally computed bad_count
UPDATE s
SET s.bad_count_new = COALESCE(b.bad_count, 0)
FROM dbo.SourceTable s
LEFT JOIN #tempBadCounts b
    ON b.id = s.id
WHERE s.id BETWEEN @minId AND @maxId

Pendekatan baru: rencana kueri

Pertama, kami membuat substring mulai dari setiap karakter offset

Kemudian buat indeks berkerumun di substring ini

Sekarang, untuk setiap frasa buruk, kami mencari ke dalam substring ini untuk mengidentifikasi kecocokan apa pun. Kami kemudian menghitung jumlah frasa buruk berbeda yang cocok dengan satu atau lebih substring dari string itu. Ini benar-benar langkah kunci; karena cara kami telah mengindeks substring, kami tidak lagi harus memeriksa produk silang lengkap dari frasa dan nama yang buruk. Langkah ini, yang melakukan perhitungan aktual, hanya menyumbang sekitar 10% dari run-time aktual (sisanya adalah pra-pemrosesan substring).

Terakhir, lakukan pernyataan pembaruan aktual, menggunakan a LEFT OUTER JOINuntuk menetapkan hitungan 0 pada nama apa pun yang kami tidak menemukan frasa buruk.

Pendekatan baru: analisis algoritmik

Pendekatan baru dapat dibagi menjadi dua fase, pra-pemrosesan dan pencocokan. Mari kita mendefinisikan variabel-variabel berikut:

• N = # nama
• B = # frasa buruk
• L = panjang nama rata-rata, dalam karakter

Fase pra-pemrosesan adalah O(N*L * LOG(N*L))untuk membuat N*Lsubstring dan kemudian mengurutkannya.

Pencocokan yang sebenarnya adalah O(B * LOG(N*L))untuk mencari ke dalam substring untuk setiap frase buruk.

Dengan cara ini, kami telah membuat algoritme yang tidak skala secara linear dengan jumlah frasa buruk, kinerja kunci terbuka saat kami skala ke frasa 3K dan seterusnya. Dengan kata lain, implementasi asli membutuhkan sekitar 10x selama kita beralih dari 300 frase buruk menjadi 3K frase buruk. Demikian pula akan butuh 10x lagi selama kita beralih dari 3K frase buruk menjadi 30K. Implementasi baru, bagaimanapun, akan meningkatkan sub-linear dan pada kenyataannya membutuhkan waktu kurang dari 2x waktu yang diukur pada frase buruk 3K ketika ditingkatkan hingga 30 ribu frase buruk.

Asumsi / Peringatan

• Saya membagi pekerjaan keseluruhan ke dalam batch berukuran sedang. Ini mungkin ide yang bagus untuk kedua pendekatan, tetapi ini sangat penting untuk pendekatan baru sehingga SORTpada substring independen untuk setiap batch dan mudah masuk dalam memori. Anda dapat memanipulasi ukuran batch sesuai kebutuhan, tetapi tidak bijaksana untuk mencoba semua baris 15MM dalam satu batch.
• Saya menggunakan SQL 2014, bukan SQL 2005, karena saya tidak memiliki akses ke mesin SQL 2005. Saya telah berhati-hati untuk tidak menggunakan sintaks yang tidak tersedia di SQL 2005, tapi saya mungkin masih mendapatkan manfaat dari fitur menulis malas tempdb di SQL 2012+ dan fitur SELECT INTO paralel dalam SQL 2014.
• Panjang nama dan frasa cukup penting untuk pendekatan baru. Saya berasumsi bahwa frasa buruk biasanya cukup pendek karena itu cenderung cocok dengan kasus penggunaan dunia nyata. Nama-nama itu sedikit lebih panjang daripada frasa yang buruk, tetapi dianggap bukan ribuan karakter. Saya pikir ini adalah asumsi yang adil, dan string nama yang lebih panjang akan memperlambat pendekatan awal Anda juga.
• Beberapa bagian dari perbaikan (tapi tidak ada yang dekat dengan semua itu) adalah karena fakta bahwa pendekatan baru dapat memanfaatkan paralelisme lebih efektif daripada pendekatan lama (yang berjalan satu-threaded). Saya menggunakan laptop quad core, jadi senang memiliki pendekatan yang dapat menggunakan core ini.

Posting blog terkait

Aaron Bertrand mengeksplorasi jenis solusi ini secara lebih rinci di posting blognya. Salah satu cara untuk mendapatkan indeks mencari% wildcard terkemuka .

Mari kita selesaikan masalah yang sudah jelas yang dibawakan oleh Aaron Bertrand dalam komentar sejenak:

Jadi, Anda memindai tabel 3K kali, dan berpotensi memperbarui semua baris 15MM semua 3K kali, dan Anda mengharapkannya cepat?

Fakta bahwa subquery Anda menggunakan kartu liar di kedua sisi secara dramatis memengaruhi daya beli . Untuk mengambil kutipan dari posting blog itu:

Itu berarti SQL Server harus membaca setiap baris dari tabel Produk, periksa untuk melihat apakah ada "gila" di mana saja dalam nama, dan kemudian mengembalikan hasil kami.

Ganti kata "nut" untuk setiap "bad word" dan "Product" untuk SourceTable, lalu gabungkan dengan komentar Aaron dan Anda harus mulai melihat mengapa sangat sulit (baca tidak mungkin) untuk membuatnya berjalan cepat menggunakan algoritma Anda saat ini.

Saya melihat beberapa opsi:

1. Meyakinkan bisnis untuk membeli server monster yang memiliki kekuatan sangat besar sehingga bisa mengatasi kueri dengan kekuatan geser kasar. (Itu tidak akan terjadi, jadi silangkan jari Anda pilihan lain lebih baik)
2. Dengan menggunakan algoritma Anda yang sudah ada, terima rasa sakitnya sekali dan kemudian sebarkan. Ini akan melibatkan penghitungan kata-kata buruk pada sisipan yang akan memperlambat sisipan, dan hanya memperbarui seluruh tabel ketika kata buruk yang baru dimasukkan / ditemukan.
3. Merangkul jawaban Geoff . Ini adalah algoritma yang hebat, dan jauh lebih baik daripada apa pun yang saya hasilkan.
4. Lakukan opsi 2 tetapi gantikan algoritma Anda dengan Geoff's.

Tergantung pada kebutuhan Anda, saya akan merekomendasikan opsi 3 atau 4.

pertama itu hanya pembaruan aneh

Update [SourceTable]  
   Set [SourceTable].[Bad_Count] = [fix].[count]
  from [SourceTable] 
  join ( Select count(*) 
           from [Bad_Phrase]  
          where [SourceTable].Name like '%' + [Bad_Phrase].[PHRASE] + '%')

Seperti '%' + [Bad_Phrase]. [PHRASE] membunuh Anda.
Itu tidak bisa menggunakan indeks

Desain data tidak optimal untuk kecepatan
Bisakah Anda membagi [Bad_Phrase]. [PHRASE] menjadi satu frase / kata?
Jika frasa / kata yang sama muncul lebih dari satu, Anda dapat memasukkannya lebih dari satu kali jika Anda menginginkannya memiliki jumlah yang lebih tinggi.
Jadi, jumlah baris dalam frase buruk akan naik.
Jika Anda dapat, maka ini akan jauh lebih cepat.

Update [SourceTable]  
   Set [SourceTable].[Bad_Count] = [fix].[count]
  from [SourceTable] 
  join ( select [PHRASE], count(*) as count 
           from [Bad_Phrase] 
          group by [PHRASE] 
       ) as [fix]
    on [fix].[PHRASE] = [SourceTable].[name]  
 where [SourceTable].[Bad_Count] <> [fix].[count]

Tidak yakin apakah 2005 mendukungnya tetapi Indeks Teks Lengkap dan menggunakan Berisi