Foro de elhacker.net

Hola gente... Les comento que tengo una base de datos donde cada registro, son links.

Hoy antes de activar el INDEXADOR de una web mia, pense en como hacer para ahorrar datos..

Tambien me dijeron hace un tiempo, en eliminar el http:// de cada link, para ahorrar espacio, como así tambien reemplazar el .com por un *, y el .org por un ] y el www. por un [
O sea, reemplanzar cadenas comunes por simbolos, para ahorrar espacio

Las preguntas son:
Tienen alguna idea mejor, o algo mas para hacer para ahorrar espacio? (no sirve cualquier sistema HASH)
Que simbolos no se utilizan en links? (para poder utilizarlos como reemplazos)


Espero respuestas tios/as!

Encontre una respuesta muy grosa:
http://www.nuevastecnologias.com.ar/2010/04/como-ahorrar-espacio-en-una-base-de.html

No hay porque reducir palabras para ello... tienes registros en una tabla que son puras direcciones URLs pero sabes que usarlas de indice es un crimen para el optimizador interno del motor y esto sin contar la lentitud que provocaria  :P  tengo un amigo programador en PHP que tenia un problema similar. El me decia como puedo crear un campo indice (ID) para cada Url si yo no voy a recordarme que ID le corresponde al registro 200 (por ejemplo). Entonces le di una solucion que espero tambien te pueda servir he de igual forma a otros webmasters porque se que esto es un dilema que ha de ocurrir bastante.

Tu me confirmas que tienes una tabla que solo guarda direcciones URLs en los campos. Asumo que es algo mas o menos asi:

 
mysql> SELECT * FROM ejemplo;
+-------------------------------------+
| direcciones                         |
+-------------------------------------+
| http://www.google.com               |
| http://www.yahoo.com/INDEX.html     |
| http://www.amazon.com/INDEX.php     |
| http://foro.elhacker.net/INDEX.php  |
| http://www.unix.com/INDEX.html?id=5 |
+-------------------------------------+
5 ROWS IN SET (0.00 sec)
 
 

Y tienes como index dicho campo (en mi caso direcciones) que es un VARCHAR de longitud variable le asigne 70 de longitud pero sabemos que es dinamica la reserva aca  :xD  eso es cruel y pesimo de usarlo como indice. Reducir o quitarle los 'http'  no es solucion. Asignarle un ID tampoco porque no vas a saberte el ID correspondiente a cada URL vamos (sobretodo si hablamos de cientos sino miles de URL como registros). Asi que tienes una opcion especial, asigna un campo extra de tipo DECIMAL el cual usaras como indice:

 
mysql> ALTER TABLE ejemplo ADD codigo DECIMAL(10,0);
Query OK, 5 ROWS affected (0.07 sec)
Records: 5  Duplicates: 0  Warnings: 0
 
mysql> CREATE INDEX indice ON ejemplo(codigo);
Query OK, 5 ROWS affected (0.07 sec)
Records: 5  Duplicates: 0  Warnings: 0
 
 

En esta parte la tarea te costara, pero valdra la pena, ya que ahora insertaras los datos de esta manera a la DB:

 
mysql> INSERT INTO ejemplo VALUES('http://www.google.com',crc32('http://www.google.com')), ('http://www.yahoo.com',crc32('http://www.yahoo.com')), ('httpd://foro.elhacker.net',crc32('http://foro.elhacker.net'));
Query OK, 3 ROWS affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0
 
mysql> SELECT * FROM ejemplo;
+---------------------------+------------+
| direcciones               | codigo     |
+---------------------------+------------+
| http://www.google.com     | 1587574693 |
| http://www.yahoo.com      |  416577886 |
| httpd://foro.elhacker.net |  794697805 |
+---------------------------+------------+
3 ROWS IN SET (0.00 sec)
 

Ahora diras sino puedo recordarme de un ID sencillo de 1 o 2 cifras como voy a recordar esos numeros tan largos en el campo codigo  :-\  simple la busquedad de la data la haras asi:

 
mysql> SELECT * FROM ejemplo;
+---------------------------+------------+
| direcciones               | codigo     |
+---------------------------+------------+
| http://www.google.com     | 1587574693 |
| http://www.yahoo.com      |  416577886 |
| httpd://foro.elhacker.net |  794697805 |
+---------------------------+------------+
3 ROWS IN SET (0.00 sec)
 
mysql> SELECT * FROM ejemplo WHERE codigo = crc32('http://www.google.com');
+-----------------------+------------+
| direcciones           | codigo     |
+-----------------------+------------+
| http://www.google.com | 1587574693 |
+-----------------------+------------+
1 ROW IN SET (0.02 sec)
 
mysql> SELECT * FROM ejemplo WHERE codigo = crc32('http://www.yahoo.com');
+----------------------+-----------+
| direcciones          | codigo    |
+----------------------+-----------+
| http://www.yahoo.com | 416577886 |
+----------------------+-----------+
1 ROW IN SET (0.00 sec)
 
 
 
 

Vas captando algo muchacho? Ahora analizemos que dice el optimizador de MySQL sobre esta consulta:

 
mysql> EXPLAIN SELECT * FROM ejemplo WHERE codigo = crc32('http://www.yahoo.com');
+----+-------------+---------+------+---------------+--------+---------+-------+------+-------------+
| id | select_type | TABLE   | TYPE | possible_keys | KEY    | key_len | REF   | ROWS | Extra       |
+----+-------------+---------+------+---------------+--------+---------+-------+------+-------------+
|  1 | SIMPLE      | ejemplo | REF  | indice        | indice | 6       | const |    1 | USING WHERE |
+----+-------------+---------+------+---------------+--------+---------+-------+------+-------------+
1 ROW IN SET (0.00 sec)
 
 

rows = 1
reference = const

 ;D  super....

O sea que tendria que reemplazar la clave "PRIMARI" del campo "link", y ponercelo a ese codigo que identificará al link?
Y que pasa con las coliciones? Ya que es muy probale que en cantidad de links, llegue aproximadamente a los 2.000.000.000 de registros.
Lo que tu me dices, ahorra tiempo de calculo y espacio por manejar mejor los indices... Pero, yo tengo problemas con el espacio en disco.

