Cara cepat mencari daftar string / catatan yang sangat besar pada database

Saya memiliki masalah berikut: Saya memiliki database yang berisi lebih dari 2 juta catatan. Setiap catatan memiliki bidang string X dan saya ingin menampilkan daftar catatan yang bidang X berisi string tertentu. Setiap record berukuran sekitar 500 byte.

Untuk membuatnya lebih konkret: di GUI aplikasi saya, saya memiliki bidang teks tempat saya dapat memasukkan string. Di atas bidang teks saya memiliki tabel yang menampilkan catatan (pertama N, misalnya 100) yang cocok dengan string di bidang teks. Ketika saya mengetik atau menghapus satu karakter di bidang teks, konten tabel harus diperbarui dengan cepat.

Saya bertanya-tanya apakah ada cara yang efisien untuk melakukan ini menggunakan struktur indeks yang sesuai dan / atau caching. Seperti dijelaskan di atas, saya hanya ingin menampilkan item N pertama yang cocok dengan kueri. Oleh karena itu, untuk N yang cukup kecil, seharusnya tidak menjadi masalah besar memuat item yang cocok dari database. Selain itu, caching item dalam memori utama dapat membuat pengambilan lebih cepat.

Saya pikir masalah utamanya adalah bagaimana menemukan item yang cocok dengan cepat, mengingat pola string. Dapatkah saya mengandalkan beberapa fasilitas DBMS, atau apakah saya harus membuat sendiri indeks dalam memori? Ada ide?

EDIT

Saya telah menjalankan percobaan pertama. Saya telah membagi catatan menjadi file teks yang berbeda (paling banyak 200 catatan per file) dan meletakkan file dalam direktori yang berbeda (saya menggunakan konten dari satu bidang data untuk menentukan pohon direktori). Saya berakhir dengan sekitar 50.000 file di sekitar 40000 direktori. Saya kemudian menjalankan Lucene untuk mengindeks file. Mencari string dengan program demo Lucene cukup cepat. Pemisahan dan pengindeksan memakan waktu beberapa menit: ini benar-benar dapat diterima bagi saya karena ini adalah kumpulan data statis yang ingin saya tanyakan.

Langkah selanjutnya adalah mengintegrasikan Lucene dalam program utama dan menggunakan hit yang dikembalikan oleh Lucene untuk memuat catatan yang relevan ke dalam memori utama.

Alih-alih memasukkan data Anda ke dalam DB, Anda dapat menyimpannya sebagai kumpulan dokumen (file teks) secara terpisah dan menyimpan tautan (jalur / url dll.) Di DB.

Ini penting karena, permintaan SQL dengan desain akan sangat lambat baik dalam pencarian sub-string maupun pengambilan.

Sekarang, masalah Anda dirumuskan sebagai, harus mencari file teks yang berisi kumpulan string. Ada dua kemungkinan di sini.

1. Kecocokan sub-string Jika gumpalan teks Anda adalah sengatan tunggal atau kata (tanpa spasi putih) dan Anda perlu mencari sub-string sewenang-wenang di dalamnya. Dalam kasus seperti itu, Anda perlu mengurai setiap file untuk menemukan file terbaik yang cocok. Satu menggunakan algoritma seperti algoritma Boyer Moor. Lihat ini dan ini untuk detailnya. Ini juga setara dengan grep - karena grep menggunakan hal serupa di dalamnya. Tetapi Anda masih dapat membuat setidaknya 100+ grep (kasus terburuk 2 juta) sebelum kembali.

2. Pencarian terindeks. Di sini Anda mengasumsikan bahwa teks berisi kumpulan kata dan pencarian terbatas pada panjang kata tetap. Dalam hal ini, dokumen diindeks untuk semua kemungkinan kemunculan kata. Ini sering disebut "Pencarian Teks Lengkap". Ada sejumlah algoritma untuk melakukan ini dan sejumlah proyek sumber terbuka yang dapat digunakan secara langsung. Banyak dari mereka, juga mendukung pencarian kartu liar, perkiraan pencarian dll. Seperti di bawah ini:
   a. Apache Lucene: http://lucene.apache.org/java/docs/index.html
   b. OpenFTS: http://openfts.sourceforge.net/
   c. Sphinx http://sphinxsearch.com/

Kemungkinan besar jika Anda membutuhkan "kata-kata tetap" sebagai pertanyaan, pendekatan dua akan sangat cepat dan efektif.

