Name Matching Alternatives

The users want to locate people by last name.  They want flexible matching.  That's not very hard.

The DBA wants to do some wild-card searches efficiently.  The DBA may not be responding to the users actual request, making this more complex than it needs to be.

I'm not in contact with the users, so I don't know the real requirements.  I'm hearing this through the DBA-filter ("all singing, all dancing, all SQL".)  I may also be hearing this through IT management filter ("only use technology I recognize from my programming days".)

In my experience, wild-card searches are rarely the user's first choice.  They want more flexible matching.  While the SQL LIKE-clause is one solution that might work, it is rarely what the users really want.

The DBA knows that the SQL LIKE-clause effectively defeats indexing and forces row-by-row comparison.  And we all know that row-by-row processing is evil.

Premature Optimization

Question 1.  Is this premature optimization?   

There's no way to tell.  The database server may be beefy enough and the query rare enough that a basic LIKE-clause regular expression will work just fine.

Step 1.  Benchmark this baseline solution.

As Fast as Possible -- in SQL

One way to find names quickly is to denormalize the data base.  In addition to the proper names, also store the soundex of the name.  Since this is stored, and there's no function call in the WHERE clause, and this is fully indexed, it will find "similar-sounding" names very quickly.

Soundex has limitations, so some folks use metaphone.  The principle is the same.  When inserting or updating the name, also insert (or update) the metaphone of the name.

This, BTW, does not involve any wild-card.  Except in unusual cases, it always returns a set of candidates.  And the set of candidates is a better fit than any wild-card search.   More focused, and the whole name is considered.

Step 2.  Prototype the soundex solution.  It's hard to explain, and impossible to visualize.  Actual result sets make it concrete.

Throw Memory At It

Here's an alternative that works really well.  

Stop using the database.

Don't waste brain cells trying to write this kind of super-flexible search in SQL. It's better done in code.  Write a simple materialized view with name and PK and nothing else.  Create the smallest possible table that can be used just for name matching -- nothing else in this table.  It's little more than an index.

Write a simple web service that queries this physically small table, doing a search algorithm.  The web service will locate near-matches in this small table.  It could return full rows for the top matches, or simply return the names and PK's for users to pick from. 

You have several candidate algorithms for this server.  A wisely-written web service can use a combination of algorithms and return a match score along with the names and PK's.

• Soundex/Metaphone match.
• Levenshtein distance.
  

Web Service for Wildcards

An alternative web service can query the name/PK table using a nice regular expression library.  Since RE syntax can be complex, you would translate from a user-friendly syntax to a proper RE syntax.  

For instance, the LIKE-like syntax can be reformulated to proper RE syntax.  The %'s become .* and the _'s become .'s.  Or perhaps you offer your users shell-like syntax.  In this case, the *'s become .* and the ?'s become .'s.

Either way, the user's wild-card becomes a proper regular expression.  The web service queries the table, matching all input against the RE.  The service could return full rows for the top matches, or simply return the names and PK's for users to pick from. 

This little web service can be granted a large amount of memory to cache large row sets.  Boy will it be fast.

Also, depending on the pace of change in the underlying table, it may be possible for this service to query all names into a cache once every few minutes.   Perhaps it can do this by first making a SQL request to refresh the materialized view and then a query to fetch the updated view into memory.

What the DBA wants

The DBA wants some magical pixie dust that somehow makes a query with a LIKE clause use an index and behave like other properly indexed columns. 

The actual email enumerated four of the possible ways a LIKE clause could be used.  I'm guessing the hope was that somehow the enumeration of a subset of candidate LIKE clauses would help locate the pixie dust.

Here's my advice.  If this magical LIKE clause feature already existed, it would be in the DBA guide.  Since it isn't in the DBA guide, perhaps it doesn't exist.   Enumerating four use cases (name, *name, name* and *name*) doesn't help, it's still not going to work out well.  Remember, SQL's been around in this form for decades; the LIKE clause continues to be a challenge.

First, benchmark.  Second, offer the users soundex.  Then, well, you've got work to do.

Applet Not Inited; the "Red X" problem

I haven't done Applet stuff in years.

I do -- intensely -- like embedding functionality in web pages.  RIA/Ajax and what-not are something I have trouble with because I'm not a graphic designer.  Javascript and Applets fall into three clear categories:

1. Basic usability.  Javascript offers lots of little enhancements to HTML presentation that make sense.  Emphasis on "little".
   
2. Client-side features.  Many things are simple calculators or other processing that makes sense on the client side -- the relevant factors can be downloaded and used by an applet or javascript script.  
3. Junk.  There are lots of graphical effects that vary from gratuitous to irritating.  Too many folks in marketing see some "pop-up" technique and think it's cool.  Worse, they'll take an application that lacks solid use cases and try to add flashing to scrolling to emphasize something instead of reducing clutter and distraction.  Sigh.

The Common Problems