Que dices de convinar tu tecnica mas el reemplazo de las siguientes palabras:
        '¢ = www.
        '£ = .com
        '¤ = .org
        '¥ = .net
        '§ = .html
        '± = .htm
        '© = .php
        '® = index
        'µ = .png
        '¼ = .jpg
        '½ = .gif
        '¾ = .png
        'Æ = .jpeg
Entonces generaría ese codigo numerico para un link que esta tambien reducido en longitud por haber reemplazado esos textos(parte derecha), por esos simbolos (parte izquierda)


Porque, mi problema principal, es el espacio, y es verdad lo que tu dices, ya que mas del 50% del espacio, lo gasto en indices.

Imagina el link:
http://www.wikipedia.org/imagenes/simbolodeleuro.jpg >>> 53 bytes
En la base de datos, puede quedan:
¢.wikipedia¤/imagenes/simbolodeleuro¼ >>> 38 bytes
Esto tambien haría que el numero identificador sea mas pequeño aun, y MENOS ESPACIO en disco utilizado

Mira por ejemplo mi querida TIFA:
en 1 minuto, el indexador, tomando como RAIZ a wikipedia.org, encontro 3200 imagenes, de las cuales, 3020 comenzaban con:
http://upload.wikimedia.org/wikipedia/....
Reemplanzar el "http://upload.wikimedia.org/wikipedia/" (ya que, como todos sabemos, es una web que dará un gran porcentaje de las imagenes) por un simbolo, por ejemplo: *, en vez que ocupar 39bytes en ese tramo de link, ocupare solo 2 bites.

Aunque, ahora que veo bien, probando el indexador, y dando como link para que comience a buscar, a WIKIPEDIA: Mira el 1º link que me encontro:
http://as.wikipedia.org/wiki/প�ৰথম_পৃষ�ঠা

Como verás, ahí ya me ocupó la mayoria de los simbolos que pensaba utilizar como reemplazo.
Habria una solucion para ésto? Utilizar otro "lenguaje" para la base de datos, para poder utilizar los simbolos que te mostre arriba, solo para reemplazar esas palabras que te dije.


Porque, te repito: mi principal problema, es ESPACIO EN DISCO

El problema con los símbolos es que se guardan con su valor ascii

Esas webs, son coreanas o que se yo (las que dan esos simbolos en los links), lo que podria hacer, es:
Antes de ingresar el link (hay 2 bases de datos, una de LINKS y otras de LINKS DE IMAGENES) a la base de datos, puedo chequear si contiene algun simbolo de los que utilizo, y en caso de ser así, NO LO AGREGO al link, y listo..

Ten en cuenta que tus datos de las URL no son constantes, por ende definir caracteres de algo para sustituir algunas palabras, no te funcionaria del todo, ya que esto podria provocar que se trunquen data de URL, asi como que 2 URL sean similares  :-\  si tus tablas estan guardadas en motor Myisam, puedes optar por usar la funcionalidad myisampack. Para comprimir tus tablas y asi reducir considerablemente el tamano, por ejemplo checa esta tabla que tengo:

 
mysql> SELECT * FROM ejemplo;
+------------+----------------------------------+
| indice     | direccion                        |
+------------+----------------------------------+
| 1587574693 | http://www.google.com            |
|  416577886 | http://www.yahoo.com             |
|  721517199 | http://www.msn.com               |
| 3177037030 | http://www.gogo.com              |
| 1722868955 | http://www.coco.com/imagenes.png |
|  650421202 | www.cucu.com                     |
| 1509117005 | www.foro.org                     |
+------------+----------------------------------+
7 ROWS IN SET (0.00 sec)
 
 
 

Y son poquitos datos, pero checa cuanto me ocupa en disco duro el archivo data y indice.


94KB la data  :-\  un poco extenso para 7 miserables registros no... asi que uso la utilidad myisampack y comprimo:

bash-3.1# myisampack ejemplo.*

Ahora checa como redujo:


de 94KB a 4.0KB y la data sigue intacta dentro de las tablas.

Ahora existe un incoveniente con myisampack (ya que no todo es religiosamente maravilloso) al comprimir la data, la tabla en cuestion solo tiene permiso de Lectura, por lo que te permite INSERTAR y SELECCIONAR datos, pero no te permite eliminar registros ni actualizar registros  ;)

Otra manera opcional que podrias considerar es utilizar un procedimiento almacenado, para al menos la data que si estas seguro que es constante (como los www y los http) pos hacerlos asi:

Esta es mi tabla por ejemplo:

mysql> SELECT * FROM ejemplo;
+------------+-----------+   
| indice     | direccion |   
+------------+-----------+   
|  526628817 | google    |   
| 3748556277 | yahoo     |   
| 1257958042 | msn       |   
+------------+-----------+   
3 ROWS IN SET (0.00 sec)     
 
 

Y hago un procedimiento:

 
mysql> CREATE PROCEDURE copia(palabra CHAR(20)) BEGIN SELECT concat('http://www.', direccion, '.com') FROM ejemplo WHERE direccion = palabra; END;/
Query OK, 0 ROWS affected (0.00 sec)                                                                                                               
 
mysql> delimiter ;
mysql> CALL copia('google');
+------------------------------------------+
| concat('http://www.', direccion, '.com') |
+------------------------------------------+
| http://www.google.com                    |
+------------------------------------------+
1 ROW IN SET (0.01 sec)                     
 
 

Mira..
El indexador esta en vb.net, por lo que, al descargar una web(su codigo fuente queda guardado en una variable STRING), o una imagen (queda guardad en un MapaBit), SI O SI tiene que comenzar con http:// el link, por pero como sé que todos comeinzan con http://, lo obviaré y al agregar los items al array para que luego sean procesados, ahí le agregaré el http://, pero no para almacenarlos en la base de datos.

Ahora, hay un problema gigante con dar por obvio el .com, ya que puede ser .com, .com.ar, y demas.. Por eso la idea de reemplazar por simbolos.

