Ranking View Query Results

ArangoSearch supports the two most popular ranking schemes:

• Okapi BM25 
• TF-IDF 

Under the hood, both models rely on two main components:

• Term frequency (TF): in the simplest case defined as the number of times a term occurs in a document
• Inverse document frequency (IDF): a measure of how relevant a term is, i.e. whether the word is common or rare across all documents

See Ranking in ArangoSearch in the ArangoSearch Tutorial  to learn more about the ranking model.

Basic Ranking

To sort View results from most relevant to least relevant, use a SORT operation with a call to a Scoring function as expression and set the order to descending. Scoring functions expect the document emitted by a FOR … IN loop that iterates over a View as first argument.

FOR doc IN viewName
  SEARCH …
  SORT BM25(doc) DESC
  RETURN doc

You can also return the ranking score as part of the result.

FOR doc IN viewName
  SEARCH …
  RETURN MERGE(doc, { bm25: BM25(doc), tfidf: TFIDF(doc) })

Scoring functions cannot be used outside of SEARCH operations, as the scores can only be computed in the context of a View, especially because of the inverse document frequency (IDF).

Dataset

IMDB movie dataset

View definition

db.imdb_vertices.ensureIndex({
  name: "inv-text",
  type: "inverted",
  fields: [
    { name: "description", analyzer: "text_en" }
  ]
});

db._createView("imdb_alias", "search-alias", { indexes: [
  { collection: "imdb_vertices", index: "inv-text" }
] });

{
  "links": {
    "imdb_vertices": {
      "fields": {
        "description": {
          "analyzers": [
            "text_en"
          ]
        }
      }
    }
  }
}

AQL queries

Search for movies with certain keywords in their description and rank the results using the BM25() function:

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("amazing action world alien sci-fi science documental galaxy", "text_en")
  SORT BM25(doc) DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score: BM25(doc)
  }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("amazing action world alien sci-fi science documental galaxy", "text_en"), "text_en")
  SORT BM25(doc) DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score: BM25(doc)
  }

Do the same but with the TFIDF() function:

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("amazing action world alien sci-fi science documental galaxy", "text_en")
  SORT TFIDF(doc) DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score: TFIDF(doc)
  }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("amazing action world alien sci-fi science documental galaxy", "text_en"), "text_en")
  SORT TFIDF(doc) DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score: TFIDF(doc)
  }

Stable pagination for results

The SORT operation does not guarantee a stable sort if there is no unique value to sort by. This leads to an undefined order when sorting equal documents.

If you run a query multiple times with varying LIMIT offsets for pagination, you can miss results or get duplicate results if the sort order is undefined. To achieve stable pagination, you must meet the following requirements:

• The dataset should not change between query runs.
• The SORT operation must have at least one field with a unique value to sort by.

When stable sort is required, you can use a tiebreaker field. If the application has a preferred field that indicates the order of documents with the same score, then this field should be used in the SORT operation as a tiebreaker. If there is no such field, you can use the _id system attribute as it is unique and present in every document.

// sort by score and break ties using the unique document identifiers
SORT BM25(doc) DESC, doc._id

Example

You can use the IMDB movie dataset and create a View for the imdb_vertices collection and call it imdb. Index the description attribute with the built-in text-en Analyzer. Then, you can run the following query to find movies that contain the token ninja in the description, sorted by best matching according to the Okapi BM25 scoring scheme:

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("ninja", "text_en")
  LET score = BM25(doc)
  SORT score DESC
  RETURN { title: doc.title, score }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("ninja", "text_en"), "text_en")
  LET score = BM25(doc)
  SORT score DESC
  RETURN { title: doc.title, score }

Note the 5th and 6th result, which both have the same score of 6.30634880065918:

If you add a LIMIT operation for pagination and fetch the first 5 results, you may get the Batman movie as the 5th result:

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("ninja", "text_en")
  LET score = BM25(doc)
  SORT score DESC
  LIMIT 0, 5
  RETURN { title: doc.title, score }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("ninja", "text_en"), "text_en")
  LET score = BM25(doc)
  SORT score DESC
  LIMIT 0, 5
  RETURN { title: doc.title, score }

If you change the query to LIMIT 5, 5 to get the second batch of results, then you may see the Batman movie again (as the 6th result overall) instead of the Ninja Turtles movie:

