Temukan elemen hilang terkecil berdasarkan formula tertentu

Saya harus dapat menemukan elemen yang hilang dari tabel dengan puluhan-juta baris, dan memiliki kunci utama BINARY(64)kolom (yang merupakan nilai input untuk menghitung dari). Nilai-nilai ini sebagian besar dimasukkan secara berurutan, tetapi kadang-kadang saya ingin menggunakan kembali nilai sebelumnya yang telah dihapus. Sangat tidak layak untuk memodifikasi catatan yang dihapus dengan IsDeletedkolom, karena kadang-kadang sebuah baris disisipkan dengan jutaan nilai di depan baris yang ada saat ini. Ini berarti data sampel akan terlihat seperti:

KeyCol : BINARY(64)
0x..000000000001
0x..000000000002
0x..FFFFFFFFFFFF

Jadi, memasukkan semua nilai yang hilang di antara 0x000000000002dan 0xFFFFFFFFFFFFtidak layak, jumlah waktu dan ruang yang digunakan tidak diinginkan. Pada dasarnya, ketika saya menjalankan algoritme, saya berharap untuk kembali 0x000000000003, yang merupakan pembukaan pertama.

Saya telah datang dengan algoritma pencarian biner dalam C #, yang akan query database untuk setiap nilai pada posisi i, dan menguji apakah nilai itu diharapkan. Untuk konteks, algoritma mengerikan saya: /codereview/174498/binary-search-for-a-missing-or-default-value-by-a-given-formula

Algoritma ini akan berjalan, misalnya, 26-27 SQL-queries di atas meja dengan 100.000.000 item. (Kelihatannya tidak banyak, tapi itu akan terjadi sangat sering.) Saat ini, tabel ini memiliki sekitar 50.000.000 baris di dalamnya, dan kinerja menjadi nyata .

Pemikiran alternatif pertama saya adalah menerjemahkan ini ke prosedur tersimpan, tetapi itu memiliki rintangan sendiri. (Saya harus menulis BINARY(64) + BINARY(64)algoritma, serta membunuh hal-hal lain.) Ini akan menyakitkan, tetapi tidak mustahil. Saya juga mempertimbangkan menerapkan algoritma terjemahan berdasarkan ROW_NUMBER, tapi saya punya firasat yang sangat buruk tentang hal ini. (A BIGINThampir tidak cukup besar untuk nilai-nilai ini.)

Saya mendukung saran lain , karena saya benar - benar membutuhkan ini secepat mungkin. Untuk apa nilainya satu - satunya kolom yang dipilih oleh permintaan C # adalah KeyCol, yang lain tidak relevan untuk bagian ini.

Selain itu, sesuai nilainya, kueri saat ini yang mengambil catatan yang sesuai ada di sepanjang baris:

SELECT [KeyCol]
  FROM [Table]
  ORDER BY [KeyCol] ASC
  OFFSET <VALUE> ROWS FETCH FIRST 1 ROWS ONLY

Di mana <VALUE>indeks dipasok oleh algoritma. Saya juga belum memiliki BIGINTmasalah OFFSET, tetapi saya akan melakukannya. (Hanya memiliki 50.000.000 baris sekarang berarti bahwa itu tidak pernah meminta indeks di atas nilai itu, tetapi pada beberapa titik itu akan mendapatkan di atas BIGINTkisaran.)

Beberapa data tambahan:

• Dari penghapusan, gap:sequentialrasionya adalah tentang 1:20;
• 35.000 baris terakhir dalam tabel memiliki nilai> BIGINTmaksimum;

Joe sudah mengenai sebagian besar poin yang saya hanya menghabiskan satu jam mengetik, dalam ringkasan:

• sangat diragukan Anda akan kehabisan KeyColnilai < bigintmaks (9.2e18), jadi konversi (jika perlu) ke / dari bigintseharusnya tidak menjadi masalah selama Anda membatasi pencarian hinggaKeyCol <= 0x00..007FFFFFFFFFFFFFFF
• Saya tidak bisa memikirkan permintaan yang akan 'secara efisien' menemukan celah sepanjang waktu; Anda mungkin beruntung dan menemukan celah di dekat awal pencarian Anda, atau Anda bisa membayar mahal untuk menemukan celah cukup banyak dalam pencarian Anda
• sementara saya berpikir sebentar tentang bagaimana memparalelkan kueri, saya dengan cepat membuang ide itu (sebagai DBA saya tidak ingin mengetahui bahwa proses Anda secara rutin merogoh server data saya dengan utilisasi cpu 100% ... terutama jika Anda bisa memiliki banyak salinan ini berjalan pada saat yang sama); Tidaaaak ... paralelisasi akan keluar dari pertanyaan

