Optimise performance of the Distinguishing Token comparison

[RobinL]

The postcode-exact safe-gap Splink comparison introduced in ba3b868 is
semantically useful, but its current DuckDB expression is expensive. In an
isolated benchmark over 1,000,000 representative comparisons, the current
expression took a median 2.231 seconds with 14 threads. Equivalent formulations
took approximately 0.408-0.416 seconds, a 5.4x speedup.

A similar optimisation should be possible re: #469

The main source of the regression is repeated use of
regexp_split_to_array(..., '\s+') inside nested list lambdas. Replacing only
that function with string_split(..., ' ') reduced median runtime by 72.8%.
Replacing the nested offset enumeration with a factored decision tree reduced
runtime by 81.7%.

A future PR should replace the current expression, preserve the existing match
weight and semantics, add direct equivalence tests, and rerun the isolated and
full Splink prediction benchmarks.

Current behaviour to preserve

The level returns true only when all of the following hold:

1. postcode_l = postcode_r.
2. distinguishing_adj_start_tokens_l exactly matches the beginning of
   clean_full_address_r.
3. The two canonical tokens immediately following that prefix in
   clean_full_address_l occur in the same order in clean_full_address_r.
4. The two evidence tokens are found within the first four positions following
   the prefix, allowing no more than two skipped tokens in total.
5. Every skipped token contains no digit.
6. No skipped token is one of:
   APARTMENT, BLOCK, BUILDING, COTTAGE, FLAT, HOUSE, MAISONETTE,
   OFFICE, STEADING, STUDIO, SUITE, UNIT, WAREHOUSE, or WORKSHOP.

The level currently contributes a fixed match weight of +10. This issue is
only about expressing the same condition more efficiently; it must not change
the weight or matching behaviour.

Why the current expression is slow

The current SQL:

• repeatedly tokenises both addresses with a regular expression;
• invokes tokenisation from inside nested range and list_transform lambdas;
• constructs six possible (first_offset, second_offset) combinations as
  nested lists;
• constructs another list for the gap offsets in each combination;
• flattens the resulting Boolean lists and searches them with list_contains.

Only six offset combinations are legal:

(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)

Enumerating these fixed cases through general-purpose list operations is much
more expensive than evaluating them directly.

Benchmark methodology

The experiment used:

• DuckDB 1.5.0;
• 1,000,000 row pairs;
• 100,000 real eligible canonical addresses sampled from the prepared Hackney
  canonical as source material;
• 514,830 true and 485,170 false results under the production expression;
• seven measured runs per formulation in shuffled order;
• one-thread and 14-thread configurations;
• materialised count(*) queries to force complete evaluation.

The generated workload exercised:

• no gaps;
• one gap;
• two adjacent gaps;
• two split gaps;
• numeric gaps;
• premise-type gaps;
• reversed evidence tokens;
• postcode mismatches;
• prefixes not at the start of the messy address.

The prepared Hackney canonical contained 392,621 rows, of which 378,623 were
eligible for this level. It contained zero clean_full_address values with
repeated whitespace. This supports replacing regex whitespace splitting with
literal-space splitting because the cleaning pipeline has already trimmed and
collapsed whitespace.

Every candidate expression was compared row-for-row with the production
expression. All candidates returned 514,830 true rows and had zero mismatches
across all 1,000,000 comparisons.

Results

One thread

Formulation	Median	Range	Speedup	Reduction
Current nested regex	17.252 s	16.979-18.727 s	1.00x	-
Nested logic with string_split	4.629 s	4.564-5.245 s	3.73x	73.17%
Explicit six-case array OR	4.406 s	4.368-4.657 s	3.92x	74.46%
Factored array decision tree	3.197 s	3.106-3.549 s	5.40x	81.47%
Explicit six-case split_part OR	4.403 s	4.393-4.907 s	3.92x	74.48%
Factored split_part tree	3.128 s	3.083-3.254 s	5.52x	81.87%

14 threads

