Subject: BUG #3965: UNIQUE constraint fails on long column values

From: "Juho Saarikko" <[email-masked]>
Date: Mon, 18 Feb 2008 11:30:23 GMT

The following bug has been logged online:

Bug reference:      3965
Logged by:          Juho Saarikko
Email address:      [email-masked]
PostgreSQL version: 8.3RC2
Operating system:   Linux
Description:        UNIQUE constraint fails on long column values
Details: 

It is impossible to add an UNIQUE constraint which includes columns with
long values. The reason seems to be that UNIQUE is implemented using b-tree
index, which cannot handle values longer than 8191 bytes.

While I didn't test, I'd imagine that this would also mean that any attempt
to insert such values to an already unique column would fail.

It is propably impossible to fix this in a simple way, since it is an
inherent result of the underlying storage specification rather than a mere
programming error, so the documentation needs to be updated to warn about
this.

I suggest implementing unique hash indexes and automatically creating one
(and turning the b-tree index into a non-unique one) when a large value is
inserted to fix this. Alternatively, fix b-trees so they can handle large
values; however, a hash index should be far more efficient for this specific
case, since the size of a hash is independent of pre-hash data size.

Exact error message:
******************
kuvat=# alter table pictures ADD constraint pic_unique unique (safe);
NOTICE:  00000: ALTER TABLE / ADD UNIQUE will create implicit index
"pic_unique" for table "pictures"
LOCATION:  DefineIndex, indexcmds.c:434
ERROR:  54000: index row requires 47148 bytes, maximum size is 8191
LOCATION:  index_form_tuple, indextuple.c:170

---

From: Gregory Stark <[email-masked]>
Date: Mon, 18 Feb 2008 15:29:44 +0000

> programming error, so the documentation needs to be updated to warn about

Point taken.

> case, since the size of a hash is independent of pre-hash data size.

With expression indexes you can do this yourself with something like 
 CREATE INDEX pk_hash on tab ((hashtext(safe)))

We can't do this automatically since it wouldn't enforce the UNIQUE
constraint. Conceivably we could actually do something about that but there's
nothing like that now.

We have hash indexes too but in practice a btree over a hash seems to work
just as well or better.

-- 
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com
  Ask me about EnterpriseDB's PostGIS support!

---

From: Bruce Momjian <[email-masked]>
Date: Mon, 18 Feb 2008 17:12:28 -0500 (EST)

> to insert such values to an already unique column would fail.

Works here in 8.3:
	
	test=> create table test (x text unique);
	NOTICE:  CREATE TABLE / UNIQUE will create implicit index "test_x_key" for table "test"
	CREATE TABLE
	test=> insert into test values (repeat('a', 50000));
	INSERT 0 1

Even this works:

	test=> insert into test values (repeat('a', 50000) || 'b');

I believe the index only indexes 8192 bytes but checks the heap for
longer values to check the full length.

-- 
  Bruce Momjian  <[email-masked]>        http://momjian.us
  EnterpriseDB                             http://postgres.enterprisedb.com

  + If your life is a hard drive, Christ can be your backup. +

---

From: Tom Lane <[email-masked]>
Date: Mon, 18 Feb 2008 17:25:46 -0500

> 	test=> insert into test values (repeat('a', 50000));

That test only works because it's eminently compressible.

The short answer to this bug report is that we're not very concerned
about fixing this because there is seldom a good reason to have an
index (unique or not) on fields that can get so wide.  As was already
noted, if you do need a uniqueness check you can easily make a 99.9999%
solution by indexing the md5 hash (or some similar digest) of the
column.  It doesn't really seem worthwhile to expend development work
on something that would benefit so few people.

			regards, tom lane

---

From: Juho Saarikko <[email-masked]>
Date: Tue, 19 Feb 2008 01:21:11 +0200

> on something that would benefit so few people.
But the documentation needs to be updated to mention this nonetheless. 
It is a nasty surprise if it hits unawares.

Besides, it's not such an impossible scenario. I encountered this bug 
when making an Usenet image archival system. Since the same images tend 
to be reposted a lot, it makes sense to store them only once, and simply 
reference the stored image from each context it was posted in. Currently 
my program does the uniqueness constraining by itself; I was examining 
having the database enforce it when I ran into this issue.

