Bagaimana LIKE diimplementasikan?

22

Adakah yang bisa menjelaskan bagaimana operator LIKE diimplementasikan dalam sistem basis data saat ini (mis. MySQL atau Postgres)? atau tunjukkan saya pada beberapa referensi yang menjelaskannya?

Pendekatan naif akan memeriksa setiap catatan, mengeksekusi ekspresi reguler atau pertandingan string parsial di bidang yang menarik, tetapi saya memiliki perasaan (harapan) bahwa sistem ini melakukan sesuatu yang lebih cerdas.

Nick
sumber

Jawaban:

19

Tidak, itu yang mereka lakukan. Sekarang, jika tidak ada wildcard terkemuka dan bidang diindeks, yang merupakan situasi biasa, mesin basis data dapat menerapkan ekspresi reguler ke indeks. Jadi, misalnya, jika Anda menulis

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

database dapat menggunakan indeks LAST_NAMEuntuk menemukan semua baris tempat nama belakang dimulai 'Cav'. Di sisi lain, jika Anda punya sesuatu seperti

SELECT *
  FROM employees
 WHERE last_name LIKE '%av%'

database harus memindai seluruh tabel (atau seluruh indeks) dan mengevaluasi ekspresi terhadap nilai penuh LAST_NAME. Jelas, itu sangat mahal.

Sebagian besar database relasional yang lebih baik memiliki fasilitas untuk melakukan pencarian teks lengkap dengan cara yang lebih efisien dengan membuat berbagai jenis indeks dan katalog teks tetapi ini tidak menggunakan kata kunci LIKE. Sebagai contoh, inilah artikel bagus yang membahas pencarian teks lengkap di PostgreSQL .

Gua Justin
sumber
4
Oracle dapat menggunakan indeks bahkan dengan persentase terkemuka. Jika data yang dicari mewakili sebagian kecil dari baris maka petunjuk dapat memaksa untuk menggunakan indeks dan membuat eksekusi lebih cepat. Lihat laurentschneider.com/wordpress/2009/07/… .
Leigh Riffel
1
"pindai seluruh tabel ... Jelas, itu sangat mahal" - itu tergantung pada tabel;) ps Anda setuju LAST_NAMEmenjadi kandidat untuk (kolom pertama dalam) indeks berkerumun? pps sejauh mana jawaban ini menganggap sistem database didasarkan pada penyimpanan yang berdekatan pada disk dan indeks B-tree?
onedaywhen
26

Selain apa yang ditulis Justin Cave, sejak PostgreSQL 9.1 Anda dapat mempercepat pencarian apa pun dengan LIKE( ~~) atau ILIKE( ~~*), dan kecocokan ekspresi reguler dasar, juga ( ~). Gunakan kelas operator yang disediakan oleh modul pg_trgm dengan indeks GIN atau GiST untuk mempercepat LIKEekspresi yang tidak berlabuh kiri. Untuk menginstal ekstensi, jalankan sekali per basis data:

CREATE EXTENSION pg_trgm;

Buat indeks formulir

CREATE INDEX tbl_col_gin_trgm_idx ON tbl USING gin (col gin_trgm_ops);

Atau:

CREATE INDEX tbl_col_gist_trgm_idx ON tbl USING gist (col gist_trgm_ops);

Membuat dan memelihara indeks GIN atau GiST membawa biaya, tetapi jika meja Anda tidak banyak ditulis, ini adalah fitur yang hebat untuk Anda.

Depesz telah menulis artikel yang bagus di blognya tentang fitur baru.

GIN atau GiST?

Dua kutipan dari manual ini harus memberikan beberapa panduan

Pilihan antara indeks GiST dan GIN tergantung pada karakteristik kinerja relatif GiST dan GIN, yang dibahas di tempat lain. Sebagai patokan, indeks GIN lebih cepat untuk dicari daripada indeks GiST, tetapi lebih lambat untuk dibangun atau diperbarui; jadi GIN lebih cocok untuk data statis dan GiST untuk data yang sering diperbarui.

Tetapi untuk jenis "tetangga terdekat" pertanyaan dengan menggunakan operator jarak <->:

Ini dapat diimplementasikan dengan cukup efisien oleh indeks GiST, tetapi tidak oleh indeks GIN.

Erwin Brandstetter
sumber
3
Membaca ini saya bertanya-tanya apakah akan menggunakan GIN atau GiST. Menurut apa yang saya baca, indeks GIN lebih mahal untuk dipertahankan tetapi lebih cepat untuk dicari, sedangkan indeks GiST lebih murah untuk dipertahankan tetapi lebih lambat untuk dicari. Ini berarti indeks GIN umumnya harus digunakan pada data yang relatif statis sementara indeks GiST lebih disukai pada tabel bermutasi lebih berat.
Colin 't Hart
1
@ Colin'tHart: Itu umumnya benar, tetapi ada pengecualian untuk aturan tersebut. Pertimbangkan adendum di atas.
Erwin Brandstetter
5

Berbicara tentang MySQL, posisi karakter wild-card (%) membuat perbedaan. Jika bagian pertama dari teks ditentukan seperti where first_name like 'Sta%', maka mesin DB akan mencari hanya sebagian kecil dari kata-kata yang menatap S, lalu pergi ke St, dan kemudian Sta, dll. Jika Anda melakukan sesuatu seperti where first_name like '%stan%', maka dan seluruh pemindaian kolom akan diperlukan. Anda juga dapat melihat indeks teks lengkap yang juga melakukan pencarian bahasa alami. Lihat dokumen MySQL di sini.

StanleyJohns
sumber
1
Mengapa ia mulai mencari "S%" ketika substring didefinisikan menjadi 3 karakter (yaitu kita tahu string bukan "Sr%")? Atau apakah Anda menganggap DB memiliki pohon awalan atas atribut dan memberikan contoh melintasi pohon ini?
Nick