Comparing client lists with Cross Joins

Question

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 <> 'D') C 
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) >= 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 >= 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"<>'D' AND TO_NUMBER("CODLAN")=3)
3 - filter("UTL_MATCH"."EDIT_DISTANCE_SIMILARITY"("NOMCLI"||'
          '||"PRNCLI","LASTNAME"||' '||"FIRSTNAME"||' '||"MIDDLENAME")>=60)

17 rows selected.

Answer 1

Given the comments on my other answer, here is a second answer.

Notes:

1. ... have you done an explain-plan to figure out which option it has taken? I suggested this in the first answer... have you done it?
2. If the explain plan shows that the code is producing a temp-table for the name-concat of the TMP_CONTROL data, and that it does a nested-loop scan of the CLIENT -> temp-table to calculate the Edit Distance - then there is nothing you can do that will be faster.
3. If you really, really can't create the tables manually, then it is likely that the best result you will be able to achieve will be to externalize the data and process it outside the database.

But, this is hard work, and, to match the DB performance, you will need a decent machine (lots of memory), and be willing to process the data in parallel, etc.

You suggested this before, using Java.

The basic algorithm I would use in Java (Java7) is as follows:

• Create a JDBC session to the database.
• Select the string-concatenation of the names from the TMP_CONTROL table.
• save these values in to an ArrayList<String> (or, if you do not have enough memory, to a file on disk - one name per line)
• Create an ExecutorService with about as many threads as you have 'logical' CPUs (Executors.newFixed...).
• Set up an ExecutorCompletionService to handle results...
• Select the ID and the string-concatenation of the names from the CLIENT table. Save each record in to a new CLient class. This Client class will look something like:

    public class Client implements Callable<Client> {
         private final int id;
         private final String fullname;
         private final Map<String, Integer> matches = new HashMap<>();

         // constructor

         // getters for ID and fullname

         public void addMatch(String naam, int score) {
             matches.put(naam, score);
         }

         public Client call() {
             // Loop over each of the TMP names we stored earlier...
             for (String othername : tempnames) {
                 // calculate the EditDistance from our name.
                 // if it is > 60, do:
                 if (editdistance > threshold) {
                     addMatch(othername, editdistance);
                 }
             } 
             return this;
         }
     }

• submit this Client to your ExecutorCompletionHandler
• Have a separate thread that retrieves completed Clients from the ExecutorCompletionHandler with the Future<Client> future = handler.take();
• Process the matching names as you feel fit....

That's about how I would do it in Java.....

Answer 2

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 <> 'D'
     ) C 
where (UTL_MATCH.EDIT_DISTANCE_SIMILARITY(NAAM, FULLNAME)) >= 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 < 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->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->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'->T' or T'->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->C, with a second possibility of nested-loop C->T. The reasons?

1. the temp table probably does not have statistics up to date, and is not indexed at all
2. the primary table probably has some indexes on CODLAN and/or STAAN
3. 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 <> '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)) >= 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.
• .....