Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Métodos de Ejecución Del Join

Tipos de metodos para agilizar la ejecución del Join en una Base de Datos
by

Hendrixs Money

on 5 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Métodos de Ejecución Del Join

Base de datos distribuidas Métodos de ejecución del Join En la ejecución de una operación join, se debe de considerar el costo de procesamiento. En este punto influyen varios factores que se deben de tomar en cuenta, para lograr la elección de la estrategia correcta, dichos factores son: Join por interacción simple Consideraciones: Para explicar este método de ejecución haremos uso de las siguientes relaciones. Relación deposito que cuenta con 10,000 tuplas y relación Clientes que cuenta con 200 clientes Merge Join Realiza operaciones de inserción, actualización o eliminación en una tabla de destino según los resultados de una combinación con una tabla de origen. Hash Join Una función hash h es usada sobre las tuplas de ambas relaciones sobre los atributos básicos del join. Estrategias para procesamiento paralelo Las estrategias antes consideradas asumen que un solo procesador esta disponible para procesar un join. Ahora se vera el caso donde varios procesadores están disponibles para el procesamiento paralelo de un join. Join Paralelo La meta de un algoritmo de join paralelo es dividir los pares de tuplas entre varios procesadores. Cada procesador entonces ejecuta una parte del join. Pipeline multiway join Existe la posibilidad del procesamiento de varios joins en paralelo. Esto es un uso importante en algunos querys que se realizan en el mundo real, particularmente cuando se tienen vistas, que involucran a varias relaciones. •El orden físico de las tuplas en la relación.
•La presencia de índices y el tipo de estos.
•El costo de creación de un índice temporal para el procesamiento de una consulta Supóngase que no se cuentan con índices, y que es necesario examinar todos los pares posibles de tuplas td en depósito y tc en cliente. De esta manera, se examinaría 10000 * 200 = 2000000 pares de tuplas. Se utiliza el siguiente procedimiento para procesar el join. En él se lee cada tupla de la relación depósito, esto requeriría accesar10000 bloques de almacenamiento físico bajo el peor de los casos, considerando que cada una de las tuplas de la relación depósito se encuentra en bloques diferentes. Si se consideran que 20 tuplas de la relación depósito se encuentran almacenadas en un bloque, entonces se tendrán 10000120 = 500 bloques distintos accesados. Iteración orientada a bloques Se obtiene un mayor ahorro en el acceso si se procesa la relación en base a un proceso por bloques en vez de un proceso basado en tuplas. Por ejemplo, puede sincronizar dos tablas insertando, actualizando o eliminando las filas de una tabla según las diferencias que se encuentren en la otra. En aquellos casos en los cuales ninguna relación se encuentra en la memoria principal, es posible realizar un join eficientemente si ambas relaciones se encuentran almacenadas en orden de acuerdo a un atributo por medio del cual se realizara el join. Para ejecutar un merge-join, se requiere de un punto de asociación en cada relación, Estos puntos son direccionados a la primera tupla de cada relación. Los punteros son movidos a lo largo de la relación y si un grupo de tuplas de la relación contiene el mismo valor que el atributo del join, se leen dichas tuplas, puesto que las tuplas están ordenadas, el conjunto de tuplas con el mismo valor estarán consecutivas. Esto permite leer cada tupla una sola vez y en el caso de que las tuplas estén almacenadas de manera ordenada, entonces se leerá cada bloque exactamente una vez. Uso de índices Cuando se utiliza un índice, sin importar la manera en como fueron almacenadas físicamente las tuplas de las relaciones, el join puede ser ejecutado con una reducción de accesos significativa. Frecuentemente los atributos del join forman parte de la llave del índice de una relación. En estos casos se puede considerar una estrategia de join que utiliza estos índices. El uso de índices permite agilizar el acceso a los datos de una tabla. Si se agrega un índice a una tabla se agilizan las búsqueda, también permite trabajar con los datos en un orden determinado, como ver una tabla de clientes ordenada por apellido. Si d es una tupla de la relación deposito y en c es una tupla de la relación clientes entonces d y c serán comparados solo si h(c) = h(d). Si h( c ) ≠ h( d ) , entonces d y c tendrán valores diferentes para nombre-cliente. Sin embargo es posible que d y c tengan valores diferentes para nombre-cliente a pesar de que sus valores en la función hash sean iguales. Three-way Join Ahora supóngase que un join envuelve tres relaciones:
sucursal JN deposito JN cliente
Se asume que dt = 10000, dc, = 200 y ds = 50. No solo se tiene que considerar la estrategia para procesar el join; sino que ahora se debe ver cual se realizara primero- Hay varias estrategias posibles a utilizar. Se procesa el join deposito JN cliente usando alguna de las técnicas antes mencionadas. Considerando que nombre - cliente es la llave para la relación clientes. Si es posible construir un índice para sucursal sobre el atributo nombre-sucursal, se podría procesar lo siguiente:

