Menemukan perkiraan tetangga terdekat, membuat indeks vektor, dan membuat kueri pada embedding vektor

Halaman ini menjelaskan cara menemukan perkiraan tetangga terdekat (ANN), membuat indeks vektor, dan membuat kueri embedding vektor menggunakan fungsi jarak ANN berikut di Spanner:

  • APPROX_COSINE_DISTANCE
  • APPROX_EUCLIDEAN_DISTANCE
  • APPROX_DOT_PRODUCT

Jika set data kecil, Anda dapat menggunakan K-nearest neighbors (KNN) untuk menemukan vektor k-terdekat yang tepat. Namun, seiring bertambahnya set data, latensi dan biaya penelusuran KNN juga meningkat. Anda dapat menggunakan ANN untuk menemukan k-tetangga terdekat yang mendekati dengan latensi dan biaya yang berkurang secara signifikan.

Perkiraan k-nearest neighbors

Dalam penelusuran ANN, vektor k yang ditampilkan bukanlah k tetangga terdekat yang sebenarnya karena penelusuran ANN menghitung perkiraan jarak dan mungkin tidak melihat semua vektor dalam set data. Terkadang, beberapa vektor yang tidak termasuk dalam k-nearest neighbors teratas akan ditampilkan. Hal ini dikenal sebagai kehilangan ingatan. Seberapa besar kehilangan perolehan yang dapat Anda terima bergantung pada kasus penggunaan, tetapi dalam sebagian besar kasus, kehilangan sedikit perolehan sebagai imbalan atas peningkatan performa database adalah pertukaran yang dapat diterima.

Untuk mengetahui detail selengkapnya tentang fungsi jarak perkiraan Spanner, lihat:

Indeks vektor

Spanner mempercepat penelusuran vektor ANN dengan menggunakan indeks vektor khusus. Indeks ini memanfaatkan Scalable Nearest Neighbor (ScaNN) dari Google Research, yaitu algoritma tetangga terdekat yang sangat efisien.

Indeks vektor menggunakan struktur berbasis pohon untuk mempartisi data dan memfasilitasi penelusuran yang lebih cepat. Spanner menawarkan konfigurasi pohon dua tingkat dan tiga tingkat:

  • Konfigurasi pohon dua tingkat: Node daun (num_leaves) berisi grup vektor yang terkait erat beserta centroid yang sesuai. Tingkat root terdiri dari sentroid dari semua node daun.
  • Konfigurasi pohon tiga tingkat: Mirip dengan konsep pohon dua tingkat, sekaligus memperkenalkan lapisan cabang tambahan (num_branches), yang sentroid node daunnya dipartisi lebih lanjut untuk membentuk tingkat root (num_leaves).

Spanner memilih indeks untuk Anda. Namun, jika Anda tahu bahwa indeks tertentu berfungsi paling baik, Anda dapat menggunakan petunjuk FORCE_INDEX untuk memilih menggunakan indeks vektor yang paling sesuai untuk kasus penggunaan Anda.

Untuk mengetahui informasi selengkapnya, lihat pernyataan VECTOR INDEX.

Batasan

  • Anda tidak dapat memisahkan indeks vektor terlebih dahulu. Untuk mengetahui informasi selengkapnya, lihat Ringkasan pra-pemisahan.

Membuat indeks vektor

Untuk mengoptimalkan recall dan performa indeks vektor, sebaiknya:

  • Buat indeks vektor Anda setelah sebagian besar baris dengan embedding ditulis ke database Anda. Anda mungkin juga perlu membangun ulang indeks vektor secara berkala setelah memasukkan data baru. Untuk mengetahui informasi selengkapnya, lihat Membangun ulang indeks vektor.

  • Gunakan klausa STORING untuk menyimpan salinan kolom dalam indeks vektor. Jika nilai kolom disimpan dalam indeks vektor, Spanner akan melakukan pemfilteran di tingkat leaf indeks untuk meningkatkan performa kueri. Sebaiknya simpan kolom jika digunakan dalam kondisi pemfilteran. Untuk mengetahui informasi selengkapnya tentang penggunaan STORING dalam indeks, lihat Membuat indeks untuk pemindaian khusus indeks.

Saat Anda membuat tabel, kolom sematan harus berupa array jenis data FLOAT32 (direkomendasikan) atau FLOAT64, dan memiliki anotasi vector_length, yang menunjukkan dimensi vektor.

Pernyataan DDL berikut membuat tabel Documents dengan kolom penyematan DocEmbedding dengan panjang vektor:

CREATE TABLE Documents (
  DocId INT64 NOT NULL,
  ...
  DocEmbedding ARRAY<FLOAT32>(vector_length=>128),
) PRIMARY KEY (DocId);