In all web-based software development, the number one problem is always permissions.  Always.  In the case of applet development, this is always hurdle number one.  The file isn't owned by the right person or doesn't have the right permissions.  You see the "applet not inited" and "red X icon" as symptoms of the applet not being downloaded at all.

The number two problem is access to resources.  Usually this is a CLASSPATH issue, but it can also be an HTML page with a wrong URI for the applet's code.  You see the "applet not inited" and "red X icon" as symptoms of the applet not being referenced correctly, or not being able to locate all of its parts.

[Technically, the basic access comes before permissions, but you usually don't get access wrong first.  Usually, you get permissions wrong; later, you discover you have a subtle access issue.]

One of the more subtle manifestations are the case-matching issues.  Your Java class definitions are usually UpperCase.  The source file and resulting class file will have this same UpperCase format.  But if you get the case wrong in your HTML, you just get an applet not inited error.  Arrgh.

When you don't work with applets all that often, the "applet not inited" is baffling.

Misdirection

I wasted hours on Google and Stack Overflow looking up "applet not inited" and "Red X icon" and similar stuff.

Then I looked at the HTML I was testing.

Surprise.  No one had moved the .jar file into the proper directory.

There's a lot of stuff on the applet not inited error.  Most of it misses the usual culprits: permissions and access to the resources.  

This sounds complicated, because it is

For a while, I generated documentation with Cheetah. I wrote bodies as a fragment of HTML and used Cheetah to wrap those bodies in standard templates with navigation and branding.

To write my books, I learned DocBook markup and used DocBook XSL tools to create HTML and PDF versions of the book's text. Even though XML is hard to work with, I managed to muddle through. It's painful -- at times -- but doable.  

[Eventually, I found XMLMind's XML Editor.  It rocks.  But that's off-topic.]

Then, I fount RST and RST2HTML.  For a while, I wrote my documentation in RST and used a simple script to create the HTML version of the documentation from RST source.

Why ReStructuredText?

From their site: "reStructuredText is an easy-to-read, what-you-see-is-what-you-get plaintext markup syntax".  

• Easy-to-Read.  The markup is very, very simple.  Mostly spacing and simple quoting.  Yet, for edge cases, there is enough richness to approach DocBook XML.
  
• WYSIWYG.  The markup doesn't get in the way; you write the text with a few conventions for spacing and quoting.
• Plain Text.  A few spacing and quoting rules are used to distinguish structure from content.  Presentation is a limited part RST (like HTML where some presentation is present in the structural markup, but can be avoided.)

RST lead me, eventually to Sphinx. 

The Secret of Sphinx

Sphinx is RST-based markup.  You write in plaintext (plus some quoting and spacing) and you get an elegant HTML web site with inter-document references all resolved correctly, contents, indexes, auto-generated API documentation for your Python software, syntax coloring, everything.  Wow.

I can't stop myself from doing everything in Sphinx.  You create a development structure for your source files.  You use a series of toctree directives to build the resulting documentation structure that people will see and use.

I've decided to convert some ancient Cheetah-based stuff to Sphinx.  

Unmarking Up

Revising HTML-based document bodies to RST is annoying.  It can be done with Beautiful Soup.  The HTML is pretty regular (and pretty simple) so it wouldn't be too bad.  Except for a bunch of edge cases that have significant complexity.

The original Cheetah-based site wasn't purely documentation.  It doesn't fit the Sphinx use cases perfectly.  A fairly significant percentage of the Cheetah-based pages are HTML pages with complex, embedded applets to do calculations.

These pages are not -- strictly speaking -- documentation.  They're an application.  They contain markup (<embed> mostly) that RST can't generate.  Further, they have to be unit tested prior to running Sphinx to build the documentation, since the HTML is actually part of the application.

Raw HTML?

The applet pages are -- more or less -- raw HTML pages that need to be folded in with the Sphinx-generated documentation.  Sphinx has an HTML_STATIC_PATH configuration parameter that can copy these applications from project folders into destination directories.

But this leaves me with dozens of Cheetah-generated pages as part of this application.  The presence of Cheetah in the midst this Sphinx operation makes things complicated.

Or, perhaps it doesn't.

It turns out that Sphinx is built on Jinja.  There's a template engine under the hood!  That's handy.  That lets me build the application HTML with a slightly different template engine; one that's compatible with the rest of the Sphinx-generated site.

I think I've got a clean, RST-based replacement for my lovingly hand-crafted HTML.  It's a lot of rework, but the simplification is of immense value.

Data Structures in Python and SQL

This is -- partially -- about the object-relational impedance mismatch.  But it's also about the parallel concepts between objects and relations.  We'll use Python as our object model.

First, the obvious.

A SQL table is a list of rows.  A row is a dictionary that maps a column name to a column value.  A SQL table has a defined type for a named column; Python doesn't pre-define the type of each column.

Some folks like to think of a table as a rigidly-defined class, which is partly true.  It can be rigidly-defined.  However, the extra meta-data doesn't help much.

Indexing

As a practical matter, most databases go beyond the minimalist definition of a relationship as a collection of rows.  An index extends the structure in one of two ways.

A unique-key index transforms the SQL table into a dictionary that maps a key to a row.

    class UniqueKeyTable( object ):
        def __init__( self ):
            self.rows = {}
        def insert( self, aRow ):
            self.rows[aRow.key()]= [aRow]

The non-unique key index transforms the SQL table into a dictionary that maps a key to a list of rows.

    class KeyedTable( object ):
        def __init__( self ):
            self.rows = collections.defaultdict(list)
        def insert( self, aRow ):
            self.rows[aRow.key()].append( aRow )

SQL Operations

The single-table SELECT algorithm has a WHERE clause that gets broken into two parts: key filtering and everything else.

The basic SELECT looks something like this.

    for k in table.rows[key]:
        for r in table.rows[k]:
            if other_where_clause( r ):
                select_group_by( r )

That's the essential feature of a basic select -- it expresses a number of design patterns.  There's a key-to-list map, a filter, and the "select-group-by" map to results.

In theory, the SELECT operation is the more general "filter" algorithm, where every row passes through the a general where_clause_filter process.  

The Join Algorithms

We have a number of alternative join algorithms.  In some cases, we have two dictionaries with the same keys.  This leads to a highly optimized query where one key locates rows on both sides of the join.

In other cases, we have a kind of nested-loops join.  We find a row in one table, and use this row's attributes to locate a row in another table.

The "Which is Better?" Question

We always have two alternatives for every algorithm:  the SQL version and the Python version.  This is an essential issue in resolving the Object-Relational Impedance mismatch issue.  We can implement our algorithm on either side: Python objects or SQL relations.

Note that there's no simple "Use SQL for this" or "Use Python for that" decision process.  The two structures -- objects and relations -- are completely isomorphic.  There's no specific set of features that dominate either representation.  

The literal question that I got was "Should I use a complex data structure in a programming language or should I use SQL ?"

Ideally, the answer is "SQL does [X] better", leading to an easy decision.  But this kind of answer doesn't exist.

The two structures are isomorphic; the correct answer is hard to determine.  You want the RDBMS to filter rows and return the smallest relevant set of data to the object representation.  While locating the fewest rows seems simple, a few things make even this hard to determine.  

While it seems that the RDBMS can be the best way to handle join algorithms, this doesn't always work.  When we're doing a join involving small tables, the RDBMS may be less effective than an in-memory dictionary.  It sometimes occurs that SQL is best for filtering very large tables only.

Indeed, the only way to chose among two isomorphic representations (objects vs. relations) is to benchmark each implementation.

iWeb -- not so nice

For techincal blogging (like this) iWeb is weak.  

The total MacOSX integration -- pictures, podcast, etc. -- is nice.  It's very cool for my travelogues. But for code samples and the kind of customized HTML widgets that are required by Technorati, it's too hard to deal with.

The size of the iWeb pages is magnificent.  Reading a posting is an undertaking.  I don't really like that, since this is mostly simple text; the ultra complex graphics aren't an asset.

For now, I still have to mess around with the ShareThis link.  I'm not sure if I like the sophistication of Share This or if I want button-by-button links to digg, facebook, tweet and track, stumble upon, reddit, del.icio.us, and yahoo buzz buttons on each post.

Multi-threaded apps and module globals

Learned about module globals the hard way.

The mod_wsgi daemon by default spawns 15 threads.  This is important, but not obvious.

During load testing, we had intermittent weird errors.  We were seeing an odd inconsistency in replies.  My experience in creating military software in the ’80’s leads me to put loop-back self-tests everywhere.  One of our loopbacks wasn’t looping back properly.

The symptom looked like a single value being overwritten.  After a design review, it appears that one information source -- a module global -- wasn’t working well.

Module globals -- like other Singletons -- are a seductive trap.   The issue is that a multi-threaded application will have one copy of the module.  The one copy may not be thread safe.  

The problem is that  thread-safety requires some fairly detailed analysis. Simple unit testing isn’t quite enough.  But the process of designing for testability is helpful.  Isolation and encapsulation are important for testability as well as locating thread-safety issues.

All Those TODO's

About a year ago, we started out doing Python development with simple rst2html documents for requirements, design, etc.  In the code, we had comments that used epydoc with the epytext markup language.

No, it wasn’t confusing.  Free-text documents (requirements, architecture, design, test plans, etc.) are easy and fun to write in RST.  Just write.  Leave the formatting to someone else.  A little semantic markup doesn’t hurt, but you don’t spend hours with MS-Word trying to  disentangle your bullets and your numbering.

Adding comments to code in epytext was pretty easy, also.

Then I discovered Sphinx.   Sphinx can add module documentation to a document tree very elegantly.  Further, Sphinx can pull in RST-formatted module comment strings.  Very nice.

Except, of course, we have hundreds of modules in epytext.  Today, I started tracking down all of the 150+ modules without proper document strings in RST notation.  Hopefully, this time tomorrow, I’ll have a much, much better -- and internally consistent -- set of documentation.