Haré eso mi querida TIFA.. reemplazaré por simbolos algunas cadenas de los links, y generaré ese codigo numerico para identificar el link ya con los reemplazos.


Mi pregunta es:
Esos numeros que identificarán al link, que serán el indice PRIMARIO, no terminaran ocupando mas espacio que si tuviese como indice PRIMARIO al link?
Que me dices de las Coliciones con ese numero que identifica? Hay probabilidades de que haya 2 numeros iguales para 2 links diferentes?


Me puse a haces unas pruebas, ahora te digo como va todo

Exactamente, como este punto se desconoce (de igual manera si una URL tiene o no www o solo usa http) entonces como tus datos No son constantes... no puedes dar por hecho reemplazar cosas por simbolos. En esa parte ya se ha aclarado que lo unico mas probable que podrias sustituir son los www y los http. Como te decia puedes comprimir las tablas pero deberas conllevar el inconveniente que te expuse (no eliminar no actualizar).


Depende, el indice primario que usaras como link cuanto tiene de longitud y que informacion guarda??? porque por ejemplo, si ese indice primario guardase cosas como :

google
msn
yahoo

Perfecto.. no es necesario dar uso a un campo numerico y procura declarar el campo como CHAR en vez de VARCHAR, pero si ese link ocupara cosas como:

google.com/index.html/imagen?
yahoo.com/?pagina.php/imagenes.png

En ese caso No conviene usar indice primario algo asi... una porque el campo en cuestion seria de tipo VARCHAR y VARCHAR es un tipo de dato dinamico no constante, con dinamico implica que aunque tu le des una longitud por ejemplo de 50 bytes si tu informacion ocupa 20 bytes pos nada de esos 50 el ocupa 20 y lo otro lo trunca... y es favorable que para indices se utilizen datos constantes no variables ya que pueden corromperse bajo alguna condicion que no detallare aca porque seria extensa. Por ende si sabes que los links tendran datos de tamano distintos opta por declarar otro campo numerico como te decia.


No, no habran colisiones con ese numero generado por la funcion crc32 que es una funcion matematica, recuerda que dicho campo sera un indice PRIMARIO o UNICO por ende, jamas generara 2 datos iguales, mas bien unicos. (Eres libre de hacer una prueba) los datos son unicos bajo las condiciones que daras, la ventaja es que el campo al ser numerico y como tu sabes que bajo el sistema operativo solicitar informacion numerica es mucho mas rapido que obtener informacion en caracter y luego convertirlo a numerico para entonces interpretar lo que significa, con el campo siendo numerico te evitas ese pekeno pasito extra  ;)

Mira, estoy haciendo las pruebas:
Mira las siguientes imagenes:
la 1º imagen, es la tabla así nomas, sin modificar ni reemplazar nada por nada... la "VIRGEN"
la 2º imagen, es la tabla luego de haber reemplazado las siguientes cadenas:
'ð = upload.wikimedia.org/wikipedia/
        '¢ = www.
        '£ = .com
        '¤ = .org
        '¥ = .net
        '§ = .html
        '± = .htm
        '© = .php
        'µ = .png
        '¼ = .jpg
        '½ = .gif
        'Æ = .jpeg
        '® = index
        'æ = wikipedia


Y tifa, no hay manera de llegar a alcanzar un error o problema al reemplazar esas cadenas por esos simbolos, si se hacen en ese orden que los he puesto.

