What is the best approach to parsing a large amount of strings?

Question

I have a table with over 400,000,000 records and I am looking for advice on how to parse it quickly.

TheNameTable
(
  NameID  int primary key,
  TheName varchar(500)
)

The names are stored like this: "FirstName, LastName" (not my table, just what I have to work with)

I need to extract a unique list of last names. My initial thoughts are to process the table in a series of batches (say 50,000 records at a time), using the NameID to control the batch ranges. I would then use SQL's built in string functions to break the string at the "," and keep the right half of the string.

right(TheName,charindex('.',reverse(TheName))-1)

I have a feeling this will still take a LONG time.

Anyone out there have any other ideas?

Would it be worthwhile to simply export the data and process the file outside the database?

The Solution I went with:

As suggested, I created two computed columns. One for first name, one for last name. They are not persisted, as I do have limited space.

alter table TheNameTable 
add LastName as substring(TheName, charindex(',',TheName)+1,1000)

alter table TheNameTable 
add FirstName as left(TheName,charindex(',',TheName)-1)

I asked the admins for a temporary increase in RAM, they bumped the VM up to 32GB.

I created a new table, with columns for both FirstName and LastName. I put a unique compound index on the columns, but specified IGNORE_DUP_KEY = ON.

I just inserted the first 1,000,000 records. It filtered out 125,000 duplicates. The whole statement took 9 seconds to run.

That is the speed I was looking for!

Answer 1

400 million names is a lot. Am I in there? ;-)

My gut level feeling says that using substring isn't going to be terribly much slower than coding up something via the CLR. I'm a SQL guy, I've done a fair amount of simple parsing in the past (2000 or 2005), and I was involved in what was going to be a very complicated parsing scheme (addresses, world-wide) written in c and called via an xproc until we found that out prototype "native" code wasn't any faster than the same thing written with tsql functions.

If you want to use a language other than tsql, I'd suggest writting a CLR in c# or vb.net. For simple things, it's not hard to code in CLR. I went from newb to having a couple of working directory and file utilities in less than one morning. There are plenty of examples of simple clr procedures on the net. and you wont have to learn anything (or install visual studio) to write it in tsql

No matter what, you will have to go through the table at least once. If you export, then parse and then put back what is not a small amount of data, that's a lot of time. Can you guarantee that your source isn't going to change in the mean time?

Here's the thing that always seems to sneak up on everyone: What happens with the parsed data? Where does it wind up? Do you intend to update the row, perhaps there are lastname and firstname columns that you don't show in your example?

If you do, and those columns are currently null or have zero length stings in them, you may find that the update statement performance is very bad because sql may have to split pages to store the lastname.

In other words, your performance problem isn't parsing, it is storing the parsed data. Often, this is worse than inserting the data into another table. Also, all of those page splits will fragment your table and cause query performance to drop, which may enrage your dba because s/he will have to run a defrag procedure on the (large) table.

Here's one last thought: Do you really need to store the parsed data? Can you get away with a computed column that calculates the last name on the fly? Those are indexable, with certain conditions, if you need that. Another approach would be a view that exposes the columns of the table as well as your "parsed lastname column".

Answer 2

It may be quicker to write a little script in another language like c# for example, to pull all the data from the table and then manipulate it.

You could then do what ever you what with the data, either sending it somewhere else, or back to the database using BCP.

Answer 3

If you have access to a set of unix shell utilities (see gnu win32 if you need to get ones that run on Windows) you could export the column TheName and process it with a shell pipeline along the lines of:

cut -d, -f2 | sed 's/ //g' | sort | uniq

The export process will be quite expensive, though. On SQL Server, you could create a temporary table with the last names using a query along the lines of:

select distinct rtrim(ltrim (substring (Name, charindex (',', TheName) + 1, 100)))
  into #DistinctSurnames
  from TheNameTable

Any way you look at it, you're up for a table scan. The export would probably be more expensive than the distinct processing on the query, so at a guess the query would be faster.

Answer 4

I've been learning alot about SQL Server processing and thought I'd take a stab at this with a Cursor. My thought process is to create another database (maybe even another instance) so that you can truncate logs as needed, since this is a "reporting" database and you want to limit interaction with "Live" data.

Cursor would be a good idea, in my opinion, because you can do processing as you go, and theoretically in one pass. It wouldn't be to hard to

• Add a count field to LastName table, for example, to count name occurances (name, count).
• Add a loop counter that clears the transaction log after 1million loops.
• Add a divider that splits names into individual tables (LastNameA, LastNameB,... LastNameOther, Invalid)

Merge is a 2008+ construct, so this would work, afaik, if you created another instance and linked to 2000/2005 if your not in 2008+:

/*
USE Master;
IF EXISTS(SELECT name FROM sys.databases WHERE name = 'Original') DROP Database Original;
GO

CREATE DATABASE Original;
GO

USE Original;
GO

IF OBJECT_ID('TheNameTable','U') is not null DROP Table TheNameTable;
GO
Create Table TheNameTable (NameID INT Primary Key Identity, TheName varchar(500));
GO
INSERT INTO TheNameTable Values('John, Wayne');
INSERT INTO TheNameTable Values('Wayne, Berry');
INSERT INTO TheNameTable Values('Bill, Murray');
INSERT INTO TheNameTable Values('Elvis, Presley');
INSERT INTO TheNameTable Values('Lady, Gaga');
INSERT INTO TheNameTable Values('Latoya, Jackson');
INSERT INTO TheNameTable Values('Michael, Jackson');
INSERT INTO TheNameTable Values('Tito, Jackson');
INSERT INTO TheNameTable Values('Randy, Jackson');
INSERT INTO TheNameTable Values('Prince');
GO
*/
SELECT * FROM TheNameTable;

USE Master;
IF EXISTS(SELECT name FROM sys.databases WHERE name = 'Reporting') DROP Database Reporting;
GO

CREATE DATABASE Reporting;
GO
ALTER DATABASE Reporting SET RECOVERY SIMPLE;
GO

USE Reporting;
GO

IF OBJECT_ID('LastName','U') is not null DROP Table LastName;
GO
Create Table LastName (Name varchar(500) PRIMARY KEY);
GO

DECLARE @TheName varchar(500);
DECLARE @LastName varchar(500);
DECLARE LastNameCursor Cursor
FOR 
Select TheName
From Original.dbo.TheNameTable;

Open LastNameCursor;

Fetch NEXT FROM LastNameCursor INTO @TheName;

WHILE @@FETCH_STATUS = 0
BEGIN
    IF (@TheName LIKE '%,%')
    BEGIN
        SET @LastName = right(@TheName,charindex(',',reverse(@TheName))-1);
        MERGE INTO dbo.LastName T
        USING (SELECT @LastName Name) S
                ON T.Name = S.Name
    --  WHEN MATCHED THEN
    --          Nothing to do here.
        WHEN NOT MATCHED
                THEN INSERT VALUES (@LastName);
    END

    FETCH NEXT FROM LastNameCursor INTO @TheName;
END

CLOSE LastNameCursor;
DEALLOCATE LastNameCursor;
GO

SELECT * FROM Reporting.dbo.LastName;
GO