SQLServerCentral / Article Discussions / Article Discussions by Author / Discuss content posted by Ben Seaman / Optimising “Ends With” searches with REVERSE / Latest Posts

RE: Optimising “Ends With” searches with REVERSE

ben-564110 — Fri, 15 Jan 2010 05:27:42 GMT

[quote][b]Calvin Lawson (1/15/2010)[/b][hr]Thanks Ben, great idea for when you absolutely have to have those fast lookups with wildcards at the beginning of the search term. Which happens more often then one might think...One small point; for the sake of code clarity, I would do something like this:SELECT NAME FROM TEST_TABLE WHERE NAME_REVERSED LIKE REVERSE('%ID')[/quote]Hi Calvin,True - I suppose it depends on whether you can get the calling code to reverse the search term for you. If you have a high volume web site doing lots of searches for example, you might want to get the web code to do this (albeit minor) string reversion as SQL is probably going to be slower at doing this than a web farm.On the other hand it makes it better for code isolation purposes if you can just give the search term you are looking for to the SQL codeSo another 'it depends' answer then!Regards,Ben

RE: Optimising “Ends With” searches with REVERSE

Calvin Lawson — Fri, 15 Jan 2010 02:09:50 GMT

Thanks Ben, great idea for when you absolutely have to have those fast lookups with wildcards at the beginning of the search term. Which happens more often then one might think...One small point; for the sake of code clarity, I would do something like this:SELECT NAME FROM TEST_TABLE WHERE NAME_REVERSED LIKE REVERSE('%ID')

RE: Optimising “Ends With” searches with REVERSE

ben-564110 — Thu, 14 Jan 2010 04:33:37 GMT

[quote][b]Peter Brase (1/13/2010)[/b][hr]Thanks for this, an excellent tip! I discovered that even if you skip the extra column and just run the reverse query, i.e., "where reverse(fieldname) like 'cba%'" instead of "where fieldname like '%abc'" the response time improves by 50%.[/quote]Hi Peter,Depending on how you measured that response time I'd be a little bit wary of that test. It might be simply that the first time you ran the query, the pages returned were kept in the SQL cache, and then when the second query was run (which would return exactly the same rows/pages) the data came straight from the cache and was therefore quicker.Regards,Ben

RE: Optimising “Ends With” searches with REVERSE

SQLRNNR — Wed, 13 Jan 2010 12:40:25 GMT

Jeff, Paul and others have made some excellent comments. I think this was a nice article. It certainly opens up avenues of thinking for any who might need to refine similar situations.

RE: Optimising “Ends With” searches with REVERSE

johnzabroski — Wed, 13 Jan 2010 11:42:04 GMT

You can circumvent the max index key sizehttp://blogs.msdn.com/anthonybloesch/archive/2009/11/23/implementing-uniqueness-constraints-on-large-columns.aspx

RE: Optimising “Ends With” searches with REVERSE

john.arnott — Wed, 13 Jan 2010 09:54:05 GMT

Bravo! Excellent example of explaining a technique that, once understood, seems so very natural. And, once again the discussion adds tremendously by making it clear that this is a "pay me now or pay me later" situation (absorb the overhead of index maintenance in favor of faster queries) and by suggesting improvements like Peter's (make the computed column only the last N characters of the search column). Articles and discussions like this have made SSC my favorite web site (edging out ESPN.com).=============edit: fix minor typo

RE: Optimising “Ends With” searches with REVERSE

JJ B — Wed, 13 Jan 2010 09:28:52 GMT

What great timing for this article!I'm just finishing up the design for an application that involves a "call module". This module is a place for users to record various data about phone calls that come into our agency. One of the features in the application is that the users need to be able to look up (search) records by the caller's phone number. For various reasons, when entering the phone number data, users will have to enter the full phone number, including an area code. Ex: (541)444-5555. However, the VAST majority of phone numbers that our users will enter or see will have the same area code. So, I've been playing with the idea of adding a feature where staff only have to enter the last 7 digits [i]when doing a search[/i]. I've been reluctant to implement such a feature for a couple reasons, one of which is precisely because I didn't want to have a WHERE clause such as: WHERE phone like '%444-5555'Yuck.This article has given me a technique that makes that feature more palatable. I understand Jeff's caution. Even so, I'm excited about this idea because I think it might be perfect for the situation in my application. Thanks.(The reason I explained my situation in detail is because I thought it might be helpful to provide a real-world example of when this need might come into play. If I didn't have such a need myself right now, I would not have been able to think of a realistic example of why anyone would really want to provide a "search the end" feature for users.)