Primera
(http://img59.imageshack.us/img59/1036/primera.png)

Segunda
(http://img31.imageshack.us/img31/246/segundav.png)

Lo siento.... con estas imagenes no entiendo nada  :huh:

No uso phpmyadmin y no entiendo nada de lo que veo aca, me parece escritura japonesa. QUe es eso de cardinalidad? porque si tu campo es Unique o Primary es imposible que accepte valores duplicados, eso de Cardinalidad es el tamano del dato en el campo???  :huh:

Lo de cardinalidad, yo tampoco lo entiendo, por eso los "?", pero mira en ESPACIO UTILIZADO

Te recuerdo que me olvide de eliminar el HTTP:// a la 2º tabla...


Ahora te paso la imagen de la tabla con el "crc32()" y sin los http://
para ver cuanto podria llegar a ahorrar

Ahhhh pos entonces el tamano ha reducido.  :rolleyes:   la segunda tabla ya tiene los indices incluidos??? (Los indices numericos de lo mas que te puede servir es optimizar la velocidad de respuesta a la hora que hagas una consulta)

Si sabes que no vas a eliminar ni actualizar campos en tu tabla, puedes considerar usar myisampack para comprimir la tabla y reducir un 60% su tamano en disco.

Aun no tiene los indices, porque probaré con y sin indices.. para ver que conviene..

Creo que por el momento no utilizaré eso de  myisampack, porque como esta en etapa de prueba la web, aun no se si los hash de las imagenes(cosas propias de la web) estan correctos... Pero cuando me "estabilice", haré eso.

EN momentos te paso los resutaldos de todo

primero hay que recordar que toda forma de compresión suele acarrear más tiempo de procesamiento ...

no soy bueno con las bases de datos, pero ... ¿Y no sería mejor armar un índice ? es decir, correr cada tanto un optimizador que maneje una tabla aparte con fragmentos de URL que se repitan y asignarles una cadena X, reemplazar y luego al vuelo añadir lo faltante

por ejemplo, asignar en otra tabla 01 a "http://upload.wikimedia.org/wikipedia/"
y en la tabla con las urls poner [01]Imagen.jpg (es decir [01] se reemplaza con la URL, sólo si está al principio en vez de un protocolo)

después usás el índice como siempre, pero si te encontrás algo del estilo [] al principio en vez del protocolo, acudís al diccionario =P

también el source podrías comprimirlo con GZip para economizar más espacio ...

añado un link : http://www.mysqlperformanceblog.com/
mirate los posts sobre InnoDB y MyISAM, ese blog no tiene desperdicio =)

Saludos ~

Es verdad lo que dices Vertex...
En cuanto a ocupar mas procesamiento, eso no es tanto problema cuando estas pagando un hosting que no te limita en ese uso (mi caso), pero el limite si esta en el espacio

Es muy probable que en un futuro (no muy lejano) haga lo que tu dices, pero para ello, antes hay que crear un hermosoooo analizador...

Ahora me pondre con las pruebas que prometi

Aqui un documento importante sobre el tema:
http://www.nuevastecnologias.com.ar/2010/04/como-ahorrar-espacio-en-una-base-de.html

Tambien he notado que crear un indice del tipo:
 ALTER TABLE `conSimboloseIndices` ADD INDEX ( `hash1` , `hash2` , `hash3` )  
O sea, un indice que abarque a 3 columnas, OCUPA MUCHO MENOS ESPACIO, que 1 indice para cada columna...

Porque será? cual es la diferencia funcional?


Las consultas que haré hacia la abse de datos, son:
Select link from TABLALINKS where hash1='x' and hash2='x' and hash3='x'

Cual de esos 2 tipos de indices me conviene?


Otra pregunta TIFA:
que implica esto:  DECIMAL( 12, 0 )
Porque la coma y el 0???


Otra pregunta mas:
Tifa, por favor, me gustaria que me respondas algo:
el numero que devuelve el crc32, que longitud maxima tiene? yo supongo tener unas cuantas entradas en la base de datos, tal vez entrando a las 12 cifras..
Si me dices que NO HABRAN COLICIONES, entonces, hoy mismo me pongo a modificar todo

WOW TIFA!!!...
Me quiero casar con vos..


Perdon por el 3º posteo consecutivo.. es que en todos hablo de diferentes cosas, y espero respuestas separadas (o citadas :D )

Increible... Haciendo lo que tu dices, se reduce la cantidad de espacio en un 99,9%

Aqui paso los datos:

La tabla comun, con links sin http:// al comienzo, con un campo: LINK, y 3 campos HASH (hash1, hash2, y hash3):
3,230 Entradas (todas las tablas tienen la misma cantidad y LAS MISMAS entradas, pero con diferentes tratamientos)
Links SIN reemplazos de algunas cadenas, por simbolos.
1 Indice UNIQUE que abarca las 3 columnas de HASH
1 Indice PRIMARY al campo LINKS

Datos     332.5     KB
Índice    430.0    KB
Total    762.5    KB


2º TABLA:
Links sin http:// un campo LINKS, y 3 campos HASH (hash1, hash2, y hash3):
Links CON reemplazos de algunas cadenas, por simbolos.
1 Indice UNIQUE que abarca las 3 columnas de HASH
1 Indice PRIMARY al campo LINKS

Espacio utilizado:
Datos    226.8    KB
Índice    312.0    KB
Total    538.8    KB

TABLA 3: (con las recomendaciones de tifa)
Links sin http:// un campo LINKS, 3 campos HASH (hash1, hash2, y hash3) Y UN CAMPO CODIGO:
Links CON reemplazos de algunas cadenas, por simbolos.
1 Indice UNIQUE que abarca las 3 columnas de HASH
1 Indice PRIMARY al campo CODIGO, el cual contiene el CRC32 de cada link

Espacio Utilizado:
Datos     245.0     KB
Índice    89,088    Bytes
Total    332.0    KB


Increible..

Conclusión:
Mi sistema, ahorró 224 KB. y Sumandole la tecnica que propone TIFA, se ahorran en total: 430 KB, y mejorando por mucho la velocidad de la base de datos :D

Hola.

Conozco a los chicos de mysqlperformanceblog  son los mismos chicos de Percona  ;)  son un grupo de consultores profesionales en MySQL. De hecho ellos mismos escribieron el libro 'MySQL Optimization' el cual he leido como 3 veces ya  :xD  pero estoy registrada en su foro y lo visito mucho para aprender cosas que aun no sepa. Eso de crear 1 tabla extra con indices y que busque bajo una condicion cuando usar la tabla indices y cuando no... es un proceso que no sabria yo si fuese muy conveniente. Ya que no solo es crear un Analizador que te haga esto, sino tambien darle mas tarea a la base de datos al utilizar varios JOINS de tablas bajo ciertas condiciones... puede ahorrarse un reducido tiempo en hacerlo todo directo... pero siempre hay opciones que considerar.


Ten algo pendiente si tus tablas son Myisam y defines como indices varios campos que eran data en la tabla.. estos pasan al archivo .MYI y ya no siguen en .MYD  ademas de la grandisima ventaja que los indices en Myisam se guardan en un buffer cache del motor MySQL, sin embargo la Data se guarda en la cache ram del sistema operativo  :-X  por ende la busquedad y lectura de indices es mas rapida porke esta en el buffer de MySQL y no en el buffer que maneja el sistema operativo, por ende es normal que reduzca en tamano el archivo MYD.

Tus indices son hash indices??? son datos constantes de longitud constante cierto?


Implica que la longitud de ese campo soporta 12 numeros decimales sin punto.. por ejemplo si defines un campo asi:

DECIMAL(5,3)

Implica que dicho campo soportara 5 numeros nada mas, pero de esos 5 numeros debes colocar 1 punto (de decimal) antes de las 3 ultimas cifras, me explico si quieres insertar el valor:

30000
40000

No puedes insertarlo asi a pelo en la tabla, porque te dara error, debes insertarlo asi:

30.000
40.000

De igual manera si tu campo fuese DECIMAL(6,2)  indica que soporta una cifra de 6 numeros pero colocandole un puntito antes de los 2 ultimos:

3000.00
4000.00

Se entiende???  :huh:

PD: Por cierto que fue lo que aplicaste de lo que yo te dije?? Usaste Myisampack???

Me quedo claro en donde se colocan en "el hadware" las columnas con indice, pero, porque es diferente tener 3 indices (uno por cada columna) a tener uno que abarque las 3 tablas?


EN cuanto a la 3º tabla, no use myisampack, sino que agregue una nueva columna: "codigo", que contiene el crc3 del campo LINK, y elimine la clave primaria de LINK que era un varchar de 300, y se la pasé (a la clave primaria) a la columna CODIGO

