Como evitar VARCHAR duplicado sem um limite de chave?

Continuamos dando respostas que não respondem diretamente à pergunta, porque é assim que resolvemos esse problema. Um índice de comprimento ilimitado é impraticável e ineficiente, mas um único hash fornece uma solução suficiente para a tarefa devido à probabilidade astronomicamente baixa de uma colisão significativa.

Semelhante às outras soluções oferecidas, minha abordagem padrão não verifica duplicatas antecipadamente - é otimista nesse sentido: ela depende da verificação de restrição pelo banco de dados, com a suposição de que a maioria das inserções não são duplicadas, portanto, não há motivo para perdendo tempo tentando determinar se eles são.

Exemplo testado e funcionando (5.7.16, compatível com versões anteriores de 5.6; as versões anteriores não possuem uma TO_BASE64()função integrada):

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;

Observe que estou armazenando a versão base64 do hash. Essa é uma compensação de tamanho de 4:3 em comparação com o armazenamento em formato binário porque torna o conteúdo da tabela e a mensagem de erro legíveis por humanos, e a ineficiência é parcialmente compensada pela compactação da tabela. A coluna de hash tem uma restrição exclusiva. O tipo de dados é CHAR, não VARCHAR, pois isso elimina o byte necessário para armazenar o tamanho -- o hash é sempre de tamanho fixo. A coluna usa o asciiconjunto de caracteres com ascii_bincollation (com distinção entre maiúsculas e minúsculas), mantendo a coluna e o índice exclusivo tão pequenos quanto possível.

O url_hash é definido por um gatilho, abaixo, mas o gatilho não verifica uma colisão -- não há necessidade de verificar, devido à restrição exclusiva em url_hash. O banco de dados bloqueará uma inserção duplicada.

Observe que url_hash deveria ter sido declarado, NOT NULLmas o MySQL impinge isso incorretamente antes do disparo do BEFORE INSERTgatilho, em vez de depois, então estamos limitados por isso. O gatilho impede que seja nulo.

A coluna url tem um comprimento de índice de prefixo de 16, que foi escolhido arbitrariamente. Esta não é uma restrição única, apenas um índice para pesquisas, e provavelmente é menor do que você gostaria que fosse, mas seu comprimento não tem impacto operacional no problema que estamos resolvendo aqui.

Aqui está o gatilho para definir o url_hash. Não precisamos incluir esse valor em uma INSERTinstrução quando inserimos linhas.

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 ;

Você também precisa de um gatilho na atualização, para bloquear atualizações se a tabela for imutável ou para atualizar o hash se o URL for alterado. Também precisamos desse gatilho para garantir que a coluna url_hash não possa ser configurada de forma inadequada, NULLpois a limitação do MySQL não nos permite declará-la dessa maneira, como deveríamos.

Agora, para testar.

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)

Até agora tudo bem. Agora, um URL diferente:

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)

Ainda funciona. Agora, uma duplicata.

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

Perfeito. Se você deseja um risco ainda menor de colisões de hash do que o MD5 oferece, use uma variante SHA, aumentando o comprimento de data_hashto CHAR_LENGTH(TO_BASE64(UNHEX( /* your hash function */ )))para acomodar os valores gerados pelo algoritmo de hash em uso.

Tabela de amostra:

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

Gatilho para INSERIR

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

Gatilho para ATUALIZAÇÃO

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

Adicionar:

Porque o autor repetidamente não confia na comunidade :) vamos tentar explicar - por que todos sugerem o mesmo:

variante 1 - como o autor deseja:

substring + comparar todas as outras velocidades dependem da substring, por exemplo VARCHAR (200), significa para um banco de dados enorme com URL longo, na segunda etapa pode comparar milhares e milhares de valores

variante 2 - usando HASH qualquer hash - criará hash a partir do URL completo, portanto, a segunda etapa funcionará apenas para o banco de dados em que o hash terá duplicatas - trilhões de linhas por outras palavras

para 99,99999% dos casos, o hash retornará uma única linha após a primeira etapa - pesquisa na coluna curta

Pseudo-código:

if md5 matches then
    compare entire text of url

Requisitos:

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

(Ajuste conforme necessário se escolher SHA1, etc.)

Eu criaria o código no aplicativo primeiro; então veja se é razoável converter para um Procedimento Armazenado.

