sql: support running LIKE operator against collated columns (with suitable indexing)

[idubrov]

Primary use case: prefixed search against collated columns (LIKE 'Prefix%').
Secondary use case: arbitrary LIKE searches against collated columns (LIKE '%Infix%').

Example:

CREATE TABLE test (name STRING COLLATE en_u_ks_level2);
INSERT INTO test(name) VALUES ('Alex' COLLATE en_u_ks_level2);
SELECT name FROM test WHERE name LIKE 'Ale%' COLLATE en_u_ks_level2; -- doesn't work!

Current output:

pq: unsupported comparison operator: <collatedstring{en_u_ks_level2}> LIKE <collatedstring{en_u_ks_level2}>

Prefix search is should-have. Arbitrary expressions are nice-to-have.

Workaround: it is possible to run range query instead of prefix LIKE search:

SELECT * FROM test WHERE (name >= 'Ale' COLLATE "en_u_ks_level2"  AND name < 'Alf' COLLATE "en_u_ks_level2");

However, the tricky part here is figuring out what should be the "next" symbol according to the collation rules ("e" -> "f" is easy, but could be different case, modifiers, etc).

On the other hand, it should be close to trivial for the CockroachDB to figure out that: once key is computed for the prefix, finding the "next" prefix is easy.

Jira issue: CRDB-5918

[idubrov]

I looked into the code a little, and I think I was too optimistic about "trivial". It looks like even if you optimize for the prefix using proper scan, you still need a correct "LIKE" implementation for DCollatedString's.

However, "LIKE" uses a regexp to run the match and regexp package seem not to support collations.

On the other hand, it does not look like an impossible task to implement an algorithm specifically tuned for "LIKE" patterns, to run against binary key generated by the collator (although, simple conversion from pattern to collation key might not work -- I don't know what would happen to '%' and '_' -- so you might need to split pattern into pieces somehow).

[knz]

cc @awoods187 please consider roadmapping this for one of the upcoming releases.

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it in
5 days to keep the issue queue tidy. Thank you for your contribution
to CockroachDB!

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it in
10 days to keep the issue queue tidy. Thank you for your contribution
to CockroachDB!

[knz]

still relevant