4

I'd like to store URLs in a database column, and enforce a constraint that values must be unique. Unfortunately, MySQL has a limit on the length of index keys which means that only the first X characters of the URL gets checked for uniqueness. Thus, I've run into false positives where two different URLs triggered a constraint integration violation because the first X characters just-so-happened to be identical.

Is there a way to enforce uniqueness on a VARCHAR column without any limit on its length?

Is it possible to, say, create a non-UNIQUE index over the first X characters and then have a trigger block INSERTs if the remaining characters are identical?

1

5 Answers 5

5

We keep giving you answers that do not directly answer the question, because that is how we solve this problem. An index of unlimited length is impractical and inefficient, but a unique hash provides a solution that sufficient to the task because of the astronomically low likelihood of a meaningful collision.

Similar to the other offered solutions, my standard approach does not check for duplicates up front -- it is optimistic in that sense: it relies on constraint checking by the database, with the assumption that most inserts are not duplicates, so there's no point in wasting time trying to determine if they are.

Working, tested example (5.7.16, backwards compatible to 5.6; previous versions do not have a built-in TO_BASE64() function):

CREATE TABLE web_page (
  id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  url LONGTEXT NOT NULL,
  url_hash CHAR(24) COLLATE ascii_bin,
  PRIMARY KEY(id),
  UNIQUE KEY(url_hash),
  KEY(url(16))
)ENGINE=InnoDB DEFAULT CHARSET=utf8 ROW_FORMAT=COMPRESSED;

Note that I am storing the base64 version of the hash. This is a 4:3 size tradeoff compared to storing it in binary form because it makes the table contents and the error message human readable, and the inefficiency is partially offset by the table compression. The hash column has a unique constraint. The data type is CHAR, not VARCHAR, since this eliminates the byte needed to store the size -- the hash is always a fixed size. The column uses the ascii character set with ascii_bin (case-sensitive) collation, keeping the column and the unique index as small as practical.

The url_hash is set by a trigger, below, but the trigger does not check for a collision -- there is no need to check, because of the unique constraint on url_hash. The database will block a duplicate insert.

Note that url_hash should have been declared NOT NULL but MySQL incorrectly enforces this before the BEFORE INSERT trigger fires, instead of after, so we are limited by that. The trigger does prevent it from being null.

The url column has a prefix index length of 16, which was chosen arbitrarily. This isn't a unique constraint, just an index for lookups, and it is probably shorter than you might want it to be, but its length has no operational impact on the problem we are solving, here.

Here's the trigger to set the url_hash. We don't need to include this value in an INSERT statement when we insert rows.

DELIMITER $$
DROP TRIGGER IF EXISTS web_page_bi $$
CREATE TRIGGER web_page_bi BEFORE INSERT ON web_page FOR EACH ROW
BEGIN
  SET NEW.url_hash = TO_BASE64(UNHEX(MD5(NEW.url)));
END $$
DELIMITER ;

You need a trigger on update also, either to block updates if the table is supposed to be immutable, or to update the hash if the URL changes. We also need this trigger to ensure that the url_hash column can't be inappropriately set to NULL since the limitation in MySQL doesn't allow us to actually declare it that way, as we should.

Now, to test.

mysql> INSERT INTO web_page (url) VALUES ('http://example.com/');
Query OK, 1 row affected (0.00 sec)

mysql> SELECT * FROM web_page;
+----+---------------------+--------------------------+
| id | url                 | url_hash                 |
+----+---------------------+--------------------------+
|  1 | http://example.com/ | pr8XV//wV/JmtpffnPF2/Q== |
+----+---------------------+--------------------------+
1 row in set (0.00 sec)

So far, so good. Now, a different URL:

mysql> INSERT INTO web_page (url) VALUES ('http://example.net/');
Query OK, 1 row affected (0.00 sec)

mysql> SELECT * FROM web_page;
+----+---------------------+--------------------------+
| id | url                 | url_hash                 |
+----+---------------------+--------------------------+
|  1 | http://example.com/ | pr8XV//wV/JmtpffnPF2/Q== |
|  2 | http://example.net/ | ZVk/eLfvBI6tHN0Luj3NnQ== |
+----+---------------------+--------------------------+
2 rows in set (0.00 sec)

Still works. Now, a duplicate.

mysql> INSERT INTO web_page (url) VALUES ('http://example.com/');
ERROR 1062 (23000): Duplicate entry 'pr8XV//wV/JmtpffnPF2/Q==' for key 'url_hash'

Perfect. If you want an even lower risk of hash collisions than MD5 provides, use a SHA variant, increasing the length of data_hash to CHAR_LENGTH(TO_BASE64(UNHEX( /* your hash function */ ))) to accommodate the values generated by the hash algorithm in use.