Jadi, apa yang harus dilakukan?

Mari kita tunggu sebentar gagasan pencarian (diulang, intensif cpu, brute force) dan lihat gambar yang lebih besar.

• rata-rata satu contoh pencarian ini akan perlu memindai jutaan kunci indeks (dan memerlukan cpu yang bagus, meronta-ronta cache db, dan pengguna menonton kaca jam berputar) hanya untuk menemukan nilai tunggal
• gandakan penggunaan-cpu / cache-meronta-ronta-jam-kaca dengan ... berapa banyak pencarian yang Anda harapkan dalam sehari?
• perlu diingat bahwa, secara umum, masing-masing contoh dari pencarian ini akan perlu untuk memindai sama set (jutaan) kunci indeks; itu BANYAK aktivitas berulang untuk keuntungan minimal

Yang ingin saya usulkan adalah beberapa tambahan pada model data ...

• tabel baru yang melacak set nilai 'tersedia untuk digunakan' KeyCol, misalnya:available_for_use(KeyCol binary(64) not null primary key)
• berapa banyak catatan yang Anda simpan dalam tabel ini terserah Anda untuk memutuskan, misalnya, mungkin cukup untuk kegiatan selama satu bulan?
• tabel dapat secara berkala (mingguan?) 'diakhiri' dengan kumpulan KeyColnilai baru (mungkin membuat proc tersimpan 'top off'?) [misalnya, perbarui select/top/row_number()kueri Joe untuk melakukan top 100000]
• Anda dapat mengatur proses pemantauan untuk melacak jumlah entri yang tersedia available_for_use kalau-kalau Anda mulai kehabisan nilai
• pemicu DELETE baru (atau dimodifikasi) pada> main_table <yang menempatkan KeyColnilai yang dihapus ke dalam tabel baru kami available_for_usesetiap kali sebuah baris dihapus dari tabel utama
• jika Anda mengizinkan pembaruan KeyColkolom maka pemicu UPDATE yang baru / dimodifikasi pada> main_table <juga menjaga agar tabel baru kami available_for_usediperbarui
• ketika tiba saatnya untuk 'mencari' KeyColnilai baru Anda select min(KeyCol) from available_for_use(jelas ada sedikit lebih dari ini karena a) Anda harus kode untuk masalah konkurensi - tidak ingin 2 salinan dari proses Anda meraih hal yang sama min(KeyCol)dan b) Anda Anda harus menghapus min(KeyCol)dari tabel; ini harus relatif mudah dikodekan, mungkin sebagai proc yang disimpan, dan dapat dialamatkan dalam tanya jawab lain jika perlu)
• dalam skenario kasus terburuk, jika select min(KeyCol)proses Anda tidak menemukan baris yang tersedia, Anda bisa memulai proc 'top off' Anda untuk menghasilkan batch baris baru

Dengan perubahan yang diajukan pada model data ini:

• Anda menghilangkan BANYAK siklus cpu berlebihan [DBA Anda akan berterima kasih]
• Anda menghilangkan SEMUA dari pemindaian indeks berulang dan meronta-ronta cache [DBA Anda akan berterima kasih]
• pengguna Anda tidak lagi harus menonton kaca jam berputar (meskipun mereka mungkin tidak suka hilangnya alasan untuk menjauh dari meja mereka)
• ada banyak cara untuk memantau ukuran available_for_usetabel untuk memastikan Anda tidak pernah kehabisan nilai baru

Ya, available_for_usetabel yang diusulkan hanyalah tabel nilai pre-generate 'next key'; dan ya, ada potensi untuk beberapa pertikaian ketika meraih nilai 'berikutnya', tetapi pertikaian a) mudah ditangani melalui desain tabel / indeks / permintaan yang tepat dan b) akan menjadi minor / berumur pendek dibandingkan dengan overhead / keterlambatan dengan gagasan saat ini pencarian berulang, kasar, indeks.

Ada beberapa tantangan dengan pertanyaan ini. Indeks dalam SQL Server dapat melakukan hal berikut dengan sangat efisien hanya dengan beberapa pembacaan logis:

• periksa apakah ada baris
• periksa apakah tidak ada baris
• temukan baris berikutnya mulai dari beberapa titik
• temukan baris sebelumnya yang dimulai di beberapa titik

Namun, mereka tidak dapat digunakan untuk menemukan baris ke-N dalam indeks. Melakukan hal itu mengharuskan Anda menggulung indeks Anda sendiri yang disimpan sebagai sebuah tabel atau untuk memindai baris N pertama dalam indeks. Kode C # Anda sangat bergantung pada fakta bahwa Anda dapat secara efisien menemukan elemen Nth dari array, tetapi Anda tidak dapat melakukannya di sini. Saya pikir algoritma itu tidak dapat digunakan untuk T-SQL tanpa perubahan model data.

