¿Puede SQL Server crear colisiones en nombres de restricciones generados por el sistema?

Tengo una aplicación que crea millones de tablas en una base de datos de SQL Server 2008 (no agrupada). Estoy buscando actualizar a SQL Server 2014 (en clúster), pero aparece un mensaje de error cuando está bajo carga:

"Ya existe un objeto llamado 'PK__tablenameprefix__179E2ED8F259C33B' en la base de datos"

Este es un nombre de restricción generado por el sistema. Parece un número de 64 bits generado aleatoriamente. ¿Es posible que esté viendo colisiones debido a la gran cantidad de tablas? Suponiendo que tengo 100 millones de tablas, calculo menos de una probabilidad de 1 en 1 billón de colisión al agregar la siguiente tabla, pero eso supone una distribución uniforme. ¿Es posible que SQL Server haya cambiado su algoritmo de generación de nombres entre la versión 2008 y 2014 para aumentar las probabilidades de colisión?

La otra diferencia significativa es que mi instancia de 2014 es un par agrupado, pero estoy luchando por formar una hipótesis de por qué eso generaría el error anterior.

PD Sí, sé que crear millones de mesas es una locura. Este es un código de terceros de caja negra sobre el que no tengo control. A pesar de la locura, funcionó en la versión 2008 y ahora no en la versión 2014.

Editar: en una inspección más cercana, el sufijo generado siempre parece comenzar con 179E2ED8, lo que significa que la parte aleatoria en realidad es solo un número de 32 bits y las probabilidades de colisiones son solo 1 en 50 cada vez que se agrega una nueva tabla, que es una coincidencia mucho más cercana a la tasa de error que estoy viendo!

¿Puede SQL Server crear colisiones en nombres de restricciones generados por el sistema?

Esto depende del tipo de restricción y la versión de SQL Server.

CREATE TABLE T1
(
A INT PRIMARY KEY CHECK (A > 0),
B INT DEFAULT -1 REFERENCES T1,
C INT UNIQUE,
CHECK (C > A)
)

SELECT name, 
       object_id, 
       CAST(object_id AS binary(4)) as object_id_hex,
       CAST(CASE WHEN object_id >= 16000057  THEN object_id -16000057 ELSE object_id +2131483591 END AS BINARY(4)) AS object_id_offset_hex
FROM sys.objects
WHERE parent_object_id = OBJECT_ID('T1')
ORDER BY name;

drop table T1

Resultados de ejemplo 2008

+--------------------------+-----------+---------------+----------------------+
|           name           | object_id | object_id_hex | object_id_offset_hex |
+--------------------------+-----------+---------------+----------------------+
| CK__T1__1D498357         | 491357015 | 0x1D498357    | 0x1C555F1E           |
| CK__T1__A__1A6D16AC      | 443356844 | 0x1A6D16AC    | 0x1978F273           |
| DF__T1__B__1B613AE5      | 459356901 | 0x1B613AE5    | 0x1A6D16AC           |
| FK__T1__B__1C555F1E      | 475356958 | 0x1C555F1E    | 0x1B613AE5           |
| PK__T1__3BD019AE15A8618F | 379356616 | 0x169C85C8    | 0x15A8618F           |
| UQ__T1__3BD019A91884CE3A | 427356787 | 0x1978F273    | 0x1884CE3A           |
+--------------------------+-----------+---------------+----------------------+

Resultados de ejemplo 2017

+--------------------------+------------+---------------+----------------------+
|           name           | object_id  | object_id_hex | object_id_offset_hex |
+--------------------------+------------+---------------+----------------------+
| CK__T1__59FA5E80         | 1509580416 | 0x59FA5E80    | 0x59063A47           |
| CK__T1__A__571DF1D5      | 1461580245 | 0x571DF1D5    | 0x5629CD9C           |
| DF__T1__B__5812160E      | 1477580302 | 0x5812160E    | 0x571DF1D5           |
| FK__T1__B__59063A47      | 1493580359 | 0x59063A47    | 0x5812160E           |
| PK__T1__3BD019AE0A4A6932 | 1429580131 | 0x5535A963    | 0x5441852A           |
| UQ__T1__3BD019A981F522E0 | 1445580188 | 0x5629CD9C    | 0x5535A963           |
+--------------------------+------------+---------------+----------------------+