À parte... Se você está esperando valores 'longos' TEXT, considere alterar a coluna para BLOBe usar compactação/descompactação no cliente (não usando as funções do MySQL). A compactação pode ser feita antes de usar UNHEX(MD5(...)), portanto está de acordo com a recomendação acima.

A compactação no cliente diminui o tráfego de rede, especialmente útil se o cliente e o servidor estiverem em máquinas diferentes. A compactação custa ciclos de cpu do cliente, aliviando os ciclos do servidor para outras coisas; especialmente benéfico se você tiver vários clientes. E, claro, o espaço em disco é economizado -- um fator de 3 na maioria dos tipos de texto; talvez mais como 4 para URLs por causa dos prefixos comuns.

Dois urls diferentes terão dois md5s diferentes, quase certamente. (Próximo o suficiente para todos os fins práticos.) Um índice de prefixo (não ÚNICO!) ocupará mais espaço em disco e exigirá uma verificação dupla. Se você não quiser confiar no md5, vá em frente e faça o prefixo.

WHERE md5 = '$md5' AND url = '$url'com INDEX(md5)raramente tocará em mais de uma linha -- não é uma varredura de tabela. Um não exclusivo INDEX(md5)permite localizar com eficiência todas as linhas que correspondem a um determinado valor md5. Normalmente, será apenas 1 linha, não 100. Mesmo se houver um bilhão de linhas na tabela, um índice BTree é muito eficiente em encontrar um item exclusivo ou quase exclusivo nela. A Wikipedia tem uma boa discussão sobre BTrees.

Respondendo à minha própria pergunta (já que todas as outras respostas usaram uma coluna de hash ou colocaram um limite no comprimento da coluna):

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 ;

Recapitular:

1. Crie um índice não ÚNICO na coluna que contém a URL ("valor" no código acima)
2. Use a chave de índice mais longa possível (191 no meu caso, porque estou usando utf8mb4codificação)
3. Adicione um BEFORE INSERTgatilho que sinalize um erro se o URL já existir.
4. Quando o gatilho usa SELECT para verificar se a URL já existe, ele usa o índice para restringir o espaço de pesquisa. Em seguida, para quaisquer colisões de índice, ele compara o URL completo e, se forem idênticos, sinaliza uma exceção.

Quero reconhecer que as respostas de Michael - sqlbot e a_vlad são excelentes, mas queria tentar uma solução sem uma coluna de hash porque suspeito que, no meu caso, a coluna extra é um exagero ou pode realmente reduzir o desempenho (mais sobre isso abaixo).

Meu entendimento das duas opções é o seguinte:

Sem uma coluna de hash

1. Fazemos o hash da URL usando o hash implícito do índice (191 caracteres no código acima).
2. Para quaisquer colisões de índice, compare valuepor completo.

Com uma coluna de hash

Usando a resposta de Michael - sqlbot como referência ...

1. Começamos fazendo o hash da URL usando o algoritmo MD5.
2. Nós hash #1 usando o hash implícito do índice (estou me referindo ao fato de url_hashser indexado em si)
3. Para quaisquer colisões de índice, compare os url_hashvalores completos.
4. Para qualquer correspondência url_hash, compare os urlvalores completos.

Comparação

A desvantagem da minha abordagem é que o hash do índice não é calculado sobre o URL completo, portanto, resultará em mais colisões (e comparações completas de URL) do que a abordagem MD5.

A desvantagem da abordagem MD5 é que ela requer duas etapas extras: o cálculo de um hash MD5 e um SELECT extra para comparar os valores MD5.

Então, qual é melhor?

Qual a probabilidade de obtermos colisões de índice com minha abordagem? A resposta depende do conjunto de dados real, então não podemos responder em termos absolutos. É para isso que servem os criadores de perfil. Eu recomendo que as pessoas testem ambas as abordagens em dados reais e tomem suas decisões de acordo.

Por exemplo, meu caso de uso específico envolve a associação de páginas da Web com referenciadores HTTP. Existem no máximo 300 referenciadores por página HTML, o que significa que a probabilidade de colisões é quase zero. Mesmo que o hash de índice mais curto leve a mais colisões, o número de comparações de URL completo com certeza permanecerá baixo.

Se 3072 bytes forem suficientes, você pode ativar innodb_large_prefix ou atualizar para uma versão recente de 5.7 para tê-lo por padrão:

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

Para uma URL, será útil usar ASCII como o conjunto de caracteres se os caracteres forem realmente limitados a esse conjunto. Um byte por caractere.