Tantangan kedua terkait dengan pembatasan pada BINARYtipe data. Sejauh yang saya tahu Anda tidak dapat melakukan penambahan, pengurangan, atau pembagian dengan cara biasa. Anda dapat mengonversikan Anda BINARY(64)ke a BIGINTdan itu tidak akan menghasilkan kesalahan konversi, tetapi perilaku tidak didefinisikan :

Konversi antara tipe data apa pun dan tipe data biner tidak dijamin sama antara versi SQL Server.

Selain itu, kurangnya kesalahan konversi agak menjadi masalah di sini. Anda dapat mengonversi apa pun yang lebih besar dari nilai terbesar yang mungkin, BIGINTtetapi itu akan memberi Anda hasil yang salah.

Memang benar bahwa Anda memiliki nilai sekarang yang lebih besar dari 9223372036854775807. Namun, jika Anda selalu mulai dari 1 dan mencari nilai minimum terkecil maka nilai-nilai besar itu tidak dapat relevan kecuali tabel Anda memiliki lebih dari 9223372036854775807 baris. Ini sepertinya tidak mungkin karena meja Anda pada saat itu akan menjadi sekitar 2000 exabytes, jadi untuk keperluan menjawab pertanyaan Anda, saya akan mengasumsikan bahwa nilai yang sangat besar tidak perlu dicari. Saya juga akan melakukan konversi tipe data karena tampaknya tidak dapat dihindari.

Untuk data pengujian, saya memasukkan setara 50 juta integer berurutan ke dalam tabel bersama dengan 50 juta integer lainnya dengan celah nilai tunggal tentang setiap 20 nilai. Saya juga memasukkan satu nilai yang tidak akan cocok dengan yang ditandatangani BIGINT:

CREATE TABLE dbo.BINARY_PROBLEMS (
    KeyCol BINARY(64) NOT NULL
);

INSERT INTO dbo.BINARY_PROBLEMS WITH (TABLOCK)
SELECT CAST(SUM(OFFSET) OVER (ORDER BY (SELECT NULL) ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS BINARY(64))
FROM
(
    SELECT 1 + CASE WHEN t.RN > 50000000 THEN
        CASE WHEN ABS(CHECKSUM(NewId()) % 20)  = 10 THEN 1 ELSE 0 END
    ELSE 0 END OFFSET
    FROM
    (
        SELECT TOP (100000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) RN
        FROM master..spt_values t1
        CROSS JOIN master..spt_values t2
        CROSS JOIN master..spt_values t3
    ) t
) tt
OPTION (MAXDOP 1);

CREATE UNIQUE CLUSTERED INDEX CI_BINARY_PROBLEMS ON dbo.BINARY_PROBLEMS (KeyCol);

-- add a value too large for BIGINT
INSERT INTO dbo.BINARY_PROBLEMS
SELECT CAST(0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000 AS BINARY(64));

Kode itu membutuhkan beberapa menit untuk berjalan di mesin saya. Saya membuat paruh pertama tabel tidak memiliki celah untuk mewakili semacam kasus yang lebih buruk untuk kinerja. Kode yang saya gunakan untuk menyelesaikan masalah memindai indeks sehingga akan selesai dengan sangat cepat jika celah pertama di awal dalam tabel. Sebelum kita sampai di sana, mari kita verifikasi bahwa data sudah sebagaimana mestinya:

SELECT TOP (2) KeyColBigInt
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    FROM dbo.BINARY_PROBLEMS
) t
ORDER By KeyCol DESC;

Hasilnya menunjukkan bahwa nilai maksimum yang kami konversi BIGINTadalah 102500672:

╔══════════════════════╗
║     KeyColBigInt     ║
╠══════════════════════╣
║ -9223372036854775808 ║
║            102500672 ║
╚══════════════════════╝

Ada 100 juta baris dengan nilai yang sesuai dengan BIGINT seperti yang diharapkan:

SELECT COUNT(*) 
FROM dbo.BINARY_PROBLEMS
WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF;

Salah satu pendekatan untuk masalah ini adalah memindai indeks secara berurutan dan berhenti segera setelah nilai baris tidak sesuai dengan ROW_NUMBER()nilai yang diharapkan . Seluruh tabel tidak perlu dipindai untuk mendapatkan baris pertama: hanya baris ke atas sampai celah pertama. Inilah salah satu cara untuk menulis kode yang kemungkinan akan mendapatkan paket kueri itu:

