MFP: uma política eficiente de liberação de memória para o operador físico Hash-Merge Join [Digital]
Dissertação
Português
621.391
Fortaleza, 2007.
Em uma MDBC as técnicas de processamento de consultas devem ser adaptadas para lidarem com a instabilidade do ambiente, assim como limitação de recursos, por exemplo memórias limitadas dos computadores móveis. Vejamos um exemplo: as fontes de dados podem ter as taxas de entregas de tuplas previstas...
Ver mais
Em uma MDBC as técnicas de processamento de consultas devem ser adaptadas para lidarem com a instabilidade do ambiente, assim como limitação de recursos, por exemplo memórias limitadas dos computadores móveis. Vejamos um exemplo: as fontes de dados podem ter as taxas de entregas de tuplas previstas pelo otimizador de consultas, no entanto devido a uma desconexão de uma das fontes de dados da rede sem fio, tal fonte de dados ficará desconectada da rede e por conseqüência, não poderá entregar suas tuplas temporariamente, logo o operador de junção ficará parado(bloqueado).
Para processar consultas em uma MDBC, os algoritmos de junção precisam ter as características seguintes: (1) produção incremental de resultados à medida que os dados são disponibilizados, (2) continuidade no processamento da consulta mesmo que a entrega dos dados esteja bloqueada, e (3) reação a situações de limitação de memória durante a execução da consulta[Erro! A origem da referência não foi encontrada.].
Esse trabalho é propõe uma nova política de liberação de dados da memória, chamada Mobile Flushing Policy(MFP). A política MFP propõe uma otimização da política Adaptive Flushing Policy(AFP), usada pelo algoritmo de junção Hash-Merge Join, mantendo o mesmo objetivo principal, enviar pares de partições para o disco, em caso de ocorrência de overflow de memória.
A política AFP libera pares correspondentes de partições para o disco com base em uma tabela resumo mantida em memória e dois parâmetros: (1) balanceamento de memória e (2) tamanho mínimo de partições. Esta política mantém uma tabela resumo em memória contendo o tamanho de cada partição, o somatório dos tamanhos de cada par de partições de ambas as relações e o tamanho total de partições de cada relação.
A política MFP também libera pares correspondentes de partições para o disco com base em uma constante de balanceamento de memória e uma tabela resumo diferenciada da tabela resumo utilizada pela política AFP. A tabela resumo da nova política tem uma coluna a mais discriminando a diferença da cardinalidade de cada par de partições das relações de entrada.
O objetivo principal da nova coluna é garantir que o par de partições escolhido para ser enviado ao disco deixará a memória balanceada, além de garantir que sempre haverá no mínimo um par de partições a ser enviado ao disco.
Ver menos
Para processar consultas em uma MDBC, os algoritmos de junção precisam ter as características seguintes: (1) produção incremental de resultados à medida que os dados são disponibilizados, (2) continuidade no processamento da consulta mesmo que a entrega dos dados esteja bloqueada, e (3) reação a situações de limitação de memória durante a execução da consulta[Erro! A origem da referência não foi encontrada.].
Esse trabalho é propõe uma nova política de liberação de dados da memória, chamada Mobile Flushing Policy(MFP). A política MFP propõe uma otimização da política Adaptive Flushing Policy(AFP), usada pelo algoritmo de junção Hash-Merge Join, mantendo o mesmo objetivo principal, enviar pares de partições para o disco, em caso de ocorrência de overflow de memória.
A política AFP libera pares correspondentes de partições para o disco com base em uma tabela resumo mantida em memória e dois parâmetros: (1) balanceamento de memória e (2) tamanho mínimo de partições. Esta política mantém uma tabela resumo em memória contendo o tamanho de cada partição, o somatório dos tamanhos de cada par de partições de ambas as relações e o tamanho total de partições de cada relação.
A política MFP também libera pares correspondentes de partições para o disco com base em uma constante de balanceamento de memória e uma tabela resumo diferenciada da tabela resumo utilizada pela política AFP. A tabela resumo da nova política tem uma coluna a mais discriminando a diferença da cardinalidade de cada par de partições das relações de entrada.
O objetivo principal da nova coluna é garantir que o par de partições escolhido para ser enviado ao disco deixará a memória balanceada, além de garantir que sempre haverá no mínimo um par de partições a ser enviado ao disco.
Ver menos
Mobile computers and wireless communication technologies are already a reality in
the modern IT environment, resulting in the paradigm of Mobile Computing.
These mobile devices may have BD and their data may be shared.
However, the junction operators of the conventional search operators do not... Ver mais Mobile computers and wireless communication technologies are already a reality in
the modern IT environment, resulting in the paradigm of Mobile Computing.
These mobile devices may have BD and their data may be shared.
However, the junction operators of the conventional search operators do not take
into account the limitations of a mobility-supporting environment, such as a
disconnection from the communication network, a narrow communication bandwidth,
the battery charge level, etc.
Therefore, the junction algorithms need to be adjusted to the limitations of the
mobile computing in order to render satisfactory results and execute a search requested
by the user within a reasonable period of time.
The necessary characteristics for an algorithm to be executed in a mobilitysupporting
environment are: (1) incremental production of results as the data become
available; (2) continuous processing of the search, even if the delivery of data is
blocked; and (3) reaction to limited memory situations during the execution of the
search [1].
It was evidenced through studies and tests that the Hash-Merge Join (HMJ) is more
efficient to guarantee these 3 characteristics (properties) needed when working with
junctions in an efficient fashion within a mobile computing environment.
When the memory is at its full storage capacity, the HMJ algorithm releases
memory partitions according to the memory status. This adaptation to the memory
status determines the best pair of partitions, being each partition from a different source,
to be sent to the disk in a way that maximizes the time until the next memory overflow.
A memory overflow occurs when the memory reaches its storage capacity.
The aim of this work is to propose a new memory data flushing policy ? MFP. This
policy offers an optimization of the Adaptive Flushing Policy (AFP) while keeping the
same main goal, i.e. to send pairs of partitions to the disk in the event of a memory
overflow.
The AFP releases corresponding pairs of partitions to the disk based on a summary
table kept in memory and on two parameters: (1) memory balance; and (2) minimum
partition size. The summary table in memory contains the size of each partition, the sum
of the individual sizes of each pair of partitions of both lists and the total size of
partitions of each list.
8
The MFP also releases corresponding pairs of partitions to the disk, based on a
constant memory balance and a summary table different from the summary table used
by the AFP. The summary table of this new policy has one more column, which states
the cardinality difference of each pair of partitions of the input lists.
The main goal of this new column is to guarantee that the pair of partitions chosen
to be sent to the disk will always leave a balanced memory, while it guarantees that
there will always be at least one pair of partitions to be sent to the disk. Ver menos
the modern IT environment, resulting in the paradigm of Mobile Computing.
These mobile devices may have BD and their data may be shared.
However, the junction operators of the conventional search operators do not... Ver mais Mobile computers and wireless communication technologies are already a reality in
the modern IT environment, resulting in the paradigm of Mobile Computing.
These mobile devices may have BD and their data may be shared.
However, the junction operators of the conventional search operators do not take
into account the limitations of a mobility-supporting environment, such as a
disconnection from the communication network, a narrow communication bandwidth,
the battery charge level, etc.
Therefore, the junction algorithms need to be adjusted to the limitations of the
mobile computing in order to render satisfactory results and execute a search requested
by the user within a reasonable period of time.
The necessary characteristics for an algorithm to be executed in a mobilitysupporting
environment are: (1) incremental production of results as the data become
available; (2) continuous processing of the search, even if the delivery of data is
blocked; and (3) reaction to limited memory situations during the execution of the
search [1].
It was evidenced through studies and tests that the Hash-Merge Join (HMJ) is more
efficient to guarantee these 3 characteristics (properties) needed when working with
junctions in an efficient fashion within a mobile computing environment.
When the memory is at its full storage capacity, the HMJ algorithm releases
memory partitions according to the memory status. This adaptation to the memory
status determines the best pair of partitions, being each partition from a different source,
to be sent to the disk in a way that maximizes the time until the next memory overflow.
A memory overflow occurs when the memory reaches its storage capacity.
The aim of this work is to propose a new memory data flushing policy ? MFP. This
policy offers an optimization of the Adaptive Flushing Policy (AFP) while keeping the
same main goal, i.e. to send pairs of partitions to the disk in the event of a memory
overflow.
The AFP releases corresponding pairs of partitions to the disk based on a summary
table kept in memory and on two parameters: (1) memory balance; and (2) minimum
partition size. The summary table in memory contains the size of each partition, the sum
of the individual sizes of each pair of partitions of both lists and the total size of
partitions of each list.
8
The MFP also releases corresponding pairs of partitions to the disk, based on a
constant memory balance and a summary table different from the summary table used
by the AFP. The summary table of this new policy has one more column, which states
the cardinality difference of each pair of partitions of the input lists.
The main goal of this new column is to guarantee that the pair of partitions chosen
to be sent to the disk will always leave a balanced memory, while it guarantees that
there will always be at least one pair of partitions to be sent to the disk. Ver menos
Disponibilidade forma física: Existe obra impressa de código : 76546
Disponibilidade forma física: Existe obra em CD-Rom de código : 76598
Brayner, Angelo Roncalli Alencar
Orientador
Brayner, Angelo Roncalli Alencar
Banca examinadora
Farias, Pedro Porfírio Muniz
Banca examinadora
Andrade, Rossana Maria de Castro
Banca examinadora
Universidade de Fortaleza. Programa de Pós-Graduação em Informática Aplicada
Dissertação (mestrado)