Next: Summary Up: Experimental Evaluation Previous: Influence of the Condensation

Impact of Black-Out Preprocessing

In section 9.4, we presented the black-out preprocessing strategy that essentially scraps all entries of an IP-table I(R) whose associated $o_{\scriptscriptstyle R}(t)$ value lies beyond a certain threshold value Y . These entries are considered as unsuitable to provide a good breakpoint for a partition. Therefore, an underflow strategy cannot choose such unsuitable breakpoints if the IP-tables that it uses have been preprocessed in this way.

The experiments of section 10.2 showed discouraging results for black-out preprocessing. However, this might be due to a bad choice for the threshold Y which was chosen to be the average of all $o_{\scriptscriptstyle R}(t)$ values in the respective IP-table I(R) according to equation (10.1). Here, we want to look at black-out preprocessing in more detail. Experiments were set up in which the threshold Y was varied. For practical purposes we express Y in percent of . A value of 70%, for example, is supposed to mean that . The respective Y' threshold was set to be 10% below the corresponding X_R and X_Q values, i.e.

Table 10.22 shows the performance results on the parallel and on the single-processor architectures. Figures 10.51 and 10.52 show the differences with respect to the time that is required if black-out preprocessing is not used in the partitioning process.

Not surprisingly, we find that the lower the threshold Y is, the higher is the impact of black-preprocessing on the performances, at least on the parallel architecture. The performance gains, if there are any, remain marginal with 5% at best. From figures 10.51 and 10.52 we can see that black-out preprocessing is often beneficial for the performances for the `mixed' join $R \Join_{\scriptscriptstyle C}Q$ while we find a negative effect on the performances for the `self' joins and . The latter effect is due to two slightly different reasons:

The periodic profile of R, especially with many sharply rising flanks, already provides many opportunities for choosing `good' breakpoints, i.e. ones with a low $o_{\scriptscriptstyle R}(t)$ value. Therefore, most X_R and X_Q values cause the ordinary primary underflow strategy (i.e. without black-out preprocessing) to produce breakpoints that lie on or close to the bottoms of the valleys. This was, for example, the case in our experiments. But this means that ordinary primary underflow partitioning already produces a good partition. The introduction of black-out preprocessing can then only have a negative effect by restricting the primary underflow strategies' choice on breakpoints and leads to a bad load balance . This also explains that there is hardly any negative impact on the performances for on the single-processor machine because there, the load balance is by far not as important.
The non-periodic profile of Q forces the ordinary primary underflow strategy to choose breakpoints with high values. Black-out preprocessing can change this but possibly on the expense of worsening the load balance between the fragments. However, we have already seen that the load balance is the most important factor for the performances on the parallel architecture. Again, the negative impact is reduced on the single-processor machine which underlines the significance of the load balance factor.

In contrast to the joins that have been discussed above, we note that the performances for the join $R \Join_{\scriptscriptstyle C}Q$ are positively affected by black-out preprocessing, although one has to stress that the improvement is modest. It is due to the reduction of overlapping intervals - the initial idea of black-out preprocessing - without affecting the load balance negatively.

In summary, we can conclude that the positive influence of black-out preprocessing are lower than we had hoped for when designing this strategy in section 9.4. In a considerable amount of cases it restricts the primary underflow strategy too much in its choice and causes a load balance which is worse than in the original case. This is usually penalised when a join is processed on a parallel architecture. In contrast, there is a modest benefit in most cases if the join is processed sequentially.

**Table:** Performance results (in sec.) depending on Y for the three joins and the primary underflow strategy using black-out preprocessing.
	3c!width 2ptparallel architecture	3c\|single-processor machine
Y		$R \Join_{\scriptscriptstyle C}Q$			$R \Join_{\scriptscriptstyle C}Q$
(in % of )	1c\|(Join 1)	1c\|(Join 2)	1c!width 2pt(Join 3)	1c\|(Join 1)	1c\|(Join 2)	1c\|(Join 3)
no black-out	716	1141	896	7898	5560	10410
120%	716	1150	896	7898	5562	10410
110%	716	1133	896	7898	5384	10410
100%	712	1133	898	7892	5385	10411
90%	723	1140	895	7889	5564	10412
80%	737	1132	901	7917	5384	10414
70%	754	1132	904	7926	5376	10413
60%	750	1142	910	7904	5560	10416
50%	752	1092	911	7908	5571	10420
40%	764	1087	911	7909	5578	10443
30%	781	1091	937	7936	5594	10475

**Figure:** Performance differences for primary underflow partitioning with black-out preprocessing on the parallel architecture.

**Figure:** Performance differences for primary underflow partitioning with black-out preprocessing on the single-processor machine.

Next: Summary Up: Experimental Evaluation Previous: Influence of the Condensation

Thomas Zurek