3
  • Your answer is excellent. It covers almost all my concerns. I am going to up-vote it, but can't accept it because it makes the false assumption that MD5 collisions imply the URLs are equal. Hash equality does not imply full-value equality. a_vlad gets this right.
    – Gili
    Dec 11, 2016 at 0:50
  • 1
    I would suggest that, strictly speaking, it does not make that assumption... at least not explicitly -- the error thrown is not that there is a URL duplication but rather that there is a hash collision, Duplicate entry ... for key 'url_hash'. The implicit assumption, though, is admittedly that the likelihood of a collision is so small that it almost certainly can be disregarded, and that there is an extremely high probability that a hash collision means a duplicate URL. Dec 11, 2016 at 4:13
  • Unlikely, sure. Does it happen in real-life? Yes, it does. Better safe than sorry :) As you can see from a_vlad's answer, running a follow-up comparison on the full URL is not hard.
    – Gili
    Dec 11, 2016 at 4:15
4

Sample table:

CREATE TABLE `tURL` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `url` text,
  `url_hash` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `url_hash` (`url_hash`)
) ENGINE=InnoDB AUTO_INCREMENT=10 DEFAULT CHARSET=latin1

Trigger for INSERT

CREATE DEFINER=`root`@`localhost` TRIGGER `test_db`.`tr_uniqURL_ins`
BEFORE INSERT ON 
test_db.tURL
FOR EACH ROW BEGIN

SET new.url_hash = SHA2(new.URL,512);

IF EXISTS (SELECT id FROM tURL WHERE url_hash = new.url_hash AND URL LIKE new.URL) THEN

    set @msg = 'Trigger Error - duplicate detected ';
    signal sqlstate '45000' set message_text = @msg;

END IF;


END

Trigger for UPDATE

CREATE DEFINER=`root`@`localhost` TRIGGER `test_db`.`tr_uniqURL_upd`
BEFORE UPDATE ON 
test_db.tURL
FOR EACH ROW BEGIN

SET new.url_hash = SHA2(new.URL,512);

IF EXISTS (SELECT id FROM tURL WHERE url_hash = new.url_hash AND  URL LIKE new.URL) THEN

    set @msg = 'Trigger Error - duplicate detected ';
    signal sqlstate '45000' set message_text = @msg;

END IF;


END

Add:

Because Author again and again not trust to community :) let try to explain - why all suggest the same:

variant 1 - as author want:

substring + compare all other speed depend from substring, for example VARCHAR(200), it mean for huge database with long URL it on second step can compare thousands and thousands values

variant 2 - using HASH any hash - will make hash from full URL, so 2nd step will work only for database where hash will have duplicates - trillions of rows by other words

for 99,99999% of cases hash will return single line after first step - lookup over short column

2
  • Thanks for the edit. I've upvoted your answer. I still believe that you need to profile against real data when choosing variants but I appreciate you clarifying the difference.
    – Gili
    Dec 11, 2016 at 0:49
  • sure - I always vote for real test
    – a_vlad
    Dec 11, 2016 at 1:13
1

Answering my own question (since all other answers used a hash column or placed a limit on the column length):

DROP TABLE IF EXISTS url;
CREATE TABLE url
(
    id BIGINT AUTO_INCREMENT PRIMARY KEY,
    value VARCHAR(2048) NOT NULL
);

CREATE INDEX url_value_idnex ON url (value (191));

DROP TRIGGER IF EXISTS url_prevent_duplicates;
DELIMITER //
CREATE TRIGGER url_prevent_duplicates
BEFORE INSERT ON url
FOR EACH ROW
BEGIN
    DECLARE matches INT;
    DECLARE msg VARCHAR(128);
    SET matches = (SELECT count(*)
        FROM url
        WHERE value = NEW.value);

    IF matches <> 0 THEN
        -- SIGNAL message limited to 128 characters: http://stackoverflow.com/a/31672877/14731
        SET msg = (SELECT CONCAT('Duplicate value: ', SUBSTRING(NEW.value, 1, 128 - CHAR_LENGTH('duplicate value: '))));
        SIGNAL SQLSTATE '23000' SET MESSAGE_TEXT = msg;
    END IF;
END//
DELIMITER ;

Recap:

  1. Create a non-UNIQUE index on the column containing the URL ("value" in the above code)
  2. Use the longest-possible index key (191 in my case, because I am using utf8mb4 encoding)
  3. Add a BEFORE INSERT trigger that signals an error if the URL already exists.
  4. When the trigger uses SELECT to check whether the URL already exists, it uses the index to narrow the search space. Then, for any index collisions, it compares the full URL and if they are identical it SIGNALs an exception.

I want to acknowledge that Michael - sqlbot's and a_vlad's answers are excellent, but I wanted to try a solution without a hash column because I suspect that, in my case, the extra column is overkill or might actually reduce performance (more on this below).