Teknologi yang Anda cari adalah pengindeksan teks lengkap. Sebagian besar RDBMS memiliki semacam kemampuan bawaan yang dapat bekerja di sini, atau Anda dapat menggunakan sesuatu seperti Lucene jika Anda ingin menjadi pelamun dan / atau hanya menjalankannya dalam memori.

Sudahkah Anda mempertimbangkan trie ? Pada dasarnya Anda membangun pohon menggunakan awalan umum, jadi semua kata yang dimulai dengan huruf yang sama adalah anak-anak dari simpul yang sama. Jika Anda akan mendukung pencocokan pada substring apa pun, maka Anda harus membuat semacam indeks permutasi dan membangun trie Anda dari itu. Itu mungkin berakhir dengan meniup persyaratan penyimpanan Anda.

Saya ingin menambahkan di atas jawaban Wyatt Barnett bahwa solusi RDBMS dengan pengindeksan teks lengkap pada kolom yang sesuai akan berfungsi, tetapi jika Anda ingin menggunakan cache lokal dari catatan yang sebelumnya diambil maka Anda perlu rencana untuk menggunakan catatan cache ini untuk keuntungan Anda.

Salah satu opsi adalah untuk mengumpulkan pengidentifikasi unik dari catatan-catatan ini yang secara eksplisit Anda tidak ingin mengambil dari kueri dan memasukkannya, mungkin dalam a NOT INatau a NOT EXISTS.

Namun, kata hati-hati, menggunakan NOT INatau NOT EXISTScenderung tidak murah dan MUNGKIN memengaruhi kinerja kueri atau rencana kueri Anda secara negatif, tergantung pada mesin basis data apa yang Anda gunakan. Jalankan rencana jelaskan pada permintaan akhir Anda untuk memastikan bahwa semua indeks Anda pada kolom yang terpengaruh digunakan.

Juga tidak ada salahnya untuk melakukan perbandingan kinerja antara kedua pendekatan untuk melihat mana yang lebih cepat. Anda mungkin terkejut mengetahui bahwa mengelola cache lokal dan memfilternya dari kueri Anda secara eksplisit mungkin memiliki kinerja yang lebih buruk daripada kueri yang disetel dengan halus yang mengambil semua catatan.

Untuk berjaga-jaga jika Anda melewatkannya. Jika Anda menggunakan Lucene untuk database Anda alih-alih pencarian teks yang didukung dalam-DB, Anda harus sangat berhati-hati saat membuat modifikasi untuk DB Anda. Bagaimana Anda memastikan bahwa Anda dapat memiliki atomisitas ketika Anda harus melakukan perubahan pada DB dan sumber daya eksternal (Lucene)? Ya itu bisa dilakukan, tetapi akan ada banyak pekerjaan.

Singkatnya, Anda kehilangan dukungan transaksional DB jika Anda memasukkan Lucene dalam skema data Anda.

Sudahkah Anda mempertimbangkan Sphinx? http://sphinxsearch.com jika Anda dapat menggunakan alat pihak ke-3 ini akan ideal untuk apa yang Anda coba capai, ini jauh lebih efisien pada pencarian teks lengkap daripada RDBMS yang saya gunakan secara pribadi.

Agak aneh bahwa tidak ada jawaban yang menyajikan istilah "indeks terbalik" , teknologi yang mendasari semua solusi yang mirip dengan Apache Lucene dan lainnya.

Indeks terbalik adalah pemetaan dari kata-kata ke dokumen ("indeks terbalik tingkat catatan") atau bahkan lokasi kata yang tepat dalam dokumen ("indeks terbalik tingkat kata").

DAN dan ATAU operasi logis mudah dilakukan. Jika Anda memiliki lokasi kata yang tepat, dimungkinkan untuk mencari kata-kata yang berdekatan, sehingga memungkinkan pencarian frase.

Jadi, pikirkan indeks yang berisi tupel (kata, file, lokasi). Ketika Anda memiliki mis ("terbalik", "foo.txt", 123) maka Anda cukup memeriksa apakah ("indeks", "foo.txt", 124) adalah bagian dari indeks untuk mencari frasa lengkap "indeks terbalik" .

Meskipun saya tidak merekomendasikan Anda untuk menerapkan kembali mesin pencari teks lengkap dari awal, penting untuk mengetahui bagaimana teknologi seperti kerja Apache Lucene.

Jadi, rekomendasi saya adalah mempelajari cara kerja indeks terbalik dan memilih teknologi yang menggunakannya seperti Apache Lucene. Maka Anda setidaknya memiliki pemahaman yang kuat tentang apa yang bisa dilakukan dan apa yang tidak bisa dilakukan.