
The table in the link below is nice, it describes the number of bits you need in a hash to keep a low probability of collision given the number of entries you plan to scale to. The 50% chance of one collision of CRC32, or any 32-bit hash algorithm, happens at 77K items (assuming it is completely uniformly distributed), so you need to go well over 32 bits to avoid collisions on 12 million or more items (as is obvious by the reason this thread started). 64-bit gives a 1% chance of collision at 600 million records, which may or may not be acceptable for cdash.<div>

<br></div><div>The reason 77K is so much less than the total space of 2^32 possible values relates to the "birthday paradox" that probability professors love to explain.<br><div><br></div><div><a href="http://en.wikipedia.org/wiki/Birthday_problem#Probability_table">http://en.wikipedia.org/wiki/Birthday_problem#Probability_table</a></div>

<div><br></div><div>Jeff<br><br><div class="gmail_quote">On Thu, Sep 3, 2009 at 9:41 AM, David Cole <span dir="ltr"><<a href="mailto:david.cole@kitware.com">david.cole@kitware.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

Julien's not only worried about the speed of the SQL query. He's also (and probably more) worried about the speed of computing the hash on large input data (test output ranges from a few bytes up to several megabytes depending on the test...)<br>


<br><div>For every test.xml file submitted that contains hundreds (or even thousands) of tests, we have to compute the hash on the test output, look it up to see if it's already in the db and then insert it if it's not.<br>


<div><br></div><div>Computing the hash on the test output is the dominant thing to worry about at test submission processing time.</div><div><div></div><div class="h5"><div><br></div><div><br><div class="gmail_quote">On Thu, Sep 3, 2009 at 9:35 AM, Eric Noulard <span dir="ltr"><<a href="mailto:eric.noulard@gmail.com" target="_blank">eric.noulard@gmail.com</a>></span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">2009/9/3 Amitha Perera <<a href="mailto:amitha.perera@kitware.com" target="_blank">amitha.perera@kitware.com</a>>:<br>


<div>> On Thu, Sep 3, 2009 at 8:43 AM, Julien Jomier<<a href="mailto:julien.jomier@kitware.com" target="_blank">julien.jomier@kitware.com</a>> wrote:<br>

>> Sorry that's what I meant: could we find a hashing algorithm which return<br>

>> value fits in one integer?. Also, what are the complexity of the different<br>

>> hashing algorithms? in another word, which one will be fast enough with the<br>

>> minimal chance of collisions?<br>

><br>

> I'm pretty sure the SHA-1 and MD5 algorithms will prove to be fast<br>

> enough for your needs. And I'm sure there are implementations of them<br>

> in any language you want.<br>

><br>

> Also, I suspect that<br>

>  SELECT * WHERE CRC=myCRC;<br>

> will run pretty much just as fast as<br>

>  SELECT * WHERE HASH_INT1=myInt1 AND HASH_INT2=myInt2 ... AND HASH_INT4=myInt4;<br>

><br>

> It's been a while since I did any serious SQL, but I think a SQL CHAR<br>

> can represent any value between 0 and 255, so it may be just as easy<br>

> to represent the hash as a CHAR(16) or what ever.  And again, I'm<br>

> pretty sure the SELECT statement would execute without any noticeable<br>

> difference in speed.<br>

<br>

</div>Julien seems to think<br>

that string comparison was slow (compared to int comparison)<br>

<div>  >> "we will need to do a string matching in SQL and I'd like to<br>

avoid this if we can for speed reasons"<br>

<br>

</div>However since as far as I understand you don't need cryptographic hash function<br>

you may look into some non-cryptographic hash function<br>

that has been designed to be fast, like that one<br>

<a href="http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash" target="_blank">http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash</a><br>

<br>

Seems to be used with MySQL too:<br>

<a href="http://www.xaprb.com/blog/2008/03/09/a-very-fast-fnv-hash-function-for-mysql/" target="_blank">http://www.xaprb.com/blog/2008/03/09/a-very-fast-fnv-hash-function-for-mysql/</a><br>

<a href="http://www.radwin.org/michael/blog/2007/03/mysql_user_defined_functio.html" target="_blank">http://www.radwin.org/michael/blog/2007/03/mysql_user_defined_functio.html</a><br>

<br>

Note that FNV may not be the sole choice in this area.<br>

<div>--<br>

Erk<br>

Membre de l'April - Ť promouvoir et défendre le logiciel libre ť -<br>

<a href="http://www.april.org" target="_blank">http://www.april.org</a><br>

_______________________________________________<br>

</div><div><div></div><div>Cdash mailing list<br>

<a href="mailto:Cdash@public.kitware.com" target="_blank">Cdash@public.kitware.com</a><br>

<a href="http://public.kitware.com/cgi-bin/mailman/listinfo/cdash" target="_blank">http://public.kitware.com/cgi-bin/mailman/listinfo/cdash</a><br>

</div></div></blockquote></div><br></div></div></div></div>

<br>_______________________________________________<br>

Cdash mailing list<br>

<a href="mailto:Cdash@public.kitware.com">Cdash@public.kitware.com</a><br>

<a href="http://public.kitware.com/cgi-bin/mailman/listinfo/cdash" target="_blank">http://public.kitware.com/cgi-bin/mailman/listinfo/cdash</a><br>

<br></blockquote></div><br><br clear="all"><br>-- <br>Jeff Baumes, Ph.D.<br>R&D Engineer, Kitware Inc.<br>(518) 881-4932<br><a href="mailto:jeff.baumes@kitware.com">jeff.baumes@kitware.com</a><br>

</div></div>