Full text search (FTS) indices

[eddyxu]

Given that we have https://github.com/lancedb/tantivy-object-store ready now, we can start to integrate tantive FTS into the rust core, and offer FTS to js/python/rust bindings.

Because we need to work on a variety of storage systems, we will likely need to vendor and adapt tantivy to meet our needs. Many of the components, such as the tokenizer and scoring can be re-used as is.

[wjones127]

Maybe worth a look when we implement this: https://github.com/huggingface/tokenizers

[wjones127]

Got some user feedback on potential API ideas we might want: https://discord.com/channels/1030247538198061086/1197630499926057021/1238721206006317066

[BubbleCal]

What is this for

With the capability of full text search, we can retrieve the document data more efficient, and with BM25 we can rank the results to reach better retrieval quality.

How we do this

The index consists of 3 parts: TokenSet, InvertedList and DocSet. We will store them on 3 individual files.

• TokenSet is basically a map from token(word) to token_id and the frequency of it.
• InvertedList records the row_id and frequency each token occurs for fast retrieving
• DocSet records the number of tokens for each row, which is used for BM25

We divide the index structure into the 3 files cause it allows us to minimize IO:

• For appending, we need to load only the previous TokenSet and generate InvertedList and DocSet for the new data
• For filtering, we need to load only the TokenSet and InvertedList
• For filtering and ranking with BM25, we need to load all the files

TODO items

Features

• Inverted Index feat: add inverted index #2526
• BM25 feat: add inverted index #2526
• Rust API feat: integrate inverted index into lance index APIs #2577
• Python API feat: integrate inverted index into lance index APIs #2577
• TypeScript API
• Brute-force search if index not created
• On-disk implement, local file system & object store
• Push down limit
• Filter expression parser
• Benchmark

Docs

• Docs
• Examples

Additional items

• More languages support

[BubbleCal]

To get it work as soon as possible, I haven't integrated it into the filter expression, instead, just added a new interface to execute the full text search, but will remove this interface once we get the parser ready. Here is a Python example:

import random
import lance
import pyarrow as pa
import string
import tempfile

# generate dataset
n = 1000
ids = range(n)
docs = ["".join(random.choices(string.ascii_letters, k=5)) for _ in range(n)]

id_array = pa.array(ids, type=pa.int64())
 # the inverted index supports large string array only
doc_array = pa.array(docs, type=pa.large_string())

table = pa.table({"id": id_array, "doc": doc_array})
temp_dir = tempfile.mkdtemp()
dataset = lance.write_dataset(table, temp_dir)
dataset.create_scalar_index("doc","INVERTED")

results = dataset.scanner(["id", "doc"], limit=10, full_text_query=("doc", docs[0])).to_table()
print(results)