hamming

Applies to VAST Cluster 5.5.

Functions › Text basics › Similarity. Returns the Hamming distance between two strings of the same length in bytes: the number of byte positions at which they differ. mismatches is the same function.

Syntax

hamming(a, b)
mismatches(a, b)

Returns: BIGINT.

Aliases: mismatches.

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_hamming. 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 six-character part codes. Row 5 has a code of the wrong length, and the last row has no code:

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

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}.parts"
run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}")
run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, code VARCHAR)")
run(f"INSERT INTO {TABLE} VALUES "
    "(1, 'AB12CD'), "
    "(2, 'AB12CE'), "
    "(3, 'XB12CD'), "
    "(4, 'ZZ99ZZ'), "
    "(5, 'AB12'), "
    "(6, NULL)")

[]
[]
[(6,)]

What it does

hamming lines the two strings up byte by byte and counts the positions where they differ. It never inserts or deletes, so the strings must have the same length; it suits fixed-length codes such as part numbers, postcodes or hashes.

It compares UTF-8 bytes, not characters. A letter outside ASCII takes two or more bytes, so hamming('é', 'e') fails: the strings are one character each, but é is two bytes and e is one. hamming('é', 'è') is 1: both are two bytes, and only the second byte differs. A string with an accented letter has more bytes than characters: 'café', with a precomposed é, is five bytes, so it can be compared with 'Hallo', and the distance is 4. Check lengths with strlen (bytes), not length (characters).

One bad row stops the whole query. If any row's strings have different lengths, or both are empty, the query fails with the error and returns no rows, including the rows that would have worked. A NULL argument gives NULL, not the error. To run hamming on a column, keep only the rows of the right length 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 hamming(NULL, 'Hallo'), hamming('a', NULL), hamming('karolin', 'kathrin'), "
    "hamming('abc', 'ABC'), mismatches('abc', 'abd')")
run("SELECT hamming('', 'Hallo')")
run("SELECT hamming('abc', 'ab')")
run("SELECT hamming('\u00e9', 'e')")
run("SELECT hamming('', '')")
run("SELECT hamming(123, 'Hallo')")

[(None, None, 3, 3, 1)]
OSError: Mismatch Function: Strings must be of equal length!
OSError: Mismatch Function: Strings must be of equal length!
OSError: Mismatch Function: Strings must be of equal length!
OSError: Mismatch Function: Strings must be of length > 0!
InternalError: Binder Error: No function matches the given name and argument types 'hamming(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts.

Examples

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

run(f"SELECT id, code, hamming(code, 'AB12CD') FROM {TABLE} ORDER BY id LIMIT 10")

OSError: Mismatch Function: Strings must be of equal length!

Keep only the six-byte codes in WHERE, so hamming() in the SELECT list runs on the rows that remain:

run(f"SELECT id, code, hamming(code, 'AB12CD') FROM {TABLE} "
    "WHERE strlen(code) = 6 ORDER BY id LIMIT 10")

[(1, 'AB12CD', 0), (2, 'AB12CE', 1), (3, 'XB12CD', 1), (4, 'ZZ99ZZ', 6)]

To filter on the distance itself, put the length check and hamming() in a CASE, so hamming() is called only when the lengths match. This keeps the codes that differ from AB12CD in at most one position:

run(f"SELECT id, code FROM {TABLE} "
    "WHERE CASE WHEN strlen(code) = 6 THEN hamming(code, 'AB12CD') <= 1 ELSE false END "
    "ORDER BY id LIMIT 10")

[(1, 'AB12CD'), (2, 'AB12CE'), (3, 'XB12CD')]

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

• In the SELECT list, the scan reads the column and the Query Engine computes hamming() for each row it returns.
• In WHERE, the scan sends the column for every row, and a FILTER step in the Query Engine computes hamming() 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 hamming(code, 'AB12CD') <= 1")

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│             #1            │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│ (hamming(code, 'AB12CD') <│
│            = 1)           │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│                           │
│        Projections:       │
│            code           │
│             id            │
│                           │
└───────────────────────────┘

Make it faster

• Store codes of one length, and their length. If you store the byte length in its own column when you write the rows, code_bytes = 6 is a comparison of a raw column with a constant, which is evaluated in VAST DataBase: rows of other lengths never leave storage and never reach hamming().
• Look up exact matches without it. code = 'AB12CD' is pushed down; hamming(code, 'AB12CD') = 0 gives the same rows but runs on every row (and fails on rows of other lengths). The plan for code = 'AB12CD' has no FILTER step:

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

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

Limitations and errors

• Same length only. Strings of different lengths fail with Mismatch Function: Strings must be of equal length!, and two empty strings with Mismatch Function: Strings must be of length > 0!. On a column, one such row stops the whole query. For strings of different lengths, use levenshtein.
• Bytes, not characters. Lengths are compared in bytes, and so are positions. See What it does.
• Strings only. A number, decimal, date, boolean, BLOB or list fails with No function matches the given name and argument types. Cast it first: hamming(CAST(n AS VARCHAR), '123').
• Case-sensitive. Compare lower() of both strings to ignore case.

run(f"SELECT mismatches(code, 'AB12CD') FROM {TABLE} WHERE id = 5")
run("SELECT hamming(123, 'Hallo')")

OSError: Mismatch Function: Strings must be of equal length!
InternalError: Binder Error: No function matches the given name and argument types 'hamming(INTEGER_LITERAL, STRING_LITERAL)'. You might need to add explicit type casts.

Similar functions

The other functions accept strings of different lengths, so they're compared on 'kitten' and 'sitting', which hamming can't compare.

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

[(2, 3, 3, 0.42857142857142855, 0.746031746031746)]
OSError: Mismatch Function: Strings must be of equal length!

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.
• levenshtein and strlen.