SELECT TOP (1) KeyCol
FROM
(
    SELECT KeyCol
    , CAST(KeyCol AS BIGINT) KeyColBigInt
    , ROW_NUMBER() OVER (ORDER BY KeyCol) RN
    FROM dbo.BINARY_PROBLEMS
    WHERE KeyCol < 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007FFFFFFFFFFFFFFF
) t
WHERE KeyColBigInt <> RN
ORDER BY KeyCol;

Untuk alasan yang tidak sesuai dengan jawaban ini, kueri ini akan sering dijalankan secara serial oleh SQL Server dan SQL Server akan sering meremehkan jumlah baris yang perlu dipindai sebelum pertandingan pertama ditemukan. Di mesin saya, SQL Server memindai 50000022 baris dari indeks sebelum menemukan kecocokan pertama. Permintaan membutuhkan waktu 11 detik untuk berjalan. Perhatikan bahwa ini mengembalikan nilai pertama melewati celah. Tidak jelas baris mana yang Anda inginkan dengan tepat, tetapi Anda harus dapat mengubah kueri agar sesuai dengan kebutuhan Anda tanpa banyak masalah. Seperti apa rencananya :

Satu-satunya ide saya adalah menggertak SQL Server menggunakan paralelisme untuk permintaan. Saya memiliki empat CPU, jadi saya akan membagi data menjadi empat rentang dan mencari rentang tersebut. Setiap CPU akan diberi kisaran. Untuk menghitung rentang, saya hanya meraih nilai maks dan mengasumsikan bahwa data didistribusikan secara merata. Jika Anda ingin lebih pintar tentang itu, Anda bisa melihat histogram statistik sampel untuk nilai kolom dan membangun rentang Anda dengan cara itu. Kode di bawah ini bergantung pada banyak trik tidak berdokumen yang tidak aman untuk diproduksi, termasuk jejak bendera 8649 :

SELECT TOP 1 ca.KeyCol
FROM (
    SELECT 1 bucket_min_value, 25625168 bucket_max_value
    UNION ALL
    SELECT 25625169, 51250336
    UNION ALL
    SELECT 51250337, 76875504
    UNION ALL
    SELECT 76875505, 102500672
) buckets
CROSS APPLY (
    SELECT TOP 1 t.KeyCol
    FROM
    (
        SELECT KeyCol
        , CAST(KeyCol AS BIGINT) KeyColBigInt
        , buckets.bucket_min_value - 1 + ROW_NUMBER() OVER (ORDER BY KeyCol) RN
        FROM dbo.BINARY_PROBLEMS
        WHERE KeyCol >= CAST(buckets.bucket_min_value AS BINARY(64)) AND KeyCol <=  CAST(buckets.bucket_max_value AS BINARY(64))
    ) t
    WHERE t.KeyColBigInt <> t.RN
    ORDER BY t.KeyCol
) ca
ORDER BY ca.KeyCol
OPTION (QUERYTRACEON 8649);

Berikut adalah pola paralel nested loop:

Secara keseluruhan, kueri lebih berfungsi daripada sebelumnya karena akan memindai lebih banyak baris dalam tabel. Namun, sekarang berjalan dalam 7 detik di desktop saya. Mungkin paralel dengan lebih baik pada server nyata. Berikut ini tautan ke paket yang sebenarnya .

Saya benar-benar tidak bisa memikirkan cara yang baik untuk menyelesaikan masalah ini. Melakukan perhitungan di luar SQL atau mengubah model data mungkin merupakan taruhan terbaik Anda.

Inilah jawaban yang mungkin tidak akan berhasil untuk Anda, tetapi saya akan menambahkannya.

Meskipun BINARY (64) dapat dihitung, ada dukungan yang buruk untuk menentukan penggantinya. Karena BIGINT tampaknya terlalu kecil untuk domain Anda, Anda mungkin mempertimbangkan untuk menggunakan DECIMAL (38,0), yang tampaknya merupakan jenis ANGKA terbesar di SQL-server.

CREATE TABLE SearchTestTableProper
( keycol decimal(38,0) not null primary key );

INSERT INTO SearchTestTableProper (keycol)
VALUES (1),(2),(3),(12);

Menemukan celah pertama itu mudah karena kita dapat membuat nomor yang kita cari:

select top 1 t1.keycol+1 
from SearchTestTableProper t1 
where not exists (
    select 1 
    from SearchTestTableProper t2 
    where t2.keycol = t1.keycol + 1
)
order by t1.keycol;

Nested loop yang tergabung dalam indeks pk harus cukup untuk menemukan item pertama yang tersedia.