Vector search over RDF literals (knnSimilar)

A SPARQL vector index embeds the text that a selector picks out — one predicate in one graph, or a pattern — and returns the matching subjects. An RDF literal index works the other way round: it embeds the string literals of the quad store once, wherever they occur, and knnSimilar then constrains the object of any triple pattern you write, much as bif:contains does for free-text search. Graph, predicate and joins stay in the query, so one index serves questions you did not plan for when you built it.

This article covers:

• Creating an index: one call, and what gets embedded
• Searching: bif:knnSimilar in SPARQL, knnSimilar in SQL
• How k works: nearest literals first, triples second
• Keeping it current: new literals, refresh, building in steps
• Managing indexes: status, several indexes, drop, permissions

Prerequisites

• Virtuoso Open Source built with the ONNX plugin and the vonnx plugin loaded — see SQL vector index how-to
• An embedding model in DB.DBA.ONNX_MODELS — the bundled granite-384-local is auto-provisioned at startup
• DBA rights to create, refresh and drop an index; searching needs none

Create an index

The examples use a small graph of notes:

SPARQL
INSERT DATA {
  GRAPH <urn:demo:notes> {
    <urn:demo:n1> <urn:demo:title> "Nightly backups" ;
                  <urn:demo:body>  "Take an online backup every night and copy the backup set to another machine." .
    <urn:demo:n2> <urn:demo:title> "Disk space" ;
                  <urn:demo:body>  "Free disk space by moving old transaction log files to archive storage." .
    <urn:demo:n3> <urn:demo:title> "Password policy" ;
                  <urn:demo:body>  "Change the dba password after installation and rotate it every ninety days." .
    <urn:demo:n4> <urn:demo:title> "Restoring" ;
                  <urn:demo:body>  "To recover a database, restore the latest backup set and replay the transaction log." .
  }
}
;

DB.DBA.RDF_OBJ_VEC_INDEX_CREATE ('urn:demo:literals', 'granite-384-local');

SELECT RVI_NAME, RVI_IRI, RVI_STATE, RVI_ROWS FROM DB.DBA.RDF_OBJ_VEC_INDEX;

RDF_OBJ_VEC_INDEX_CREATE creates the index and, by default, embeds and builds it before it returns — on a new database this took under two seconds. The index holds 443 literals, not 8: it covers every eligible literal in the quad store, in every graph, Virtuoso's own system graphs included. Restrict results to your data in the query (by graph, predicate or subject), or narrow what is embedded with the _min_length and _langs arguments.

What is embedded

Each literal is embedded once, however many triples use it, and is identified by its row in DB.DBA.RDF_OBJ. A literal stored inline in DB.DBA.RDF_QUAD.O without an RDF_OBJ row is not covered; string literals written by SPARQL INSERT and the RDF loaders get one.

RDF_OBJ_VEC_INDEX_CREATE

DB.DBA.RDF_OBJ_VEC_INDEX_CREATE (
  _name,                   -- an IRI or a plain name
  _model,                  -- a model in DB.DBA.ONNX_MODELS
  _opts       := NULL,     -- WITH options as name/value pairs, e.g. vector ('hnsw_m', 32)
  _min_length := 0,        -- skip literals shorter than this many characters
  _langs      := NULL,     -- e.g. vector ('en', '') — '' means no language tag; null = any
  _build      := 'bulk',   -- 'bulk' or 'incremental'
  _build_now  := 1);       -- 0 = define only; see Build in steps

The index is an ordinary SQL vector index on DB.DBA.RDF_OBJ, so _opts takes the options of CREATE VECTOR INDEX (distance_metric, hnsw_m, ef_construction, …). Its key name is RDF_OBJ_ followed by the name with every character that is not a letter or digit replaced by _. Two names that differ only in punctuation therefore collide, and the second is refused:

VEC97: RDF_OBJ vector index name "urn/faq/literals" collides with the existing index
"urn:faq:literals": both map to the key RDF_OBJ_urn_faq_literals. Choose a name that
differs in letters or digits.

Search from SPARQL

bif:knnSimilar is written like bif:contains: as a triple whose subject is the variable holding the literal, in the same group as the triple pattern that binds it.

SPARQL
SELECT ?title ?sim
WHERE {
  GRAPH <urn:demo:notes> {
    ?note <urn:demo:title> ?title ;
          <urn:demo:body>  ?body .
    ?body bif:knnSimilar "how do I back up my data" option (score ?sim) .
  }
}
ORDER BY DESC (?sim)
;

The search matched the body text, and the query returned the titles: graph, predicates and the join are ordinary SPARQL.

bif:knnSimilar searches one index: a list such as index (<a>, <b>) is refused, and so is any other option (ef_search, ranking, …):

SP031: SPARQL compiler: bif:knnSimilar searches one index; write option (index <name>)
SP031: SPARQL compiler: bif:knnSimilar accepts only INDEX <name>, LIMIT, SCORE ?var and DISTANCE ?var options

It can appear more than once in a pattern, each on its own variable, and inside a sub-query. Keep it out of OPTIONAL — see Known issues.

Search from SQL

In SQL, knnSimilar is a predicate on the O column of DB.DBA.RDF_QUAD, and the table gains two virtual columns, SIMILARITY and DISTANCE:

knnSimilar (O, text [, index_name] [, k])

SELECT id_to_iri (S) AS note, SIMILARITY, DISTANCE
  FROM DB.DBA.RDF_QUAD
 WHERE G = iri_to_id ('urn:demo:notes')
   AND P = iri_to_id ('urn:demo:body')
   AND knnSimilar (O, 'how do I back up my data')
 ORDER BY SIMILARITY DESC;

How k works

knnSimilar first retrieves the k nearest literals in the whole index, then joins them to the triples the query allows. Three things follow:

