Comparing client lists with Cross Joins I've written a query to compare the clients in our database with the people in a list that I've received. It needs to check if anyone from the list is one of our clients. I've created a temporary table which has been filled with the names and the query below makes a cross-join with the two tables. That query works very slowly (two very large tables), so I was wondering if there's any way to speed this up.
Would it be faster to just join everything in the database and compare strings in code (java or something similar)?

(The second list was just names, so I can't use any indexed columns in our database.)

select C.NUMCLI, C.NAAM, T.FULLNAME, (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) 
as DIFF from (select LASTNAME ||' '|| FIRSTNAME ||' '|| MIDDLENAME  as FULLNAME from 
TMP_CONTROL) T, (select NUMCLI, NOMCLI ||' '|| PRNCLI as NAAM from CLIENT
where CODLAN = 3 and STAANN &lt;&gt; 'D') C 
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) &gt;= 60


NOTE: A large portion of people on the list may have their name written in a slightly different manner, which is why I'm using the EDIT_DISTANCE SIMILARITY &gt;= 60. The goal is just to filter out the large differences, so I can easily compare the smaller ones.



Update

This is the explain-plan for the query: 

SQL> SET LINESIZE 130
SQL> SET PAGESIZE 0
SQL> SELECT *
  2  FROM   TABLE(DBMS_XPLAN.DISPLAY);
Plan hash value: 1462516232

---------------------------------------------------------------------------------
| Id  | Operation          | Name       | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |            |    74M|  3041M|  2197K  (3)| 07:19:29 |
|   1 |  NESTED LOOPS      |            |    74M|  3041M|  2197K  (3)| 07:19:29 |
|*  2 |   TABLE ACCESS FULL| CLIENT     | 71843 |  2174K|  2386   (2)| 00:00:29 |
|*  3 |   TABLE ACCESS FULL| TMP_CONTROL|  1033 | 12396 |    31   (4)| 00:00:01 |
---------------------------------------------------------------------------------


Predicate Information (identified by operation id):

2 - filter("STAANN"&lt;&gt;'D' AND TO_NUMBER("CODLAN")=3)
3 - filter("UTL_MATCH"."EDIT_DISTANCE_SIMILARITY"("NOMCLI"||'
          '||"PRNCLI","LASTNAME"||' '||"FIRSTNAME"||' '||"MIDDLENAME")&gt;=60)


17 rows selected.
Fundamentally, at some point, you have to do a cross-join to calculate your results. Performance will be a problem... but there are things that can be done.

First though, why the ugly SQL? Formatting SQL to make it readable is not hard to do:

select C.NUMCLI,
       C.NAAM,
       T.FULLNAME,
       (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) as DIFF
from (
        select LASTNAME ||' '|| FIRSTNAME ||' '|| MIDDLENAME  as FULLNAME
        from TMP_CONTROL
     ) T,
     (
        select NUMCLI,
               NOMCLI ||' '|| PRNCLI as NAAM
        from CLIENT
        where CODLAN = 3
          and STAANN &lt;&gt; 'D'
     ) C 
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) &gt;= 60


We can see a few things in here.....


Your source data contains a middle-name but your main table does not. Are you sure you want to be joining them this way? Will it create the correct results?


Now, about those performance improving options....

Let's assume that the best way to solve this problem is to do a cross-product of the two tables. Compare each value in table a with all values in table b. Oracle ha a few options for doing this. I will list them in what I consider to be a worst-to-best order:


true cross-product - It can do a true Cartesian product of the data - build an in-memory join of each value in the temp table joined to each value in the primary table, and then scan the results once, calculating the edit distance, and then discarding those results which are &lt; 60. It can either calculate the string concatenation of the names before or after the Cartesian product, either option will be (very) slow.
nested-loop T-&gt;C - It can loop through each temp table value, and for each of them, it can do the name-concatenation, and then it will need to join to the primary table (with the conditions), do the name-concatenation, and discard bad edit-distances.
nested-loop C-&gt;T - It can loop through each value in the primary table, check the conditions, and for each successful value, it can do the String-concatenation, it can scan all values in the temp table, compute the name-concatenation, and then calculate the edit distance, and discard the bad results.
nested-loop C'-&gt;T' or T'-&gt;C' - It can produce a temporary, or in-memory version of the pre-filtered C table and name-concatenated T and C tables, and then do a nested-loop of these two in-memory tables, discarding bad edit distances.


Your SQL is written to suggest you want it to do the last option, create two in-memory data sets, each of them pre-computed to contain just the name-concatenated values, and then you only perform the cross-product on these tables.... but, just because you wrote the SQL that way does not mean that Oracle will do the process that way....

... have you done an explain-plan to figure out which option it has taken?

My guess is that it has chosen nested-loop T-&gt;C, with a second possibility of nested-loop C-&gt;T. The reasons?


the temp table probably does not have statistics up to date, and is not indexed at all
the primary table probably has some indexes on CODLAN and/or STAAN
when Oracle optimizes the query, it will likely decide the temp-space required to store all the name-concatenated values will require too much memory, or even physical IO


Now, we want/need Oracle to choose the most efficient cross-join mechanism... and we do not want it calculating the name-concatenation on the fly because it will need to repeat that many times for at least one side of the cross-product.

The solution is to force Oracle's plan to do what we want, and the way to do that is to pre-compute the data needed for the cross-product.

Your temp table should already have the pre-computed name-concatenated values... why are you having to do the name-concatenation as part of the query? Call this column FULLNAME

Then, create a second table as:

create table TMP_CLIENTNAME (
    NUMCLI INTEGER NOT NULL,
    NAAM NVARCHAR(255) NOT NULL)
)

insert into TMP_CLIENTNAME
select NUMCLI,
       NOMCLI ||' '|| PRNCLI as NAAM
from CLIENT
where CODLAN = 3
  and STAANN &lt;&gt; 'D'


Then your cross-product query becomes:

select C.NUMCLI,
       C.NAAM,
       T.FULLNAME,
       (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) as DIFF
from TMP_CONTROL T,
     TMP_CLIENTNAME C
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) &gt;= 60


This query forces Oracle not to do any calculations other than the edit-distance in the join. This will make a difference....

The down-side is that you need additional storage for the data.

Once you have your data in this format you can consider some other options.... (which will likely affect the results of the edit-distance calculations)


index the first letter of each name, and only calculate the edit distances where the first letters are the same.
only calculate the edit distance when the length of the two names are less than say 5 characters different.
.....