How to improve performance of this Scalar Function for search with ranking by word

Question

I have a function that searches and ranks to be used on inventory and part numbers. We have tried Full Text Search and Azure Cognitive Search and its been a long journey. I need to match and rank on arbitrary words defined as "Space delimited". On tables of > 75k records, the query takes 3-5sec.

The following demonstrates what I have working but would like to optimize:

Setup:

IF OBJECT_ID(N'dbo.MyTable', N'U') IS NOT NULL DROP TABLE MyTable;

CREATE TABLE MyTable (
    Id int NOT NULL,
    Data varchar(255),
    PRIMARY KEY (Id)
);

INSERT INTO MyTable VALUES (1, 'A CAR'), (2, 'A BIKE'), (3, 'CAR WASH'), (4, 'CAR BIKE RACK'), (5, 'A HOUSE');

IF OBJECT_ID('dbo.fn__SearcRankMyTable') IS NOT NULL DROP FUNCTION fn__SearcRankMyTable
GO

The function:

CREATE FUNCTION [dbo].[fn__SearcRankMyTable]
(
  @Id INT, 
  @Query VARCHAR(MAX)
)
RETURNS INT
AS
BEGIN
  DECLARE @Result INT;
  WITH T AS ( 
      SELECT B.[value] FROM MyTable
      CROSS APPLY STRING_SPLIT([Data], ' ') as A
      CROSS JOIN STRING_SPLIT(@Query, ' ') AS B
      WHERE Id = @id AND A.value LIKE b.[value] + '%'
    )
  SELECT @Result =  COUNT(Distinct(value)) FROM T
  RETURN @Result
END
GO

Intended use query:

SELECT S.*, Rank FROM MyTable S
CROSS APPLY ( SELECT [dbo].[fn__SearcRankMyTable](S.iD, 'CAR BIKE RACK')) ca (Rank)
WHERE RANK > 0
ORDER BY Rank DESC;

This above query for "CAR BIKE RACK" produces the following as desired:

Search behavior defined:

• Assume row already has computed column(data) of distinct words:
• Foreach query word that matches the beginning of a word in the data row, increment the rank. The highest possible rank will be the number of words in the query.
• Search query can be at most 4 words, can be passed broken into words server-side as passed if helps.

Next things to try:

• I have read that Scalar Valued Functions are slow(er) / Single threaded. Try to convert to Table Valued function.
• Inside the CROSS APPLY STRING_SPLIT([Data], ' ') as A and the latter Distinct would be nice to have a way to bail out. This will be my next approach.

Are there other considerations / technologies / approaches I should consider?

Optimization with RETURN SELECT using WHERE EXISTS (60% slower unfortunately)

CREATE FUNCTION [dbo].[fn__SearcRankMyTable]
(
  @Id INT, 
  @Query VARCHAR(MAX)
)
RETURNS INT
AS
BEGIN 
    RETURN (SELECT COUNT(*) FROM STRING_SPLIT(@Query, ' ') as A
    WHERE EXISTS (SELECT value FROM STRING_SPLIT((SELECT DATA FROM MyTable WHERE Id = @Id), ' ') WHERE [value] LIKE a.[value] + '%' ));
END
GO

Answer 1

For the following example data

INSERT INTO MyTable VALUES ('A CAR'), 
                           ('A BIKE'), 
                           ('CAR WASH'), 
                           ('CAR BIKE RACK'), 
                           ('A HOUSE');

INSERT INTO MyTable
SELECT TOP 75000 REPLACE(NEWID(), '-', ' ' )
FROM sys.all_columns c1, sys.all_columns c2

In WPR your current method looks like this

There is a sort for the final ranking, and other inner sorts for the count distinct as well as CPU time spent in string split (potentially made worse by dealing with LOB datatypes)

A faster method that works with your existing structure would be

DECLARE @Query VARCHAR(8000) = 'car BIKE RACK';

