jaro_winkler_similarity

Applies to VAST Cluster 5.5.

Functions › Text basics › Similarity. Returns the Jaro-Winkler similarity of two strings: the Jaro similarity, raised when the strings start with the same characters, with an optional cutoff below which the score is 0.0. It has no aliases.

Syntax

jaro_winkler_similarity(a, b)
jaro_winkler_similarity(a, b, cutoff)

Returns: DOUBLE.

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_jaro_winkler_similarity. 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 four contacts: the name on record and the name as someone typed it. The last row has no values:

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_jaro_winkler_similarity"'

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}.contacts"
run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}")
run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, name VARCHAR, typed VARCHAR, city VARCHAR)")
run(f"INSERT INTO {TABLE} VALUES "
    "(1, 'Ada Lovelace', 'Ada Lovelase', 'London'), "
    "(2, 'Grace Hopper', 'Grace Hoper', 'New York'), "
    "(3, 'José Martí', 'Jose Marti', 'Havana'), "
    "(4, NULL, NULL, NULL)")

[]
[]
[(4,)]

What it does

jaro_winkler_similarity starts from the Jaro similarity J of the two strings: the share of units (UTF-8 bytes) they have in common within a window, corrected for units that appear in a different order. It then adds a bonus for a common prefix, so that strings which start the same way score higher than strings that differ at the start.

The Winkler prefix weighting. Let l be the number of leading units the two strings have in common, up to 4. The score is J + l × 0.1 × (1 − J): each shared leading unit closes a tenth of the gap between the Jaro score and 1.0. Strings with no common prefix keep their Jaro score, and so do strings whose Jaro score is low.

| 'abcdefgh', 'abcdefgx' | abcdefg (7, counted as 4) | 0.9166666666666666 | 0.95 |
| 'abxxxx', 'abyyyy' | ab (2), but the Jaro score is low | 0.5555555555555555 | 0.5555555555555555 |

jaro_winkler_similarity('dixon', 'dicksonx'), with the prefix di, returns 0.8133333333333332.

The prefix is counted in bytes, like the rest of the score: 'éa' and 'éb' share the two bytes of é, so l is 2, and jaro_winkler_similarity('éa', 'éb') returns 0.8222222222222222 (the Jaro score is 0.7777777777777777). The comparison is case-sensitive.

The cutoff. With a third argument, a Jaro-Winkler score below the cutoff comes back as 0.0. The cutoff is compared with the final score, after the prefix bonus: jaro_winkler_similarity('martha', 'marhta', 0.95) returns 0.9611111111111111 although the Jaro score alone is 0.944, and a cutoff of 0.99 returns 0.0. Use it to make "not similar enough" a plain zero: jaro_winkler_similarity('abc', 'xyz', 0.5) returns 0.0. A NULL cutoff returns NULL.

Empty strings score 0.0. jaro_winkler_similarity('', '') returns 0.0, as does an empty string against another string.

NULLs and edge cases

The same cases, as the cluster returns them, and 'martha' and 'marhta' with a cutoff below and above its score. They use the table and helpers from Set up the examples:

run("SELECT jaro_winkler_similarity(NULL, 'Hallo'), jaro_winkler_similarity('a', NULL)")
run("SELECT jaro_winkler_similarity('', ''), jaro_winkler_similarity('', 'Hallo'), jaro_winkler_similarity('abc', 'xyz', 0.5)")
run("SELECT jaro_winkler_similarity('martha', 'marhta'), jaro_winkler_similarity('martha', 'marhta', 0.9), "
    "jaro_winkler_similarity('martha', 'marhta', 0.99)")
run("SELECT jaro_winkler_similarity(123, 'Hallo')")

[(None, None)]
[(0.0, 0.0, 0.0)]
[(0.9611111111111111, 0.9611111111111111, 0.0)]
InternalError: Binder Error: No function matches the given name and argument types 'jaro_winkler_similarity(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts.

Examples