Setelah mengisi tabel Documents, Anda dapat membuat indeks vektor dengan pohon dua tingkat dan 1.000 node daun pada tabel Documents dengan kolom embedding DocEmbedding menggunakan jarak kosinus:

CREATE VECTOR INDEX DocEmbeddingIndex
  ON Documents(DocEmbedding)
  STORING (WordCount)
  OPTIONS (distance_type = 'COSINE', tree_depth = 2, num_leaves = 1000);

Untuk membuat indeks vektor dengan pohon tiga tingkat dan 1000000 node daun:

CREATE VECTOR INDEX DocEmbeddingIndex
  ON Documents(NullableDocEmbedding)
  STORING (WordCount)
  WHERE NullableDocEmbedding IS NOT NULL
  OPTIONS (distance_type = 'COSINE', tree_depth = 3, num_branches=1000, num_leaves = 1000000);

Jika kolom sematan Anda tidak ditandai sebagai NOT NULL dalam definisi tabel, Anda harus mendeklarasikannya dengan klausa WHERE COLUMN_NAME IS NOT NULL:

CREATE VECTOR INDEX DocEmbeddingIndex
  ON Documents(NullableDocEmbedding)
  STORING (WordCount)
  WHERE NullableDocEmbedding IS NOT NULL
  OPTIONS (distance_type = 'COSINE', tree_depth = 2, num_leaves = 1000);

Memfilter indeks vektor

Anda juga dapat membuat indeks vektor yang difilter untuk menemukan item yang paling mirip di database Anda yang cocok dengan kondisi filter. Indeks vektor yang difilter secara selektif mengindeks baris yang memenuhi kondisi filter yang ditentukan, sehingga meningkatkan performa penelusuran.

Dalam contoh berikut, tabel Documents memiliki kolom bernama Category. Dalam penelusuran vektor, kita ingin mengindeks kategori "Teknologi", jadi kita membuat kolom yang dihasilkan yang bernilai NULL jika kondisi kategori tidak terpenuhi.

CREATE TABLE Documents (
  DocId INT64 NOT NULL,
  Category STRING(MAX),
  NullIfFiltered BOOL AS (IF(Category = 'Tech', TRUE, NULL)) HIDDEN,
  DocEmbedding ARRAY<FLOAT32>(vector_length=>128),
) PRIMARY KEY (DocId);

Kemudian, kita membuat indeks vektor dengan filter. Indeks vektor TechDocEmbeddingIndex hanya mengindeks dokumen dalam kategori "Teknologi".

CREATE VECTOR INDEX TechDocEmbeddingIndex
  ON Documents(DocEmbedding)
  STORING(NullIfFiltered)
  WHERE DocEmbedding IS NOT NULL AND NullIfFiltered IS NOT NULL
  OPTIONS (...);

Saat menjalankan kueri berikut, yang memiliki filter yang cocok dengan TechDocEmbeddingIndex, Spanner akan otomatis memilih dan dipercepat oleh TechDocEmbeddingIndex. Kueri hanya menelusuri dokumen dalam kategori "Teknologi". Anda juga dapat menggunakan {@FORCE_INDEX=TechDocEmbeddingIndex} untuk memaksa Spanner menggunakan TechDocEmbeddingIndex secara eksplisit.

SELECT *
FROM Documents
WHERE DocEmbedding IS NOT NULL AND NullIfFiltered IS NOT NULL
ORDER BY APPROX_(....)
LIMIT 10;

Mengkueri embedding vektor

Untuk membuat kueri indeks vektor, gunakan salah satu dari tiga fungsi jarak perkiraan:

  • APPROX_COSINE_DISTANCE
  • APPROX_EUCLIDEAN_DISTANCE
  • APPROX_DOT_PRODUCT

Batasan saat menggunakan fungsi jarak jauh perkiraan mencakup hal berikut:

  • Fungsi jarak perkiraan harus menghitung jarak antara kolom penyematan dan ekspresi konstanta (misalnya, parameter atau literal).
  • Output fungsi jarak perkiraan harus digunakan dalam klausa ORDER BY sebagai satu-satunya kunci pengurutan, dan LIMIT harus ditentukan setelah ORDER BY.
  • Kueri harus secara eksplisit mengecualikan baris yang tidak diindeks. Dalam sebagian besar kasus, ini berarti kueri harus menyertakan klausa WHERE <column_name> IS NOT NULL yang cocok dengan definisi indeks vektor, kecuali jika kolom sudah ditandai sebagai NOT NULL dalam definisi tabel.

Untuk daftar batasan mendetail, lihat halaman referensi fungsi jarak perkiraan.

Contoh

Untuk menelusuri 100 vektor terdekat ke [1.0, 2.0, 3.0]:

