Pertanyaan ini mirip dengan Mengoptimalkan Pencarian Rentang IP? tapi itu terbatas pada SQL Server 2000.
Misalkan saya memiliki 10 juta rentang untuk sementara disimpan dalam tabel terstruktur dan diisi seperti di bawah ini.
CREATE TABLE MyTable
(
Id INT IDENTITY PRIMARY KEY,
RangeFrom INT NOT NULL,
RangeTo INT NOT NULL,
CHECK (RangeTo > RangeFrom),
INDEX IX1 (RangeFrom,RangeTo),
INDEX IX2 (RangeTo,RangeFrom)
);
WITH RandomNumbers
AS (SELECT TOP 10000000 ABS(CRYPT_GEN_RANDOM(4)%100000000) AS Num
FROM sys.all_objects o1,
sys.all_objects o2,
sys.all_objects o3,
sys.all_objects o4)
INSERT INTO MyTable
(RangeFrom,
RangeTo)
SELECT Num,
Num + 1 + CRYPT_GEN_RANDOM(1)
FROM RandomNumbers
Saya perlu tahu semua rentang yang berisi nilai 50,000,000
. Saya mencoba pertanyaan berikut
SELECT *
FROM MyTable
WHERE 50000000 BETWEEN RangeFrom AND RangeTo
SQL Server menunjukkan bahwa ada 10.951 pembacaan logis dan hampir 5 juta baris dibaca untuk mengembalikan 12 pencocokan.
Bisakah saya meningkatkan kinerja ini? Setiap restrukturisasi tabel atau indeks tambahan baik-baik saja.
sql-server
optimization
Martin Smith
sumber
sumber
contains
permintaan dan sementara mereka bekerja dengan baik dalam mengurangi jumlah data yang dibaca mereka tampaknya menambahkan lainnya overhead yang mengatasi ini.Jawaban:
Columnstore sangat senang di sini dibandingkan dengan indeks nonclustered yang memindai setengah tabel. Indeks columnstore nonclustered memberikan sebagian besar manfaat tetapi memasukkan data yang dipesan ke dalam indeks columnstore clustered bahkan lebih baik.
Dengan desain saya bisa mendapatkan penghapusan rowgroup pada
RangeFrom
kolom yang akan menghilangkan setengah dari rowgroup saya. Tetapi karena sifat data saya juga mendapatkan penghapusan rowgroup padaRangeTo
kolom juga:Untuk tabel yang lebih besar dengan lebih banyak data variabel ada berbagai cara untuk memuat data untuk menjamin penghapusan rowgroup terbaik di kedua kolom. Khusus untuk data Anda, kueri membutuhkan waktu 1 ms.
sumber
Paul White menunjukkan jawaban untuk pertanyaan serupa yang berisi tautan ke artikel menarik oleh Itzik Ben Gan . Ini menjelaskan model "Pohon Interval Relasional Statis" yang memungkinkan ini dilakukan secara efisien.
Singkatnya, pendekatan ini melibatkan penyimpanan nilai yang dihitung ("forknode") berdasarkan nilai interval di baris. Saat mencari rentang yang memotong rentang lain, dimungkinkan untuk menghitung ulang nilai-nilai forknode yang mungkin dimiliki oleh baris-baris yang cocok dan menggunakan ini untuk menemukan hasil dengan maksimum 31 operasi pencarian (di bawah ini mendukung bilangan bulat dalam kisaran 0 hingga maks yang ditandatangani 32) bit int)
Berdasarkan ini saya merestrukturisasi tabel seperti di bawah ini.
Dan kemudian menggunakan kueri berikut (artikel mencari interval berpotongan sehingga menemukan interval yang mengandung titik adalah kasus yang merosot)
Ini biasanya dijalankan
1ms
pada mesin saya ketika semua halaman dalam cache - dengan statistik IO.dan merencanakan
NB: Sumbernya menggunakan TVF multistatement daripada CTE rekursif untuk mendapatkan node untuk bergabung tetapi untuk kepentingan membuat jawaban saya mandiri saya telah memilih yang terakhir. Untuk penggunaan produksi, saya mungkin akan menggunakan TVF.
sumber
Saya dapat menemukan pendekatan mode baris yang bersaing dengan pendekatan N / CCI, tetapi Anda perlu tahu sesuatu tentang data Anda. Misalkan Anda memiliki kolom yang berisi perbedaan
RangeFrom
danRangeTo
dan Anda mengindeksnya bersama denganRangeFrom
:Jika Anda mengetahui semua nilai berbeda
DiffOfColumns
maka Anda dapat melakukan pencarian untuk setiap nilaiDiffOfColumns
dengan filter rentang aktifRangeTo
untuk mendapatkan semua data yang relevan. Misalnya, jika kita tahu bahwaDiffOfColumns
= 2 maka nilai yang diizinkan hanya untukRangeFrom
49999998, 49999999, dan 50000000. Rekursi dapat digunakan untuk mendapatkan semua nilai yang berbedaDiffOfColumns
dan ini bekerja dengan baik untuk kumpulan data Anda karena hanya ada 256 di antaranya. Kueri di bawah ini membutuhkan sekitar 6 ms pada mesin saya:Anda dapat melihat bagian rekursif biasa bersama dengan indeks mencari setiap nilai yang berbeda:
Kelemahan dari pendekatan ini adalah mulai lambat ketika ada terlalu banyak nilai berbeda untuk
DiffOfColumns
. Mari kita lakukan tes yang sama, tetapi gunakanCRYPT_GEN_RANDOM(2)
sebagai gantiCRYPT_GEN_RANDOM(1)
.Kueri yang sama sekarang menemukan 65536 baris dari bagian rekursif dan membutuhkan 823 ms CPU pada mesin saya. Ada PAGELATCH_SH menunggu dan hal-hal buruk lainnya sedang terjadi. Saya dapat meningkatkan kinerja dengan menambahkan nilai diff untuk menjaga agar jumlah nilai unik tetap terkendali dan menyesuaikan untuk bucket di
CROSS APPLY
. Untuk rangkaian data ini saya akan mencoba 256 ember:Salah satu cara untuk menghindari mendapatkan baris tambahan (sekarang saya membandingkan dengan nilai bulat bukan nilai sebenarnya) adalah dengan memfilter pada
RangeTo
:Permintaan lengkap sekarang membutuhkan 6 ms pada mesin saya.
sumber
Salah satu cara alternatif untuk mewakili suatu rentang adalah sebagai titik pada suatu garis.
Di bawah ini memigrasikan semua data ke tabel baru dengan kisaran yang direpresentasikan sebagai
geometry
tipe data.Kueri yang setara untuk menemukan rentang yang berisi nilai di
50,000,000
bawah.Bacaan untuk ini menunjukkan peningkatan pada
10,951
dari permintaan asli.Namun tidak ada peningkatan yang signifikan dibandingkan yang asli dalam hal waktu yang berlalu . Hasil eksekusi yang umum adalah 250 ms vs 252 ms.
Rencana pelaksanaan lebih kompleks seperti di bawah ini
Satu-satunya kasus di mana penulisan ulang bekerja andal lebih baik bagi saya adalah dengan cache dingin.
Sangat mengecewakan dalam hal ini dan sulit untuk merekomendasikan penulisan ulang ini tetapi publikasi hasil negatif juga dapat bermanfaat.
sumber
Sebagai penghormatan kepada tuan robot baru kami, saya memutuskan untuk melihat apakah ada fungsi R-dan Python yang baru dapat membantu kami di sini. Jawabannya adalah tidak, setidaknya untuk skrip yang saya dapat bekerja dan mengembalikan hasil yang benar. Jika ada orang dengan pengetahuan yang lebih baik datang, yah, jangan ragu untuk memukul saya. Harga saya masuk akal.
Untuk melakukan ini, saya mengatur VM dengan 4 core dan 16 GB RAM, berpikir ini akan cukup untuk menangani set data ~ 200MB.
Mari kita mulai dengan bahasa yang tidak ada di Boston!
R
Ini waktu yang buruk.
The rencana eksekusi yang cukup tidak menarik, meskipun aku tidak tahu mengapa operator tengah memiliki untuk menghubungi kami nama.
Selanjutnya, koding dengan krayon!
Python
Tepat ketika Anda berpikir itu tidak bisa lebih buruk daripada R:
Rencana eksekusi bermulut kotor lainnya :
Hmm dan Hmmer
Sejauh ini, saya tidak terkesan. Saya tidak sabar untuk menghapus VM ini.
sumber
DECLARE @input INT = 50000001; EXEC dbo.sp_execute_external_script @language = N'R', @script = N'OutputDataSet <- InputDataSet[which(x >= InputDataSet$RangeFrom & x <= InputDataSet$RangeTo) , ]', @parallel = 1, @input_data_1 = N'SELECT Id, RangeFrom, RangeTo FROM dbo.MyTable;', @params = N'@x INT', @x = 50000001 WITH RESULT SETS ( ( Id INT NOT NULL, RangeFrom INT NOT NULL, RangeTo INT NOT NULL ));
tapi ya kinerjanya tidak bagus. Saya menggunakan R untuk hal-hal yang tidak dapat Anda lakukan dalam SQL, katakan jika Anda ingin memprediksi sesuatu.Saya menemukan solusi yang cukup bagus menggunakan kolom yang dihitung, namun itu hanya baik untuk nilai tunggal. Yang sedang berkata, jika Anda memiliki nilai sihir, mungkin itu sudah cukup.
Mulai dengan sampel yang Anda berikan, lalu modifikasi tabel:
Pertanyaannya menjadi:
Yang mengembalikan hasil yang sama dengan permintaan awal Anda. Dengan rencana eksekusi dimatikan, berikut adalah statistik (terpotong karena singkatnya):
Dan inilah rencana permintaannya :
sumber
WHERE (50000000 BETWEEN RangeFrom AND RangeTo) INCLUDE (..)
?CREATE INDEX IX1_redo ON dbo.MyTable (curtis_jackson) INCLUDE (RangeFrom, RangeTo) WHERE RangeTo >= 50000000 AND RangeFrom <= 50000000
akan bekerja. Dan permintaanSELECT * FROM MyTable WHERE RangeTo >= 50000000 AND RangeFrom <= 50000000;
itu menggunakannya - jadi tidak banyak kebutuhan untuk Curtis yang malangSolusi saya didasarkan pada pengamatan bahwa interval memiliki lebar maksimum W yang diketahui . Untuk data sampel ini adalah satu byte atau 256 bilangan bulat. Oleh karena itu untuk pencarian nilai parameter yang diberikan P kita tahu RangeFrom terkecil yang dapat di set hasil P - W . Menambahkan ini ke predikat memberi
Mengingat pengaturan asli dan permintaan mesin saya (64 bit Windows 10, 4-core hyperthreaded i7, 2.8GHz, 16GB RAM) mengembalikan 13 baris. Kueri itu menggunakan pencarian indeks paralel dari indeks (RangeFrom, RangeTo). Permintaan yang direvisi juga melakukan pencarian indeks paralel pada indeks yang sama.
Pengukuran untuk kueri asli dan revisi adalah
Untuk kueri asli, jumlah baris yang dibaca sama dengan jumlah baris yang kurang dari atau sama dengan @P. Pengoptimal kueri (QO) tidak memiliki alternatif selain membacanya semuanya karena tidak dapat menentukan sebelumnya yang jika baris ini akan memenuhi predikat. Indeks multi-kolom pada (RangeFrom, RangeTo) tidak berguna dalam menghilangkan baris yang tidak cocok dengan RangeTo karena tidak ada korelasi antara kunci indeks pertama dan kedua yang dapat diterapkan. Misalnya, baris pertama mungkin memiliki interval kecil dan dihilangkan sedangkan baris kedua memiliki interval besar dan dikembalikan, atau sebaliknya.
Dalam satu upaya yang gagal saya mencoba memberikan kepastian itu melalui kendala pemeriksaan:
Tidak ada bedanya.
Dengan memasukkan pengetahuan eksternal saya tentang distribusi data ke dalam predikat, saya dapat menyebabkan QO melewati baris RangeFrom bernilai rendah, yang tidak pernah bisa menjadi bagian dari resultset, dan melintasi kolom utama indeks ke baris yang dapat diterima. Ini menunjukkan dalam pencarian predikat yang berbeda untuk setiap permintaan.
Dalam argumen cermin batas atas RangeTo adalah P + W . Ini tidak berguna, bagaimanapun, karena tidak ada korelasi antara RangeFrom dan RangeTo yang akan memungkinkan kolom tambahan indeks multi-kolom untuk menghilangkan baris. Karenanya tidak ada manfaat dari menambahkan klausa ini ke kueri.
Pendekatan ini mendapatkan sebagian besar manfaatnya dari ukuran interval kecil. Karena ukuran interval yang mungkin meningkatkan jumlah baris bernilai rendah yang dilewati berkurang, meskipun beberapa masih akan dilewati. Dalam kasus yang membatasi, dengan interval sebesar rentang data, pendekatan ini tidak lebih buruk daripada permintaan asli (yang saya akui kenyamanan dingin).
Saya mohon maaf atas kesalahan off-by-one apa pun yang mungkin ada dalam jawaban ini.
sumber