

![0_image_0.png](0_image_0.png)

a(name sal proj) :- Emp(name ssn) ^ Payroll(ssn sal) ^ Proj ects(name proj)
our DP algorithm onsiders bushy join trees. However, to improve its planning time, DP

```
applies the heuristi
                     of avoiding 
                                 ross-produ
                                            ts during join enumeration. Thus, in some rare
                                                                                           
 ases DP may not produ
                          e the optimal plan.
                                             

Initial: This is the initial plan generator for PbR. It generates query plans a
                                                                                 
                                                                                  ording to a
                                                                                              

```

random depth-rst sear h parse of the query. The only non-random hoi e is that it pla es

```
sele
    tions as soon as they 
                       an be exe
                                 uted. It is the fastest planner but may produ
                                                                          e very
                                                                               

```

low quality plans.

PbR: We used the Remote-Join-Eval and Join-Swap rules dened in Figure 29. These two rules are suÆ
ient to optimize the queries in the test set. We tested two gradient-

```
des
   ent sear
         h strategies for PbR: rst improvement with four random restarts (PbR-FI),
                                                                

```

and steepest des ent with three random restarts (PbR-SD).

In this experiment we ompare the behavior of Sage, DP, Initial, PbR-FI, and PbR-SD

in a distributed query planning domain as the size of the queries in reases. We generated a

```
syntheti
         domain for the SIMS mediator and dened a set of 
                                                       onjun
                                                             tive queries involving
                                                                                

```

from 1 to 30 relations. The queries have one sele tion on an attribute of ea h table. Ea h

```
information sour
                e 
                   ontains two relations and 
                                             an perform remote operations. Therefore,
                                                                                     

```

the optimal plans involve pushing operations to be evaluated remotely at the sour es.

The results of this experiment are shown in Figure 31. Figure 31(a) shows the planning

```
time, in a logarithmi
                      s
                        ale, for Sage, DP, Initial, PbR-FI, and PbR-SD as the query size
                                                                                         

```

grows. The times for PbR in lude both the generation of all the random initial plans and

```
their rewriting. The times for Initial are the average of the initial plan 
                                                                            onstru
                                                                                    tion a
                                                                                           ross
                                                                                               

```

all restarts of ea h query. Sage is able to solve queries involving up to 6 relations, but larger