Formulation	Median	Range	Speedup	Reduction
Current nested regex	2.231 s	2.172-2.298 s	1.00x	-
Nested logic with string_split	0.607 s	0.603-0.621 s	3.67x	72.78%
Explicit six-case array OR	0.573 s	0.564-0.631 s	3.89x	74.30%
Factored array decision tree	0.408 s	0.404-0.419 s	5.47x	81.71%
Explicit six-case split_part OR	0.578 s	0.572-0.596 s	3.86x	74.11%
Factored split_part tree	0.416 s	0.403-0.445 s	5.36x	81.33%

The factored array tree was fastest and most stable at the production-like
14-thread setting. The factored split_part tree was marginally faster with one
thread, but the difference between the two factored forms was small.

SQL options

The SQL below uses the existing Splink _l and _r column suffixes.

Option 0: current production expression

This is the reference expression from ba3b868:

postcode_l = postcode_r
AND list_slice(
    regexp_split_to_array(clean_full_address_r, '\s+'),
    1,
    len(distinguishing_adj_start_tokens_l)
) = distinguishing_adj_start_tokens_l
AND list_contains(
    flatten(
        list_transform(
            range(1, 5),
            first_offset -> list_transform(
                range(first_offset + 1, 5),
                second_offset ->
                    list_extract(
                        regexp_split_to_array(clean_full_address_r, '\s+'),
                        len(distinguishing_adj_start_tokens_l) + first_offset
                    ) = list_extract(
                        regexp_split_to_array(clean_full_address_l, '\s+'),
                        len(distinguishing_adj_start_tokens_l) + 1
                    )
                    AND list_extract(
                        regexp_split_to_array(clean_full_address_r, '\s+'),
                        len(distinguishing_adj_start_tokens_l) + second_offset
                    ) = list_extract(
                        regexp_split_to_array(clean_full_address_l, '\s+'),
                        len(distinguishing_adj_start_tokens_l) + 2
                    )
                    AND NOT list_contains(
                        list_transform(
                            list_filter(
                                range(1, second_offset + 1),
                                gap_offset ->
                                    gap_offset != first_offset
                                    AND gap_offset != second_offset
                            ),
                            gap_offset ->
                                regexp_matches(
                                    list_extract(
                                        regexp_split_to_array(
                                            clean_full_address_r,
                                            '\s+'
                                        ),
                                        len(distinguishing_adj_start_tokens_l)
                                            + gap_offset
                                    ),
                                    '[0-9]'
                                )
                                OR list_extract(
                                    regexp_split_to_array(
                                        clean_full_address_r,
                                        '\s+'
                                    ),
                                    len(distinguishing_adj_start_tokens_l)
                                        + gap_offset
                                ) IN (
                                    'APARTMENT', 'BLOCK', 'BUILDING', 'COTTAGE',
                                    'FLAT', 'HOUSE', 'MAISONETTE', 'OFFICE',
                                    'STEADING', 'STUDIO', 'SUITE', 'UNIT',
                                    'WAREHOUSE', 'WORKSHOP'
                                )
                        ),
                        TRUE
                    )
            )
        )
    ),
    TRUE
)

Option 1: retain nested logic and use string_split

This is the lowest-risk implementation. It keeps all current list enumeration
and changes only tokenisation:

-regexp_split_to_array(clean_full_address_r, '\s+')
+string_split(clean_full_address_r, ' ')

-regexp_split_to_array(clean_full_address_l, '\s+')
+string_split(clean_full_address_l, ' ')

Applied to the complete current expression, the SQL is:

