7

Naively I assumed that the relationship between a like 'foo%' and a >= 'foo' is that the latter matches the former and some additional rows that come after in the index order. More generally, I thought that for a given text t an index on a character column splits into four regions, being

  1. the entries before (<) t,
  2. the entries equal to (=) t,
  3. the entries greater than (>) t that still have t as a prefix (like concat(t, '%')) and
  4. the rest,

and that those regions are contiguous and in that order.

Also, all rows having t as a prefix (like concat(t, '%')) form a contiguous region in the index as well and that this region contains region 2 at its start (meaning it's exactly the regions 2 and 3 together).

It may not be that simple though. For example, in SQL Server the word Häuser compares equal to Haeuser in the collation German_PhoneBook_CI_AI and both are >= 'Ha'.

However, only Haeuser matches like 'Ha%', so the additional assumptions about prefixes don't entirely hold.

You can see this in this fiddle.

My question is what other assumptions here may be wrong. Does the result of an anchored like even always give a contiguous slice of the index or can there be gaps?1 Do I at least still have those four contiguous regions?

The underlying problem I'm working on is a generic database UI that shows index slices for a given search term. It's beneficial from a user experience point of view to not have the user select whether they want to make a prefix, equality or greater-than search, but to simply start at the equality (in the case of ascending seeking), following the index and then marking the two further boundaries "no longer equal from here" and "not even a prefix anymore here".

Only character types have this issue as it comes from the complications of collations.

This question is tagged SQL Server, but I feel if there's a RDMS where this isn't true that it's probably a deeper issue I need to know about - so feel free to comment about any engine that would disagree with my assumptions.


1Meaning, can there be values r and s with r < t < s where r and s both match the anchored like but t does not?

0

4 Answers 4

7

For example, in SQL Server the word Häuser comes before Haeuser in the collation German_PhoneBook_CI_AI

No it doesn't. They are equal.

  select case when  N'Häuser' < N'Haeuser' Collate German_PhoneBook_CI_AI 
              then 'true' else 'false' end

returns

false

N'Hä' = N'Hae' Collate German_PhoneBook_CI_AI 

but

 N'Ha' < N'Hä'  Collate German_PhoneBook_CI_AI 

And so N'Häuser' is not like 'Ha%' but is like N'Hae%' and like N'Hä%'.

It's possible that SQL Server will not be able to completely evaluate the like predicate in an index seek+ordered scan, instead having to seek+scan a larger range and apply the like operator to the rows in the larger range. See Dynamic Seeks and Hidden Implicit Conversions

2
  • 2
    @John but precisely due to the fact that N'Hä' = N'Hae', we can construct alternating ordered sequences like N'Hä' < N'Haeb' < N'Häc' < N'Haed' < N'Häm' < N'Haeu'... Isn't that what your last paragraph (r<t<s) asks about? Commented Sep 5, 2022 at 17:31
  • Right. With that, I guess we can have gaps in the like range. Interesting. It should be possible to construct an example where a like clause doesn't have logarithmic performance and basically has to scan then. That's surprising.
    – John
    Commented Sep 5, 2022 at 19:27
3

This behavior is due to how the LIKE operator/function is expanded. To see this more clearly, I started with your db<>fiddle test and made some changes and additions (shown below):

SETUP

-- DROP TABLE CollationTests;
create table CollationTests (
    i int identity,
    v varchar(20) collate German_PhoneBook_100_CI_AS not null, -- German_PhoneBook_CI_AI

    index IX_CollationTests_v nonclustered (v),
    constraint PK_CollationTests primary key clustered (i)
)


insert into CollationTests (v) values
('Hammer'),
('Hauser'),
('Häuser'),
('Haeuser'),
('Hae'),
('Hä'),
('Hc'),
('Horse'),
('Melon')
;

Please note the following changes from the original db<>fiddle test:

  • Table:
    • Changed collation to German_PhoneBook_100_CI_AS
      • When using SQL Server > 2005, then you really should be using a 100 level collation (or 140 level for Japanese collations on SQL Server 2017+)
      • I switched to (A)ccent (S)ensitive to help illustrate that ä == ae
    • Changed clustered index to be "PK" instead of "IX" to make it clearer if any of the test cases forced a clustered index scan
  • Data:
    • I added the final five rows to help make the behavior clearer

TESTS

Please note: I executed these in SQL Server Management Studio (SSMS) and enabled "Include Actual Execution Plan       Ctrl + M"

select * from CollationTests
where v = 'Ha' collate German_PhoneBook_100_CI_AI
order by v;
-- No rows
select * from CollationTests
where v = 'Hä'
order by v
/*
5   Hae
6   Hä
*/
select * from CollationTests
where v > 'Ha'
order by v
/*
5   Hae
6   Hä
3   Häuser
4   Haeuser
1   Hammer
2   Hauser
7   Hc
8   Horse
9   Melon
*/
select * from CollationTests where v like 'Ha%' order by v;
/* -- Seek Keys:
           Start: [dbo].[CollationTests].v >= Scalar Operator('Ha'),
             End: [dbo].[CollationTests].v <  Scalar Operator('HB')

5   Hae
4   Haeuser
1   Hammer
2   Hauser
*/

The following test actually shows (via the "Seek Keys", as taken from the execution plan) the ä being decomposed into ae (through Unicode normalization):

select * from CollationTests where v like 'Hä%' order by v;
/* -- Seek Keys:
           Start: [dbo].[CollationTests].v >= Scalar Operator('Hae'),
             End: [dbo].[CollationTests].v <  Scalar Operator('HaF')

5   Hae
6   Hä
3   Häuser
4   Haeuser
*/

The following test uses the "Seek Keys" as shown two tests above:

select * from CollationTests
where v >= 'Ha'
and v < 'HB'
order by v
/* -- Seek Keys:
  Start: [dbo].[CollationTests].v >= Scalar Operator(CONVERT_IMPLICIT(varchar(8000),[@1],0))
    End: [dbo].[CollationTests].v < Scalar Operator(CONVERT_IMPLICIT(varchar(8000),[@2],0))

5   Hae
6   Hä
3   Häuser
4   Haeuser
1   Hammer
2   Hauser
*/

The results show two additional rows are returned, which could indicate either that there is a timing difference for when the ä is decomposed into ae, or perhaps there is something happening with CONVERT_IMPLICIT() as that is not in the execution plan for the queries with the LIKE operator/function.

(It seems that a little more investigation is needed. I'll see if I can come up with something, else will note here if this is as far as it goes for now)

1
  • 2
    Like isn't directly seekable. The index range is manufactured by the optimiser so it can seek the index. The original like expression is always applied to all found rows in a residual predicate to ensure only exact matches are returned. See the link in David's answer
    – Paul White
    Commented Sep 5, 2022 at 20:03
2

Since the answers are good but a bit orthogonal, I'd like to summarize what I learned here:

  1. SQL Server translates the like into an index range that can be seen in the query plan (not always though, I tried Korean and then SQL Server does something more tricky to figure the range boundaries and doesn't expose them literally in the plan).
  2. This range doesn't match the anchored likes result set exactly, and with respect to the range the result set may
    • even have gaps,
    • not even be able to use the index efficiently.
-2

Ordering uses collation. If your table has an accent-insensitive german collation then ä and ae are identical.

LIKE doesn't use collation and performs exact matching as far as accents are concerned. To perform accent-insensitive LIKE comparisons, you can use a "collation cast".

Here is my example in a FRENCH_CI_AS database :

SELECT M
FROM (SELECT 'du' AS M UNION ALL SELECT 'dû') AS Liste
WHERE M COLLATE FRENCH_CI_AI LIKE 'DU'
ORDER BY 1;

If I omit the "collation cast" only 'du' matches. With the "collation cast", both match.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.