Open Gsperoni97 opened 3 years ago
Hola,
Primero, me gustaría señalar que la idea de esta tarea es que con lo que vimos en clases ustedes puedan proponer índices para las tablas que según ustedes van a hacer que los algoritmos funcionen más rápido. No es necesario señalar un algoritmo en particular, sino que hay que explicar desde la intuición.
Ahora bien, si quieres material particular, revisa el Database Management System de Ramakrishnan, ahí hay un montón de detalles de implementación. El algoritmo que hace join con las tablas ordenadas se llama Merge-sort Join. El algoritmo propone primero ordenar y después checkear las tuplas compatibles. Si hay un B+Tree no es necesario ordenar, y además, si el índice es secundario no importa, porque lo que tienes que hacer es checkear que ids forman parte del resultado, y en caso de que encuentres ids compatibles, vas a buscar la tupla entera a la tabla con índice secundario. Así, el costo de I/O aumenta, pero aún así es mejor que ordenar y hacer el join. por lo mismo, el costo dependerá de cuantas tuplas tengas que ir a buscar, es decir, cuantas tuplas de la tabla con índice secundario formen parte de la respuesta. Sin embargo hay hartas alternativas para usar bien el buffer y traer a memoria la menor cantidad de páginas posibles, pero esto depende del criterio de cada implementador.
Saludos!
Profesor., (1)¿Tendrá algún material para revisar el funcionamiento de estos algoritmos para join?
Adicionalmente entiendo que en el ejemplo final que vimos en la clase lunes 22 se aprovechaba el sorting de las tablas (2)(¿Cómo se llama ese algoritmo?). Sin embargo en ese caso las llaves de ambas relaciones eran primarias de modo que la pregunta es... (3)¿Qué pasaría en el desempeño del algoritmo si el atributo de una de las relaciones es foránea y no primaria como en el ejemplo?
Saludos.,