RE: Optimising “Ends With” searches with REVERSE

Peter Brase — Wed, 13 Jan 2010 09:18:04 GMT

Thanks for this, an excellent tip! I discovered that even if you skip the extra column and just run the reverse query, i.e., "where reverse(fieldname) like 'cba%'" instead of "where fieldname like '%abc'" the response time improves by 50%.

RE: Optimising “Ends With” searches with REVERSE

Jeff Moden — Wed, 13 Jan 2010 09:13:40 GMT

[quote][b]Rome1981 (1/13/2010)[/b][hr]I was just about to post the same. Good to know there are people testing these solutions/examples.Jeff- That is very good advice, I did not know that.[/quote]Thanks for the feedback. They key is that you have to look, though. Like Paul says, "Logical Reads" isn't the best and most reliable parametric and execution plans can lie like a rug.

RE: Optimising “Ends With” searches with REVERSE

Jeff Moden — Wed, 13 Jan 2010 09:10:54 GMT

RE: Optimising “Ends With” searches with REVERSE

Jeff Moden — Wed, 13 Jan 2010 09:09:58 GMT

[quote][b]Jeff Moden (1/13/2010)[/b][hr]Don't get me started on what a poor metric the number of 'logical reads is' [/quote]Heh... now you know why I couched it all in "It Depends". :hehe: Between that and the crud that shows up in the execution plan....

RE: Optimising “Ends With” searches with REVERSE

ben-564110 — Wed, 13 Jan 2010 09:06:40 GMT

[quote][b]peter-757102 (1/13/2010)[/b][hr]Note that indexes can only have a limited width (300 bytes or so , I believe).Because of this, it makes sense to do a reverse of only the last N characters and limit the length of the search text to match. If your strings have varying lengths between 3 and 250 characters and your search strings are strict enough with 12 characters, add a few extra and use the reverse of the rightmost 16 characters to put the index on and truncate the search string to 16 characters as well. This saves you a ton of otherwise unneeded duplicate data and keeps the number of page reads to a minimum.[/quote]That's a great idea and a good refinement. I suppose you could also search on the last n characters which would potentially return you a list of primary keys from the table and then do a normal 'forwards' search on the resulting rows to narrow those down to the specifc results you want. The max index key size is 900 bytes BTW. See [url=http://msdn.microsoft.com/en-us/library/ms191241.aspx][/url] for details.Regards,Ben

RE: Optimising “Ends With” searches with REVERSE

alen teplitsky — Wed, 13 Jan 2010 09:04:03 GMT

this is great and would be a great replacement for Full Text Indexing for smaller text columns. my biggest gripe about FTI is the blocking caused by inserting large amounts of data if you have change tracking set to auto

RE: Optimising “Ends With” searches with REVERSE

peter-757102 — Wed, 13 Jan 2010 08:17:23 GMT

Note that indexes can only have a limited width (300 bytes or so , I believe).Because of this, it makes sense to do a reverse of only the last N characters and limit the length of the search text to match. If your strings have varying lengths between 3 and 250 characters and your search strings are strict enough with 12 characters, add a few extra and use the reverse of the rightmost 16 characters to put the index on and truncate the search string to 16 characters as well. This saves you a ton of otherwise unneeded duplicate data and keeps the number of page reads to a minimum.

RE: Optimising “Ends With” searches with REVERSE

Tab Alleman — Wed, 13 Jan 2010 07:49:42 GMT

When I saw the title of this article, I immediately envisioned replacing:...WHERE Name LIKE '%son'with:WHERE LEFT(REVERSE(Name),3)='nos'Because to answer the introductory question, "How often do I need to do a search like...?": Not nearly often enough to justify creating a new indexed column solely for that purpose. A pure-SQL solution would be interesting though.

RE: Optimising “Ends With” searches with REVERSE

Rome1981 — Wed, 13 Jan 2010 06:56:23 GMT

I was just about to post the same. Good to know there are people testing these solutions/examples.Jeff- That is very good advice, I did not know that.

