Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!weretis.net!feeder1.news.weretis.net!feeder.erje.net!tudelft.nl!txtfeed1.tudelft.nl!feeder1.cambriumusenet.nl!feed.tweaknews.nl!216.196.110.149.MISMATCH!Xl.tags.giganews.com!border2.nntp.ams.giganews.com!nntp.giganews.com!local2.nntp.ams.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 10 Jun 2011 04:51:25 -0500
Date: Fri, 10 Jun 2011 10:51:25 +0100
From: bugbear <bugbear@trim_papermule.co.uk_trim>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.19) Gecko/20110429 Fedora/2.0.14-1.fc13 SeaMonkey/2.0.14
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer,comp.programming,comp.lang.java.databases
Subject: Re: Storing large strings for future equality checks
References: <iso8cm$a80$1@speranza.aioe.org> <g6evu6t9847r0g5u2nj17aj61gsktspb93@4ax.com> <isre5k32k44@news3.newsguy.com>
In-Reply-To: <isre5k32k44@news3.newsguy.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <z6qdnRH0SMqAdGzQnZ2dnUVZ8n-dnZ2d@brightview.co.uk>
Lines: 36
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-NhY6b4ne+tkNsET5zLxZKFRGyFIjNsr5O8u37mLPaLUNuaQ6ztus19johIKrXUHldV5DLP1QeBMSgZj!qsArarit1XHU1z5wkiZDKhOJq3hd7fnKizQ4MnxXkhrfFFmsgPl0/qBq65L6aWuFpVtDCZN7LsrG!CMCVSbagUb5hjP7EJYKpIgQGKg==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3006
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:5174 comp.programming:453 comp.lang.java.databases:475

Michael Wojcik wrote:
> Gene Wirchenko wrote:
>> On Wed, 08 Jun 2011 22:05:30 +0530, Abu Yahya<abu_yahya@invalid.com>
>> wrote:
>>
>>> I considered using an SHA-512 hash of these strings and storing them in
>>> the database. However, while these will save on storage space, it will
>>> take time to do the hashing before comparing an incoming string. So I'm
>>> still wasting time. (Collisions due to hashing will not be a problem,
>>> since an occasional false positive will not be fatal for my application).
>>
>>       What does "occasional" mean?
>
> Assuming the application doesn't accidentally run afoul of a
> hitherto-unknown flaw in SHA-512 - a tremendously unlikely event - it
> means "once in every N/2**256 uses", where N is the current number of
> hashes in the database. (2**256 because of the Birthday Paradox; we're
> interested in the probability of two arbitrary colliding pre-images.)
>
> Or, in other words, "probably not before the heat death of the
> universe". (Or false vacuum decay, zombie apocalypse, Rapture, etc.)
>
> Worrying about the time to hash the string is silly. It's linear in
> the length of the string, so it's roughly equivalent to the time taken
> to do a few comparisons (where "a few" depends on how long, on
> average, the matching prefix of the new string and the candidates is).
>
> However, as various others have pointed out, this is premature
> optimization. There's no reason to use any design other than the
> obvious until a problem is demonstrated.

I any case, it's plausible that the DB is using "something"
to index the strings, in other words the string search in the DB
already has some-kind-of optimisation.

   BugBear