sucursal JN (deposito JN cliente)

Considerando que nombre - sucursal es la llave para sucursal es posible saber que se examinarán únicamente una tupla de la relación sucursal para cada una de las 10000 tuplas de la operación deposito JN cliente. El número exacto de bloques accesados en esta estrategia depende de la manera en que la operación deposito JN cliente es ejecutada, y la forma en que la relación sucursal es almacenada físicamente. Estrategia 1: Estrategia 2: Es posible ejecutar el join con las tres relaciones sin utilizar índices. Esto requerirá el acceso de 50 * 10000 * 200 posibilidades, es decir un total de 10000000. Estrategia 3: En lugar de procesar dos joins, es posible hacer el proceso de un par de joins en uno solo. La técnica primero requiere la construcción de dos índices:
•En sucursal con nombre-sucursal.
•En cliente con nombre-cliente.
A continuación se considera para cada tupla t en la relación deposito, las correspondientes tuplas dentro de las relaciones clientes y sucursal.
Así, se examinará por cada tupla en depósito - una sola en las otras dos relaciones. La estrategia 3 presenta una forma de realizar una operación que no tiene una correspondencia directa dentro del álgebra relacionar. En cambio, combina 2 operaciones dentro de una operación especial. El costo relativo depende de la forma en como las relaciones son almacenadas físicamente. Antes que nada se debe considerar que:
•Todos los procesadores tienen acceso a todos los discos.
•Todos los procesadores comparten la memoria principal.
Las técnicas que se presentarán a continuación pueden ser adaptadas en otras arquitecturas en las cuales cada procesador tiene su propia memoria privada. En un paso final, el resultado individual de cada procesador es recolectado para producir el resultado final. Idealmente, el trabajo global para procesar el join es dividido equivalente sobre todos los procesadores. Esto sin que ningún procesador caiga en un overhead. Un join paralelo que utiliza N procesadores, tomará 1/N del tiempo que se tardaría en ejecutar el mismo join en un solo procesador. En la practica la velocidad es más dramática por varias razones: •Un overhead ocurre en la partición del trabajo entre procesadores.
•Un overhead ocurre en la recolección de los resultados arrojados por cada uno de los procesadores, para producir el resultado final.
•El esfuerzo hecho para dividir el trabajo equitativamente es una aproximación, ya que algunos procesadores, tienen más trabajo que otros. El resultado final obtenido hasta que el último procesador haya terminado.
•El procesador tal vez tenga que competir por recursos compartidos del sistema. El resultado se retrasa debido a que un procesador espera a que otro procesador libere los recursos. Considere el siguiente join entre cuatro relaciones:
r1JN r2 JN r3 JN r4
Es posible ejecutar t1(r1JNr2) en paralelo con t2(r3JNr4) y cuando este procesotermine se ejecutará:
t1JNt2 Se puede lograr un alto grado de paralelismo si se tiene un "pipeline" que permita a los tres join ejecutarse en paralelo. Se asigna al procesador P1la ejecución de r1JN r2y al procesador P2se asigna r3JNr4. Como las tuplas resultantes del proceso de P1están disponibles para P3, así comolas tuplas resultantes del procesador P2, entonces P3podrá comenzar el proceso (r1 JN r2)JN(r3JNr4) antes de que r1JNr2yr3JNr4hallan terminado. Gracias por su atención!
Full transcript