En cuanto a las columnas HASH, son: smallint(3).. ahí dentro guardo numeros entre 0 y 266.

Digamos que, la 3º tabla es:

CREATE TABLE IF NOT EXISTS `conSimboloseIndices` (
  `hash1` SMALLINT(3) NOT NULL,
  `hash2` SMALLINT(3) NOT NULL,
  `hash3` SMALLINT(3) NOT NULL,
  `link` VARCHAR(300) NOT NULL,
  `codigo` DECIMAL(12,0) NOT NULL DEFAULT '0',
  PRIMARY KEY  (`codigo`),
  KEY `hash1` (`hash1`,`hash2`,`hash3`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

Otra pregunta mas:
Tifa, por favor, me gustaria que me respondas algo:
el numero que devuelve el crc32, que longitud maxima tiene? yo supongo tener unas cuantas entradas en la base de datos, tal vez entrando a las 12 cifras..
Si me dices que NO HABRAN COLICIONES, entonces, hoy mismo me pongo a modificar todo

@^TiFa^ : El problema con crc son las colisiones, y teniendo 2 mil millones de registros complica evitar una colisión usando un algoritmo de 32 bits (una en 2^32), asumiendo que de esos 2 mil millones hayan dado todos diferentes hashes ..

si se siguiese con esa técnica, para posponer el tema de las colisiones yo diría mejor un crc64, o un MD5 o SHA1 (128 o 160 bits comparados con 32 o 64 ...), aunque claro, reduce lo que podés comprimir una URL ...

acá hay una charla interesante del tema : http://is.gd/8f209

lo que plantee es una forma básica de evitarlo (bueno, la complejidad depende del algoritmo del optimizador que uses ....), y dependiendo de la masa de registro, de qué recursos disponga el servidor y que implementación uses (no hay necesidad de JOIN, sólo se acude al "diccionario" sólo si se necesita, primero se pide la URL y si esta parece estar achicada, recién ahí se acude al diccionario)

hay mil formas de escurrir bytes, pero todas dependen específicamente de lo que necesites y de qué dispongas ...

Saludos ~

Por dios Skeletron un VARCHAR de longitud 300 como Primary Key  :-\  intenta no hacer esto. Ten siempre pendiente recordar que los campos que vas a definir como PK que sean de longitud constantes o fijas (char, int, tinyint, smallint, etc) Y no de longitud variable (varchar) los datos de longitus variable suelen desfragmentarse mucho... no lo uses como indices.


CRC64 hasta lo que yo se, No existe en MySQL como funcion. La funcion Matematica CRC32 retorna valores unicos que no sobrepasan las 11 cifras por mas larga que sea la entrada que estas convirtiendo con CRC32 Por este lado Skeletrun confia.

Yo particularmente no recomendaria ni MD5 ni SHA1 para indice, la razon ademas de que retorna un tamano en bits mayor (algo que quiere evitarse Skeletrum) no son datos numericos sino alfanumericos... por lo cual sabes que en lenguaje de computador es mucho mas rapido la lectura de datos numericos que alfanumericos ya que los alfanumericos deben traducirse primero a numericos (aunque sea en fraciones de milisegundos pero segun lo hace) para poder interpretarlos. Entonces considerando lo anterior, CRC32 es mejor porque ahorra bityes de espacio, son caracteres siempre numericos y no sobrepasan las 11 cifras. (Hasta la fecha No he visto colisiones usando esta funcion la CRC32 en millones de datos, para mi hay una alta posibilidad que funcione acorde a lo que he visto... pero, no podria descartar que a lo mejor colisione alguna vez pero particularmente en millones de datos yo no lo he visto aun).

Que conste que la idea de insertar campos indices con la funcion CRC32 la obtuve de un ejemplo del libro 'High MySQL Optimization' escrito por la gente de Percona, esa misma gente que mencionas Vertex en los links que refieres... esa sugerencia la obtuve de ellos y hasta la fecha a mis amistades developers webs le ha servido enormemente.  ;)

Las/os 2 tienen razon:

Tifa, mi idea, es llegar a las 12 sifras de entradas.. o sea 100.000.000.000
Un algortimo de 32 bits, (2^32=4294967296) digamos que con la suerte al 100%, podria tener 4.294.967.296 entradas sin coliciones, y en la entrada 4294967296 + 1, ya sería una colicion.. Digamos que perdería MUCHISIMAS IMAGENES!!!

Ahora, un algoritmo de 2^62=18446744073709551616 que el resultado sea una cadena solamente numerica, daría la chanse de tener 18.446.744.073.709.551.616 entradas...

Lo que aumentaría en espacio, lo ahorrarian en el "costo de espacio" que me genera tener un indice privario en el varchar de 300...

No me quiero arriesgar a perder billones de imagenes por culpa de un algoritmo.. Sería bastate tonto...

Tiene que haber algun algoritmo que no me de problema con coliciones (o pocos problemas)...


Creo que alargar la longitud del resultado a guardar en "CODIGO", para disminuir las coliciones, será una buena idea.
Tal vez pierda unos 50bites por entrada (porque crece el tamaño de CODIGO), pero sigo ganando mucho por eliminar el UNIQUE de un varchar de 300, y quedando solo en la columna CODIGO...


Ustedes son los que saben... que me dicen?

Y entonces que me dicen?
Habrá algun hash que disminuya la cantidad de coliciones?

Es mala la idea de un MD5 en un CHAR(32)??

Bueno tienes un pequeno dilema.

CRC32 vs MD5 en cuestion de velocidad y desempeno es mejor porque al ser un convertidor mas pequeno, pues el calculo el motor lo interpreta mas rapido. Y como te expuse los valores en CRC32 son tratados como numeros enteros en cambio funciones como MD5, SHA1, etc. etc son tratados como datos caracteres alfanumericos hexadecimales  :-\  esto sin considerar que los calculos sobre numeros es mas rapido que los calculos sobre funciones criptograficas sin necesidad en tu caso que no vas a guardar una contraseña, ni una tarjeta de credito ni mucho menos para aplicar una funcion criptografica.


Vas a guardar imagenes dentro del motor???  :-\  recuerda que esto convertido en dato binario ocupa muchisimo espacio... lo cual alentaria sobremanera una busquedad que te retorne una imagen independientemente que utilizes hasta 20 indices primarios numericos.

Como te decia una funcion Matematica en tu caso es muchisimo mas recomendable que una funcion criptografica, no solo te ahorras velocidad sino tambien tamano en el disco. No existe lamentablemente hasta lo que me concierne una funcion matematica oficial en MySQL de 64bits. Pero, como siempre existen aplicaciones de terceros (Y a no ser que Vertex quisiera cooperar contigo y desarrollarte en C una funcion que funcione como un hash matematico de 64 y luego la implementas dentro de MySQL como una funcion UDF  ;) ) De lo contrario, ya han habido usuarios que han creado funciones UDF para MySQL, como este amigo:

