gcd

Applies to VAST Cluster 5.5.

Functions › Numeric and math functions › Arithmetic. gcd(a, b) returns the greatest common divisor of two integers: the largest whole number that divides both without a remainder. The result is never negative. greatest_common_divisor is the same function.

Syntax

gcd(a, b)
greatest_common_divisor(a, b)

Returns: BIGINT, for every integer type up to BIGINT: gcd(12::TINYINT, 18::TINYINT) is a BIGINT. UBIGINT and HUGEINT arguments give a HUGEINT, which the ADBC driver returns as a DECIMAL(38,0) and Python prints as a Decimal.

Aliases: greatest_common_divisor.

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_numeric_gcd. 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 three fractions, each a numerator (BIGINT) and a denominator (INTEGER). The second numerator is negative, the third is 0, and 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_numeric_gcd"'

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}.fractions"
run(f"CREATE SCHEMA IF NOT EXISTS {SCHEMA}")
run(f"CREATE TABLE IF NOT EXISTS {TABLE} (id BIGINT, num BIGINT, den INTEGER)")
run(f"INSERT INTO {TABLE} VALUES "
    "(1, 12, 18), "
    "(2, -42, 56), "
    "(3, 0, 5), "
    "(4, NULL, NULL)")

[]
[]
[(4,)]

What it does

gcd(a, b) is the largest whole number that divides both a and b: gcd(12, 18) is 6.

• Signs don't matter. The result is the same for a and -a, and it's never negative: gcd(-12, 18), gcd(12, -18) and gcd(-12, -18) are all 6.
• 0 is divisible by everything, so gcd(0, 5) and gcd(5, 0) are 5, and gcd(0, 0) is 0.
• Two arguments only. For three or more values, nest the calls: gcd(gcd(a, b), c).
• A numeric string is converted: gcd('12', 6) is 6. A string that isn't a number fails with Could not convert string 'abc' to INT64.

A common use is reducing a fraction: dividing the numerator and the denominator by their gcd gives the same fraction in lowest terms, as in the first example below.

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 gcd(NULL, 6), gcd(6, NULL), gcd(12, 18), greatest_common_divisor(12, 18)")
run("SELECT gcd(-12, 18), gcd(12, -18), gcd(-12, -18), gcd(0, 0), gcd(0, 5), gcd(5, 0)")
run("SELECT typeof(gcd(12::TINYINT, 18::TINYINT)), gcd(18446744073709551615::UBIGINT, 5), gcd('12', 6)")
run("SELECT gcd(-9223372036854775808::BIGINT, 0)")
run("SELECT gcd(12.0, 18)")
run("SELECT gcd(1, 2, 3)")
run("SELECT gcd(1.5::DOUBLE, 6)")

[(None, None, 6, 6)]
[(6, 6, 6, 0, 5, 5)]
[('BIGINT', Decimal('5'), 6)]
OSError: Type INT128 with value 9223372036854775808 can't be cast because the value is out of range for the destination type INT64
InternalError: Binder Error: No function matches the given name and argument types 'gcd(DECIMAL(3,1), INTEGER_LITERAL)'. You might need to add explicit type casts.
InternalError: Binder Error: No function matches the given name and argument types 'gcd(INTEGER_LITERAL, INTEGER_LITERAL, INTEGER_LITERAL)'. You might need to add explicit type casts.
InternalError: Binder Error: No function matches the given name and argument types 'gcd(DOUBLE, INTEGER_LITERAL)'. You might need to add explicit type casts.

Examples

Each fraction in lowest terms: the numerator and the denominator divided by their gcd. The fraction 0/5 reduces to 0/1:

run(f"SELECT id, num, den, gcd(num, den), num // gcd(num, den), den // gcd(num, den) FROM {TABLE} ORDER BY id LIMIT 10")

[(1, 12, 18, 6, 2, 3), (2, -42, 56, 14, -3, 4), (3, 0, 5, 5, 0, 1), (4, None, None, None, None, None)]

The same with greatest_common_divisor, and the greatest common divisor of three values, nested:

run(f"SELECT id, greatest_common_divisor(num, den), gcd(gcd(num, den), 4) FROM {TABLE} ORDER BY id LIMIT 10")

[(1, 6, 2), (2, 14, 2), (3, 5, 1), (4, None, None)]

Keep only the fractions that are already in lowest terms:

run(f"SELECT id, num, den FROM {TABLE} WHERE gcd(num, den) = 1 ORDER BY id LIMIT 10")

[]

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

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

┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│             #2            │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│   (gcd(num, CAST(den AS   │
│        BIGINT)) = 1)      │
│                           │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         VAST_SCAN         │
│    ────────────────────   │
│    Function: VAST_SCAN    │
│                           │
│        Projections:       │
│            num            │
│            den            │
│             id            │
│                           │
└───────────────────────────┘

Make it faster

• Store the result if you filter on it often. Compute gcd() when you write the rows and keep it in its own column, or store the fractions already reduced: a comparison of a column with a constant, such as den = 3, is pushed down to VAST DataBase. The plan for it has no FILTER step:

plan(f"SELECT id FROM {TABLE} WHERE den = 3")

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

• Combine it with a pushed-down condition. In id > 100 AND gcd(num, den) = 1, id > 100 is still evaluated in VAST DataBase, so gcd() runs only on the rows that pass it.

Limitations and errors

• Integers only. DECIMAL, DOUBLE and FLOAT values fail with No function matches the given name and argument types, even 12.0. Cast them first: gcd(CAST(x AS BIGINT), 18).
• Two arguments only. gcd(1, 2, 3) fails with No function matches the given name and argument types. Nest the calls.
• The smallest BIGINT fails. gcd(-9223372036854775808::BIGINT, 0) stops the query with Type INT128 with value 9223372036854775808 can't be cast because the value is out of range for the destination type INT64. gcd(-9223372036854775808::BIGINT, -1) fails the same way, although its result, 1, would fit. Cast to HUGEINT first, as in the block below.
• UHUGEINT isn't accepted and fails with No function matches the given name and argument types.

run("SELECT gcd(CAST(12.0 AS BIGINT), 18), gcd(gcd(12, 18), 8)")
run("SELECT gcd(CAST(-9223372036854775808 AS HUGEINT), 0)")

[(6, 2)]
[(Decimal('9223372036854775808'),)]

Similar functions

run("SELECT gcd(12, 18), greatest_common_divisor(12, 18), lcm(12, 18), least_common_multiple(12, 18), 12 * 18 // gcd(12, 18), 18 % gcd(12, 18)")

[(6, 6, 36, 36, 36, 0)]

Clean up:

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

[]
[]

See also

• Numeric and math functions: all the arithmetic functions.
• lcm, factorial and % (modulo).
• Where filters run and pushdowns.
• EXPLAIN: how to read a plan.