postcode_l = postcode_r
AND list_slice(
    string_split(clean_full_address_r, ' '),
    1,
    len(distinguishing_adj_start_tokens_l)
) = distinguishing_adj_start_tokens_l
AND list_contains(
    flatten(
        list_transform(
            range(1, 5),
            first_offset -> list_transform(
                range(first_offset + 1, 5),
                second_offset ->
                    list_extract(
                        string_split(clean_full_address_r, ' '),
                        len(distinguishing_adj_start_tokens_l) + first_offset
                    ) = list_extract(
                        string_split(clean_full_address_l, ' '),
                        len(distinguishing_adj_start_tokens_l) + 1
                    )
                    AND list_extract(
                        string_split(clean_full_address_r, ' '),
                        len(distinguishing_adj_start_tokens_l) + second_offset
                    ) = list_extract(
                        string_split(clean_full_address_l, ' '),
                        len(distinguishing_adj_start_tokens_l) + 2
                    )
                    AND NOT list_contains(
                        list_transform(
                            list_filter(
                                range(1, second_offset + 1),
                                gap_offset ->
                                    gap_offset != first_offset
                                    AND gap_offset != second_offset
                            ),
                            gap_offset ->
                                regexp_matches(
                                    list_extract(
                                        string_split(clean_full_address_r, ' '),
                                        len(distinguishing_adj_start_tokens_l)
                                            + gap_offset
                                    ),
                                    '[0-9]'
                                )
                                OR list_extract(
                                    string_split(clean_full_address_r, ' '),
                                    len(distinguishing_adj_start_tokens_l)
                                        + gap_offset
                                ) IN (
                                    'APARTMENT', 'BLOCK', 'BUILDING', 'COTTAGE',
                                    'FLAT', 'HOUSE', 'MAISONETTE', 'OFFICE',
                                    'STEADING', 'STUDIO', 'SUITE', 'UNIT',
                                    'WAREHOUSE', 'WORKSHOP'
                                )
                        ),
                        TRUE
                    )
            )
        )
    ),
    TRUE
)

Measured reduction at 14 threads: 72.78%.

Shared notation for Options 2-5

The remaining options were benchmarked as expanded scalar expressions. The
following definitions make their exact Boolean layouts readable.

For the array variants:

-- n
len(distinguishing_adj_start_tokens_l)

-- left evidence tokens
l1 = list_extract(string_split(clean_full_address_l, ' '), n + 1)
l2 = list_extract(string_split(clean_full_address_l, ' '), n + 2)

-- messy tokens after the prefix
r1 = list_extract(string_split(clean_full_address_r, ' '), n + 1)
r2 = list_extract(string_split(clean_full_address_r, ' '), n + 2)
r3 = list_extract(string_split(clean_full_address_r, ' '), n + 3)
r4 = list_extract(string_split(clean_full_address_r, ' '), n + 4)

-- prefix predicate
list_slice(string_split(clean_full_address_r, ' '), 1, n)
    = distinguishing_adj_start_tokens_l

For the split_part variants:

-- n
len(distinguishing_adj_start_tokens_l)

-- left evidence tokens
l1 = split_part(clean_full_address_l, ' ', n + 1)
l2 = split_part(clean_full_address_l, ' ', n + 2)

-- messy tokens after the prefix
r1 = split_part(clean_full_address_r, ' ', n + 1)
r2 = split_part(clean_full_address_r, ' ', n + 2)
r3 = split_part(clean_full_address_r, ' ', n + 3)
r4 = split_part(clean_full_address_r, ' ', n + 4)

-- prefix predicate
starts_with(
    clean_full_address_r,
    array_to_string(distinguishing_adj_start_tokens_l, ' ') || ' '
)

For both families, safe(token) expands exactly to:

NOT regexp_matches(token, '[0-9]')
AND token NOT IN (
    'APARTMENT', 'BLOCK', 'BUILDING', 'COTTAGE', 'FLAT', 'HOUSE',
    'MAISONETTE', 'OFFICE', 'STEADING', 'STUDIO', 'SUITE', 'UNIT',
    'WAREHOUSE', 'WORKSHOP'
)

These names are explanatory notation only. The benchmark expanded every name to
its full scalar expression, matching what a Splink sql_condition can contain.

Option 2: explicit six-case array OR

Use the array definitions above and replace the nested lambdas with all six
legal offset pairs:

postcode_l = postcode_r
AND prefix_predicate
AND (
    (r1 = l1 AND r2 = l2)
    OR (r1 = l1 AND safe(r2) AND r3 = l2)
    OR (r1 = l1 AND safe(r2) AND safe(r3) AND r4 = l2)
    OR (safe(r1) AND r2 = l1 AND r3 = l2)
    OR (safe(r1) AND r2 = l1 AND safe(r3) AND r4 = l2)
    OR (safe(r1) AND safe(r2) AND r3 = l1 AND r4 = l2)
)

Measured reduction at 14 threads: 74.30%.

This is explicit and easy to compare with the six legal offset pairs, but it
repeats several predicates.

Option 3: factored array decision tree

Use the same array definitions but factor shared branches:

