Message-ID: <4E732DFF.9070900@enterprisedb.com>
Date: Fri, 16 Sep 2011 14:07:43 +0300
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; fi-FI;
	rv:1.9.2.21) Gecko/20110831 Icedove/3.1.13
MIME-Version: 1.0
To: Alexander Korotkov <aekorotkov@gmail.com>
CC: pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: Double sorting split patch
References: 
 <CAPpHfdtkUfgdMwTsoNUiaKUM3HBQre1iZFiHjR2umqgTf5D_dQ@mail.gmail.com>
	<4E72197B.9040602@enterprisedb.com>
	<CAPpHfdu+7RKA+jF4ek9CjAiAbCV=v666AMffg2RyvFnvKdbuyQ@mail.gmail.com>
In-Reply-To: 
 <CAPpHfdu+7RKA+jF4ek9CjAiAbCV=v666AMffg2RyvFnvKdbuyQ@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

On 15.09.2011 21:46, Alexander Korotkov wrote:
> On Thu, Sep 15, 2011 at 7:27 PM, Heikki Linnakangas<
> heikki.linnakangas@enterprisedb.com>  wrote:
>
>> I've looked at the patch, and took a brief look at the paper - but I still
>> don't understand the algorithm. I just can't get my head around the concepts
>> of split pairs and left/right groups. Can you explain that in layman's
>> terms? Perhaps an example would help?
>
> In short algorithm works as following:
> 1) Each box can be projected to the axis as an interval. Box (x1,y1)-(x2,y2)
> are projected to X axis as (x1,x2) interval and to the Y axis as (y1,y2)
> interval. At the first step we search for splits of those intervals and
> select the best one.
> 2) At the second step produced split are converting into terms of boxes
> and ambiguities are solving.
>
> Let's see a little deeper how intervals split search are performed by
> considering an example. We've intervals (0,1), (1,3), (2,3), (2,4). We
> assume intervals of the groups to be (0,a), (b,4). So, "a" can be some upper
> bound of interval: {1,3,4}, and "b" can be some lower bound of inteval:
> {0,1,2}.
> We consider following splits: each "a" with greatest possible "b"
> (0,1), (1,4)
> (0,3), (2,4)
> (0,4), (2,4)
> and each "b" with least possible "a". In this example splits will be:
> (0,1), (0,4)
> (0,1), (1,4)
> (0,3), (2,4)
> By removing the duplicates we've following splits:
> (0,1), (0,4)
> (0,1), (1,4)
> (0,3), (2,4)
> (0,4), (2,4)

Ok, thanks, I understand that now.

> Proposed algorithm finds following splits by single pass on two arrays: one
> sorted by lower bound of interval and another sorted by upper bound of
> interval.

That looks awfully complicated. I don't understand how that works. I 
wonder if two passes would be simpler?

-- 
   Heikki Linnakangas
   EnterpriseDB   http://www.enterprisedb.com