Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

We need to create hash value of nvarchar data for comparison purposes.

There are multiple hash algorithms available in T-SQL, but which one the best to choose from in this scenario? We want to ensure the risk of having duplicate hash value for two different nvarchar value is the minimum. Based on my research on the internet MD5 seems the best one. Is that right? MSDN tells us about the available algorithms, but no description on which one for what conditions? http://msdn.microsoft.com/en-au/library/ms174415%28v=sql.105%29.aspx

share|improve this question
    
Can you give us some context as to what you're trying to do? –  Jon Seigel Feb 22 '13 at 17:57
    
We need to join two tables on two nvarchar(max) columns. As you can imagine the query takes along time to execute. We thought it would be better to keep the hashsum value of each nvarchar(max) data and do the join on the hash values rather than the nvarchar(max) values which are blobs. The question is which hash algorithm provides the uniqueness, so that we don't run into the risk of having one hash value for more than one nvarchar(max). –  Nazila Beikpour Feb 24 '13 at 23:35
add comment

3 Answers

up vote 7 down vote accepted

The HASHBYTES function only takes up to 8000 bytes as input. Because your inputs are potentially larger than that, duplicates in the range of the field that gets hashed will cause collisions, regardless of the algorithm chosen. Carefully consider the range of data you plan to hash -- using the first 4000 characters is the obvious choice, but may not be the best choice for your data.

In any event, because of what a hash function is, even if the inputs are 8000 bytes or less, the only way to ensure 100% correctness in the results is to compare the base values at some point (read: not necessarily first). Period.

The business will dictate whether or not 100% accuracy is required. This will tell you that either (a) comparing the base values is required, or (b) you should consider not comparing the base values -- how much accuracy should be traded off for performance.

While hash collisions are possible in a unique input set, they are infinitesimally rare, regardless of the algorithm chosen. The whole idea of using a hash value in this scenario is to efficiently narrow down the join results to a more manageable set, not to necessarily arrive at the final set of results immediately. Again, for 100% accuracy, this cannot be the final step in the process. This scenario isn't using hashing for the purpose of cryptography, so an algorithm such as MD5 will work fine.

It would be extremely hard for me to justify moving up to a SHA-x algorithm for "accuracy" purposes because if the business is going to freak out about the miniscule collision possibilities of MD5, chances are they're also going to freak out that the SHA-x algorithms aren't perfect either. They either have to come to terms with the slight inaccuracy, or mandate that the query be 100% accurate and live with the associated technical implications. I suppose if the CEO sleeps better at night knowing you used SHA-x instead of MD5, well, fine; it still doesn't mean much from a technical point of view in this case.

Speaking of performance, if the tables are read-mostly and the join result is needed frequently, consider implementing an indexed view to eliminate the need to compute the entire join every time it's requested. Of course you trade off storage for that, but it may be well worth it for the performance improvement, particularly if 100% accuracy is required.

For further reading on indexing long string values, I published an article that walks through an example of how to do this for a single table, and presents things to consider when attempting the full scenario in this question.

share|improve this answer
    
Thanks Jon. The requirements tolerates no collision. So I think SHA1 is a safer option. We thought about defining index, but it's not possible. Because the columns used for joining are of Nvarchar(max). Even if the size was defined(e.g.: Nvarchar(4000), I don't think defining index on such a long column was not acceptable by SQL Server. I would double check though. –  Nazila Beikpour Feb 25 '13 at 10:11
4  
@Nazila: As my answer says, in order to satisfy 100% correctness in the comparisons, you cannot only use the hash value to compare. Therefore, the algorithm you use to generate the hash is irrelevant. It is not possible to completely prevent duplicate hash values. –  Jon Seigel Feb 25 '13 at 14:15
    
Well, I was hoping not to have collision on SHA1 (for example based on this link: en.wikipedia.org/wiki/SHA-1 en.wikipedia.org ). However now that we can not rely on that, it means we can't use any hash value comparison. –  Nazila Beikpour Feb 26 '13 at 1:09
3  
@Nazila: You can still use a hash -- there's nothing wrong with that approach; in fact, it's a very good idea -- it's just that to ensure 100% correctness, the base values also have to be compared. You don't have to create an index that includes the base values for the hash comparison to be beneficial. –  Jon Seigel Feb 26 '13 at 1:59
4  
@NazilaBeikpour Just for (even more) emphasis, your strategy should check the hash value first and only then proceed to check the whole string where the hash value matched. I agree with Jon that MD5 looks like a good choice here. Great answer by the way, Jon. –  Paul White Feb 26 '13 at 4:26
show 3 more comments

MD5 should be fine and the output can be stored in a binary (16). The probability of a collision (see birthday paradox) is still very low, even with a large physical sample size. The output of SHA-1 takes 20 bytes and the output of SHA-256 takes 32 bytes. Unless you have such a large number of records that your birthday collision probability becomes significant (physically impossible or at least impractical with current hardware technologies) it will probably be OK.

share|improve this answer
add comment

I would go with SHA-1 it is the better one of the available algorithms and has the least collision expectency out of all of them (2^51 compared to MD5 which is 2^20.96). MD5 has also been proven to be vulnerable to collisions in certain scenarios.

Sources:

http://en.wikipedia.org/wiki/SHA-1 http://en.wikipedia.org/wiki/Comparison_of_cryptographic_hash_functions#Cryptanalysis http://en.wikipedia.org/wiki/MD5

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.