PDF de programación - OPCOLAPH: Optimizador de Consultas OLAP para Cluster de Bases de Datos basado en Histogramas

CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS

AVANZADOS DEL IPN



DEPARTAMENTO DE COMPUTACIÓN



OPCOLAPH: Optimizador de Consultas OLAP para Cluster de Bases de

Datos basado en Histogramas



Tesis que presenta el



Ing. Eduardo Pérez Rivas



Para obtener el Grado de

Maestro en Ciencias de la Computación



Director de la tesis



Dra. Xiaoou Li Zhang



México, D.F. Diciembre 2012





˝ndice general

1. Introduccin

1.1. Motivacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Planteamiento del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Contribuciones
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Organizacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2. Sistemas de Bases de Datos Paralelas

2.1. Sistemas de Bases de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2. Vista de los Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3. Bases de Datos Relacionales . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4. Almacenamiento y Consultas . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5. Optimizacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.6. Arquitecturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Sistemas de Bases de Datos Paralelas . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2. Arquitecturas de Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3. Arquitecturas de Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4. Distribucin de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.5. Procesamiento de Consultas . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.6. Optimizacin de Consulta . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.7. Balance de Carga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Sistemas OLAP en un SCBD

3.1. Sistemas OLAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Diseæo de la BD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
3
5
7
7

9

9
10
12
16
18
21
25
29

31
32
37
40
41
44
46

49
51
52

ii

˝NDICE GENERAL

3.1.2. Consultas OLAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3. Arquitecturas OLAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Sistemas de Cluster de Bases de Datos para Procesamiento de Consultas OLAP . . .
3.2.1. Distribucin de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. Procesamiento de Consultas con Particionamiento Virtual . . . . . . . . . . .
3.2.3. Balance de Carga DinÆmico
. . . . . . . . . . . . . . . . . . . . . . . . . . .

4. OPCOLAPH: Optimizador de Consultas OLAP para Cluster de Base de Datos

basado en Histogramas
4.1. Sesgo de Datos y Desequilibrio de Carga . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. OPCOLAPH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Arquitectura Propuesta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Estadsticas Complementarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1. Histograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.2. Creacin del Histograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Optimizacin de consultas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . .
4.5.1. Generacin de los Rangos del Particionamiento Virtual
4.5.2. Generacin de Consultas para Ejecucin . . . . . . . . . . . . . . . . . . . . .

56
57
60
60
64
67

69
70
72
73
74
75
77
81
82
84

5. Caso de Estudio

87
87
5.1. SCBD de Prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
5.1.1. ParGres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
5.1.2. Postgres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
5.1.3. Cluster de Computadoras . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
5.1.4. TPC-H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
5.2.1. Consultas de Prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
5.2.2. MØtricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
5.3. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1. Tiempos de Ejecucin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
5.3.2. Aceleracin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.3.3. Mensajes de Balance de Carga . . . . . . . . . . . . . . . . . . . . . . . . . . 102

5.2. Diseæo de los experimentos

6. Conclusiones y Trabajo Futuro

109
6.1. Discusin de Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.2. Trabajo a Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

˝NDICE GENERAL

iii

7. Anexos

113
7.1. GrÆcas Complementarias de Aceleracin . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2. Consultas TPC-H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Bibliograa

137

iv

˝NDICE GENERAL

Captulo 1

Introduccin

Una parte vital de los sistemas informÆticos es el almacenamiento de la informacin. Esta im-
portancia recae en muchas ocasiones en que esta informacin es crtica en los diferentes Æmbitos en
que se utilizan los sistemas informÆticos, ya sea por la importancia en s de los datos almacenados, o
por el costo de los requerimientos de los propios sistemas a los almacenes de datos -que se disponga
de un acceso eciente, que la capacidad de almacenamiento sea adecuado, etc.-. El concepto de base
de datos y su desarrollo se da precisamente de esa necesidad de darle un tratamiento adecuado a
la importancia de los datos para las distintas aplicaciones y los requerimientos que los sistemas en
desarrollo presentan para su correcto tratamiento.

Los Sistemas de Bases de Datos en Paralelo (SBDP) han demostrado su ecacia en diversas
aplicaciones, sin embargo, no terminan de encontrar un Ærea en el cual se vuelvan indispensables o
al menos referente. Esto ha tenido diversas explicaciones con el paso del tiempo. Desde el hardware
necesario y los costos que lo vuelven incosteable para muchos Æmbitos hasta la compleja migracin
que se requiere para muchas aplicaciones que se encuentran funcionando y cuyo benecio no alcanza
a superar el costo que traera con ello una operacin de este tipo.

Como alternativa a las computadoras paralelas y su alto costo, aparece un modelo de cmputo
paralelo llamado Cluster de Computadoras(CC). En Øl se permite crear cmputo paralelo a un
costo bajo, debido a que simplemente funciona con un conjunto de computadoras comunicadas
mediante una red preferentemente de alta velocidad y que ante los usuarios se representa como
una computadora paralela. Si bien es cierto que presenta algunas desventajas como lo es el costo de
comunicacin, es de notar que la alternativa presenta un mayor nœmero de ventajas y que permite
un cmputo paralelo de alto rendimiento.

En el Æmbito de las BDP se comenz a desarrollar un concepto llamado Cluster de Base de
Datos (CBD), cuya arquitectura fsica estÆ basada en un CC y donde en cada nodo se instala un
Sistema Gestor de Base de Datos (SGBD) que se encargarÆ de manejar œnicamente la informacin

2

Introduccin

almacenada en ese nodo. Es fÆcil identicar entonces que para que se pueda trabajar como un SBDP,
es necesario una capa que ejerza la funcin de coordinador entre los SGBD y ofrezca los servicios
de un SBDP a los distintos usuarios. En el desarrollo del concepto, se trabaj el SGBD como una
caja negra que no permitiera ver la informacin sobre el manejo de los datos ni la forma en la que
lo haca, Østo pensando en que pudiera incluso manejar un SGBD distinto cada nodo presente en
el sistema. Buscando entonces crear un SBDP que ofreciera alto rendimiento y gran disponibilidad,
se comienzan a desarrollar mØtodos de paralelismo intra-consulta e inter-consulta que alcancen los
objetivos antes mencionados. Estos mØtodos toman forma en una capa intermedia coordine todos
los nodos presentes en el sistema. Con la conjuncin de dicha capa, los nodos y sus respectivos
SGBD es que se produce el concepto de Sistema de Cluster de Base de Datos (SCBD).

El alto rendimiento se puede alcanzar de una forma simple al crear algœn tipo de replicacin,
ya que esto hace que las peticiones hechas a la capa intermedia sean divididas entre alguna de las
replicas. Sin embargo, el alto rendimiento es un tema un poco mÆs complejo, principalmente porque
se tiene la limitante de la falta de conocimiento de lo que ocurre dentro del SGBD del nodo. Esto
lmita severamente el paralelismo intra-consulta (aquella que paraleliza una œnica consulta), ya que
no se permite una comunicacin de datos entre los n