SELECT DocId
FROM Documents
WHERE WordCount > 1000
ORDER BY APPROX_EUCLIDEAN_DISTANCE(
  ARRAY<FLOAT32>[1.0, 2.0, 3.0], DocEmbedding,
  options => JSON '{"num_leaves_to_search": 10}')
LIMIT 100

Jika kolom penyematan dapat bernilai null:

SELECT DocId
FROM Documents
WHERE NullableDocEmbedding IS NOT NULL AND WordCount > 1000
ORDER BY APPROX_EUCLIDEAN_DISTANCE(
  ARRAY<FLOAT32>[1.0, 2.0, 3.0], NullableDocEmbedding,
  options => JSON '{"num_leaves_to_search": 10}')
LIMIT 100

Praktik terbaik

Ikuti praktik terbaik berikut untuk mengoptimalkan indeks vektor dan meningkatkan kualitas hasil kueri.

Menyesuaikan opsi penelusuran vektor

Nilai penelusuran vektor yang paling optimal bergantung pada kasus penggunaan, set data vektor, dan vektor kueri. Anda mungkin perlu melakukan penyesuaian berulang untuk menemukan nilai terbaik untuk workload spesifik Anda.

Berikut beberapa panduan berguna yang harus diikuti saat memilih nilai yang sesuai:

  • tree_depth (tingkat pohon): Jika tabel yang diindeks memiliki kurang dari 10 juta baris, gunakan tree_depth sebesar 2. Jika tidak, tree_depth dari 3 mendukung tabel hingga sekitar 10 miliar baris.

  • num_leaves: Gunakan akar kuadrat dari jumlah baris dalam set data. Nilai yang lebih besar dapat meningkatkan waktu pembuatan indeks vektor. Hindari menyetel num_leaves lebih besar dari table_row_count/1000 karena akan menghasilkan daun yang terlalu kecil dan performa yang buruk.

  • num_leaves_to_search: Opsi ini menentukan jumlah node daun indeks yang ditelusuri. Meningkatkan num_leaves_to_search akan meningkatkan perolehan, tetapi juga meningkatkan latensi dan biaya. Sebaiknya gunakan angka yang 1% dari total jumlah daun yang ditentukan dalam pernyataan CREATE VECTOR INDEX sebagai nilai untuk num_leaves_to_search. Jika Anda menggunakan klausa filter, tingkatkan nilai ini untuk memperluas penelusuran.

Jika perolehan yang dapat diterima tercapai, tetapi biaya kueri terlalu tinggi, sehingga menghasilkan QPS maksimum yang rendah, coba tingkatkan num_leaves dengan mengikuti langkah-langkah berikut:

  1. Tetapkan num_leaves ke beberapa kelipatan k dari nilai aslinya (misalnya, 2 * sqrt(table_row_count)).
  2. Tetapkan num_leaves_to_search agar sama dengan kelipatan k dari nilai aslinya.
  3. Lakukan eksperimen dengan mengurangi num_leaves_to_search untuk meningkatkan biaya dan QPS sambil mempertahankan perolehan.

Meningkatkan ingatan

Ada beberapa kemungkinan penyebab penurunan kualitas ingatan, termasuk yang berikut:

  • num_leaves_to_search terlalu kecil: Anda mungkin akan kesulitan menemukan tetangga terdekat untuk beberapa vektor kueri, jadi meningkatkan num_leaves_to_search untuk menelusuri lebih banyak daun dapat membantu meningkatkan recall. Kueri terbaru mungkin telah bergeser sehingga berisi lebih banyak vektor yang sulit ini.

  • Indeks vektor perlu dibangun ulang: Struktur hierarki indeks vektor dioptimalkan untuk set data pada saat pembuatan, dan bersifat statis setelahnya. Oleh karena itu, jika vektor yang sangat berbeda ditambahkan setelah membuat indeks vektor awal, struktur hierarki mungkin menjadi kurang optimal, sehingga menyebabkan recall yang lebih buruk.

Membangun ulang indeks vektor

Untuk membangun ulang indeks vektor tanpa periode nonaktif:

  1. Buat indeks vektor baru pada kolom embedding yang sama dengan indeks vektor saat ini, perbarui parameter (misalnya, OPTIONS) sebagaimana mestinya.
  2. Setelah pembuatan indeks selesai, gunakan petunjuk FORCE_INDEX untuk menunjuk indeks baru guna memperbarui kueri penelusuran vektor. Hal ini memastikan bahwa kueri menggunakan indeks vektor baru. Anda mungkin juga perlu menyetel ulang num_leaves_to_search dalam kueri baru Anda.
  3. Hapus indeks vektor yang sudah tidak berlaku.

Langkah berikutnya