http://www.xaprb.com/blog/2008/03/09/a-very-fast-fnv-hash-function-for-mysql/

Compilar una funcion UDF dentro de un ya existente motor de MySQL no es complicado, si tanto te preocupa el desempeno y el tamano me temo que tendras que usar una funcion matematica de un tercero como la que te postee anteriormente, o usar CRC32 y sus limites o inclinarte por un hash criptografico pero de antemano conociendo sus inconvenientes para tu caso en especifico.

Gracias por los comentarios Tifa..

Cuando me referia a IMAGENES, queria decir: LINKS, ya que esos links que hay en la base de datos, son links a imagenes.

Me gusta que quede claro, que no hay problemas en cuando a la velocidad de la base de datos si utilizo MD5, ya que los "SELECTS" que haré, seran con un WHERE hash1=xxxx.. o sea, los selects tendran en su "WHERE" a valores de la columna HASH1 HASH2 y HASH2, y no la columna de CODIGO (donde estaria guardado el MD5)


Ahora tambien, estaba mirando, y creo que tambien tendre que implementar el sistema que VERTEX presenta, el de 2 tablas..
Tabla 1:
[1]google[2]

Donde en tabla 2 esta:
[1] = www.
[2] = .com

Porque, analizando recien, tengo muchas, pero muchas palabras que siempre aparecen en los links, como por ejemplo:
link = link.Replace("upload.wikimedia.org/", "^")
            link = link.Replace("wikipedia", "`")
            link = link.Replace("img", "~")
            link = link.Replace("fotolog", "¢")
            link = link.Replace("metroflog", "£")
            link = link.Replace("image", "Æ")
            link = link.Replace("photo", "Ø")
            link = link.Replace("picture", "Þ")
            link = link.Replace("static.flickr.com/", "ß")

            link = link.Replace("www.", "¢")
            link = link.Replace(".com", "£")
            link = link.Replace(".org", "¤")
            link = link.Replace(".net", "¥")
            link = link.Replace(".html", "¦")
            link = link.Replace(".htm", "§")
            link = link.Replace(".php", "©")
            link = link.Replace(".png", "®")
            link = link.Replace(".jpg", "±")
            link = link.Replace(".gif", "µ")
            link = link.Replace(".jpeg", "¶")
            link = link.Replace(".index", "¼")
            link = link.Replace(".asp", "½")
            link = link.Replace(".aspx", "¾")
            link = link.Replace(".bmp", "ð")

Y como verán, aun quedan muchos opr agregar, como por ejemplo: photoS, tumbalins, y demas palabras que siempre aparecen en los links de imagenes.

Alrespecto, Tifa respondio que se comenzaria a crear un gran problemas con los "UNION" y demas.. (o me equivoco?) y es verdad...
Pregunta:
supongamos que con un select, devuelvo el LINK (campo), que tiene como HASH1(campo)=123

SELECT links FROM tablanoel WHERE hash1='123'

Una vez que tengo el link, tendré que recorrerlo buscando indices del tipo: [X]??? y realizar OTRO select por cada [X] que encuentre para reemplazar el valor?
O se podra hacer todo en una sola Consulta?

Disculpa que no te este entendiendo muy bien en tus ultimos comentarios...


Eso solo te retornara todos los campos links donde el campo hash1 sea igual a 123 y eso lo sabias. Lo poco que he entendido (y explicame sino es asi) es que seguido obtengas el link correspondiente al hash1 = 123 digamos que ese link es 'wikipedia' estas diciendo que si luego tendrias que ir a una segunda tabla con otra consulta y ver que campos links corresponden a 'wikipedia' y despues de eso ejecutar el algoritmo este que reemplazara todos esos datos encontrados que concordaban??? si tu pregunta era esa... la respuesta es SI

Si lo haces de la forma como Vertex te sugirio si... por eso te decia que le proceso iba a ser un poco mas largo de esta manera, porque tienes que realizar muchas evaluaciones. Obviamente las 2 consultas se pueden colocar en 1 sola linea separadas por punto y coma cada una al final... pero me temo que el proceso aunque lo coloques en 1 sola linea, sera el mismito el resultado el motor debera realizar los 3 algoritmos para hacer eso que buscas....

Lo siento, yo no voy muy acorde a esa idea, entiendo que quieres ahorrar espacio.. pero yo me preocuparia mas porque las consultas sean rapidas ya que el espacio se puede reducir luego, pero una estructura inicial implementada en base a calculos de algoritmos y luego resultados... bueno eso con el tiempo (digase cuando tengas muchos datos mas de miles) comenzaran a alentarse y alentarse y alentarse... independientemente que uses hasta 64 indices constantes  :xD

Por cierto cuando escribas hash te refieres al nombre del campo indice no al tipo de indice que este es verdad? porque hasta lo que se, Myisam no maneja ni soporta indices de tipo hash sino btree y rtree.

Has acertado en todo lo que dije.
Cuando hablaba de HASH, me referia a la columna, porque 3 columnas se llaman: hash1, hash2 y hash3.
bueno, a esta altura, me he quedado muy liado.

