levenshtein

Applies to VAST Cluster 5.5.

Functions › Text basics › Similarity. Returns the Levenshtein edit distance between two strings: the smallest number of single-unit insertions, deletions and substitutions that turn one string into the other. editdist3 is the same function.

Syntax

levenshtein(a, b)
editdist3(a, b)

Returns: BIGINT.

Aliases: editdist3.

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_levenshtein. 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 five people. The last row has no name:

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

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}.people"
run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}")
run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, name VARCHAR)")
run(f"INSERT INTO {TABLE} VALUES "
    "(1, 'Grace Hopper'), "
    "(2, 'Ada Lovelace'), "
    "(3, 'Alan Turing'), "
    "(4, 'grace hopper'), "
    "(5, NULL)")

[]
[]
[(5,)]

What it does

levenshtein counts the edits needed to turn a into b. Each edit inserts one unit, deletes one unit or replaces one unit with another; every edit costs 1. A result of 0 means the strings are equal.

It compares UTF-8 bytes, not characters. An unaccented ASCII letter is one byte, so for ASCII text the result is the number of character edits. A letter outside ASCII takes two or more bytes, and each byte is edited on its own:

To compare accented text by letters, remove the accents first with strip_accents, or bring both strings to the same form with nfc_normalize.

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 levenshtein(NULL, 'Hallo'), levenshtein('a', NULL), levenshtein('', 'Hallo'), "
    "levenshtein('kitten', 'sitting'), editdist3('kitten', 'sitting')")
run("SELECT levenshtein('ab', 'AB'), levenshtein('café', 'cafe'), levenshtein('e\u0301', '\u00e9')")
run("SELECT levenshtein(123, 'Hallo')")

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

Examples

The distance from each name to a misspelt search term, Grace Hoper. Row 1 is one edit away; row 4 differs in case as well, so it's further:

run(f"SELECT id, name, levenshtein(name, 'Grace Hoper') FROM {TABLE} ORDER BY id LIMIT 10")

[(1, 'Grace Hopper', 1), (2, 'Ada Lovelace', 10), (3, 'Alan Turing', 10), (4, 'grace hopper', 3), (5, None, None)]

Find the names within two edits of the search term, ignoring case by comparing lower of both strings:

run(f"SELECT id, name FROM {TABLE} "
    "WHERE levenshtein(lower(name), lower('Grace Hoper')) <= 2 ORDER BY id LIMIT 10")

[(1, 'Grace Hopper'), (4, 'grace hopper')]

The closest name first, with editdist3, which is the same function:

run(f"SELECT name, editdist3(name, 'Alan Turnig') AS distance FROM {TABLE} "
    "WHERE name IS NOT NULL ORDER BY distance, id LIMIT 1")

[('Alan Turing', 2)]

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

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

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

plan(f"SELECT id FROM {TABLE} WHERE levenshtein(name, 'Grace Hoper') <= 1")

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│             #1            │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ (levenshtein(name, 'Grace │
│        Hoper') <= 1)      │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│                           │
│        Projections:       │
│            name           │
│             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 levenshtein(). In id > 100 AND levenshtein(name, 'Grace Hoper') <= 2, id > 100 is evaluated in storage.
• Use a stored length as a cheap bound. Each edit changes the length by at most one byte, so two strings whose byte lengths differ by more than k are always more than k edits apart. If you store strlen of the name in its own column when you write the rows, in name_bytes BETWEEN 9 AND 13 AND levenshtein(name, 'Grace Hoper') <= 2 the length condition compares a raw column with constants, so levenshtein() runs only on the rows of a suitable length.
• Look up exact matches without it. name = 'Grace Hopper' is pushed down; levenshtein(name, 'Grace Hopper') = 0 gives the same rows but runs on every row. The plan for name = 'Grace Hopper' has no FILTER step:

plan(f"SELECT id FROM {TABLE} WHERE name = 'Grace Hopper'")

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

Limitations and errors

• Strings only. A number, decimal, date, boolean, BLOB or list fails with No function matches the given name and argument types. Cast it first: levenshtein(CAST(n AS VARCHAR), '123').
• Two arguments only. There's no argument for a maximum distance or for the cost of each kind of edit: levenshtein('a', 'b', 1) fails with No function matches the given name and argument types.
• Bytes, not characters. Accented and other non-ASCII letters count as more than one edit. See What it does.
• Case-sensitive. Compare lower() of both strings to ignore case.
• Other SQL dialects' names aren't available. soundex and similarity fail with Scalar Function with name ... does not exist!. Use levenshtein, or a similarity score from Similar functions.

run("SELECT levenshtein('a', 'b', 1)")
run("SELECT soundex('Robert')")
run("SELECT similarity('ab', 'ab')")

InternalError: Binder Error: No function matches the given name and argument types 'levenshtein(STRING_LITERAL, STRING_LITERAL, INTEGER_LITERAL)'. You might need to add explicit type casts.
InternalError: Catalog Error: Scalar Function with name soundex does not exist!
InternalError: Catalog Error: Scalar Function with name similarity does not exist!

Similar functions

levenshtein and damerau_levenshtein return a count of edits (lower is closer); jaccard and the Jaro functions return a score (higher is closer).

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

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

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.
• damerau_levenshtein, strip_accents and lower.