TSQL join performance

The short answer is don't use the LIKE operator to join two tables containing millions of rows. It's not going to be fast, no matter how you tune it. You might be able to improve it incrementally, but it will just be putting lipstick on a pig.

You need to have a distinct value on which to join the tables. Right now it has to do a complete scan of tableA, and do an item-by-item wildcard comparison between Customer_Name and CustomerMask. You're looking at 14 billion comparisons, all using the slow LIKE operator.

The only suggestion I can give is to re-think the architecture of associating rules with Customers.

Only change order join then faster and enjoy! use this query:

Select tableA.CUSTOMER_NAME, tableB.CUSTOMER_NUMBER, TableB.RuleID  
FROM tableB  
INNER JOIN tableA  
on tableB.CustomerMask like tableA.CUST_PO_NUMBER

Am I missing something? What about the following:

Select
  tableA.CUSTOMER_NAME,
  tableA.CUSTOMER_NUMBER,
  tableB.RuleID
FROM tableA, tableB 
WHERE tableA.CUST_PO_NUMBER = tableB.CustomerMask

EDIT2: Thinking about it, how many of those masks start and end with wildcards? You might gain some performance by first:

• Indexing CUST_PO_NUMBER
• Creating a persisted computed column CUST_PO_NUMBER_REV that's the reverse of CUST_PO_NUMBER
• Indexing the persisted column
• Putting statistics on these columns

Then you might build three queries, and UNION ALL the results together:

SELECT ...
  FROM ...
         ON CUSTOM_PO_NUMBER LIKE CustomerMask
 WHERE /* First character of CustomerMask is not a wildcard but last one is */

UNION ALL

SELECT ...
  FROM ...
         ON CUSTOM_PO_NUMBER_REV LIKE REVERSE(CustomerMask)
 WHERE /* Last character of CustomerMask is not a wildcard but first one is */

UNION ALL

SELECT ...
  FROM ...
         ON CUSTOM_PO_NUMBER LIKE CustomerMask
 WHERE /* Everything else */

That's just a quick example, you'll need to take some care that the WHERE clauses give you mutually exclusive results (or use UNION, but aim for mutually exclusive results first).

If you can do that, you should have two queries using index seeks and one query using index scans.

EDIT: You can implement a sharding system to spread out the customers and customer masks tables across multiple servers and then have each server evaluate 1/n% of the results. You don't need to partition the data -- simple replication of the entire contents of each table will do. Link the servers to your main server and you can do something to the effect of:

SELECT ... FROM OPENQUERY(LinkedServer1, 'SELECT ... LIKE ... WHERE ID BETWEEN 0 AND 99')
  UNION ALL
SELECT ... FROM OPENQUERY(LinkedServer2, 'SELECT ... LIKE ... WHERE ID BETWEEN 100 AND 199')

_{Note: the OPENQUERY may be extraneous, SQL Server might be smart enough to evaluate queries on remote servers and stream the results back. I know it doesn't do that for JET linked servers, but it might handle its own kind better.}

That or through more hardware at the problem.

You can create an Indexed View of your query to improve performance.

This should improve the performance of this particular query, but note that inserts, updates and deleted into the tables it uses may be slowed.

You can't use LIKE if you care about performance.

If you are trying to do approximate string matching (e.g. Test and est and best, etc.) and you don't want to use Sql full-text search take a look at this article.

At least you can shortlist approximate matches then run your wildcard test on them.

--EDIT 2--

Your problem is interesting in the context of your limitation. Thinking about it again, I am pretty sure that using 3 gram would boost the performance (going back to my initial suggestion).

Let's say if you setup your 3gram data, you'll be having the following tables:

Customer : 14M 
Customer3Grams : Maximum 700M //Considering the field is varchar(50)
3Grams : 78
Pattern : 1000
Pattern3Grams : 50K

To join pattern to customer then you need the following join:

Pattern x Pattern3Grams x Customer3Grams x Customer

With appropriate indexing (which is easy) each look-up can happen in O(LOG(50K)+LOG(700M)+LOG(14M)) which is equal to 47.6.

Considering appropriate indexes are present the whole join can be calculated with less than 50,000 look-ups and of course the cost of scanning after look ups. I expect it to be very efficient (matter of seconds).

The cost of creating 3grams for each new customer is also minimal because it would be maximum of 50x75 possible three grams that should be appended to the customer3Grams table.

--EDIT--

Depending to your data I can also suggest hash based clustering. I assume customer numbers are numbers with some character patterns in them (e.g. 123231ttt3x4). If this is the case you can create a simple hash function that calculates the result of bit-wise OR for every letter (not numbers) and add it as an indexed column to your table. You can filter on the result of the hash before applying LIKE.

Depending to your data this may cluster your data effectively and improve your search by factor of the number of clusters (number of hash). You can test it by applying the hash and counting the number of distinct generated hash.