postcode_l = postcode_r
AND prefix_predicate
AND (
    (
        r1 = l1
        AND (
            r2 = l2
            OR (
                safe(r2)
                AND (
                    r3 = l2
                    OR (safe(r3) AND r4 = l2)
                )
            )
        )
    )
    OR (
        safe(r1)
        AND (
            (
                r2 = l1
                AND (
                    r3 = l2
                    OR (safe(r3) AND r4 = l2)
                )
            )
            OR (
                safe(r2)
                AND r3 = l1
                AND r4 = l2
            )
        )
    )
)

Measured reduction at 14 threads: 81.71%. This was the fastest and most
stable production-like result and is the recommended target.

Option 4: explicit six-case split_part OR

Use the split_part token and prefix definitions with the exact six-case layout
from Option 2:

postcode_l = postcode_r
AND prefix_predicate
AND (
    (r1 = l1 AND r2 = l2)
    OR (r1 = l1 AND safe(r2) AND r3 = l2)
    OR (r1 = l1 AND safe(r2) AND safe(r3) AND r4 = l2)
    OR (safe(r1) AND r2 = l1 AND r3 = l2)
    OR (safe(r1) AND r2 = l1 AND safe(r3) AND r4 = l2)
    OR (safe(r1) AND safe(r2) AND r3 = l1 AND r4 = l2)
)

Measured reduction at 14 threads: 74.11%.

Option 5: factored split_part decision tree

Use the split_part token and prefix definitions with the exact factored layout
from Option 3:

postcode_l = postcode_r
AND prefix_predicate
AND (
    (
        r1 = l1
        AND (
            r2 = l2
            OR (
                safe(r2)
                AND (
                    r3 = l2
                    OR (safe(r3) AND r4 = l2)
                )
            )
        )
    )
    OR (
        safe(r1)
        AND (
            (
                r2 = l1
                AND (
                    r3 = l2
                    OR (safe(r3) AND r4 = l2)
                )
            )
            OR (
                safe(r2)
                AND r3 = l1
                AND r4 = l2
            )
        )
    )
)

Measured reduction at 14 threads: 81.33%.

Recommendation

Implement Option 3, the factored array decision tree using
string_split(clean_full_address, ' ') and list_extract.

Reasons:

• it was fastest at 14 threads;
• it had the narrowest measured range of the high-performance options;
• array prefix equality is direct and does not rely on constructing a prefix
  string;
• its behavior matched the production expression on every benchmark row;
• its control flow directly represents the bounded-gap rule.

Option 1 is a useful fallback if the PR needs the smallest possible diff. It
captures most of the available improvement while retaining the existing nested
logic.

Proposed implementation work

1. Replace the comparison level's sql_condition in
   uk_address_matcher/data/splink_model.json.
2. Keep its label, m_probability, u_probability, and fixed-probability flags
   unchanged.
3. Retain or expand direct comparison-level tests covering:
   • zero gaps;
   • one gap;
   • two adjacent gaps;
   • two split gaps;
   • postcode mismatch;
   • numeric gap;
   • premise gap;
   • oversized gap;
   • reversed evidence;
   • prefix not at the start.
4. Add an equivalence test that evaluates the old and new SQL over a generated
   matrix of representative token sequences.
5. Rerun the one-million-row isolated benchmark.
6. Rerun the area-scoped and national isolated Splink prediction benchmarks,
   using one warm-up plus five measured runs and timing predict() through full
   materialisation.
7. Confirm candidate-pair counts and matching outputs are unchanged.

Acceptance criteria

• The optimized level has no semantic mismatches against the current condition
  over the generated equivalence matrix.
• Existing linker and comparison-level tests pass.
• Candidate-pair counts are unchanged in area-scoped and national prediction
  benchmarks.
• The national prediction regression introduced by the safe-gap level is
  materially reduced.
• The precision-recall output is unchanged because the level's truth values and
  match weight are unchanged.

Caveats

This benchmark isolates the comparison expression. It demonstrates that the
expression itself can be evaluated approximately 5.4x faster, but it does not
prove that the complete Splink prediction query will improve by the same factor.
The full prediction benchmark is required before merging.

The string_split(..., ' ') optimization relies on the cleaning pipeline's
normalised-whitespace invariant. The PR should retain a focused test for that
assumption or explicitly document it alongside the optimized condition.