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