Re: PostgreSQL - 'SKYLINE OF' clause added!

The query Ranbeer gave - as with any skyline query - can be solved with 
just pure SQL:

select * from books b where not exists(  select * from books b2 where    b2.rating >= b.rating and b2.price <= b.price
and   (b2.rating > b.rating or b2.price < b.price)
 
);     book_name     | rating | price
-------------------+--------+------- Prodigal Daughter |      3 |   250 The Notebook      |      4 |   300 Fountain
Head    |      5 |   350
 
(3 rows)

The idea of the BNL (block nested loop) skyline algorithm is to avoid 
the nested loop by storing "dominating" records as the query proceeds - 
in the above example, records which are relatively high in rating and 
low in price - and comparing each candidate record to those first.

BNL is the most reasonable skyline algorithm in the absence of a 
multidimensional (usually R-Tree) index on the columns.  For answering 
skyline queries where such an index exists over all query columns, the 
most broadly used generalized algorithm is BBS [1].

Thanks,

Dave Fuhry

[1] Papadias, D., Tao, Y., Fu, G., and Seeger, B. 2005. Progressive 
skyline computation in database systems. ACM Trans. Database Syst. 30, 1 
(Mar. 2005), 41-82. DOI= http://doi.acm.org/10.1145/1061318.1061320

Gavin Sherry wrote:
> On Tue, 6 Mar 2007, Alvaro Herrera wrote:
> 
>> Also, keep in mind that there were plenty of changes in the executor.
>> This stuff is not likely to be very easy to implement efficiently using
>> our extant executor machinery; note that Ranbeer mentioned
>> implementation of "block nested loop" and other algorithms.  Not sure
>> how easy would be to fold that stuff into the optimizer for multi-input
>> aggregates, instead of hardwiring it to the SKYLINE OF syntax.
>>
> 
> Yes, there's been a lot of working on calculating skyline efficiently,
> with different sorting techniques and so on. This is the most interesting
> part of the idea. You could calculate the query Ranbeer gave using pure
> SQL and, perhaps, use of some covariance aggregates or something already.
> Of course, it gets harder when you want to calculate across many
> dimensions.
> 
> Personally, I'd love to see some of these newer data analysis
> capabilities added to PostgreSQL -- or at least put out there as
> interesting patches.
> 
> Thanks,
> 
> Gavin
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 3: Have you checked our extensive FAQ?
> 
>                http://www.postgresql.org/docs/faq