• A row count is not k. One literal can be the object of many triples, and each matching triple is a row.
• Restrictions apply after retrieval. A query limited to one graph or predicate returns only the nearest literals that happen to sit there; if closer literals elsewhere fill the k slots, it returns fewer rows than you expect. Raise k for selective patterns.
• k is also the search breadth. The approximate search explores about k candidates, so a small k can miss a close match. On the new database above (a few hundred literals, most of them Virtuoso's own short system literals), searching for "change the dba password" with k = 20 did not return the note whose body says exactly that, although it scores 0.936; with the default k = 100 it ranked first. Keep the default of 100, or more, rather than asking for exactly the number of rows you want, and trim the result with ORDER BY … LIMIT in the query.

Keeping the index current

Literals are never updated in place in DB.DBA.RDF_OBJ — a changed value is a new literal — so maintenance is about new literals:

• Every new string literal, from SPARQL updates and the RDF loaders alike, is logged in DB.DBA.RDF_OBJ_VEC_LOG. It is not searchable until the log is drained.
• DB.DBA.RDF_OBJ_VEC_LOG_DRAIN (max_rows := 1000) embeds logged literals into every ready index and returns the number of log rows it consumed. The scheduled SQL worker (DB.DBA.VEC_SQL_WORKER_START) also drains it, up to 1,000 rows per run — see Draining the queue.
• DB.DBA.RDF_OBJ_VEC_INDEX_REFRESH (name) embeds every eligible literal not yet in the index and removes the ones that are no longer eligible. It returns (embedded, removed).

SPARQL
INSERT DATA {
  GRAPH <urn:demo:notes> {
    <urn:demo:n5> <urn:demo:title> "Offsite copies" ;
                  <urn:demo:body>  "Keep one copy of every backup in a different building." .
  }
}
;

SELECT count (*) FROM DB.DBA.RDF_OBJ_VEC_LOG;     -- 2: the new title and body
SELECT DB.DBA.RDF_OBJ_VEC_LOG_DRAIN ();           -- 2

Before the drain, the search above still returned four notes; after it, urn:demo:n5 ranks second at 0.849.

A literal whose triples are all deleted stays in DB.DBA.RDF_OBJ, and so in the index. It produces no rows — there is no triple to join to — but it can still take one of the k slots.

Build in steps

For a large store, separate the steps: define the index without building it, embed (this can be stopped and resumed), then build the graph in one pass.

DB.DBA.RDF_OBJ_VEC_INDEX_CREATE ('urn:faq:long-literals', 'granite-384-local',
                                 NULL, 40, NULL, 'bulk', 0);   -- state: new
SELECT DB.DBA.RDF_OBJ_VEC_INDEX_EMBED ('urn:faq:long-literals'); -- state: embedded
SELECT DB.DBA.RDF_OBJ_VEC_INDEX_BUILD ('urn:faq:long-literals'); -- state: ready

RDF_OBJ_VEC_INDEX_EMBED skips literals it has already embedded, so after an interruption run it again and it continues where it stopped. While any RDF literal index is embedding, embedded or building, the change log is held: RDF_OBJ_VEC_LOG_DRAIN returns 0 and new literals wait until the graph exists to take them. An embed or build interrupted by a server restart leaves the index in state error with an RVI_LAST_ERROR that says which call continues it.

Managing indexes

DB.DBA.RDF_OBJ_VEC_INDEX has one row per index:

SELECT count (*) FROM DB.DBA.RDF_OBJ_VEC_LOG shows the literals waiting to be embedded.

Several indexes — for example one over everything and one over long English texts — can exist side by side; every search must then name one. Drop an index with DB.DBA.RDF_OBJ_VEC_INDEX_DROP (name); a query that names it afterwards fails with VEC95.

Permissions. Creating, embedding, building, refreshing and dropping an index are DBA-only (VEC92). Searching is not: a SPARQL_SELECT user and the anonymous /sparql endpoint can both use bif:knnSimilar, and the triples a search returns are subject to the same graph-level security as any other triple pattern.

Known issues

Inside OPTIONAL. Binding score or distance in an optional group fails to compile (SQ200: No column … SIMILARITY), and with a small limit the optional part can attach the same literal to every row. Put bif:knnSimilar in the required part of the pattern.

One score on every row. In some join plans, SIMILARITY / DISTANCE (and the SPARQL score and distance variables) report the best hit's value on every row, while the rows themselves are correct. It shows when the optimizer puts the vector search on the build side of a hash join. If every row of a joined result has the same score, ask for a loop join:

-- SPARQL
SPARQL DEFINE sql:select-option "loop"
SELECT ?question ?sim
WHERE {
  GRAPH <urn:openlink:faqs> {
    ?q <http://schema.org/name> ?question ;
       <http://schema.org/acceptedAnswer> ?a .
    ?a <http://schema.org/text> ?answer .
    ?answer bif:knnSimilar "how much does a commercial license cost"
      option (INDEX <urn:faq:literals>, score ?sim) .
  }
}
ORDER BY DESC (?sim)
LIMIT 3
;

-- SQL: append OPTION (LOOP) to the SELECT

On the FAQ tutorial data, with that hint, the query matches answer texts and returns their questions: "What kind of support does the commercial license offer?" (0.886), "What information is provided in the License section of sys_stat function?" (0.876) and "How is the price of the commercial license determined?" (0.876).

Next steps

• SPARQL vector index how-to — subject-level search with a selector
• Index parameters — the WITH options _opts accepts
• API reference — every RDF_OBJ_VEC_* procedure and error code

Related content

• Embedding models — local and remote models an index can use
• Similarity metrics — what the scores mean

PreviousHow-To: Build and use the SPARQL vector index (Virtuoso) NextEmbedding models for the Virtuoso vector index