jaccard

Applies to VAST Cluster 5.5.

Functions › Text basics › Similarity. Returns the Jaccard similarity of two strings: the distinct bytes they have in common as a share of all the distinct bytes that appear in either, from 0 to 1. For ASCII text, each byte is a character. It has no aliases.

Syntax

jaccard(a, b)

Returns: DOUBLE, from 0.0 (no byte in common) to 1.0 (the same set of bytes).

Aliases: none.

Set up the examples

The examples connect with the ADBC driver, as in VAST Query Engine (ADBC), and work in a schema called docs_sql_fn_jaccard. Set QE_ENDPOINT, AWS_ACCESS_KEY_ID, AWS_SECRET_ACCESS_KEY and VASTDB_BUCKET (SQL reference), and run the blocks in order in one Python session. Below each block is the output you should see.

This block connects, defines the run() and plan() helpers, and creates a table of words. Row 5 is an empty string, and the last row has no word:

import os
import re

import adbc_driver_manager
import adbc_driver_manager.dbapi as dbapi
import adbc_driver_vastdb

BUCKET = os.environ["VASTDB_BUCKET"]
SCHEMA = f'"{BUCKET}/docs_sql_fn_jaccard"'

conn = dbapi.connect(
    driver=adbc_driver_vastdb.get_driver_path(),
    db_kwargs={
        "vast.db.endpoint": os.environ["QE_ENDPOINT"],
        "vast.db.access_key": os.environ["AWS_ACCESS_KEY_ID"],
        "vast.db.secret_key": os.environ["AWS_SECRET_ACCESS_KEY"],
    },
    autocommit=True,
)

def server_message(e):
    """The server's message in a driver error, without the request ID or the echoed statement."""
    text = re.sub(r"\[req=0x[0-9a-f]+\]: ", "", str(e))
    found = (re.search(r'message: "(.*?)", request_id', text, re.S)
             or re.search(r"description: (.*)\)", text, re.S))
    message = found.group(1) if found else text.strip().splitlines()[-1]
    message = re.sub(r"^Plan query: '.*?' failed with: ", "", message, flags=re.S)
    message = re.split(r"\\n|\n", message)[0].replace('\\"', '"')
    return message.replace(BUCKET, "<bucket>")

def run(sql):
    """Run one statement. Print the rows it returns, or the error."""
    try:
        with conn.cursor() as cur:
            cur.execute(sql)
            rows = cur.fetchall() if cur.description else []
    except (adbc_driver_manager.Error, OSError) as e:
        print(f"{type(e).__name__}: {server_message(e)}")
    else:
        print(rows)

def plan(sql):
    """Print the plan without its ~N Rows lines: the table's row count, which can still be 0 just after an insert."""
    with conn.cursor() as cur:
        cur.execute("EXPLAIN " + sql)
        steps = cur.fetchall()[0][1]
    print("\n".join(line for line in steps.splitlines() if "Rows" not in line))

TABLE = f"{SCHEMA}.words"
run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}")
run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, word VARCHAR)")
run(f"INSERT INTO {TABLE} VALUES "
    "(1, 'listen'), "
    "(2, 'silent'), "
    "(3, 'tinsel'), "
    "(4, 'lantern'), "
    "(5, ''), "
    "(6, NULL)")

[]
[]
[(6,)]

What it does

jaccard doesn't compare the strings as sequences. It turns each string into the set of distinct characters it contains, and divides the number of characters in both sets by the number of characters in either set:

jaccard(a, b) = (characters in both a and b) / (characters in a or b, or both)

Because it compares sets, the order of the characters and how often each one appears don't matter. The comparison is case-sensitive: a and A are different characters.

It compares UTF-8 bytes, not characters. An ASCII character is one byte, so for ASCII text the sets are sets of characters. A letter outside ASCII takes two or more bytes, and each byte goes into the set on its own. Accented letters that share their first byte overlap partly, and an accented letter shares nothing with its unaccented form:

To compare accented text by letters, remove the accents first with strip_accents.

So 1.0 doesn't mean the strings are equal: anagrams such as listen and silent score 1.0. Use it to find strings made of similar characters, and an edit distance such as levenshtein when the order matters.

An empty string is an error, not a score of 0. If either argument is '', the query fails with Jaccard Function: An argument too short!. On a column, one empty row stops the whole query and it returns no rows, including the rows that would have worked. A NULL argument gives NULL, not the error. To run jaccard on a column that may hold empty strings, remove them first (Examples shows how).

NULLs and edge cases

The same cases, as the cluster returns them. They use the table and helpers from Set up the examples:

run("SELECT jaccard(NULL, 'Hallo'), jaccard('a', NULL), jaccard('ab', 'ba'), jaccard('aab', 'ab'), "
    "jaccard('abc', 'xyz'), jaccard('night', 'nacht')")
run("SELECT jaccard('', 'Hallo')")
run("SELECT jaccard('abc', '')")
run("SELECT jaccard('', '')")
run("SELECT jaccard(123, 'Hallo')")

[(None, None, 1.0, 1.0, 0.0, 0.42857142857142855)]
OSError: Jaccard Function: An argument too short!
OSError: Jaccard Function: An argument too short!
OSError: Jaccard Function: An argument too short!
InternalError: Binder Error: No function matches the given name and argument types 'jaccard(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts.

