Optimizacion de consultas paralelas

Bases de Datos Paralelas
Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Contenido

1

Introducci´n o

2

Paralelismo de I/O

3

Paralelismo entre Consultas

4

OPS

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Introducci´n o

Por qu´ tener bases de datosparalelas? e Tipos de arquitecturas:
Memoria Compartida Disco Compartido Sin Compartimento Jer´rquica a

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Paralelismo de I/O

Divisi´n de las relaciones en varios discos (particiones) o Aumento de la velocidad en el acceso a los datos T´cnicas de divisi´n e o
Turno Rotatorio: Asignar la i-esima tupla al Disco i mod n.Asegura distribuci´n homog´nea o e Divisi´n por Asociaci´n: Definir una funci´n o o o F (a1 , ..an ) → Particion Divisi´n por Rangos: Dado un atributo partirlo en rangos y o cada rango se almacena en un disco.

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Comparaci´n entre las t´cnicas de divisi´n o e o

Turno Rotatorio D. Asociaci´n o

Exploraci´n oCompleta Ok Ok

D. Rangos

Ok

Consulta Concreta Deficiente Ok si coinciden con los atributos de F Ok si coinciden con el atributo de divisi´n o

Consulta Rangos Deficiente Deficiente

Ok si coinciden con el atributo de divisi´n o

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Sesgo

La divisi´n entre los discos no es equitativa o Clasificaci´n: o
Sesgo devalores de los atributos: Un determinado valor para un atributo es mas frecuente que otro Sesgo de la divisi´n: Desequilibrio en la carga de la o distribuci´n aunque no haya sesgo en los atributos o

La operaci´n mas larga en paralelo es la que determina el tiempo o total de la operaci´n o

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Paralelismo entreConsultas

Varias transacciones al tiempo El tiempo de una transacci´n es el mismo pero se incrementa o la productividad (throughput) Consideraciones de implementaci´n: o
Coherencia del cache Evitar que dos procesadores modifiquen al tiempo un mismo dato (Protocolos de Bloqueo)

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Paralelismo en Consultas

Los conjuntosson parte constitutiva de las bases de datos y por tanto son susceptibles a ser paralelizables Se pueden hacer en paralelo cada uno de los nodos del ´rbol a de operaciones. Puede presentare paralelismo en o entre operaciones

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Paralelismo en Operaciones

Ordenamiento: Realizar una partici´n de los datos para cada oprocesador (depende del esquema de particionamiento utilizado). Hacer merge de cada una de las partes ordenadas Reuni´n: o
Por divisi´n: Solo para equireuniones y los atributos de reuni´n o o deben ser los mismos del particionamiento. Las dos relaciones deben particionarse con la misma funci´n o rango. Cada o procesador se encarga de seleccionar las tuplas que concuerdan Reuni´n con fragmentos yr´plicas: Para reuniones con o e condiciones de desigualdad Se parte una de las relaciones y se replica la otra en cada procesador. La relaci´n peque˜a suele o n replicarse. En general, se pueden dividir ambas relaciones y construir una “matriz de procesadores”

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Continuaci´n o

Por Divisi´n o

Fragmentos y R´plicase

Carlos A. Olarte (carlosolarte@puj.edu.co) BDII

Bases de Datos Paralelas

Paralelismo en otras Operaciones

Selecci´n: Si la condici´n es una condici´n de o o o particionamiento, cada procesador puede seleccionar algunas tuplas y luego reunirlas Eliminaci´n de duplicados: Utilizar un ordenamiento paralelo y o luego realizar la eliminaci´n o Agregaci´n: Calcular resultados parciales...