We have a question about MonetDB's quicksort routine. It seems that sometimes the head and tail values in a BAT remain paired and sometimes not after passing the BAT through quicksort. For example, a BAT might have the following values before and after quicksor. (This is an artificial example.)

index H T

-----------------

0 1 0

1 3 0

3 7 1

4 7 0

5 7 2

6 7 0

7 32 3

8 34 0

9 35 4

10 38 0

After MonetDB qsort

index H T

-----------------

0 1 0

1 3 0

3 7 1

4 7 0

5 7 5 <----- Why is this value 5? Why not 2?

6 7 0

7 32 4 <----- Shouldn't it still be 3?

8 34 0

9 35 3 <----- Shouldn't it still be 4?

10 38 0

With some queries, the values seem to move in pairs, but in others, they don't. With some queries, the head-tail pairing seems to be maintained, but with others, it isn't. For example, the first query below apparently preserves the pairing (when run against the TPCH database), but the second query does not (and this happens consistently).

select l_suppkey, l_partkey from lineitem where l_partkey > 150000 order by l_orderkey;

select o_orderkey, o_custkey, o_orderstatus from orders where o_custkey > 40000 and o_custkey < 10000000 order by o_orderkey;

Any light you might throw on this would be very helpful.

Thanks,

Steve Morgan