Para las restricciones predeterminadas, verifique las restricciones y las restricciones de clave externa, los últimos 4 bytes del nombre generado automáticamente son una versión hexadecimal del objectid de la restricción. Como objectidse garantiza único, el nombre también debe ser único. En Sybase también estos usantabname_colname_objectid

Para restricciones únicas y restricciones de clave principal, Sybase utiliza

tabname_colname_tabindid, donde tabindid es una concatenación de cadenas de la ID de la tabla y la ID del índice

Esto también garantizaría la singularidad.

SQL Server no usa este esquema.

Tanto en SQL Server 2008 como en 2017 utiliza una cadena de 8 bytes al final del nombre generado por el sistema, sin embargo, el algoritmo ha cambiado en cuanto a cómo se generan los últimos 4 bytes.

En 2008 los últimos 4 bytes representan un contador entero con signo que está desplazado del object_idpor -16000057con cualquier valor de ajuste de negativo en torno a int firmado máx. (La importancia de 16000057es que este es el incremento aplicado entre sucesivamente creadoobject_id ). Esto todavía garantiza la unicidad.

En 2012 hacia arriba, no veo ningún patrón entre el object_id de la restricción y el entero obtenido al tratar los últimos 8 caracteres del nombre como la representación hexadecimal de un int con signo.

Los nombres de las funciones en la pila de llamadas en 2017 muestran que ahora crea un GUID como parte del proceso de generación de nombres (en 2008 no veo mención de MDConstraintNameGenerator). Supongo que esto es para proporcionar alguna fuente de aleatoriedad. Claramente, no está usando los 16 bytes completos del GUID en esos 4 bytes que, sin embargo, cambian entre restricciones.

Supongo que el nuevo algoritmo se realizó por alguna razón de eficiencia a expensas de una mayor posibilidad de colisiones en casos extremos como el suyo.

Este es un caso bastante patológico ya que requiere que el prefijo del nombre de la tabla y el nombre de la columna de la PK (en la medida en que esto afecte a los 8 caracteres que preceden a los 8 finales) sean idénticos para decenas de miles de tablas antes de que sea probable, pero puede reproducirse bastante fácilmente con el siguiente.

CREATE OR ALTER PROC #P
AS
    SET NOCOUNT ON;

    DECLARE @I INT = 0;


    WHILE 1 = 1
      BEGIN
          EXEC ('CREATE TABLE abcdefghijklmnopqrstuvwxyz' + @I + '(C INT PRIMARY KEY)');
          SET @I +=1;
      END 

GO

EXEC #P

Un ejemplo ejecutado en SQL Server 2017 contra una base de datos recién creada falló en poco más de un minuto (después de haber creado 50,931 tablas)

Mensaje 2714, Nivel 16, Estado 30, Línea 15 Ya existe un objeto llamado 'PK__abcdefgh__3BD019A8175067CE' en la base de datos. Msg 1750, Nivel 16, Estado 1, Línea 15 No se pudo crear restricción o índice. Ver errores anteriores.

Suponiendo que tengo 100 millones de tablas, calculo menos de 1 en 1 billón de posibilidades de colisión.

Recuerde que este es el " problema del cumpleaños ". No está intentando generar una colisión para un solo hash dado, sino que está midiendo la probabilidad de que ninguno de los muchos pares de valores choque.

Entonces, con N tablas, hay N * (N-1) / 2 pares, así que aquí hay unos 10 ¹⁶ pares. Si la probabilidad de una colisión es de 2 a ⁶⁴ , la probabilidad de que un solo par no colisione es de 1-2 a ⁶⁴ , pero con tantos pares, la probabilidad de no tener colisiones aquí es de aproximadamente (1-2 a ⁶⁴ ) ^{10 16} , o más como 1 / 10,000. Ver, por ejemplo, https://preshing.com/20110504/hash-collision-probabilities/

Y si es solo un hash de 32 bits, la probabilidad de una colisión cruza 1/2 a solo 77k.