Pero he tomado una decicion:

Por ahora, reemplazare solamente los .com, .org, y esas cadenas cortitas, por simbolos extraños que se que no aparecerán en ningun link.
Luego de un tiempo, cuando vea (con algun programa que tome estadisticas de la base de datos) que hay palabras muy largas, que se repiten mucho, y que realmente vale la pena reemplazarlas por alguna otra cadena que la identifique, entonces, ahí si implementaré lo que dice Vertex.

Tendria que poner el indexador a trabajar unos cuannntoosssss dias y ver luego, cuando ya tenga muchas entradas.

Les agradezco mucho la ayuda!
Los volveré a molestar pronto..


PD.: Ya he mandado a imprimir el libro: LA BIBLIA DE MYSQL, así que espero la proxima tener menos dudas :D

A todo esto.... pareciera que volaste cuando te recomende la sustituciones de valores constantes con un procedimiento almacenado  ::)

Porque no generas un procedimiento almacenado en Mysql que diga que cuando reciba no se la palabra 'google' le agregue 'http://www' y '.com'.... etc, etc, etc....

Te puse un ejemplo en la pagina anterior ... hubiera trabajado sobre ese procedimiento almacenado en vez de crear mas tablas y un algoritmo que analize las 3 tablas para obtener una solucion....

digo yo no  :P

CRC32 SI tiene colisiones

SI jujub si ya se hablo de las posibles colisiones de CRC32  ;) despues de 4 billones de entradas  de ahi surgio las recomendaciones de funciones externas y links que le referi para descargarselas. Pero creo que Skeletrum le busco la vuelta ya a este dilema.

Si yo fuese Skeletrum, usase procedimientos almacenados para reemplazar valores por cosas fijas como http y www.

Tifa, te respondo:
Ahora que me doy cuenta, tampoco es necesario hacerlo con otra tabla en la base de datos...
Con PHP puedo hacerlo.. con la funcoin REPLACE.
Digamos que, cuando la web quiera X link, en base a esos 3 hash, supongamos que la sentencia devuelve 2 links.
Antes de "imprimirlos" con el ECHO (php), paso al link a una variable, la cual le aplico todas las REGLAS DE PRODUCCION, pero de manera INVERSA a como se guardaron en la base de datos.

Por ejemplo, si uso las sigueintes reglas:
www. se transforma en ----> |1
.com ------> |2

En mi indexador, al encontrar el link: www.google.com, luego de aplicarle esas 2 reglas de produccion, quedaría:
|1google|2
..

Luego, cuando en la web, luego de una sentencia SELECT, me devuelve ese link: |1google|2, con la funcion reemplace de PHP, haría ésto:
$link=replace("|1","www.",$link);
$link=replace("|2",".com",$link);
LISTO, la varible $LINK, tendría el siguiente valor: www.google.com
Imprimo $link dentro de un campo de link:
<a href="$link" >link</a>
Y el link, queda perfecto..

Digamos que en Conclusión:
AUMENTO EL TIEMPO de procesamiento en CPU por el reemplazo.
DISMINUYO EL TIEMPO de espera de los resultados de la 2 sentencia(que me traería los valores para reemplazar)
DISMINUYO EL ESPACIO utilizado en la base de datos.

En cuanto a lo de las situaciones constantes Tifa, te digo que no estoy al tanto (es mas, SOY MUY EXTREMADAMENTE NOVATO EN ESTO).. Pero por tu ejemplo, debe ser mas de lo mismo que hablo yo.. simplemente que tu lo implementeas en la base de datos. y yo estoy creando como FILTROS desde PHP

Advertencia - mientras estabas escribiendo, una nueva respuesta fue publicada. Probablemente desees revisar tu mensaje.


PD.: Cuales creen que son las palabras mas utilizadas en links? las que seguro estaran escritas miles de veces en la base de datos...??

datos constantes son datos fijos tu sabes, asi como puedo decir un campo de longitud constante es un campo que si defines su longitud 20 espacio ocupara esos 20 espacios aunque tu le insertes una informacion de 10 espacios  :xD

SI suponia que podia implementar todo eso del reemplazo en el codigo PHP, solo que yo te lo sugeri como procedimiento almacenado dentro del Motor MySQL, pero eso mismo que expones para PHP fue lo mismo que sugeria pero para un procedimiento almacenado  :xD  creo que es mas comodo de esta forma que crear varias tablas ciertamente.

Sobre eso de palabras repetidas y como se llaman, no hay un nombre... la longitud del campo que guarda este dato puede ser constante (CHAR por ejemplo) sin embargo quien condiciona si el dato se repite o no es si tu declaras este campo como una llave primaria o como un indice unique. Fuera de esto si declaras dicho campo como index o key seran indices pero podran repetirse.

Vuelvo a joderlos: Creo que tengo la solucion

Que pasa si en vez de colocar en CODIGO, el resultado del MD5 del LINK, coloco: el resultado del CRC32 del link y el CRC32 de la concatenacion de los numeros que hay en la columna HASH1, HASH2, y HASH3?



Lean ésto por favor:
Mi tabla, se llama: IMGS, que contiene los siguientes campos:
CODIGO << aqui se guardaba el crc32 o el md5
LINK << aca hay links SOLAMENTE DE IMAGENES.. SOLAMENTE!!
HASH1 << aca se guardala cantidad de color ROJO que tiene la imagen
HASH2 << aca se guarda la cantidad de color VERDE que tiene la imagen
HASH3 << aca se guarda la cantidad de color AZUL que tiene la imagen

Ahora bien.. Mi indexador, tiene en otra base de datos, LINKS de IMAGENES A PROCESAR.
Mi indexador toma de esa base de datos (que esta en mi PC) 1 link.
Descarga ese link, mira la cantidad de colores que tiene (analizando los pixeles) y hace al final:
INSERT INTO imgs (codigo, link, hash1, hash2, hash3) VALUES ('XXXXXXXX', 'www.google.com/logo.jpg', '123', '912', '465');

OK?? se entiende?

