1 |
[en] EXPERIMENTAL STUDY OF CONJUNCTIVE QUERIES OPTIMIZATION WITH EXPENSIVE PREDICATES / [pt] ESTUDO EXPERIMENTAL DE ALGORITMOS PARA OTIMIZAÇÃO DE CONSULTAS CONJUNTIVAS COM PREDICADOS CAROSRODRIGO SILVA GUARINO 12 July 2004 (has links)
[pt] As técnicas tradicionais de otimização de consultas em
banco de dados possuem como heurística fundamental a
organização dos predicados de uma consulta em dois tipos
principais: predicados simples e predicados
envolvendo junção(join) de tabelas. Como príncipio geral
considera-se a priori os predicados envolvendo junção bem
mais caros do que os predicados simples, e também que não
existam diferenças significativas entre os tempos de
processamento dos predicados simples, o que leva o
otimizador a executar primeiro os predicados simples(em
uma
ordem qualquer), a fim de se diminuir a quantidade de
tuplas que seriam necessárias à execução da junção. Essa
consideração que se aplica bem à maioria das aplicações
convencionais de banco de dados, passou a não se aplicar
mais à novas aplicações que envolviam o preprocessamento
de
dados e/ou funções complexas nos predicados que não
envolviam junções. Dessa forma esses novos predicados
simples passaram a ter um tempo de processamento não mais
desprezível em relação aos predicados que envolviam
junções
e também em relação a outros predicados simples. Dessa
forma a heurística principal de otimização não se
aplicava
mais e tornou-se necessário o desenvolvimento de novas
técnicas para resolver consultas que envolvessem esse
novo
tipo de predicado, que passou a ser chamado de predicado
caro. O presente trabalho tem dois objetivos principais:
apresentar um framework que possibilite o
desenvolvimento,
teste e análise integrada de algoritmos para o
processamento de predicados caros, e analisar o
desempenho
de quatro implementações de algoritmos baseados na
abordagem Cherry Picking, cujo o objetivo é explorar a
dependência entre os dados que compõem as consultas. Os
experimentos são conduzidos em consultas envolvendo
predicados conjuntivos (AND) e a idéia geral é tentar
avaliar os atributos em uma ordem que minimize o custo de
avaliação geral das tuplas. / [en] Traditional database query optimization technique have as
its
main heuristic the organization of predicates in two main
types: selection
predicates and join predicates. Join predicates are
considered much more
expensive than selection predicates. In additional, it's
also considered that there's no big difference among the
costs of different selection predicates,
what makes the optimizer executes them first in any order,
reducing the number of tuples necessary to execute join
predicates.This assumption, that is well applied in
traditional database applications, becomes invalid
in respect of recent database applications, that executes
complex functions over complex data in selection
predicates. In this cases, selection predicates
are considered more expensive than join predicates and
their costs cannot be considered equivalent anymore. This
makes the main heuristic of push down selections invalid
for these kind of new selection predicates which calls for
new optimization techniques. These type of cue named
expensive predicates. This work has two main objectives:
Present a software that makes possible the development,
test and integrat analisys of different algorithms for
evaluating expensive predicates and analyse the performance
of four algorithm's implementations that are based on
Cherry Picking strategy, which aims at exploring the data
dependency between input values to expensive predicates.
The experiments considered conjunctive(AND) queries, and
the general idea is to try evaluate the attributes in a
order that minimizes the general cost of the tuples.
|
Page generated in 0.0242 seconds