RE: Optimising “Ends With” searches with REVERSE

ben-564110 — Wed, 13 Jan 2010 03:24:55 GMT

Hi Varun.C,Well spotted! I have made the correction.Many thanks,Ben

RE: Optimising “Ends With” searches with REVERSE

Paul White — Wed, 13 Jan 2010 03:10:52 GMT

[quote][b]Jeff Moden (1/13/2010)[/b][hr]Good article and makes a lot of sense... providing that the table doesn't have a lot of inserts where every index counts AGAINST inserts. Most people don't know that INSERTS on heavily indexed tables are one of the primary causes of very high reads. For example and using the given example table, if I run the following code...... then we can see that a single insert after the index is created now takes 11 reads instead of just 3.[/quote]On my 2008 system, the logical reads change from 3 to 5 (there are 7090 rows). [quote][b]Jeff Moden (1/13/2010)[/b][hr]If you have an IO bound system, you need to be really careful about adding any indexes to tables that have a high insertion rate. Like everything else, "It Depends" and only a bit of "complete" testing will show you things that you may have not considered.[/quote]It is important to consider the impact of index maintenance, for sure, but there's nothing unusual about that. Every new index has to justify itself in terms of the trade off between increased maintenance overhead versus the benefits produced by having the index. Generally, one would expect most useful indexes to involve a net saving in reads; the reduced reads coming from queries that benefit from the index should outweigh the reads added by index maintenance.Don't get me started on what a poor metric the number of 'logical reads is' ;-)All that aside, I found this to be a good article, and a fine approach for any system that finds itself requiring a lot of 'ends with' searches. It is also well presented and clear - so top marks for style.Paul

RE: Optimising “Ends With” searches with REVERSE

Jeff Moden — Wed, 13 Jan 2010 00:26:39 GMT

Good article and makes a lot of sense... providing that the table doesn't have a lot of inserts where every index counts AGAINST inserts. Most people don't know that INSERTS on heavily indexed tables are one of the primary causes of very high reads. For example and using the given example table, if I run the following code...[code="sql"]--drop table test_tableSELECT object_id, name, system_type_id INTO test_table FROM master.sys.all_parametersCREATE NONCLUSTERED INDEX ix_name ON test_table (name ASC)ALTER TABLE test_table ADD name_REVERSED AS REVERSE(name)PRINT '========== Insert with no index =========='SET STATISTICS IO ONSET STATISTICS TIME ONINSERT INTO test_table SELECT 1,'Dodah',2SET STATISTICS TIME OFFSET STATISTICS IO OFFGOCREATE NONCLUSTERED INDEX IX_REVERSED ON TEST_TABLE (NAME_REVERSED ASC) INCLUDE (NAME)GOPRINT '========== Insert with index =========='SET STATISTICS IO ONSET STATISTICS TIME ONINSERT INTO test_table SELECT 1,'Dodah',2SET STATISTICS TIME OFFSET STATISTICS IO OFF[/code]... then we can see that a single insert after the index is created now takes 11 reads instead of just 3.[code="plain"](6756 row(s) affected)========== Insert with no index ==========SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.Table 'test_table'. Scan count 0, logical reads 3, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.SQL Server Execution Times: CPU time = 0 ms, elapsed time = 1 ms.(1 row(s) affected)========== Insert with index ==========SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.Table 'test_table'. Scan count 0, logical reads 11, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.SQL Server Execution Times: CPU time = 0 ms, elapsed time = 1 ms.(1 row(s) affected)[/code]If you have an IO bound system, you need to be really careful about adding any indexes to tables that have a high insertion rate. Like everything else, "It Depends" and only a bit of "complete" testing will show you things that you may have not considered.

RE: Optimising “Ends With” searches with REVERSE

Varun.c — Tue, 12 Jan 2010 23:52:30 GMT

Nice Article.I think you need to correct this query fromSELECT NAME FROM TEST_TABLE WHERE NAME LIKE 'DI%'ToSELECT NAME FROM TEST_TABLE WHERE NAME_REVERSED LIKE 'DI%'Best,Varun.C

Optimising “Ends With” searches with REVERSE

ben-564110 — Tue, 12 Jan 2010 21:27:27 GMT

Comments posted to this topic are about the item [B]Optimising “Ends With” searches with REVERSE[/B]