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><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">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">amitha.perera@kitware.com</a>>:<br>
<div class="im">> On Thu, Sep 3, 2009 at 8:43 AM, Julien Jomier<<a href="mailto:julien.jomier@kitware.com">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 class="im">  >> "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 class="im">--<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 class="h5">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>
</div></div></blockquote></div><br></div></div>