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<rLen; i++) { printf("[%d]: %d\n", ary1[i], ary2[i]); } } It prints the values to the merovingian.log. We modified do_sort() to call print2IntAry() as follows: static gdk_return do_sort(void *h, void *t, const void *base, size_t nn, int hs, int ts, int tpe, int reverse, int stable) { size_t n; n = nn; printf("do_sort: nn = %d tpe = %d\n", (int) nn, tpe); fflush(stdout); if (tpe == TYPE_int) { print2IntAry(h, t, 100, "Before sorting:"); fflush(stdout); } if (n <= 1) /* trivially sorted */ return GDK_SUCCEED; if (reverse) { . . GDKqsort_rev() . } else { . . GDKqsort() . } if (tpe == TYPE_int) { print2IntAry(h, t, 100, "After sorting:"); fflush(stdout); } return GDK_SUCCEED; } After running this, the merovingian log contains the following: 2013-06-04 10:33:11 MSG merovingian[1806]: target connection is on local UNIX domain socket, passing on filedescriptor instead of proxying 2013-06-04 10:34:18 MSG db1[1811]: do_sort: nn = 30008780 tpe = 5 2013-06-04 10:34:18 MSG db1[1811]: print2IntAry: Before sorting: 2013-06-04 10:34:18 MSG db1[1811]: [1]: 0 2013-06-04 10:34:18 MSG db1[1811]: [3]: 0 2013-06-04 10:34:18 MSG db1[1811]: [7]: 1 2013-06-04 10:34:18 MSG db1[1811]: [7]: 0 2013-06-04 10:34:18 MSG db1[1811]: [7]: 2 2013-06-04 10:34:18 MSG db1[1811]: [7]: 0 2013-06-04 10:34:18 MSG db1[1811]: [32]: 3 2013-06-04 10:34:18 MSG db1[1811]: [34]: 0 2013-06-04 10:34:18 MSG db1[1811]: [35]: 4 2013-06-04 10:34:18 MSG db1[1811]: [38]: 0 2013-06-04 10:34:18 MSG db1[1811]: [39]: 5 2013-06-04 10:34:18 MSG db1[1811]: [66]: 0 2013-06-04 10:34:18 MSG db1[1811]: [67]: 6 2013-06-04 10:34:18 MSG db1[1811]: [67]: 0 2013-06-04 10:34:18 MSG db1[1811]: [68]: 7 2013-06-04 10:34:18 MSG db1[1811]: [70]: 0 2013-06-04 10:34:18 MSG db1[1811]: [70]: 8 2013-06-04 10:34:18 MSG db1[1811]: [71]: 0 2013-06-04 10:34:18 MSG db1[1811]: [98]: 9 2013-06-04 10:34:18 MSG db1[1811]: [101]: 0 2013-06-04 10:34:18 MSG db1[1811]: [102]: 10 2013-06-04 10:34:18 MSG db1[1811]: [102]: 0 2013-06-04 10:34:18 MSG db1[1811]: [103]: 11 2013-06-04 10:34:18 MSG db1[1811]: [129]: 0 2013-06-04 10:34:18 MSG db1[1811]: [129]: 12 2013-06-04 10:34:18 MSG db1[1811]: [131]: 0 2013-06-04 10:34:18 MSG db1[1811]: [131]: 13 2013-06-04 10:34:18 MSG db1[1811]: [133]: 0 2013-06-04 10:34:18 MSG db1[1811]: [134]: 14 2013-06-04 10:34:18 MSG db1[1811]: [134]: 0 2013-06-04 10:34:18 MSG db1[1811]: [135]: 15 2013-06-04 10:34:18 MSG db1[1811]: [135]: 0 2013-06-04 10:34:18 MSG db1[1811]: [162]: 16 2013-06-04 10:34:18 MSG db1[1811]: [163]: 0 2013-06-04 10:34:18 MSG db1[1811]: [163]: 17 2013-06-04 10:34:18 MSG db1[1811]: [163]: 0 2013-06-04 10:34:18 MSG db1[1811]: [165]: 18 2013-06-04 10:34:18 MSG db1[1811]: [165]: 0 2013-06-04 10:34:18 MSG db1[1811]: [166]: 19 2013-06-04 10:34:18 MSG db1[1811]: [167]: 0 2013-06-04 10:34:18 MSG db1[1811]: [192]: 20 2013-06-04 10:34:18 MSG db1[1811]: [192]: 0 2013-06-04 10:34:18 MSG db1[1811]: [193]: 21 2013-06-04 10:34:18 MSG db1[1811]: [194]: 0 2013-06-04 10:34:18 MSG db1[1811]: [194]: 22 2013-06-04 10:34:18 MSG db1[1811]: [197]: 0 2013-06-04 10:34:18 MSG db1[1811]: [197]: 23 2013-06-04 10:34:18 MSG db1[1811]: [224]: 0 2013-06-04 10:34:18 MSG db1[1811]: [224]: 24 2013-06-04 10:34:18 MSG db1[1811]: [224]: 0 2013-06-04 10:34:18 MSG db1[1811]: [225]: 25 2013-06-04 10:34:18 MSG db1[1811]: [225]: 0 2013-06-04 10:34:18 MSG db1[1811]: [227]: 26 2013-06-04 10:34:18 MSG db1[1811]: [227]: 0 2013-06-04 10:34:18 MSG db1[1811]: [229]: 27 2013-06-04 10:34:18 MSG db1[1811]: [229]: 0 2013-06-04 10:34:18 MSG db1[1811]: [230]: 28 2013-06-04 10:34:18 MSG db1[1811]: [230]: 0 2013-06-04 10:34:18 MSG db1[1811]: [231]: 29 2013-06-04 10:34:18 MSG db1[1811]: [231]: 0 2013-06-04 10:34:18 MSG db1[1811]: [258]: 30 2013-06-04 10:34:18 MSG db1[1811]: [258]: 0 2013-06-04 10:34:18 MSG db1[1811]: [259]: 31 2013-06-04 10:34:18 MSG db1[1811]: [259]: 0 2013-06-04 10:34:18 MSG db1[1811]: [259]: 32 2013-06-04 10:34:18 MSG db1[1811]: [260]: 0 2013-06-04 10:34:18 MSG db1[1811]: [260]: 33 2013-06-04 10:34:18 MSG db1[1811]: [261]: 0 2013-06-04 10:34:18 MSG db1[1811]: [262]: 34 2013-06-04 10:34:18 MSG db1[1811]: [288]: 0 2013-06-04 10:34:18 MSG db1[1811]: [289]: 35 2013-06-04 10:34:18 MSG db1[1811]: [292]: 0 2013-06-04 10:34:18 MSG db1[1811]: [293]: 36 2013-06-04 10:34:18 MSG db1[1811]: [295]: 0 2013-06-04 10:34:18 MSG db1[1811]: [320]: 37 2013-06-04 10:34:18 MSG db1[1811]: [322]: 0 2013-06-04 10:34:18 MSG db1[1811]: [322]: 38 2013-06-04 10:34:18 MSG db1[1811]: [323]: 0 2013-06-04 10:34:18 MSG db1[1811]: [324]: 39 2013-06-04 10:34:18 MSG db1[1811]: [325]: 0 2013-06-04 10:34:18 MSG db1[1811]: [325]: 40 2013-06-04 10:34:18 MSG db1[1811]: [326]: 0 2013-06-04 10:34:18 MSG db1[1811]: [326]: 41 2013-06-04 10:34:18 MSG db1[1811]: [326]: 0 2013-06-04 10:34:18 MSG db1[1811]: [354]: 42 2013-06-04 10:34:18 MSG db1[1811]: [357]: 0 2013-06-04 10:34:18 MSG db1[1811]: [357]: 43 2013-06-04 10:34:18 MSG db1[1811]: [358]: 0 2013-06-04 10:34:18 MSG db1[1811]: [358]: 44 2013-06-04 10:34:18 MSG db1[1811]: [358]: 0 2013-06-04 10:34:18 MSG db1[1811]: [358]: 45 2013-06-04 10:34:18 MSG db1[1811]: [359]: 0 2013-06-04 10:34:18 MSG db1[1811]: [359]: 46 2013-06-04 10:34:18 MSG db1[1811]: [359]: 0 2013-06-04 10:34:18 MSG db1[1811]: [384]: 47 2013-06-04 10:34:18 MSG db1[1811]: [384]: 0 2013-06-04 10:34:18 MSG db1[1811]: [385]: 48 2013-06-04 10:34:18 MSG db1[1811]: [386]: 0 2013-06-04 10:34:18 MSG db1[1811]: [387]: 49 2013-06-04 10:34:18 MSG db1[1811]: [389]: 0 2013-06-04 10:34:23 MSG db1[1811]: do_sort: B 2013-06-04 10:34:23 MSG db1[1811]: print2IntAry: After sorting: 2013-06-04 10:34:23 MSG db1[1811]: [1]: 0 2013-06-04 10:34:23 MSG db1[1811]: [3]: 0 2013-06-04 10:34:23 MSG db1[1811]: [7]: 1 2013-06-04 10:34:23 MSG db1[1811]: [7]: 0 2013-06-04 10:34:23 MSG db1[1811]: [7]: 5 <--- e.g. change from 2 to 5 2013-06-04 10:34:23 MSG db1[1811]: [7]: 0 2013-06-04 10:34:23 MSG db1[1811]: [32]: 4 2013-06-04 10:34:23 MSG db1[1811]: [34]: 0 2013-06-04 10:34:23 MSG db1[1811]: [35]: 3 2013-06-04 10:34:23 MSG db1[1811]: [38]: 0 2013-06-04 10:34:23 MSG db1[1811]: [39]: 2 2013-06-04 10:34:23 MSG db1[1811]: [66]: 0 2013-06-04 10:34:23 MSG db1[1811]: [67]: 6 2013-06-04 10:34:23 MSG db1[1811]: [67]: 0 2013-06-04 10:34:23 MSG db1[1811]: [68]: 7 2013-06-04 10:34:23 MSG db1[1811]: [70]: 0 2013-06-04 10:34:23 MSG db1[1811]: [70]: 8 2013-06-04 10:34:23 MSG db1[1811]: [71]: 0 2013-06-04 10:34:23 MSG db1[1811]: [98]: 9 2013-06-04 10:34:23 MSG db1[1811]: [101]: 0 2013-06-04 10:34:23 MSG db1[1811]: [102]: 10 2013-06-04 10:34:23 MSG db1[1811]: [102]: 0 2013-06-04 10:34:23 MSG db1[1811]: [103]: 11 2013-06-04 10:34:23 MSG db1[1811]: [129]: 0 2013-06-04 10:34:23 MSG db1[1811]: [129]: 13 2013-06-04 10:34:23 MSG db1[1811]: [131]: 0 2013-06-04 10:34:23 MSG db1[1811]: [131]: 12 2013-06-04 10:34:23 MSG db1[1811]: [133]: 0 2013-06-04 10:34:23 MSG db1[1811]: [134]: 14 2013-06-04 10:34:23 MSG db1[1811]: [134]: 0 2013-06-04 10:34:23 MSG db1[1811]: [135]: 16 2013-06-04 10:34:23 MSG db1[1811]: [135]: 0 2013-06-04 10:34:23 MSG db1[1811]: [162]: 15 2013-06-04 10:34:23 MSG db1[1811]: [163]: 0 2013-06-04 10:34:23 MSG db1[1811]: [163]: 17 2013-06-04 10:34:23 MSG db1[1811]: [163]: 0 2013-06-04 10:34:23 MSG db1[1811]: [165]: 18 2013-06-04 10:34:23 MSG db1[1811]: [165]: 0 2013-06-04 10:34:23 MSG db1[1811]: [166]: 19 2013-06-04 10:34:23 MSG db1[1811]: [167]: 0 2013-06-04 10:34:23 MSG db1[1811]: [192]: 21 2013-06-04 10:34:23 MSG db1[1811]: [192]: 0 2013-06-04 10:34:23 MSG db1[1811]: [193]: 20 2013-06-04 10:34:23 MSG db1[1811]: [194]: 0 2013-06-04 10:34:23 MSG db1[1811]: [194]: 22 2013-06-04 10:34:23 MSG db1[1811]: [197]: 0 2013-06-04 10:34:23 MSG db1[1811]: [197]: 24 2013-06-04 10:34:23 MSG db1[1811]: [224]: 0 2013-06-04 10:34:23 MSG db1[1811]: [224]: 23 2013-06-04 10:34:23 MSG db1[1811]: [224]: 0 2013-06-04 10:34:23 MSG db1[1811]: [225]: 26 2013-06-04 10:34:23 MSG db1[1811]: [225]: 0 2013-06-04 10:34:23 MSG db1[1811]: [227]: 25 2013-06-04 10:34:23 MSG db1[1811]: [227]: 0 2013-06-04 10:34:23 MSG db1[1811]: [229]: 27 2013-06-04 10:34:23 MSG db1[1811]: [229]: 0 2013-06-04 10:34:23 MSG db1[1811]: [230]: 29 2013-06-04 10:34:23 MSG db1[1811]: [230]: 0 2013-06-04 10:34:23 MSG db1[1811]: [231]: 28 2013-06-04 10:34:23 MSG db1[1811]: [231]: 0 2013-06-04 10:34:23 MSG db1[1811]: [258]: 31 2013-06-04 10:34:23 MSG db1[1811]: [258]: 0 2013-06-04 10:34:23 MSG db1[1811]: [259]: 30 2013-06-04 10:34:23 MSG db1[1811]: [259]: 0 2013-06-04 10:34:23 MSG db1[1811]: [259]: 32 2013-06-04 10:34:23 MSG db1[1811]: [260]: 0 2013-06-04 10:34:23 MSG db1[1811]: [260]: 35 2013-06-04 10:34:23 MSG db1[1811]: [261]: 0 2013-06-04 10:34:23 MSG db1[1811]: [262]: 34 2013-06-04 10:34:23 MSG db1[1811]: [288]: 0 2013-06-04 10:34:23 MSG db1[1811]: [289]: 33 2013-06-04 10:34:23 MSG db1[1811]: [292]: 0 2013-06-04 10:34:23 MSG db1[1811]: [293]: 37 2013-06-04 10:34:23 MSG db1[1811]: [295]: 0 2013-06-04 10:34:23 MSG db1[1811]: [320]: 36 2013-06-04 10:34:23 MSG db1[1811]: [322]: 0 2013-06-04 10:34:23 MSG db1[1811]: [322]: 38 2013-06-04 10:34:23 MSG db1[1811]: [323]: 0 2013-06-04 10:34:23 MSG db1[1811]: [324]: 39 2013-06-04 10:34:23 MSG db1[1811]: [325]: 0 2013-06-04 10:34:23 MSG db1[1811]: [325]: 41 2013-06-04 10:34:23 MSG db1[1811]: [326]: 0 2013-06-04 10:34:23 MSG db1[1811]: [326]: 40 2013-06-04 10:34:23 MSG db1[1811]: [326]: 0 2013-06-04 10:34:23 MSG db1[1811]: [354]: 42 2013-06-04 10:34:23 MSG db1[1811]: [357]: 0 2013-06-04 10:34:23 MSG db1[1811]: [357]: 44 2013-06-04 10:34:23 MSG db1[1811]: [358]: 0 2013-06-04 10:34:23 MSG db1[1811]: [358]: 43 2013-06-04 10:34:23 MSG db1[1811]: [358]: 0 2013-06-04 10:34:23 MSG db1[1811]: [358]: 46 2013-06-04 10:34:23 MSG db1[1811]: [359]: 0 2013-06-04 10:34:23 MSG db1[1811]: [359]: 45 2013-06-04 10:34:23 MSG db1[1811]: [359]: 0 2013-06-04 10:34:23 MSG db1[1811]: [384]: 49 2013-06-04 10:34:23 MSG db1[1811]: [384]: 0 2013-06-04 10:34:23 MSG db1[1811]: [385]: 48 2013-06-04 10:34:23 MSG db1[1811]: [386]: 0 2013-06-04 10:34:23 MSG db1[1811]: [387]: 47 2013-06-04 10:34:23 MSG db1[1811]: [389]: 0 We don't understand why, e.g., qsort() apparently changed the tail associated with the value 7 from 2 to 5. We expect qsort to rearrange items in the list, but thought that the head and tails were linked, so they would be moved together as a unit. Can you give us a rough explanation why we are seeing this? Better yet, can you explain the relationship between the head and tail members? Thanks, Steve Morgan --- On Mon, 6/3/13, Martin Kersten <Martin.Kersten@cwi.nl> wrote: From: Martin Kersten <Martin.Kersten@cwi.nl> Subject: Re: Question on Quicksort To: users-list@monetdb.org Date: Monday, June 3, 2013, 11:29 PM 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
_______________________________________________ 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 <stephen_p_morgan@sbcglobal.net> wrote: From: Stephen P. Morgan <stephen_p_morgan@sbcglobal.net> Subject: Re: Question on Quicksort To: "Communication channel for MonetDB users" <users-list@monetdb.org> Date: Tuesday, June 4, 2013, 11:29 AM 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<rLen; i++) { printf("[%d]: %d\n", ary1[i], ary2[i]); } } It prints the values to the merovingian.log. We modified do_sort() to call print2IntAry() as follows: static gdk_return do_sort(void *h, void *t, const void *base, size_t nn, int hs, int ts, int tpe, int reverse, int stable) { size_t n; n = nn; printf("do_sort: nn = %d tpe = %d\n", (int) nn, tpe); fflush(stdout); if (tpe == TYPE_int) { print2IntAry(h, t, 100, "Before sorting:"); fflush(stdout); } if (n <= 1) /* trivially sorted */ return GDK_SUCCEED; if (reverse) { . . GDKqsort_rev() . } else { . . GDKqsort() . } if (tpe == TYPE_int) { print2IntAry(h, t, 100, "After sorting:"); fflush(stdout); } return GDK_SUCCEED; } After running this, the merovingian log contains the following: 2013-06-04 10:33:11 MSG merovingian[1806]: target connection is on local UNIX domain socket, passing on filedescriptor instead of proxying 2013-06-04 10:34:18 MSG db1[1811]: do_sort: nn = 30008780 tpe = 5 2013-06-04 10:34:18 MSG db1[1811]: print2IntAry: Before sorting: 2013-06-04 10:34:18 MSG db1[1811]: [1]: 0 2013-06-04 10:34:18 MSG db1[1811]: [3]: 0 2013-06-04 10:34:18 MSG db1[1811]: [7]: 1 2013-06-04 10:34:18 MSG db1[1811]: [7]: 0 2013-06-04 10:34:18 MSG db1[1811]: [7]: 2 2013-06-04 10:34:18 MSG db1[1811]: [7]: 0 2013-06-04 10:34:18 MSG db1[1811]: [32]: 3 2013-06-04 10:34:18 MSG db1[1811]: [34]: 0 2013-06-04 10:34:18 MSG db1[1811]: [35]: 4 2013-06-04 10:34:18 MSG db1[1811]: [38]: 0 2013-06-04 10:34:18 MSG db1[1811]: [39]: 5 2013-06-04 10:34:18 MSG db1[1811]: [66]: 0 2013-06-04 10:34:18 MSG db1[1811]: [67]: 6 2013-06-04 10:34:18 MSG db1[1811]: [67]: 0 2013-06-04 10:34:18 MSG db1[1811]: [68]: 7 2013-06-04 10:34:18 MSG db1[1811]: [70]: 0 2013-06-04 10:34:18 MSG db1[1811]: [70]: 8 2013-06-04 10:34:18 MSG db1[1811]: [71]: 0 2013-06-04 10:34:18 MSG db1[1811]: [98]: 9 2013-06-04 10:34:18 MSG db1[1811]: [101]: 0 2013-06-04 10:34:18 MSG db1[1811]: [102]: 10 2013-06-04 10:34:18 MSG db1[1811]: [102]: 0 2013-06-04 10:34:18 MSG db1[1811]: [103]: 11 2013-06-04 10:34:18 MSG db1[1811]: [129]: 0 2013-06-04 10:34:18 MSG db1[1811]: [129]: 12 2013-06-04 10:34:18 MSG db1[1811]: [131]: 0 2013-06-04 10:34:18 MSG db1[1811]: [131]: 13 2013-06-04 10:34:18 MSG db1[1811]: [133]: 0 2013-06-04 10:34:18 MSG db1[1811]: [134]: 14 2013-06-04 10:34:18 MSG db1[1811]: [134]: 0 2013-06-04 10:34:18 MSG db1[1811]: [135]: 15 2013-06-04 10:34:18 MSG db1[1811]: [135]: 0 2013-06-04 10:34:18 MSG db1[1811]: [162]: 16 2013-06-04 10:34:18 MSG db1[1811]: [163]: 0 2013-06-04 10:34:18 MSG db1[1811]: [163]: 17 2013-06-04 10:34:18 MSG db1[1811]: [163]: 0 2013-06-04 10:34:18 MSG db1[1811]: [165]: 18 2013-06-04 10:34:18 MSG db1[1811]: [165]: 0 2013-06-04 10:34:18 MSG db1[1811]: [166]: 19 2013-06-04 10:34:18 MSG db1[1811]: [167]: 0 2013-06-04 10:34:18 MSG db1[1811]: [192]: 20 2013-06-04 10:34:18 MSG db1[1811]: [192]: 0 2013-06-04 10:34:18 MSG db1[1811]: [193]: 21 2013-06-04 10:34:18 MSG db1[1811]: [194]: 0 2013-06-04 10:34:18 MSG db1[1811]: [194]: 22 2013-06-04 10:34:18 MSG db1[1811]: [197]: 0 2013-06-04 10:34:18 MSG db1[1811]: [197]: 23 2013-06-04 10:34:18 MSG db1[1811]: [224]: 0 2013-06-04 10:34:18 MSG db1[1811]: [224]: 24 2013-06-04 10:34:18 MSG db1[1811]: [224]: 0 2013-06-04 10:34:18 MSG db1[1811]: [225]: 25 2013-06-04 10:34:18 MSG db1[1811]: [225]: 0 2013-06-04 10:34:18 MSG db1[1811]: [227]: 26 2013-06-04 10:34:18 MSG db1[1811]: [227]: 0 2013-06-04 10:34:18 MSG db1[1811]: [229]: 27 2013-06-04 10:34:18 MSG db1[1811]: [229]: 0 2013-06-04 10:34:18 MSG db1[1811]: [230]: 28 2013-06-04 10:34:18 MSG db1[1811]: [230]: 0 2013-06-04 10:34:18 MSG db1[1811]: [231]: 29 2013-06-04 10:34:18 MSG db1[1811]: [231]: 0 2013-06-04 10:34:18 MSG db1[1811]: [258]: 30 2013-06-04 10:34:18 MSG db1[1811]: [258]: 0 2013-06-04 10:34:18 MSG db1[1811]: [259]: 31 2013-06-04 10:34:18 MSG db1[1811]: [259]: 0 2013-06-04 10:34:18 MSG db1[1811]: [259]: 32 2013-06-04 10:34:18 MSG db1[1811]: [260]: 0 2013-06-04 10:34:18 MSG db1[1811]: [260]: 33 2013-06-04 10:34:18 MSG db1[1811]: [261]: 0 2013-06-04 10:34:18 MSG db1[1811]: [262]: 34 2013-06-04 10:34:18 MSG db1[1811]: [288]: 0 2013-06-04 10:34:18 MSG db1[1811]: [289]: 35 2013-06-04 10:34:18 MSG db1[1811]: [292]: 0 2013-06-04 10:34:18 MSG db1[1811]: [293]: 36 2013-06-04 10:34:18 MSG db1[1811]: [295]: 0 2013-06-04 10:34:18 MSG db1[1811]: [320]: 37 2013-06-04 10:34:18 MSG db1[1811]: [322]: 0 2013-06-04 10:34:18 MSG db1[1811]: [322]: 38 2013-06-04 10:34:18 MSG db1[1811]: [323]: 0 2013-06-04 10:34:18 MSG db1[1811]: [324]: 39 2013-06-04 10:34:18 MSG db1[1811]: [325]: 0 2013-06-04 10:34:18 MSG db1[1811]: [325]: 40 2013-06-04 10:34:18 MSG db1[1811]: [326]: 0 2013-06-04 10:34:18 MSG db1[1811]: [326]: 41 2013-06-04 10:34:18 MSG db1[1811]: [326]: 0 2013-06-04 10:34:18 MSG db1[1811]: [354]: 42 2013-06-04 10:34:18 MSG db1[1811]: [357]: 0 2013-06-04 10:34:18 MSG db1[1811]: [357]: 43 2013-06-04 10:34:18 MSG db1[1811]: [358]: 0 2013-06-04 10:34:18 MSG db1[1811]: [358]: 44 2013-06-04 10:34:18 MSG db1[1811]: [358]: 0 2013-06-04 10:34:18 MSG db1[1811]: [358]: 45 2013-06-04 10:34:18 MSG db1[1811]: [359]: 0 2013-06-04 10:34:18 MSG db1[1811]: [359]: 46 2013-06-04 10:34:18 MSG db1[1811]: [359]: 0 2013-06-04 10:34:18 MSG db1[1811]: [384]: 47 2013-06-04 10:34:18 MSG db1[1811]: [384]: 0 2013-06-04 10:34:18 MSG db1[1811]: [385]: 48 2013-06-04 10:34:18 MSG db1[1811]: [386]: 0 2013-06-04 10:34:18 MSG db1[1811]: [387]: 49 2013-06-04 10:34:18 MSG db1[1811]: [389]: 0 2013-06-04 10:34:23 MSG db1[1811]: do_sort: B 2013-06-04 10:34:23 MSG db1[1811]: print2IntAry: After sorting: 2013-06-04 10:34:23 MSG db1[1811]: [1]: 0 2013-06-04 10:34:23 MSG db1[1811]: [3]: 0 2013-06-04 10:34:23 MSG db1[1811]: [7]: 1 2013-06-04 10:34:23 MSG db1[1811]: [7]: 0 2013-06-04 10:34:23 MSG db1[1811]: [7]: 5 <--- e.g. change from 2 to 5 2013-06-04 10:34:23 MSG db1[1811]: [7]: 0 2013-06-04 10:34:23 MSG db1[1811]: [32]: 4 2013-06-04 10:34:23 MSG db1[1811]: [34]: 0 2013-06-04 10:34:23 MSG db1[1811]: [35]: 3 2013-06-04 10:34:23 MSG db1[1811]: [38]: 0 2013-06-04 10:34:23 MSG db1[1811]: [39]: 2 2013-06-04 10:34:23 MSG db1[1811]: [66]: 0 2013-06-04 10:34:23 MSG db1[1811]: [67]: 6 2013-06-04 10:34:23 MSG db1[1811]: [67]: 0 2013-06-04 10:34:23 MSG db1[1811]: [68]: 7 2013-06-04 10:34:23 MSG db1[1811]: [70]: 0 2013-06-04 10:34:23 MSG db1[1811]: [70]: 8 2013-06-04 10:34:23 MSG db1[1811]: [71]: 0 2013-06-04 10:34:23 MSG db1[1811]: [98]: 9 2013-06-04 10:34:23 MSG db1[1811]: [101]: 0 2013-06-04 10:34:23 MSG db1[1811]: [102]: 10 2013-06-04 10:34:23 MSG db1[1811]: [102]: 0 2013-06-04 10:34:23 MSG db1[1811]: [103]: 11 2013-06-04 10:34:23 MSG db1[1811]: [129]: 0 2013-06-04 10:34:23 MSG db1[1811]: [129]: 13 2013-06-04 10:34:23 MSG db1[1811]: [131]: 0 2013-06-04 10:34:23 MSG db1[1811]: [131]: 12 2013-06-04 10:34:23 MSG db1[1811]: [133]: 0 2013-06-04 10:34:23 MSG db1[1811]: [134]: 14 2013-06-04 10:34:23 MSG db1[1811]: [134]: 0 2013-06-04 10:34:23 MSG db1[1811]: [135]: 16 2013-06-04 10:34:23 MSG db1[1811]: [135]: 0 2013-06-04 10:34:23 MSG db1[1811]: [162]: 15 2013-06-04 10:34:23 MSG db1[1811]: [163]: 0 2013-06-04 10:34:23 MSG db1[1811]: [163]: 17 2013-06-04 10:34:23 MSG db1[1811]: [163]: 0 2013-06-04 10:34:23 MSG db1[1811]: [165]: 18 2013-06-04 10:34:23 MSG db1[1811]: [165]: 0 2013-06-04 10:34:23 MSG db1[1811]: [166]: 19 2013-06-04 10:34:23 MSG db1[1811]: [167]: 0 2013-06-04 10:34:23 MSG db1[1811]: [192]: 21 2013-06-04 10:34:23 MSG db1[1811]: [192]: 0 2013-06-04 10:34:23 MSG db1[1811]: [193]: 20 2013-06-04 10:34:23 MSG db1[1811]: [194]: 0 2013-06-04 10:34:23 MSG db1[1811]: [194]: 22 2013-06-04 10:34:23 MSG db1[1811]: [197]: 0 2013-06-04 10:34:23 MSG db1[1811]: [197]: 24 2013-06-04 10:34:23 MSG db1[1811]: [224]: 0 2013-06-04 10:34:23 MSG db1[1811]: [224]: 23 2013-06-04 10:34:23 MSG db1[1811]: [224]: 0 2013-06-04 10:34:23 MSG db1[1811]: [225]: 26 2013-06-04 10:34:23 MSG db1[1811]: [225]: 0 2013-06-04 10:34:23 MSG db1[1811]: [227]: 25 2013-06-04 10:34:23 MSG db1[1811]: [227]: 0 2013-06-04 10:34:23 MSG db1[1811]: [229]: 27 2013-06-04 10:34:23 MSG db1[1811]: [229]: 0 2013-06-04 10:34:23 MSG db1[1811]: [230]: 29 2013-06-04 10:34:23 MSG db1[1811]: [230]: 0 2013-06-04 10:34:23 MSG db1[1811]: [231]: 28 2013-06-04 10:34:23 MSG db1[1811]: [231]: 0 2013-06-04 10:34:23 MSG db1[1811]: [258]: 31 2013-06-04 10:34:23 MSG db1[1811]: [258]: 0 2013-06-04 10:34:23 MSG db1[1811]: [259]: 30 2013-06-04 10:34:23 MSG db1[1811]: [259]: 0 2013-06-04 10:34:23 MSG db1[1811]: [259]: 32 2013-06-04 10:34:23 MSG db1[1811]: [260]: 0 2013-06-04 10:34:23 MSG db1[1811]: [260]: 35 2013-06-04 10:34:23 MSG db1[1811]: [261]: 0 2013-06-04 10:34:23 MSG db1[1811]: [262]: 34 2013-06-04 10:34:23 MSG db1[1811]: [288]: 0 2013-06-04 10:34:23 MSG db1[1811]: [289]: 33 2013-06-04 10:34:23 MSG db1[1811]: [292]: 0 2013-06-04 10:34:23 MSG db1[1811]: [293]: 37 2013-06-04 10:34:23 MSG db1[1811]: [295]: 0 2013-06-04 10:34:23 MSG db1[1811]: [320]: 36 2013-06-04 10:34:23 MSG db1[1811]: [322]: 0 2013-06-04 10:34:23 MSG db1[1811]: [322]: 38 2013-06-04 10:34:23 MSG db1[1811]: [323]: 0 2013-06-04 10:34:23 MSG db1[1811]: [324]: 39 2013-06-04 10:34:23 MSG db1[1811]: [325]: 0 2013-06-04 10:34:23 MSG db1[1811]: [325]: 41 2013-06-04 10:34:23 MSG db1[1811]: [326]: 0 2013-06-04 10:34:23 MSG db1[1811]: [326]: 40 2013-06-04 10:34:23 MSG db1[1811]: [326]: 0 2013-06-04 10:34:23 MSG db1[1811]: [354]: 42 2013-06-04 10:34:23 MSG db1[1811]: [357]: 0 2013-06-04 10:34:23 MSG db1[1811]: [357]: 44 2013-06-04 10:34:23 MSG db1[1811]: [358]: 0 2013-06-04 10:34:23 MSG db1[1811]: [358]: 43 2013-06-04 10:34:23 MSG db1[1811]: [358]: 0 2013-06-04 10:34:23 MSG db1[1811]: [358]: 46 2013-06-04 10:34:23 MSG db1[1811]: [359]: 0 2013-06-04 10:34:23 MSG db1[1811]: [359]: 45 2013-06-04 10:34:23 MSG db1[1811]: [359]: 0 2013-06-04 10:34:23 MSG db1[1811]: [384]: 49 2013-06-04 10:34:23 MSG db1[1811]: [384]: 0 2013-06-04 10:34:23 MSG db1[1811]: [385]: 48 2013-06-04 10:34:23 MSG db1[1811]: [386]: 0 2013-06-04 10:34:23 MSG db1[1811]: [387]: 47 2013-06-04 10:34:23 MSG db1[1811]: [389]: 0 We don't understand why, e.g., qsort() apparently changed the tail associated with the value 7 from 2 to 5. We expect qsort to rearrange items in the list, but thought that the head and tails were linked, so they would be moved together as a unit. Can you give us a rough explanation why we are seeing this? Better yet, can you explain the relationship between the head and tail members? Thanks, Steve Morgan --- On Mon, 6/3/13, Martin Kersten <Martin.Kersten@cwi.nl> wrote: From: Martin Kersten <Martin.Kersten@cwi.nl> Subject: Re: Question on Quicksort To: users-list@monetdb.org Date: Monday, June 3, 2013, 11:29 PM 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
_______________________________________________ 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