Question on Quicksort
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
LS, Could you identify the MonetDB version. Your artificial program is incorrect, because BATs are supposed to have :oid heads for some time now. Please, provide a correct and complete MAL program to assess your issue. regards, Martin On 6/4/13 3:40 AM, Stephen P. Morgan wrote:
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
_______________________________________________ users-list mailing list users-list@monetdb.org http://mail.monetdb.org/mailman/listinfo/users-list
Hi Martin,
My questions were poorly worded. I apologize. MonetDB is working correctly. We're trying to understand how the quicksort function works, because it doesn't seem to work the way we imagined that it would. I believe Masood described to you why this is of some interest to us.
Here's a description of our environment. I believe it is a MonetDB 11.15.3 release system but I'm not sure. We're working with a TPCH scale factor 20 database and the query:
select l_orderkey, l_suppkey, l_partkey from lineitem where l_partkey > 3000000 order by l_orderkey;
We added a function print2IntAry() to gdk_batop.c to print a certain number of elements of an int BAT. The function is defined as:
void print2IntAry(int* ary1, int* ary2, int rLen, const char* msg)
{
printf("print2IntAry: %s\n", msg);
for (int i=0; i
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
_______________________________________________ users-list mailing list users-list@monetdb.org http://mail.monetdb.org/mailman/listinfo/users-list
_______________________________________________ users-list mailing list users-list@monetdb.org http://mail.monetdb.org/mailman/listinfo/users-list
Hi Martin,
We've found out the answer through experimentation. Thanks for your time.
Steve Morgan
--- On Tue, 6/4/13, Stephen P. Morgan
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
_______________________________________________ users-list mailing list users-list@monetdb.org http://mail.monetdb.org/mailman/listinfo/users-list
_______________________________________________ users-list mailing list users-list@monetdb.org http://mail.monetdb.org/mailman/listinfo/users-list -----Inline Attachment Follows----- _______________________________________________ users-list mailing list users-list@monetdb.org http://mail.monetdb.org/mailman/listinfo/users-list
participants (2)
-
Martin Kersten -
Stephen P. Morgan