Bien.. El problema, es QUE GUARDAR EN CODIGO? ese fue nuestro problema desde que empezamos con ésta idea..
Pues bien, se me ocurrió algo genial!
Guardar ahí, en el campo CODIGO, el resultado de 2 crc32 concatenados.. para así aumentar a 2^64 la longitud de los resultados, y disminuir MUCHISIMO la posibilidad de coliciones.
Cuales serían los 2 CRC32 a calcular?
1º: el crc32 del LINK
2º, el CRC32 de HASH1HASH2HASH3

Porque digo que sería bueno?
Supongamos que 2 link de imagenes, son TOTALMENTE DIFERENTES, ejemplo:
A = www.noel.com/foto.jpg
B = www.foro.com/foto.jpg
Pero, ambos links, aplicandole el CRC32, devuelven el mismo resultado (COLICION), el cual es: 123456789

Problema: Al querer agregar estos links, uno de los 2 no se agregará, ya que el que ingrese primero, no permitirá al 2º entrar, porque el campo CODIGO (que posee hasta el momento 1 solo CRC32 del LINK) tienen el MISMO VALOR DE CRC32.

PERO!, esas 2 imagenes, son TOTALMENTE DIFERENTES (obviamente), entonces sus valores de HASH1, HASH2, y HASH3, TAMBIEN!, ya que contienen diferentes cantidades de colores en cada pixel.

Supongamos:
A = www.noel.com/foto.jpg | HASH1=123 | HASH2=234 | HASH3=345
B = www.foro.com/foto.jpg | HASH1=567 | HASH2=678 | HASH3=789
En este caso, si en CODIGO, colocamos los 2 CRC32, de ésta manera:
CODIGO=CRC32='www.noel.com/foto.jpg'CRC32='123234345'

LA UNICA MANERA de dar la COLICION, sería que el CRC32 de los 2 links SEAN IGUALES, y el CRC32 de los valores CONCATENADOS que hay en HASH1, HASH2, y HASH3, TAMBIEN DEVUELVAN EL MISMO VALORRR!!!...
SERÍA EXTREMADAMENTE MUCHA CASUALIDAD!!!!!


Todo funcionaría perfectamente.. PORQUE?
Porque si es EL MISMO LINK, entonces, los valores de los 3 HASH, SERAN IGUALES TAMBIEN. ya que es la misma imagen, por ENDE, los valores serían iguales tanto en el resultado del CRC32 del link como el de CRC32 de los hash. Y NO SE INGRESARÍA EL LINK, por duplicidad en la KEY PRIMARIA.

Que pasa si 2 imagenes son iguales, COPIAS, pero estan guardadas en 2 webs diferentes.. entonces, tendrán el mismo CRC32 de sus HASHES, pero diferentes en el CRC32 de su link (a no ser que se de una colicion ahí, pero las probabilidades son casi nulas)


Que ventaja tiene ésto?
La Key sería SOLAMENTE de NUMEROS, de una longitud de 20, (si mal no recuerdo, CRC32 devuelve un numero de HASTA 10 sifras), y con esa longitud, no habrá casi coliciones. Disminuiré mucho el peso de la base de datos, ya que el MD5 tiene 32 caracteres de longitud. y el indice será solo de NUMEROS... :D

Habra muchas coliciones por los links, pero el 2º crc32, hará la diferencia :)

Y si 20 carateres, es poco para evitar coliciones, entonces, podria concatenar 3 crc32, por ejemplo, del LINK, del 1º y 2º HASH y del 3º HASH

QUE ME DICEN?

Honestamente... aunque se lea cruel, yo poco te puedo ayudar en esta logica presentada  :xD  la razon? soy extremadamente mala, mediocre, pesima cuando se me presenta algun tema donde me hablen de numeros y funciones matematicas.

No quiero decirte una tonteria, y a lo mejor este equivocada (que tengo mas fe que si) pero... si sacas el CRC32 de los 3 indices y lo concatenas esto en que diferenciaria en que saques 1 solo CRC32 de 1 indice??  :huh:  o sea.. CRC32 su maximo seran 4 billones de entradas perfecto, que haras tu cuando concatenes 3 convertisiones CRC32 de 3 indices... si despues que pase de 4 billones habra colision???  :huh:  si hubiese algun bucle o algo que diga que despues de 4 billones de entradas pos se le sume un numero extra al final ya es otro asunto que podria ser valido y evitar colisiones....

Pero hay otro dilema  :-\  si se hace lo del bucle.. como se usaria el indice CRC32 si cuando digas traeme el link donde el hash1 = 'www.google.com'  por ejemplo.... el retornaria nada porque el valor de la ultima cifra fue generada por un contador  :-X

Repito puedo estar diciendo una tonteria.. los numeros efectivamente no se hicieron para mi  :D

Pero TIFA!, CONCATENAR, significa poner al lado 2 numeros.. pegados...
serán 2 numeros de hasta 4 millones pegados al lado.. será un numero entonces desde 00 hasta 42949672964294967296

(CRC32 de LINK)   UNIDO/PEGADO A (CRC32 de (hash1 unido a hash2 unido a hash3))
Si (CRC32 de LINK) = 123456
y
CRC32 de (hash1 unido a hash2 unido a hash3) = 456456456
El numero a ingresar en CODIGO, será: 123456456456456

Ejemplo:

INSERT INTO imgs (codigo, link, hash1, hash2, hash3) VALUES (crc32='http://foto.com/foto.jpg'crc32='456123678', 'http://foto.com/foto.jpg', '456', '123', '678')
Da error porque no se como concatenar los resultados de los 2 crc32===== crc32='http://foto.com/foto.jpg'crc32='456123678'

Ejecuta esa sentencia

Perdoname.... te decia que los calculos y los numeros me vuelven un ocho .... es como que me hablasen chino o japones...

Pero si estas seguro que funcionara.. puedes concatenar mas de 2 valores usando  ||

Algo asi como:

INSERT INTO TABLA VALUES(CRC32=campo1||CRC32=campo2||CRC32=campo3||'123'||'456');

 :P