Masalah
Kita semua memiliki hari-hari di tempat kerja ketika seseorang mendatangi kita dengan persyaratan yang benar-benar mustahil, pemenuhannya membutuhkan mukjizat. Kasus saya terjadi ketika seorang rekan pemasaran mendekati saya dengan pertanyaan yang tampaknya sederhana: jika saya bisa mendapatkan data dari satu meja untuk bulan tertentu beberapa tahun yang lalu. Tidak apa-apa, Anda mungkin berkata, tapi saya samar-samar ingat bahwa meja itu sangat besar. Tabel memiliki bidang datetime pada saat pembuatan, tetapi apakah ada indeks pada bidang itu?
Tentu saja, mereka juga ingin mendapatkan data dengan cepat. Saya, seperti biasa, berkata: "Saya akan melihat apa yang bisa saya lakukan" dan pergi untuk melihat lebih dekat ke meja yang sedang dibahas. Semoga sukses tidak akan pernah meninggalkan kita, indeksnya benar-benar tidak ada, dan meja sangat besar. Bukan masalah, kita bisa memindai tabel, kan? Salah. Jika saya telah belajar sesuatu dari tahun-tahun bekerja dengan database, itu yang penting. Tabel dengan ratusan juta catatan dan beberapa kolom bilangan bulat akan cukup hebat. Kemudian tambahkan berbagai kolom varchar dan datetime. Nah, itu tantangan nyata, bukan?
Meja yang saya lihat memiliki satu miliar catatan, secara harfiah. Pemindaian tabel sederhana bisa memakan waktu lebih dari satu hari, dan saya perlu memproses data yang diekstraksi juga. Selain itu, memindai tabel dengan ukuran ini mungkin tidak bermanfaat bagi kesehatan keseluruhan sistem seperti yang terlihat pada pandangan pertama. Semua halaman yang dipindai harus diekstraksi dari disk ke dalam memori server sql dengan mengisinya. Ini, pada gilirannya, akan membongkar halaman data dari cache, yang dapat digunakan untuk tugas operasional saat ini. Permintaan pengguna Anda saat ini mungkin menunggu lebih lama saat server membaca ulang data dari disk, daripada dengan cepat menggunakan kembali halaman data dari memori. Kinerja dapat menurun, dan dalam kasus terburuk, server mungkin benar-benar bertekuk lutut. Jadi,saat memindai tabel, Anda harus menggunakan teknik khusus - jalankan dalam batch kecil, menjaga posisi saat ini dan hasil antara di suatu tempat. Pendekatan ini memungkinkan server untuk mengkonfigurasi ulang dan bernafas tanpa membiarkan hit kinerja besar.
Jadi saya merenungkan skenario kerja dan memperkirakan waktu yang diperlukan untuk menjalankan dan menjalankan skrip ketika saya sadar bahwa nilai waktu pembuatan waktu terkait dengan ID tabel. Identifier (ID) adalah kolom dengan nilai yang terus tumbuh dan kunci utama berdasarkan itu. Saat mengambil oleh pengenal, nilai tanggal dan waktu pembuatan secara alami dipilah sebelumnya dengan cara yang sama seperti nilai pengenal. Tunggu, pikirku, aku bisa mengimplementasikan sesuatu yang sangat cepat daripada pemindaian tabel, sesuatu yang dalam kasus terburuk hanya akan mengambil 30 langkah alih-alih 500.000.000! Pencarian Biner!
Cari
Untuk semua orang yang, seperti saya, lulus dari pelatihan dahulu kala, pelatihan kembali dalam teori harus sesuai urutan. Pencarian biner adalah cara sederhana namun sangat efisien untuk menemukan nilai dalam array yang diurutkan (dalam kasus kami, kolom tabel). Array harus dipilah sebelumnya dan terbatas. Pencarian dilakukan dengan membandingkan elemen tengah array Anda dengan target. Jika mereka sama, maka pencarian selesai. Jika tidak, Anda menghapus setengah di mana elemen yang Anda cari jelas hilang, dan ulangi langkah sebelumnya sampai Anda memilikinya. Temukan tengah, bandingkan target dengan itu, jika mereka tidak sama, hapus setengah lagi, dan seterusnya. Jumlah langkah yang diperlukan untuk menemukan tujuan dalam kasus terburuk, ketika Anda menemukannya pada langkah terakhir, adalah log (N), di mana N adalah jumlah elemen. Bandingkan ini dengan N / 2,ketika Anda hanya mengulangi array. Secara umum, ini akan menjadi N, tetapi jika kita bisa menebak apakah tujuannya lebih dekat ke akhir, kita bisa kembali, sehingga mengurangi jumlah langkah yang diperlukan.
Dalam kasus saya, N = 1.000.000.000 dan ini adalah bagaimana saya sampai pada dua angka di atas: 30 dan 500.000.000. Identifier (ID) akan memainkan peran enumerator array, dan datetime pembuatan akan menjadi nilai elemen array. Namun ada satu peringatan. Pencacah larik, menurut definisi, adalah urutan bilangan bulat yang berkelanjutan. ID tabel mudah berisi spasi karena penghapusan catatan atau ID overflow. Cukup menentukan tengah dengan membagi rentang pengidentifikasi dengan 2, Anda tidak boleh berharap bahwa akan ada entri dengan pengenal tersebut. Alih-alih mencari secara langsung, saya harus menggunakan fungsi top (). Sesuatu seperti itu:
Select top(1) * from Table where id <= @id order by id descSaya menggunakan "<=" dan "desc" karena saya ingin menemukan nilai yang sama dengan atau segera sebelum sasaran. Dalam kondisi @l, @r adalah batas kiri dan kanan, masing-masing,Indo Apakah tengah, @dt adalah waktu pembuatan, tdt Apakah tujuannya dan Indor adalah ID tabel sebenarnya (ID), algoritme mungkin terlihat seperti ini:
while @l <@r
begin
--
@id = @l +floor((@r-@l)/2)
--
select top(1) @idr = id, @dt = creation_datetime from Table where id <= @id order by id desc
--
if(@dt<@tdt)
@l = @id +1
else
@r = @id
end
Ditemukan terakhir Indor akan menjadi pengidentifikasi entri diikuti oleh yang diinginkan. Algoritma memiliki semacam offset "kiri", yaitu kecenderungan untuk memilih yang paling kiri dari semua nilai. Karena saya ingin entri nilai sedekat mungkin dengan target, saya juga memeriksa tetangga kiri dan kanan terdekat di tabel untuk melihat apakah ada yang lebih baik. Harap dicatat bahwa saya tidak menggunakan ID asli dari tabel untuk proses iterasi, seperti dalam kasus ini, dengan spasi dalam nilai ID, dan dalam beberapa keadaan, algoritma bisa masuk ke loop tak terbatas.
Butuh waktu sekitar satu jam untuk menulis dan menguji naskah. Dengan menggunakannya, saya menemukan catatan pertama dengan tanggal dan waktu pembuatan yang spesifik. Setelah itu, saya menggunakan pernyataan pilih sederhana dengan klausa where yang berisi kedua kondisi: id> = @ dan creation_datetime> = @ dt1 dan creation_datetime <@ dt2. Saya hanya perlu memastikan optimizer akan memilih untuk menggunakan kunci utama alih-alih pemindaian indeks atau tabel. Secara keseluruhan, saya melakukannya dalam waktu kurang dari 2 jam! Itu mengejutkan untuk menemukan lagi bahwa algoritma bukanlah sesuatu yang esoteris terkubur jauh di dalam server sql, tetapi sesuatu yang dapat dengan mudah digunakan dalam pekerjaan sehari-hari.
Di bawah ini adalah seluruh naskah yang saya tulis. Silakan lihat komentar di dalam untuk memahami cara menggunakannya.
/*
, .
, datetime 3
*/
-- , ,
declare @debug bit = 0
-- @Table - , .
declare @Table varchar(128) = 'TableX'
-- @Id - (id)
declare @ID varchar(128) = 'Id'
-- @DateTimeColumn - datetime
declare @DateTimeColumn varchar(128) = 'created_dt'
--
declare @TargetDateTime datetime = '2020-01-03 18:23:03'
declare @Sql varchar(max)
set @sql = '
--
declare @debug bit = <debug>
--
declare @tdt datetime = ''<TargetDateTime>''
-- ( )
declare @id bigint
--
declare @l bigint, @r bigint
-- , , datetime
declare @dt datetime, @idr bigint
-- «» «»
select @l = min(<ID>), @r = max(<ID>) from <Table>
while @l < @r
begin
--
set @id = @l +floor((@r-@l)/2)
--
select top(1) @dt = <DateTimeColumn>, @idr = <ID> from <Table> where <ID> <= @id order by <ID> desc
-- ,
if( @debug = 1 )
begin
select ''@id'' = @id, ''@l'' = @l, ''@r'' = @r, ''@dt'' = @dt, ''@idr'' = @idr
end
if(@dt < @tdt)
set @l = @id +1
else
set @r = @id
end
-- ,
declare @t table(id bigint, dt datetime, dlt float)
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float))
from <Table>
where <ID> < @idr
order by <ID> desc
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float))
from <Table>
where <ID> > @idr
order by <ID>
insert @t(id, dt, dlt)
select @idr, @dt, abs(cast(@dt as float) -cast(@tdt as float))
select top(1) @dt = dt, @idr = id from @t order by dlt, id
select ''Found Value'' = @dt, ''Record Id'' = @idr
'
set @sql = replace(
replace(
replace(
replace(
replace(@sql, '<ID>', @ID),
'<Table>', @Table),
'<TargetDateTime>', convert(varchar(50), @TargetDateTime, 121)),
'<debug>', @debug),
'<DateTimeColumn>', @DateTimeColumn)
exec (@sql)