Score each name as typed against the name on record, with the plain Jaro score next to it. The prefix bonus is the difference between the two columns; the row with no values scores NULL:

run(f"SELECT id, name, typed, round(jaro_similarity(name, typed), 3), round(jaro_winkler_similarity(name, typed), 3) "
    f"FROM {TABLE} ORDER BY id LIMIT 10")

[(1, 'Ada Lovelace', 'Ada Lovelase', 0.944, 0.967), (2, 'Grace Hopper', 'Grace Hoper', 0.972, 0.983), (3, 'José Martí', 'Jose Marti', 0.822, 0.876), (4, None, None, None, None)]

Find the closest names to a misspelt search term, best first:

run(f"SELECT name, round(jaro_winkler_similarity(name, 'Grace Hoper'), 3) AS score FROM {TABLE} "
    "WHERE name IS NOT NULL ORDER BY score DESC LIMIT 3")

[('Grace Hopper', 0.983), ('Ada Lovelace', 0.557), ('José Martí', 0.396)]

Keep only the rows where the typed name is close to the name on record:

run(f"SELECT id, name, typed FROM {TABLE} WHERE jaro_winkler_similarity(name, typed) > 0.9 ORDER BY id LIMIT 10")

[(1, 'Ada Lovelace', 'Ada Lovelase'), (2, 'Grace Hopper', 'Grace Hoper')]

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 jaro_winkler_similarity() is always computed by the Query Engine:

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

The plan of the WHERE example shows the FILTER step above the scan:

plan(f"SELECT id FROM {TABLE} WHERE jaro_winkler_similarity(name, typed) > 0.9")

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│             #2            │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│  (jaro_winkler_similarity │
│    (name, typed) > 0.9)   │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│                           │
│        Projections:       │
│            name           │
│           typed           │
│             id            │
│                           │
└───────────────────────────┘

Make it faster

• 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 the FILTER step. In city = 'London' AND jaro_winkler_similarity(name, 'Ada Lovlace') > 0.9, city = 'London' is pushed down and jaro_winkler_similarity() runs only on the London rows. The plan of the raw comparison on its own has no FILTER step:

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

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

• Store the score if you filter on it often. If you compare against the same reference value every time, compute the score when you write the rows and keep it in its own column: name_score > 0.9 is pushed down, jaro_winkler_similarity(name, 'Grace Hopper') > 0.9 isn't.

Limitations and errors

• Strings only. A number, a decimal, a date, a boolean, a BLOB or a list fails with No function matches the given name and argument types. Cast it first: jaro_winkler_similarity(CAST(n AS VARCHAR), '123').
• Bytes, not characters. Like jaro_similarity, it compares UTF-8 bytes, so an accented letter is two units, and the prefix is counted in bytes too.
• Case-sensitive. 'abc' and 'ABC' score 0.0. Compare lower(a) with lower(b) if case shouldn't count.
• The prefix bonus stops at 4 units, so two long strings that share a long prefix get the same bonus as two that share 4 units.
• Two empty strings score 0.0, not 1.0. Test for empty strings separately if your logic treats them as equal.

run("SELECT jaro_winkler_similarity('\\xAA'::BLOB, 'Hallo')")
run("SELECT jaro_winkler_similarity(['a', 'b'], 'Hallo')")

InternalError: Binder Error: No function matches the given name and argument types 'jaro_winkler_similarity(BLOB, STRING_LITERAL)'. You might need to add explicit type casts.
InternalError: Binder Error: No function matches the given name and argument types 'jaro_winkler_similarity(VARCHAR[], STRING_LITERAL)'. You might need to add explicit type casts.

Similar functions

With no common prefix the two Jaro scores are equal; 'martha' and 'marhta' share a prefix, so they differ:

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

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

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.
• jaro_similarity: the score without the prefix weighting, and how the Jaro score is computed.
• Where filters run and pushdowns.
• EXPLAIN: how to read a plan.