Such applications are not exactly rare: bayimg, img.google.com, etc. and 
of course the innumerable Usenet archival sites could all conceivably 
want to do something like this. So could any application which monitors 
potentially repeating phenomena, for that matter. After all, saving a 
single state of the system only once not only reduces the amount of data 
stored, but could also help in actual analysis of it, since it becomes 
trivial to recognize most and least often recurring states.

---

From: Kris Jurka <[email-masked]>
Date: Mon, 18 Feb 2008 19:26:14 -0500 (EST)

> 	test=> insert into test values (repeat('a', 50000) || 'b');

This only works because it gets toasted before being put in the index. 
Since you've selected something real compressible, you can fit 50k chars 
into it.

Kris Jurka

---

From: "Heikki Linnakangas" <[email-masked]>
Date: Wed, 20 Feb 2008 08:54:50 +0000

> case, since the size of a hash is independent of pre-hash data size.

The current implementation of hash indexes actually store the whole key, 
in addition to the hash, so the size of the hash index is not 
independent of the key size. There has been some discussion on revamping 
the hash index implementation, and changing that among other things, but 
don't hold your breath.

As others have pointed out, CREATE UNIQUE INDEX i ON ((md5(column)) is a 
pretty good work-around.

-- 
   Heikki Linnakangas

---

From: Gregory Stark <[email-masked]>
Date: Wed, 20 Feb 2008 09:26:35 +0000

"Heikki Linnakangas" <[email-masked]> writes:

> As others have pointed out, CREATE UNIQUE INDEX i ON ((md5(column)) is a pretty
> good work-around.

Unless you need cryptographic security I would not suggest using MD5. MD5 is
intentionally designed to take a substantial amount of CPU resources to
calculate.

Postgres's internal hash method is exposed for most data types as hashtext()
hashfloat8(), hashint4(), etc. These functions were chosen for their
lightweight design.

Cryptographic security is important only if you're concerned with people being
able to intentionally create collisions. In this scenario that's probably not
a top threat. Conceivably someone could create a denial-of-service attack
slowing down your server by causing your indexes to become unbalanced. But it
would be fairly challenging to engineer.

-- 
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com
  Ask me about EnterpriseDB's RemoteDBA services!

---

From: Francisco Olarte Sanz <[email-masked]>
Date: Wed, 20 Feb 2008 12:21:03 +0100

On Wednesday 20 February 2008, Gregory Stark wrote:

> Unless you need cryptographic security I would not suggest using MD5. MD5
> is intentionally designed to take a substantial amount of CPU resources to
> calculate.

I thought it was the exact opposite, quoting from RFC1321:

The MD5 algorithm is designed to be quite fast on 32-bit machines. In
   addition, the MD5 algorithm does not require any large substitution
   tables; the algorithm can be coded quite compactly.

F.O.S.

---

From: "Heikki Linnakangas" <[email-masked]>
Date: Wed, 20 Feb 2008 11:25:53 +0000

> would be fairly challenging to engineer.

Return type of hash* functions is just 32 bits. I wonder if that's wide 
enough to avoid accidental collisions? Depends on the application of 
course...

---

From: Gregory Stark <[email-masked]>
Date: Wed, 20 Feb 2008 11:51:47 +0000

"Heikki Linnakangas" <[email-masked]> writes:

> Return type of hash* functions is just 32 bits. I wonder if that's wide enough
> to avoid accidental collisions? Depends on the application of course...

Oh, I missed that you were suggesting a UNIQUE index. That seems unsafe to me
even for md5 or its ilk. But that would depend on the application too.

---

From: Michael Fuhr <[email-masked]>
Date: Wed, 20 Feb 2008 07:41:54 -0700

> I thought it was the exact opposite, quoting from RFC1321:

And if you *do* need cryptographic security then don't use MD5, and
consider using SHA-256 instead of SHA-1.  See RFC 4270 for discussion.

ftp://ftp.rfc-editor.org/in-notes/rfc4270.txt

-- 
Michael Fuhr

---

From: Tom Lane <[email-masked]>
Date: Wed, 20 Feb 2008 11:04:45 -0500

> even for md5 or its ilk. But that would depend on the application too.

md5 is designed to be a signature, remember?  If there weren't a very
high probability of its output being different for different inputs,
it wouldn't be good for anything.

The built-in hash functions definitely cannot be relied on to not have
collisions, though.

			regards, tom lane

---

From: Gregory Stark <[email-masked]>
Date: Thu, 21 Feb 2008 11:07:58 +0000

>> I thought it was the exact opposite, quoting from RFC1321:

Hm, ok, strike "intentionally". Nonetheless MD5 is quite computationally
intensive compared to quick hashes like the ones Postgres uses or CRC hashes
(which we ought to have functions for, but we don't seem to). SHA-1 is even
more computationally intensive and SHA-256 far more again.

For purposes of speeding up access a simple hash with the possibility of a few
collisions is normally fine. You add an additional clause to recheck the
original constraint.

For purposes of enforcing uniqueness I would be leery of depending on any
hash. The decision would depend on the application and the consequences of a
spurious error. The chances are slim but it's not impossible.

> ftp://ftp.rfc-editor.org/in-notes/rfc4270.txt

One of the factors in deciding between cryptographic algorithms is the
longevity required. MD5 has not been cracked but some suspicious weaknesses
have been discovered which might lead to a crack sometime in the future where
an attacker might be able to construct new plaintexts with identical hashes.
If you just need something secure for session keys then that's not going to be
a concern. If you need to distinguish user-provided documents from other
user-provided documents you're keeping for decades then it is.

-- 
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com
  Ask me about EnterpriseDB's 24x7 Postgres support!

---

From: Bruce Momjian <[email-masked]>
Date: Wed, 5 Mar 2008 11:20:32 -0500 (EST)

Does anyone think it is a good idea to document that our indexes cannot
index arbirarily-long strings?  I see nothing in the documentation now
about it.

---------------------------------------------------------------------------

Juho Saarikko wrote:
> ---------------------------(end of broadcast)---------------------------
> TIP 5: don't forget to increase your free space map settings

---

From: Phil Frost <[email-masked]>
Date: Wed, 5 Mar 2008 11:32:57 -0500

> index arbirarily-long strings?  I see nothing in the documentation now

+1

I never even knew. I'd be especially interested to hear about  
details, like how long strings can be until they are not guaranteed  
unique.

---

From: Bruce Momjian <[email-masked]>
Date: Wed, 5 Mar 2008 11:56:44 -0500 (EST)

> details, like how long strings can be until they are not guaranteed  

Part of the problem is we don't know the length --- it is the compressed
length that is limited, I think to 8k.

---

From: Tom Lane <[email-masked]>
Date: Wed, 05 Mar 2008 12:09:44 -0500

> length that is limited, I think to 8k.

That's a problem, and the length limit is different for different index
types.  So you're really not going to be able to say anything very
specific.  Another problem is where would you put the information?

			regards, tom lane

---

From: "Gurjeet Singh" <[email-masked]>
Date: Thu, 6 Mar 2008 00:00:33 +0530

> specific.  Another problem is where would you put the information?

In 'CREATE INDEX'  docs...

http://www.postgresql.org/docs/8.3/interactive/sql-createindex.html

Along with the following statement:

method: The name of the index method to be used. Choices are btree, hash,
gist, and gin. The default method is btree.

Best regards,
-- 
gurjeet[.singh]@EnterpriseDB.com
singh.gurjeet@{ gmail | hotmail | indiatimes | yahoo }.com

17° 29' 34.37"N,  78° 30' 59.76"E - Hyderabad *
18° 32' 57.25"N,  73° 56' 25.42"E - Pune
37° 47' 19.72"N, 122° 24' 1.69" W - San Francisco

http://gurjeet.frihost.net

Mail sent from my BlackLaptop device

---

From: Bruce Momjian <[email-masked]>
Date: Wed, 5 Mar 2008 13:36:26 -0500 (EST)

> gist, and gin. The default method is btree.

We are trying to figure out how to specify the index-type-specific length
limits, not the index types themselves.