Como ahorro espacio en la base de datos?

Foxy Rider · 12 Febrero 2010, 18:08 PM

@^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 ~

^Tifa^ · 12 Febrero 2010, 18:29 PM

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.

Citarsi 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 ...

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.

Skeletron · 12 Febrero 2010, 18:44 PM

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?

Skeletron · 12 Febrero 2010, 19:17 PM

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)??

^Tifa^ · 12 Febrero 2010, 20:08 PM

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.

CitarDigamos que perdería MUCHISIMAS IMAGENES!!!

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.

Skeletron · 12 Febrero 2010, 20:35 PM

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

Código (sql) [Seleccionar]

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?

^Tifa^ · 12 Febrero 2010, 21:03 PM

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

Código [Seleccionar]

SELECT links FROM tablanoel WHERE hash1='123'

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

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.

Skeletron · 12 Febrero 2010, 21:16 PM

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

^Tifa^ · 12 Febrero 2010, 21:26 PM

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

Jubjub · 12 Febrero 2010, 21:45 PM

CRC32 SI tiene colisiones