My understanding of the two options is as follows:

Without a hash column

  1. We hash the URL using the index's implicit hash (191 characters-long in the above code).
  2. For any index collisions, compare value in full.

With a hash column

Using Michael - sqlbot's answer as reference...

  1. We begin by hashing the URL using the MD5 algorithm.
  2. We hash #1 using the index's implicit hash (I am referring to the fact that url_hash is indexed itself)
  3. For any index collisions, compare the url_hash values in full.
  4. For any matching url_hash, compare the url values in full.

Comparison

The downside of my approach is that the index hash is not calculated over the full URL, hence it is going to result in more collisions (and full URL comparisons) than the MD5 approach will.

The downside of the MD5 approach is that it requires two extra steps: the calculation of an MD5 hash and an extra SELECT to compare MD5 values.

So, which is better?

How likely are we to get index collisions with my approach? The answer is dependent on the actual dataset, so we can't answer in absolute terms. This is what profilers are for. I recommend people test both approaches against real data and make their decisions accordingly.

For example, my specific use-case involves associating web pages with HTTP referrers. There are at most 300 referrers per HTML page, which means that the probability of collisions is almost zero. Even if the shorter index hash leads to more collisions, the number of full-URL comparisons is guaranteed to remain low.

5
  • How you search for 191-4000 characters? Based on Your idea - long URL, 191 give a lot of duplicates, so over this number of rows it will be full scan, hash or give You 1 row or max 2 for full compare. Let test it, sure You will see difference (this is not a "theory") on not a huge data sizes
    – a_vlad
    Dec 11, 2016 at 1:08
  • @a_vlad Yes, if the first 191 characters match with index the trigger SELECT will compare the full URL of collisions without index.
    – Gili
    Dec 11, 2016 at 1:09
  • and this is VERY bad, it is Your performance killer. if You worry about hash duplicates - this is kill Your system :)
    – a_vlad
    Dec 11, 2016 at 1:10
  • @a_vlad read the end of my answer. The question is how often HTTP referrers are identical after 191 characters, per page (which only has 300 referrers max). It's not as bad as you think.
    – Gili
    Dec 11, 2016 at 1:14
  • Bad and Good - is very very sensible .. today it 300, tomorrow You can remember about "NO ANY LIMITS" we just suggest You way for real unlimited, plus in case of MD5 it will 32Bit column, which is shorter than 191
    – a_vlad
    Dec 11, 2016 at 1:16
1

Pseudo code:

if md5 matches then
    compare entire text of url

Requirements:

INDEX(md5) -- not UNIQUE
md5 BINARY(16) NON NULL  -- and use UNHEX(MD5(url)) for assigning

(Adjust as needed if picking SHA1, etc.)

I would build the code in the app first; then see if it is reasonable to convert to a Stored Procedure.

Aside... If you are expecting 'long' TEXT values, then consider changing the column to BLOB and using compression/uncompression in the client (not using MySQL's functions). The compression can be done before using UNHEX(MD5(...)), so it is consistent with the recommendation above.

Compression in the client decreases the network traffic, especially useful if client and server are on different machines. Compression costs client cpu cycles, relieving server cycles for other things; especially beneficial if you have multiple clients. And, of course, disk space is saved -- a factor of 3 most most types of text; perhaps more like 4 for urls because of the common prefixes.

Two different urls will have two different md5s, almost certainly. (Close enough for all practical purposes.) A prefix index (not UNIQUE!) will take more disk space and will require the double check. If you don't want to trust md5, then go ahead and do the prefixing.

WHERE md5 = '$md5' AND url = '$url' with INDEX(md5) will rarely touch more than one row -- not a table scan. A non-unique INDEX(md5) lets you efficiently find all the rows that match a given md5 value. Usually that will be only 1 row, not 100. Even if there are a billion rows in the table, a BTree index is very efficient at finding a unique, or nearly-unique item in it. Wikipedia has a good discussion of BTrees.

0
-1

If 3072 bytes will be enough, you can enable innodb_large_prefix, or upgrade to a recent version of 5.7 to have it by default:

http://dev.mysql.com/doc/refman/5.7/en/innodb-parameters.html#sysvar_innodb_large_prefix

For a URL, it will help to use ASCII as the character set if the characters will be truly limited to that set. One byte per char.

2
  • 2
    I know of innodb_large_prefix but I asking for an algorithm that has no limits whatsoever on the length of varchar.
    – Gili
    Dec 9, 2016 at 15:00
  • Right, I qualified my answer so that it could be helpful to others who land on this question from search and have the indicated constraint. For your purposes, you should ignore this answer. (This answer is the easiest to implement for those it suits). Dec 30, 2016 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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