Examples

On the whole column, the query fails because of the empty string in row 5, and returns nothing:

run(f"SELECT id, word, jaccard(word, 'listen') FROM {TABLE} ORDER BY id LIMIT 10")

OSError: Jaccard Function: An argument too short!

Remove the empty strings in WHERE, so jaccard() in the SELECT list runs on the rows that remain. silent and tinsel use exactly the letters of listen, so they score 1.0:

run(f"SELECT id, word, jaccard(word, 'listen') FROM {TABLE} WHERE word <> '' ORDER BY id LIMIT 10")

[(1, 'listen', 1.0), (2, 'silent', 1.0), (3, 'tinsel', 1.0), (4, 'lantern', 0.5)]

To filter on the score itself, put the empty-string check and jaccard() in a CASE, so jaccard() is called only on non-empty words. This keeps the words made of the same letters as listen:

run(f"SELECT id, word FROM {TABLE} "
    "WHERE CASE WHEN word <> '' THEN jaccard(word, 'listen') = 1.0 ELSE false END ORDER BY id LIMIT 10")

[(1, 'listen'), (2, 'silent'), (3, 'tinsel')]

How it runs in VAST

The Query Engine runs on the cluster's CNodes, and a query on a table starts with a scan in VAST DataBase (VAST_SCAN). VAST DataBase can evaluate a comparison of a column with a constant, but not a function of a column, so jaccard() is always computed by the Query Engine:

• In the SELECT list, the scan reads the column and the Query Engine computes jaccard() for each row it returns.
• In WHERE, the scan sends the column for every row, and a FILTER step in the Query Engine computes jaccard() and keeps the rows that match. No rows are skipped in storage.

The plan of a score filter shows the FILTER step above the scan:

plan(f"SELECT id FROM {TABLE} WHERE jaccard(word, 'listen') > 0.5")

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│             #1            │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ (jaccard(word, 'listen') >│
│            0.5)           │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│                           │
│        Projections:       │
│            word           │
│             id            │
│                           │
└───────────────────────────┘

Make it faster

• Keep empty strings out of the column. Store NULL rather than '' when there's no value: jaccard() returns NULL for a NULL argument instead of failing the query, so no guard is needed. Without row 5, the NULL in row 6 gives None:

run(f"SELECT id, jaccard(word, 'listen') FROM {TABLE} WHERE id <> 5 ORDER BY id LIMIT 10")

[(1, 1.0), (2, 1.0), (3, 1.0), (4, 0.5), (6, None)]

• Narrow the rows with a pushed-down condition first. A comparison of a raw column with a constant is evaluated in VAST DataBase, so only the rows that pass it reach jaccard(). The plan for word = '' has no FILTER step:

plan(f"SELECT id FROM {TABLE} WHERE word = ''")

┌───────────────────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│      Projections: id      │
│                           │
└───────────────────────────┘

Limitations and errors

• No empty strings. An empty argument fails with Jaccard Function: An argument too short!, and on a column one such row stops the whole query. See What it does.
• Single bytes, not words or n-grams. It compares single bytes (single characters, for ASCII text), so it can't tell listen from silent. There's no argument to change that.
• Strings only. A number, decimal, date, boolean, BLOB or list fails with No function matches the given name and argument types. Cast it first: jaccard(CAST(n AS VARCHAR), '123').
• Other SQL dialects' names aren't available. similarity and word_similarity fail with Scalar Function with name ... does not exist!. Use jaccard, or jaro_winkler_similarity for a score that depends on order.
• Bytes, not characters. Accented and other non-ASCII letters are split into their bytes. See What it does.
• Case-sensitive. jaccard('Listen', 'listen') is 0.7142857142857143 (5 of 7 characters in common). To ignore case, compare lower of both strings. This block compares 'Listen' with 'listen', with and without lower():

run(f"SELECT jaccard(word, 'listen') FROM {TABLE} WHERE id = 5")
run("SELECT similarity('ab', 'ab')")
run("SELECT word_similarity('a', 'b')")
run("SELECT jaccard('Listen', 'listen'), jaccard(lower('Listen'), 'listen')")

OSError: Jaccard Function: An argument too short!
InternalError: Catalog Error: Scalar Function with name similarity does not exist!
InternalError: Catalog Error: Scalar Function with name word_similarity does not exist!
[(0.7142857142857143, 1.0)]

Similar functions

run("SELECT jaccard('kitten', 'sitting'), jaro_similarity('kitten', 'sitting'), "
    "jaro_winkler_similarity('kitten', 'sitting'), levenshtein('kitten', 'sitting'), "
    "damerau_levenshtein('kitten', 'sitting'), hamming('kitten', 'sittin')")

[(0.42857142857142855, 0.746031746031746, 0.746031746031746, 3, 3, 2)]

Clean up:

run(f"DROP TABLE IF EXISTS {TABLE}")
run(f"DROP SCHEMA IF EXISTS {SCHEMA}")
conn.close()

[]
[]

See also

• Text basics: all the text functions.
• Where filters run and pushdowns.
• EXPLAIN: how to read a plan.
• jaro_winkler_similarity and levenshtein.