Procesamiento de Consultas Distribuidas
El procesamiento de consultas distribuidas evalúa consultas sobre datos distribuidos en muchos nodos, aprovechando el paralelismo para la velocidad y minimizando la comunicación de red que domina el costo en un entorno distribuido.
Definition
El procesamiento de consultas distribuidas es la descomposición, optimización y ejecución de una consulta sobre datos ubicados en múltiples sitios o particiones, donde el plan debe coordinar el trabajo entre nodos y minimizar tanto el cálculo como la transferencia de datos entre nodos.
Scope
Este tema cubre cómo se ejecutan las consultas sobre datos particionados y replicados: formas de paralelismo (particionado, en tubería e independiente); estrategias de unión paralelas y distribuidas, como la unión por repartición y la unión por difusión; técnicas de reducción de la comunicación, como la semijoin; y la extensión de la optimización basada en costos para tener en cuenta la transferencia de red y la ubicación de los datos. Trata cómo se descompone y programa una consulta lógica entre nodos. Excluye las decisiones de ubicación de datos y los protocolos de confirmación para transacciones distribuidas.
Core questions
- ¿Qué formas de paralelismo (particionado, en tubería, independiente) puede explotar un plan distribuido?
- ¿Cómo se ejecutan las uniones cuando las entradas están particionadas entre nodos?
- ¿Cómo reduce la semijoin la cantidad de datos enviados entre sitios?
- ¿Cómo cambia la optimización cuando el costo de la red domina?
- ¿Cómo afecta la ubicación de los datos a qué plan es el más económico?
Key concepts
- paralelismo particionado
- paralelismo en tubería
- paralelismo independiente
- unión por repartición (shuffle)
- unión por difusión
- reducción por semijoin
- costo de comunicación
- localización de datos
Key theories
- Paralelismo en la ejecución de consultas
- Los planes distribuidos explotan el paralelismo particionado (el mismo operador se ejecuta en particiones de datos disjuntas), el paralelismo en tubería (los operadores en una cadena se ejecutan concurrentemente) y el paralelismo independiente (subplanes no relacionados se ejecutan a la vez) para reducir el tiempo de respuesta.
- Uniones distribuidas y paralelas
- Las uniones sobre datos particionados utilizan la repartición (mezclando ambas entradas por la clave de unión) o la difusión de una entrada pequeña a todos los nodos; la elección entre ellas depende de los tamaños de las relaciones y de la partición existente.
- Semijoin y minimización de la comunicación
- La semijoin reduce una relación a solo las tuplas que pueden coincidir antes de enviarla a través de la red, reduciendo el costo de comunicación; esta técnica fue central para los primeros procesadores de consultas distribuidas como SDD-1.
Clinical relevance
El procesamiento de consultas distribuidas es lo que permite a los sistemas analíticos responder consultas sobre datos mucho más grandes de lo que cualquier máquina individual podría contener, y las técnicas para minimizar el tráfico de red y maximizar el paralelismo determinan directamente la velocidad de los almacenes de datos y los motores de consulta a gran escala.
History
El procesamiento de consultas distribuidas temprano fue pionero en el sistema SDD-1 alrededor de 1980, que introdujo la reducción de la comunicación basada en semijoin. Las bases de datos paralelas de "shared-nothing" de las décadas de 1980 y 1990, encuestadas por DeWitt y Gray, establecieron las uniones por repartición y difusión y la taxonomía de paralelismo que los motores de consulta distribuidos modernos todavía utilizan.
Key figures
- Philip Bernstein
- David DeWitt
- M. Tamer Özsu
- Patrick Valduriez
Related topics
Seminal works
- bernstein1981
- dewitt1992
- ozsu2011
Frequently asked questions
- ¿Por qué es tan importante el costo de la red en el procesamiento de consultas distribuidas?
- En una base de datos distribuida, el recurso más lento y más disputado suele ser la red entre nodos. El envío de grandes resultados intermedios entre nodos puede dominar el tiempo total de la consulta, por lo que los optimizadores y técnicas como la semijoin se centran en transferir la menor cantidad de datos posible, incluso a costa de un cálculo local adicional.
- ¿Cuándo se utiliza una unión por difusión en lugar de una unión por repartición?
- Una unión por difusión envía una copia de una entrada a cada nodo y es eficiente cuando esa entrada es pequeña. Una unión por repartición (shuffle) redistribuye ambas entradas por la clave de unión entre nodos y se utiliza cuando ambas relaciones son grandes. El optimizador compara el costo de comunicación de la difusión frente a la mezcla para elegir.