The problem is the undefined order of results with the same score. There is no guarantee whether the Batman or the Ninja Turtle movie comes first, and as a result, both batches may include the same movie and miss the other entirely. As the order is undefined, you can randomly encounter this problem, even if it seems to work at first, because it may work some of the time.

To establish a stable order, you change the query to SORT score DESC, doc._id. This still ranks movies by the score, but matches with the same score are consistently sorted by the document identifier to break ties. This guarantees that either the Batman or the Ninja Turtles movie is included in the first batch and the other movie in the second batch.

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("ninja", "text_en")
  LET score = BM25(doc)
  SORT score DESC, doc._id
  LIMIT 0, 5  // first batch
  RETURN { title: doc.title, score }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("ninja", "text_en"), "text_en")
  LET score = BM25(doc)
  SORT score DESC, doc._id
  LIMIT 0, 5  // first batch
  RETURN { title: doc.title, score }

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("ninja", "text_en")
  LET score = BM25(doc)
  SORT score DESC, doc._id
  LIMIT 5, 5  // second batch
  RETURN { title: doc.title, score }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("ninja", "text_en"), "text_en")
  LET score = BM25(doc)
  SORT score DESC, doc._id
  LIMIT 5, 5  // second batch
  RETURN { title: doc.title, score }

Query Time Relevance Tuning

You can fine-tune the scores computed by the Okapi BM25 and TF-IDF relevance models at query time via the BOOST() AQL function and also calculate a custom score. In addition, the BM25() function lets you adjust the coefficients at query time.

The BOOST() function is similar to the ANALYZER() function in that it accepts any valid SEARCH expression as first argument. You can set the boost factor for that sub-expression via the second parameter. Documents that match boosted parts of the search expression will get higher scores.

Dataset

IMDB movie dataset

View definition

db.imdb_vertices.ensureIndex({
  name: "inv-text",
  type: "inverted",
  fields: [
    { name: "description", analyzer: "text_en" }
  ]
});

db._createView("imdb_alias", "search-alias", { indexes: [
  { collection: "imdb_vertices", index: "inv-text" }
] });

{
  "links": {
    "imdb_vertices": {
      "fields": {
        "description": {
          "analyzers": [
            "text_en"
          ]
        }
      }
    }
  }
}

AQL queries

Prefer galaxy over the other keywords:

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("amazing action world alien sci-fi science documental", "text_en")
      OR BOOST(doc.description IN TOKENS("galaxy", "text_en"), 5)
  SORT BM25(doc) DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score: BM25(doc)
  }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("amazing action world alien sci-fi science documental", "text_en")
      OR BOOST(doc.description IN TOKENS("galaxy", "text_en"), 5), "text_en")
  SORT BM25(doc) DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score: BM25(doc)
  }

If you are an information retrieval expert and want to fine-tuning the weighting schemes at query time, then you can do so. The BM25() function accepts free coefficients as parameters to turn it into BM15 for instance:

FOR doc IN imdb_alias
  SEARCH doc.description IN TOKENS("amazing action world alien sci-fi science documental", "text_en")
      OR BOOST(doc.description IN TOKENS("galaxy", "text_en"), 5)
  LET score = BM25(doc, 1.2, 0)
  SORT score DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score
  }

FOR doc IN imdb
  SEARCH ANALYZER(doc.description IN TOKENS("amazing action world alien sci-fi science documental", "text_en")
      OR BOOST(doc.description IN TOKENS("galaxy", "text_en"), 5), "text_en")
  LET score = BM25(doc, 1.2, 0)
  SORT score DESC
  LIMIT 10
  RETURN {
    title: doc.title,
    description: doc.description,
    score
  }

You can also calculate a custom score, taking into account additional fields of the document.

Match movies with the (normalized) phrase star war in the title and calculate a custom score based on BM25 and the movie runtime to favor longer movies:

FOR doc IN imdb_alias
  SEARCH PHRASE(doc.title, "Star Wars", "text_en")
  LET score = BM25(doc) * LOG(doc.runtime + 1)
  SORT score DESC
  RETURN {
    title: doc.title,
    runtime: doc.runtime,
    bm25: BM25(doc),
    score
  }

FOR doc IN imdb
  SEARCH PHRASE(doc.title, "Star Wars", "text_en")
  LET score = BM25(doc) * LOG(doc.runtime + 1)
  SORT score DESC
  RETURN {
    title: doc.title,
    runtime: doc.runtime,
    bm25: BM25(doc),
    score
  }