2

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: Results

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
13
  • "I have read that Scalar Valued Functions are slow(er) / Single threaded" - Yes, and multi-statement table valued functions (such as yours) also force serialized zones in the execution plans they're a part of. Not as bad as (non-inlinable) scalar functions but that means your function itself will always be single threaded. Could you provide more context on your use case from a business logic perspective? Your part numbers have a nomenclature that involves space delimited words?
    – J.D.
    Jan 12, 2023 at 21:02
  • Business case is we want the users to be able to input manufacturer name and or type and or part number and or description in a single unstructured intput string and return a ranked list of Items that match. I have a search table that is populated with Mfr Names, Item Types, Part Number and it has a computed column that stores the distinct words.
    – ttugates
    Jan 12, 2023 at 21:11
  • A cross cutting, alternate example of business case with more detail: Client lists a table of Invoices. There is a single search input above it should accept Customer Name or Vehicle Description in addition to the Invoice Number which narrows the results of Invoices in the Table, which has paging(Skip / Take) and thus ordering.. I left all this out to keep question focused on the piece I need assistance with.
    – ttugates
    Jan 12, 2023 at 21:22
  • Ok that makes more sense now. (Having worked in manufacturing, I've never heard of anyone with part numbers that are named with words and spaces.) But your goal is to just offer a global search to the end user, essentially. Having a denormalized search table probably complicates things and hurts performance more than it helps you, to be honest. You'd likely be better off unioning the results of custom queries for each table of data, with a search predicate tailored to that table. E.g. when searching on part numbers, you don't need to worry about full text search, since they're single words.
    – J.D.
    Jan 12, 2023 at 22:43
  • 1
    Hopefully the revised version in the answer chips away at that timing a bit more Jan 16, 2023 at 17:43

3 Answers 3

4
+100

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

enter image description here

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).

enter image description here

8
  • 1
    Thank you for all your time, immensly! Some additional detail I didn't include. The Data column will only be all Upper, numbers and these '(', ')', '|', '-'. I am string building in C# and replacing the CTE with for ex: (SELECT 'car' AS [0], 'oil' AS [1]) and this allows me to also string build the correct number of IIF(CHARINDEX([1],SpacePadded) > 0,1,0)
    – ttugates
    Jan 16, 2023 at 18:09
  • 1
    @ttugates - in that case you can get rid of UPPER(Data) and just use Data as the UPPER won't do anything there and will take some CPU time Jan 16, 2023 at 18:11
  • @ttugates - I just noticed what you said about SELECT 'car' AS [0] - in that case you don't need QSplit at all. You can just start the query at SELECT m.*, Rank and instead of CHARINDEX([1],SpacePadded) do CHARINDEX(' ' + @Param1,SpacePadded) etc - and pass the parameter values as upper cased individual values Jan 16, 2023 at 18:32
  • Thats exactly what I did. Replace QSplit is what I meant by saying replacing the CTE
    – ttugates
    Jan 16, 2023 at 21:44
  • @ttugates - the query in my answer works fine., from your comment above it looks like you dropped the CONCAT(' ', when rewriting it., This was the purpose of that Jan 17, 2023 at 18:30
1

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.

enter image description here

1
  • you could also just create a tvf using the string_split functions...lol
    – stecyk
    Jan 22, 2023 at 21:45
0

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 

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.