WITH QSplit([1], [2], [3], [4]) As
(
SELECT ' ' + [1], 
       ' ' + [2], 
       ' ' + [3], 
       ' ' + [4]
FROM string_split(UPPER(@Query), ' ', 1)
PIVOT (MAX(value) FOR ordinal IN ([1], [2], [3], [4])) AS P
)
SELECT m.*, Rank
FROM MyTable m
CROSS JOIN QSplit
CROSS APPLY (VALUES (CONCAT(' ', UPPER(Data) COLLATE Latin1_General_100_BIN2))) V(SpacePadded)
CROSS APPLY (VALUES (IIF(CHARINDEX([1],SpacePadded) > 0,1,0) + 
                     IIF(CHARINDEX([2],SpacePadded) > 0,1,0) + 
                     IIF(CHARINDEX([3],SpacePadded) > 0,1,0) + 
                     IIF(CHARINDEX([4],SpacePadded) > 0,1,0))               
                ) V2(Rank)
WHERE Rank > 0 
ORDER BY Rank DESC;

This

• Defines @Query as a non max datatype as doesn't sound like you need max and that can be slower.
• Only splits @Query once rather than redoing the splitting for each row in MyTable
• Removes the overhead of the (non inlined) scalar UDF
• Simplifies the calculation of RANK to remove some execution plan operators - including the inner sort.
• Uses a binary collation in the expectation that this should speed up the CHARINDEX search (NB: If you are able to ensure that all the Data will be stored in a canonical upper case form then do so and remove that UPPER(Data) call to avoid spending CPU time doing that at run time)

With this dummy data I found the revised method executes in around 100ms on my machine (original method was around 3 seconds).

The binary collate clause made a reduction from 500ms to 100ms even with the additional overhead of calling UPPER but if the data can be stored as upper case in the table then this will save some additional CPU time as no need to call UPPER(Data) which will remove the highlighted operation (reduces it down to ~65 ms for me).

Answer 2

you can try a tally table for a table value function call...

    CREATE function [dbo].[tvf_DelimitedString] 
(
    @string varchar(8000)
    , @demiliter char(1)
)

returns table with schemabinding as
return

with tally (n)
    as
        ( -- declare a tally table of up to 8000 records and limit it to the length of the incoming variable
            select top(isnull(datalength(@string), 0))
                row_number() over(order by (select null))
            from (values (0), (0), (0), (0), (0), (0), (0), (0)) as a(n) -- 8
            cross join (values (0), (0), (0), (0), (0), (0), (0), (0), (0), (0)) as b(n) -- 80
            cross join (values (0), (0), (0), (0), (0), (0), (0), (0), (0), (0)) as c(n) -- 800
            cross join (values (0), (0), (0), (0), (0), (0), (0), (0), (0), (0)) as d(n) -- 8000
                    
        )

, cteStartPos (n1) 
    as 
        (-- this notates the starting position for the first character of each word in the string)
            select 1 
            union all
            select t.n+1 
            from Tally t 
            where substring(@String,t.N,1) = @demiliter
        )
, cteLength (n1,l1)
    as
        ( -- this notates the length of each word in the string
            select s.n1
            -- is null | null if handles instances where the incoming string doesn't have a space
            , isnull(nullif(charindex(@demiliter, @string, s.n1), 0)-s.n1, 8000)
            from cteStartPos as s
        )
-- split the string based on the delimiter
 select ItemNumber = row_number() over(order by l.n1)
        , Item = substring(@String, l.n1, l.l1)
   from cteLength as l
;
GO

then you can call the table value function similar to how you call the string_split function

  declare @string varchar(8000) = 'car bike rack'
 SELECT myt.data, count(rankto.item) as Ranked
   FROM dbo.Mytable as myt
   cross apply  dbo.tvf_DelimitedString (data,' ') split
   cross apply  dbo.tvf_DelimitedString (@string, ' ') as rankto
   where rankto.item = split.item
   group by myt.data
   order by ranked

i basically took your sample table and created a 100k record table in SQL express and got a result set in 1 second. If you can do the ordering at the application layer, then that could help the performance as well.

Answer 3

when using the string split function, the longer the string you pass in, the worse the execution plan is going to get because the engine has no idea how many words are in your string.

[B.Ozar had a blog post about this recently.][1]

create function dbo.tvf_SSrank (
    @string varchar(8000)
    , @demiliter char(1)
    )
    
    returns table with schemabinding
    return
    
    select data, count(t1.value) as ranked
    from dbo.MyTable as tbl
    cross apply string_split(tbl.data, @demiliter) as t1
    cross apply string_split(@string,@demiliter) as t2
    where t1.value = t2.value
    group by data