PostgreSQL - 'SKYLINE OF' clause added!

On Sat, Mar 03, 2007 at 07:02:41PM +0530, ranbeer makin wrote:

We at International Institute of Information Technology (IIIT) Hyderabad,
India, have extended the Postgres database
system with the skyline operation. For this work, we were guided by our
Prof. Kamalakar Karlapalem
(http://www.iiit.ac.in/~kamal/).

<snip>

Can this piece of work contribute to PostgreSQL? If yes, then we'll send out
a detailed report of this project including changes
made, issues involved/need to be solved, limitations, future work, and the
source code etc.

Well, that kind of depends. I have no idea what "Skyline" means so
telling us what it is would be a good start

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

Show quoted text

From each according to his ability. To each according to his ability to litigate.

Martijn van Oosterhout wrote:

Well, that kind of depends. I have no idea what "Skyline" means so
telling us what it is would be a good start

Also, showing us the diffs (maybe on a web site) would give us an idea
of how intrusive it would be.

But I agree with Martijn - the first thing is to describe the
functionality properly.

cheers

andrew

Here is a description of what the SKYLINE operator is:
---
Suppose you wish to purchase books and you are looking for books with high
rating and low price. However, both the criteria of selecting books are
complementary since books of higher rating are generally more expensive. For
finding such books, you'll query the database system of the book store which
will return a set of interesting books. The word 'interesting' implies all
the books which are as good or better in both the dimensions (rating and
price) and better in at least one dimension. This set of interesting points
forms the Skyline.

Skyline operator finds points which are not dominated by other data points.
A point dominates another point if it is as good or better in all dimensions
and better in at least one dimension.

For specifying the Skyline queries, we extend SQL SELECT statement by an
optional *SKYLINE OF* clause as given below:

SELECT ... FROM ... WHERE...

GROUP BY ... HAVING...

*SKYLINE OF [DISTINCT] d1 [MIN | MAX | DIFF], .., dm [MIN | MAX | DIFF]*

ORDER BY...

Where, d1, d2 ,…, dm denote the dimensions of the Skyline, and MIN, MAX,
DIFF specify whether the value in that dimension should be minimized,
maximized, or simply be different. When DIFF is specified, two tuples are
compared only if the value of the attribute on which DIFF is applied is
different.

When DISTINCT clause is specified and if there are two or more tuples with
the same values of skyline attributes, then only one of them is retained in
the skyline set. Otherwise, all of them are retained.

Let's consider the above example of purchasing books with high rating and
low price.

*Book Name*

*Rating (out of 5)*

*Price (Rs)*

Prodigal Daughter

3

250

The city of Joy

5

400

Vanishing Acts

2

250

The Notebook

4

300

Fountain Head

5

350

Dear John

5

500

*Table1. Sample of book database*

Now, in order to get books with high rating and low price, you simply can
issue the following query:

SELECT *

FROM Books

SKYLINE OF rating MAX, price MIN;

The Skyline set returned will be:

*Book Name*

*Rating (out of 5)*

*Price (Rs)*

Prodigal Daughter

3

250

The Notebook

4

300

Fountain Head

5

350

*Table2. Skyline set*

From this set, you can now make your choice of books, by weighing your
personal preferences for price and rating of the books.

For more information, you can refer to:
S. Borzsonyi, D. Kossmann, and K. Stocker. The skyline operator. In *ICDE*,
pages 421.430, 2001

---

Thanks.

Show quoted text

On 3/3/07, Martijn van Oosterhout <kleptog@svana.org> wrote:

On Sat, Mar 03, 2007 at 07:02:41PM +0530, ranbeer makin wrote:

We at International Institute of Information Technology (IIIT)

Hyderabad,

India, have extended the Postgres database
system with the skyline operation. For this work, we were guided by our
Prof. Kamalakar Karlapalem
(http://www.iiit.ac.in/~kamal/).

<snip>

Can this piece of work contribute to PostgreSQL? If yes, then we'll send

out

a detailed report of this project including changes
made, issues involved/need to be solved, limitations, future work, and

the

source code etc.

Well, that kind of depends. I have no idea what "Skyline" means so
telling us what it is would be a good start

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/

From each according to his ability. To each according to his ability to

litigate.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFF6XrkIB7bNG8LQkwRAqw8AJ0UKAy41OMxdgLUdY1G+e7R6/jGPwCZAQY4
9uCKFUW65UBIx7fpogR75Yo=
=6Yc0
-----END PGP SIGNATURE-----

ranbeer makin wrote:

We at International Institute of Information Technology (IIIT) Hyderabad,
India, have extended the Postgres database
system with the skyline operation. For this work, we were guided by our
Prof. Kamalakar Karlapalem
(http://www.iiit.ac.in/~kamal/).

We have extended SQL 'SELECT' clause by an optional 'SKYLINE OF' clause in
version 8.0.3. The changes are done in parser, transformation,
planner/optimizer (a bit) and executor stages. For its execution, two novel
algorithms - BNL (Block Nested Loop) and SFS
(Sort Filter Skyline) - are also implemented.

From what I read on your web pages it sounds interesting and may be a
worthwhile addition to PostgreSQL. I'll have a look at it when it is
available.

Can this piece of work contribute to PostgreSQL? If yes, then we'll send
out
a detailed report of this project including changes
made, issues involved/need to be solved, limitations, future work, and the
source code etc.

I am not one making the choice of accepting your work but from what I
know you would want to make your patch available so others can review
the stability/quality of your work and decide whether there is enough
demand for the feature to have it included in the main distribution
either as part of the main code or within the contrib section.

One option you have is to start a project at pgfoundry.org so others can
access and try your contribution. This will allow your work to be
available and to be tested by those interested in this feature. If your
work proves to be worthwhile and in demand it can progress from there
into the main distribution.

You most probably want to look at porting your changes to the latest
postgresql release as well.

Thanks very much.

Regards,
Nikita
Ranbeer

--
http://students.iiit.ac.in/~nikita/
http://students.iiit.ac.in/~ranbeer/

--

Shane Ambler
pgSQL@Sheeky.Biz

Get Sheeky @ http://Sheeky.Biz

You most probably want to look at porting your changes to the latest
postgresql release as well.

I believe many people would be interested, but to get the feature
accepted we would need a patch against -head as that is the latest
version of PostgreSQL under development.

You can see more information about that here:

http://www.postgresql.org/developer/

The above link will also help you with our required coding styles,
acceptance policies etc...

Sincerely,

Joshua D. Drake

Thanks very much.

Regards,
Nikita
Ranbeer

--
http://students.iiit.ac.in/~nikita/
http://students.iiit.ac.in/~ranbeer/

--

=== The PostgreSQL Company: Command Prompt, Inc. ===
Sales/Support: +1.503.667.4564 || 24x7/Emergency: +1.800.492.2240
Providing the most comprehensive PostgreSQL solutions since 1997
http://www.commandprompt.com/

Donate to the PostgreSQL Project: http://www.postgresql.org/about/donate
PostgreSQL Replication: http://www.commandprompt.com/products/

FWIW, this sounds like a subset of the Query By Example stuff that
someone is working on. I don't have a URL handy since I'm on a plane,
but I think google can find it.

On Mar 3, 2007, at 8:12 AM, ranbeer makin wrote:

Here is a description of what the SKYLINE operator is:
---
Suppose you wish to purchase books and you are looking for books
with high rating and low price. However, both the criteria of
selecting books are complementary since books of higher rating are
generally more expensive. For finding such books, you'll query the
database system of the book store which will return a set of
interesting books. The word 'interesting' implies all the books
which are as good or better in both the dimensions (rating and
price) and better in at least one dimension. This set of
interesting points forms the Skyline.
Skyline operator finds points which are not dominated by other data
points. A point dominates another point if it is as good or better
in all dimensions and better in at least one dimension.

For specifying the Skyline queries, we extend SQL SELECT statement
by an optional SKYLINE OF clause as given below:

SELECT ... FROM ... WHERE...

GROUP BY ... HAVING...

SKYLINE OF [DISTINCT] d1 [MIN | MAX | DIFF], .., dm [MIN | MAX |
DIFF]

ORDER BY...

Where, d1, d2 ,…, dm denote the dimensions of the Skyline, and MIN,
MAX, DIFF specify whether the value in that dimension should be
minimized, maximized, or simply be different. When DIFF is
specified, two tuples are compared only if the value of the
attribute on which DIFF is applied is different.

When DISTINCT clause is specified and if there are two or more
tuples with the same values of skyline attributes, then only one of
them is retained in the skyline set. Otherwise, all of them are
retained.

Let's consider the above example of purchasing books with high
rating and low price.

Book Name

Rating (out of 5)

Price (Rs)

Prodigal Daughter

3

250

The city of Joy

5

400

Vanishing Acts

2

250

The Notebook

4

300

Fountain Head

5

350

Dear John

5

500

Table1. Sample of book database

Now, in order to get books with high rating and low price, you
simply can issue the following query:

SELECT *

FROM Books

SKYLINE OF rating MAX, price MIN;

The Skyline set returned will be:

Book Name

Rating (out of 5)

Price (Rs)

Prodigal Daughter

3

250

The Notebook

4

300

Fountain Head

5

350

Table2. Skyline set

From this set, you can now make your choice of books, by weighing
your personal preferences for price and rating of the books.

For more information, you can refer to:
S. Borzsonyi, D. Kossmann, and K. Stocker. The skyline operator. In
ICDE, pages 421.430, 2001

---

Thanks.

On 3/3/07, Martijn van Oosterhout <kleptog@svana.org> wrote: On
Sat, Mar 03, 2007 at 07:02:41PM +0530, ranbeer makin wrote:

We at International Institute of Information Technology (IIIT)

Hyderabad,

India, have extended the Postgres database
system with the skyline operation. For this work, we were guided

by our

Prof. Kamalakar Karlapalem
(http://www.iiit.ac.in/~kamal/).

<snip>

Can this piece of work contribute to PostgreSQL? If yes, then

we'll send out

a detailed report of this project including changes
made, issues involved/need to be solved, limitations, future

work, and the

source code etc.

Well, that kind of depends. I have no idea what "Skyline" means so
telling us what it is would be a good start

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/
kleptog/

From each according to his ability. To each according to his

ability to litigate.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFF6XrkIB7bNG8LQkwRAqw8AJ0UKAy41OMxdgLUdY1G+e7R6/jGPwCZAQY4
9uCKFUW65UBIx7fpogR75Yo=
=6Yc0
-----END PGP SIGNATURE-----

--
Jim Nasby jim@nasby.net
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

On Mon, Mar 05, 2007 at 09:04:46PM -0600, Jim Nasby wrote:

FWIW, this sounds like a subset of the Query By Example stuff that
someone is working on. I don't have a URL handy since I'm on a plane,
but I think google can find it.

It's now called ObelisQ <http://pgfoundry.org/projects/qbe&gt;

Cheers,
D

On Mar 3, 2007, at 8:12 AM, ranbeer makin wrote:

Here is a description of what the SKYLINE operator is:
---
Suppose you wish to purchase books and you are looking for books
with high rating and low price. However, both the criteria of
selecting books are complementary since books of higher rating are
generally more expensive. For finding such books, you'll query the
database system of the book store which will return a set of
interesting books. The word 'interesting' implies all the books
which are as good or better in both the dimensions (rating and
price) and better in at least one dimension. This set of
interesting points forms the Skyline.
Skyline operator finds points which are not dominated by other data
points. A point dominates another point if it is as good or better
in all dimensions and better in at least one dimension.

For specifying the Skyline queries, we extend SQL SELECT statement
by an optional SKYLINE OF clause as given below:

SELECT ... FROM ... WHERE...

GROUP BY ... HAVING...

SKYLINE OF [DISTINCT] d1 [MIN | MAX | DIFF], .., dm [MIN | MAX |
DIFF]

ORDER BY...

Where, d1, d2 ,���, dm denote the dimensions of the Skyline, and MIN,
MAX, DIFF specify whether the value in that dimension should be
minimized, maximized, or simply be different. When DIFF is
specified, two tuples are compared only if the value of the
attribute on which DIFF is applied is different.

When DISTINCT clause is specified and if there are two or more
tuples with the same values of skyline attributes, then only one of
them is retained in the skyline set. Otherwise, all of them are
retained.

Let's consider the above example of purchasing books with high
rating and low price.

Book Name

Rating (out of 5)

Price (Rs)

Prodigal Daughter

3

250

The city of Joy

5

400

Vanishing Acts

2

250

The Notebook

4

300

Fountain Head

5

350

Dear John

5

500

Table1. Sample of book database

Now, in order to get books with high rating and low price, you
simply can issue the following query:

SELECT *

FROM Books

SKYLINE OF rating MAX, price MIN;

The Skyline set returned will be:

Book Name

Rating (out of 5)

Price (Rs)

Prodigal Daughter

3

250

The Notebook

4

300

Fountain Head

5

350

Table2. Skyline set

From this set, you can now make your choice of books, by weighing
your personal preferences for price and rating of the books.

For more information, you can refer to:
S. Borzsonyi, D. Kossmann, and K. Stocker. The skyline operator. In
ICDE, pages 421.430, 2001

---

Thanks.

On 3/3/07, Martijn van Oosterhout <kleptog@svana.org> wrote: On
Sat, Mar 03, 2007 at 07:02:41PM +0530, ranbeer makin wrote:

We at International Institute of Information Technology (IIIT)

Hyderabad,

India, have extended the Postgres database
system with the skyline operation. For this work, we were guided

by our

Prof. Kamalakar Karlapalem
(http://www.iiit.ac.in/~kamal/).

<snip>

Can this piece of work contribute to PostgreSQL? If yes, then

we'll send out

a detailed report of this project including changes
made, issues involved/need to be solved, limitations, future

work, and the

source code etc.

Well, that kind of depends. I have no idea what "Skyline" means so
telling us what it is would be a good start

Have a nice day,
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/
kleptog/

From each according to his ability. To each according to his

ability to litigate.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFF6XrkIB7bNG8LQkwRAqw8AJ0UKAy41OMxdgLUdY1G+e7R6/jGPwCZAQY4
9uCKFUW65UBIx7fpogR75Yo=
=6Yc0
-----END PGP SIGNATURE-----

--
Jim Nasby jim@nasby.net
EnterpriseDB http://enterprisedb.com 512.569.9461 (cell)

---------------------------(end of broadcast)---------------------------
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

--
David Fetter <david@fetter.org> http://fetter.org/
phone: +1 415 235 3778 AIM: dfetter666
Skype: davidfetter

Remember to vote!
Consider donating to PostgreSQL: http://www.postgresql.org/about/donate

decibel@decibel.org (Jim Nasby) writes:

FWIW, this sounds like a subset of the Query By Example stuff that
someone is working on. I don't have a URL handy since I'm on a plane,
but I think google can find it.

The pgFoundry project is here...
http://pgfoundry.org/projects/qbe

And yes, indeed, this sounds quite a lot like what Meredith Patterson
presented at the Toronto conference.
--
(reverse (concatenate 'string "ofni.secnanifxunil" "@" "enworbbc"))
http://linuxfinances.info/info/finances.html
Rules of the Evil Overlord #189. "I will never tell the hero "Yes I
was the one who did it, but you'll never be able to prove it to that
incompetent old fool." Chances are, that incompetent old fool is
standing behind the curtain." <http://www.eviloverlord.com/&gt;

And yes, indeed, this sounds quite a lot like what Meredith Patterson
presented at the Toronto conference.

This would be good to have, though, since Meredith's work has some problematic
IP encumbrances.

Question, though: is the SKYLINE syntax part of a standard anywhere?

--
Josh Berkus
PostgreSQL @ Sun
San Francisco

Josh Berkus <josh@agliodbs.com> writes:

Question, though: is the SKYLINE syntax part of a standard anywhere?

There's certainly not anything like that in SQL2003.

I'm also kind of wondering if the main use-cases couldn't be met with
suitable multi-input custom aggregates, which is something we already
have as of 8.2.

regards, tom lane

Tom,

I'm also kind of wondering if the main use-cases couldn't be met with
suitable multi-input custom aggregates, which is something we already
have as of 8.2.

Actually, given that "skyline of" is *only* for aggregate sorting (as far as I
can tell) it doesn't present the complications which QBE did for using a
function interface.

Ranbeer, would it be possible to use an aggregate function syntax instead of
the SKYLINE OF syntax extension? This allows us to sidestep the issue of
non-standard additions to the reserved word list.

--
Josh Berkus
PostgreSQL @ Sun
San Francisco

Josh Berkus wrote:

Tom,

I'm also kind of wondering if the main use-cases couldn't be met with
suitable multi-input custom aggregates, which is something we already
have as of 8.2.

Actually, given that "skyline of" is *only* for aggregate sorting (as far as I
can tell) it doesn't present the complications which QBE did for using a
function interface.

There is people on a Venezuelan university working on SKYLINE OF and
other operators on Postgres. I had some looks at their work because
they asked for help in the spanish list.

Not only they added the SKYLINE OF clause, but they also had some mods
to the ORDER BY clause, and a couple of other grammar changes as well.
While SKYLINE OF itself could probably be folded as aggregates, the
other stuff is not likely to be amenable to such treatment.

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.

There's a certain group in the Venezuelan Uni that was about to finish
their thesis. They promised me a look into their report; maybe I can
give further input from that and maybe merge Ranbeer's stuff with it.

--
Alvaro Herrera http://www.CommandPrompt.com/
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

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

Gavin,

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.

I think if the code is good enough, and we can avoid horrible non-standard
syntax extensions, they should go in. We have to defend our title as "most
advanced database" and having stuff like Skyline first (before DB2 or MS)
goes a long way for that.

--
Josh Berkus
PostgreSQL @ Sun
San Francisco

Josh Berkus <josh@agliodbs.com> writes:

I think if the code is good enough, and we can avoid horrible non-standard
syntax extensions, they should go in. We have to defend our title as "most
advanced database" and having stuff like Skyline first (before DB2 or MS)
goes a long way for that.

Well, whether it's horrible or not is in the eye of the beholder, but
this is certainly a non-standard syntax extension.

My questions about whether to adopt it have more to do with
cost/benefit. I haven't seen the patch, but it sounds like it will be
large and messy; and it's for a feature that nobody ever heard of before,
let alone one that the community has developed a consensus it wants.
I'm not interested in adopting stuff just "because DB2 hasn't got it".

It's also worth noting that what we've got here is a large patch
developed, by students, completely outside our normal development
process; so the odds that it's going to be anywhere near acceptable are
low. I think the last time we applied a patch that met that description
was the INTERSECT/EXCEPT patch in 1999 ... maybe you don't remember
what a fiasco that was, but I do.

Sorry to be a thrower of cold water, but I just don't see that this
comes anywhere near being something we should be eager to accept.

regards, tom lane

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]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.

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
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:

Show quoted text

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

Tom,

My questions about whether to adopt it have more to do with
cost/benefit. I haven't seen the patch, but it sounds like it will be
large and messy; and it's for a feature that nobody ever heard of before,
let alone one that the community has developed a consensus it wants.
I'm not interested in adopting stuff just "because DB2 hasn't got it".

OK, to make it a clearer case: we have an increasing user base using
PostgreSQL for decision support. One of the reasons for this is that PG is
the *only* OSDB which does a decent job of DSS. Adding unique DSS features
will make PostgreSQL attractive to a lot more DSS application developers, and
help make up for the things which we don't have yet (parallel query, async
I/O, windowing functions).

"Approximate queries" is something with DSS users *want*. Jim Grey addressed
this in his ACM editiorial on the databases of the future. It's something
that *I* want, and if the Greenplum people aren't speaking up here, it's
because they're not paying atttention.

Now, I don't know if this Skyline patch is our answer for approximate queries.
Maybe I should pester Meredith about getting QBE free of its IP issues; it
certainly looked more flexible than Skyline. In either case, the code
probably needs a complete refactor.

But I think that approximate queries ought to be on our TODO list.

--
Josh Berkus
PostgreSQL @ Sun
San Francisco

Josh Berkus wrote:

Now, I don't know if this Skyline patch is our answer for approximate queries.
Maybe I should pester Meredith about getting QBE free of its IP issues; it
certainly looked more flexible than Skyline. In either case, the code
probably needs a complete refactor.

But I think that approximate queries ought to be on our TODO list.

+1

On Wed, 7 Mar 2007, Josh Berkus wrote:

"Approximate queries" is something with DSS users *want*. Jim Grey addressed
this in his ACM editiorial on the databases of the future. It's something
that *I* want, and if the Greenplum people aren't speaking up here, it's
because they're not paying atttention.

Now, I don't know if this Skyline patch is our answer for approximate queries.
Maybe I should pester Meredith about getting QBE free of its IP issues; it
certainly looked more flexible than Skyline. In either case, the code
probably needs a complete refactor.

What people want from "approximate queries" is different to this: the
desire is usually to balance run time with level of accuracy/quality (some
times the desire is to have accurate results as well as similar results).
Neither skyline or QBE are about this. The only thing in the spec which
addresses this is 'tablesample'.

Thanks,

Gavin

Yep - we're paying attention Josh!

I like the category being explored with skyline, I'm not sure yet how it fits with existing 'soft data' models and applications that use them.

If SKYLINE is interesting to app developers, maybe we should consider it for Bizgres?

- Luke

Msg is shrt cuz m on ma treo

-----Original Message-----
From: Gavin Sherry [mailto:swm@alcove.com.au]
Sent: Wednesday, March 07, 2007 05:44 PM Eastern Standard Time
To: Josh Berkus
Cc: Tom Lane; pgsql-hackers@postgresql.org; Alvaro Herrera; Chris Browne
Subject: Re: [HACKERS] PostgreSQL - 'SKYLINE OF' clause added!

On Wed, 7 Mar 2007, Josh Berkus wrote:

"Approximate queries" is something with DSS users *want*. Jim Grey addressed
this in his ACM editiorial on the databases of the future. It's something
that *I* want, and if the Greenplum people aren't speaking up here, it's
because they're not paying atttention.

Now, I don't know if this Skyline patch is our answer for approximate queries.
Maybe I should pester Meredith about getting QBE free of its IP issues; it
certainly looked more flexible than Skyline. In either case, the code
probably needs a complete refactor.

What people want from "approximate queries" is different to this: the
desire is usually to balance run time with level of accuracy/quality (some
times the desire is to have accurate results as well as similar results).
Neither skyline or QBE are about this. The only thing in the spec which
addresses this is 'tablesample'.

Thanks,

Gavin

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

Tom Lane wrote:

Josh Berkus <josh@agliodbs.com> writes:

I think if the code is good enough, and we can avoid horrible non-standard
syntax extensions, they should go in. We have to defend our title as "most
advanced database" and having stuff like Skyline first (before DB2 or MS)
goes a long way for that.

Well, whether it's horrible or not is in the eye of the beholder, but
this is certainly a non-standard syntax extension.

Being non-standard should not be the only reason to reject a worthwhile
feature. Do you really believe that the SQL standard covers every
feature that a RDBMS could ever want to implement? Do you think that the
current non-standard features of PostgreSQL should be removed?

My questions about whether to adopt it have more to do with
cost/benefit. I haven't seen the patch, but it sounds like it will be
large and messy; and it's for a feature that nobody ever heard of before,
let alone one that the community has developed a consensus it wants.
I'm not interested in adopting stuff just "because DB2 hasn't got it".

Partially agree but I do think it is worth looking at to see if some or
all of the feature is worth implementing. The fact that several
different groups have been mentioned to be working on this feature would
indicate that it is worth considering. Maybe one of the other groups
will have implemented it better than the first off the rank. Maybe our
core developers can work out a better way to implement these features.

A few people on this list have said they are interested in this.

It's also worth noting that what we've got here is a large patch
developed, by students, completely outside our normal development
process; so the odds that it's going to be anywhere near acceptable are
low. I think the last time we applied a patch that met that description
was the INTERSECT/EXCEPT patch in 1999 ... maybe you don't remember
what a fiasco that was, but I do.

True but the quals he has listed on his web pages look impressive and
probably give him a little reason to have his work considered/looked at.
He may just end up being a main PostgreSQL developer in the future.

Sorry to be a thrower of cold water, but I just don't see that this
comes anywhere near being something we should be eager to accept.

True we shouldn't just say "sounds good let's put it in" but with some
indication that this feature is along the lines of what users want,
would indicate that we should be asking -

Do we want this or a similar feature?
Is the theory behind this feature solid?
Can the same end results be gained with other existing methods?
Is the implementation offered worth considering?
Has it been developed to meet the PostgreSQL developer guidelines?
Is it reasonable to work on it to reach a level of quality/performance
that we will be happy to include?
Can we implement this feature better ourselves?
Do we want to start this feature from scratch ourselves?

--

Shane Ambler
pgSQL@Sheeky.Biz

Get Sheeky @ http://Sheeky.Biz

Shane Ambler <pgsql@Sheeky.Biz> writes:

Tom Lane wrote:

Well, whether it's horrible or not is in the eye of the beholder, but
this is certainly a non-standard syntax extension.

Being non-standard should not be the only reason to reject a worthwhile
feature.

No, but being non-standard is certainly an indicator that the feature
may not be of widespread interest --- if it were, the SQL committee
would've gotten around to including it; seems they've managed to include
everything but the kitchen sink already. Add to that the complete lack
of any previous demand for the feature, and you have to wonder where the
market is.

The fact that several
different groups have been mentioned to be working on this feature would
indicate that it is worth considering.

It looks to me more like someone published a paper that caught the
attention of a few profs looking for term projects for their students.

Now maybe it really is the best idea since sliced bread and will be seen
in the next SQL spec edition, but color me skeptical. It seems to me
to be a very narrow-usage extension, as opposed to (eg) multi-input
aggregates or WITH/RECURSIVE, which provide general mechanisms applicable
to a multitude of problems. Now even so it would be fine if the
implementation were similarly narrow in scope, but the published
description of the patch mentions a large chunk of additional executor
mechanisms. If we're going to be adding as much code as that, I'd like
to see a wider scope of usage for it.

Basically, this patch isn't sounding like it has a reasonable
bang-to-the-buck ratio ...

regards, tom lane

Few things from our side:

1. 'Skyline Of' is a new operator proposed in ICDE 2003, one of the topmost
conferences of Data Engineering. Skyline operation is a hot area of research
in query processing. Many of the database community people do know about
this operator, and it is fast catching the attention.

2. The skyline operation is very useful in data analysis. Suppose, if we
have a cricket database, and we want to find the bowlers who have taken
maximum wickets in minimum overs, we can issue an easy-to-write query using
'Skyline of' syntax as follows:

Select * from Player_Match Skyline Of overs_bowled min, wickets_taken max;

This query gives 25 interesting tuples (result set) out of 24750 tuples in
0.0509 seconds. The same result is obtained in 0.8228 seconds if the
following equivalent nested-query is issued:

select * from Player_Match p1 where not exists ( select * from Player_Match
p2 where p2.overs_bowled <= p1.overs_bowled and p2.wickets_taken >=
p1.wickets_taken and (p2.overs_bowled < p1.overs_bowled or p2.wickets_taken>
p1.wickets_taken))

Note that the above time is the time elapsed between issuing a query and
obtaining the result set.
As can be seen, the above query looks pretty cumbersome to write and is
inefficient too. So, which query will the user prefer? As the number of
dimensions increases, writing a nested-query will become a hedious task.
Btw, how can such a query be written using aggregate function syntax??

3. As far as optimizing the Skyline is concerned, it is still a research
problem since it requires estimating the cardinality of the skyline result
set.

4. Until and unless this operator is implemented in a popular database
system, how can a user ever get to know about it and hence appreciate its
usefulness?

Btw, it was our B.Tech final year project, and not a term project :-)

Regards.

On 3/8/07, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Shane Ambler <pgsql@Sheeky.Biz> writes:

Tom Lane wrote:

Well, whether it's horrible or not is in the eye of the beholder, but
this is certainly a non-standard syntax extension.

Being non-standard should not be the only reason to reject a worthwhile
feature.

No, but being non-standard is certainly an indicator that the feature
may not be of widespread interest --- if it were, the SQL committee
would've gotten around to including it; seems they've managed to include
everything but the kitchen sink already. Add to that the complete lack
of any previous demand for the feature, and you have to wonder where the
market is.

The fact that several
different groups have been mentioned to be working on this feature would
indicate that it is worth considering.

It looks to me more like someone published a paper that caught the
attention of a few profs looking for term projects for their students.

Now maybe it really is the best idea since sliced bread and will be seen
in the next SQL spec edition, but color me skeptical. It seems to me
to be a very narrow-usage extension, as opposed to (eg) multi-input
aggregates or WITH/RECURSIVE, which provide general mechanisms applicable
to a multitude of problems. Now even so it would be fine if the
implementation were similarly narrow in scope, but the published
description of the patch mentions a large chunk of additional executor
mechanisms. If we're going to be adding as much code as that, I'd like
to see a wider scope of usage for it.

Basically, this patch isn't sounding like it has a reasonable
bang-to-the-buck ratio ...

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend

--
Pride sullies the noblest character

I do see your points regarding the existence of use cases for this
feature, and I agree that at worst, the implementation of this feature
would provide a way to greatly simplify query design and at best provide
a whole new method of obtaining decision supporting data from a
relational database.

However I am strongly in disagreement with your fourth point, I.e., that
users will only become aware of it once it has been implemented. This
sort of mentality is what gave us the sad case of late 90s HTML in which
browser vendors assumed that they could use the "if you build it they
will come" argument for feature extension of the HTML spec. That is a
debacle we are still suffering the effects of. Let us not do the same to
SQL and implement SKYLINE on our own, only to have other DBMS vendors
implement it in different ways and then finally when the SQL standard
includes it they try to make some kind of average approximation of the
implementations resulting in *none* of the DBs being compliant. Then
we'll be between the rock of breaking backwards compatibility and the
hard place of unwarranted standards non-compliance.

While Josh did point out that being in the leading group as far as
implementing new functionality goes, I feel that it has to be weighed
against the need to not strike out too aggressively, potentially
isolating ourselves with excessive non-standard syntax or behavior.

While I am convinced there is a strong use case for this functionality
and we should definitely start looking at it, I don't see why we should
be in a rush to get it into core. People have survived without it up to
now, I don't think our userbase will suffer if it is implemented 6
months after <foo commercial DB> implements it, at least, not as much as
it will suffer if we start drifting away from standards compliance.

Just my 2 rupees. :)

- Naz

Nikita wrote:

Show quoted text

Few things from our side:

1. 'Skyline Of' is a new operator proposed in ICDE 2003, one of the
topmost conferences of Data Engineering. Skyline operation is a hot
area of research in query processing. Many of the database community
people do know about this operator, and it is fast catching the
attention.

2. The skyline operation is very useful in data analysis. Suppose, if
we have a cricket database, and we want to find the bowlers who have
taken maximum wickets in minimum overs, we can issue an easy-to-write
query using 'Skyline of' syntax as follows:

Select * from Player_Match Skyline Of overs_bowled min, wickets_taken max;

This query gives 25 interesting tuples (result set) out of 24750
tuples in 0.0509 seconds. The same result is obtained in 0.8228
seconds if the following equivalent nested-query is issued:

select * from Player_Match p1 where not exists ( select * from
Player_Match p2 where p2.overs_bowled <= p1.overs_bowled and
p2.wickets_taken >= p1.wickets_taken and (p2.overs_bowled <
p1.overs_bowled or p2.wickets_taken > p1.wickets_taken))

Note that the above time is the time elapsed between issuing a query
and obtaining the result set.
As can be seen, the above query looks pretty cumbersome to write and
is inefficient too. So, which query will the user prefer? As the
number of dimensions increases, writing a nested-query will become a
hedious task.
Btw, how can such a query be written using aggregate function syntax??

3. As far as optimizing the Skyline is concerned, it is still a
research problem since it requires estimating the cardinality of the
skyline result set.

4. Until and unless this operator is implemented in a popular database
system, how can a user ever get to know about it and hence appreciate
its usefulness?

Btw, it was our B.Tech final year project, and not a term project :-)

Regards.

On 3/8/07, *Tom Lane* <tgl@sss.pgh.pa.us <mailto:tgl@sss.pgh.pa.us>>
wrote:

Shane Ambler <pgsql@Sheeky.Biz <mailto:pgsql@Sheeky.Biz>> writes:

Tom Lane wrote:

Well, whether it's horrible or not is in the eye of the

beholder, but

this is certainly a non-standard syntax extension.

Being non-standard should not be the only reason to reject a

worthwhile

feature.

No, but being non-standard is certainly an indicator that the feature
may not be of widespread interest --- if it were, the SQL committee
would've gotten around to including it; seems they've managed to
include
everything but the kitchen sink already. Add to that the complete
lack
of any previous demand for the feature, and you have to wonder
where the
market is.

The fact that several
different groups have been mentioned to be working on this

feature would

indicate that it is worth considering.

It looks to me more like someone published a paper that caught the
attention of a few profs looking for term projects for their students.

Now maybe it really is the best idea since sliced bread and will
be seen
in the next SQL spec edition, but color me skeptical. It seems to me
to be a very narrow-usage extension, as opposed to (eg) multi-input
aggregates or WITH/RECURSIVE, which provide general mechanisms
applicable
to a multitude of problems. Now even so it would be fine if the
implementation were similarly narrow in scope, but the published
description of the patch mentions a large chunk of additional executor
mechanisms. If we're going to be adding as much code as that, I'd
like
to see a wider scope of usage for it.

Basically, this patch isn't sounding like it has a reasonable
bang-to-the-buck ratio ...

regards, tom lane

---------------------------(end of
broadcast)---------------------------
TIP 6: explain analyze is your friend

--
Pride sullies the noblest character

Naz Gassiep wrote:

Let us not do the same to
SQL and implement SKYLINE on our own, only to have other DBMS vendors
implement it in different ways and then finally when the SQL standard
includes it they try to make some kind of average approximation of the
implementations resulting in *none* of the DBs being compliant. Then
we'll be between the rock of breaking backwards compatibility and the
hard place of unwarranted standards non-compliance.

While Josh did point out that being in the leading group as far as
implementing new functionality goes, I feel that it has to be weighed
against the need to not strike out too aggressively, potentially
isolating ourselves with excessive non-standard syntax or behavior.

While I am convinced there is a strong use case for this functionality
and we should definitely start looking at it, I don't see why we should
be in a rush to get it into core. People have survived without it up to
now, I don't think our userbase will suffer if it is implemented 6
months after <foo commercial DB> implements it, at least, not as much as
it will suffer if we start drifting away from standards compliance.

And where did most of the SQL standard come from? A lot of it copies or
is based on either the first db to implement a feature or the one to
implement the best syntax.

And how much of the standard became standard because most of the db's
had already implemented similar features?

Some things can syntactically be expressed more than one way, while
others are limited in ways to coherently express what you want to achieve.

If we consider this thoroughly and compile a suitable syntax that covers
all bases it could be used as the basis of the standard definition or be
close to what ends up in the standard.

--

Shane Ambler
pgSQL@Sheeky.Biz

Get Sheeky @ http://Sheeky.Biz

Shane Ambler <pgsql@Sheeky.Biz> writes:

If we consider this thoroughly and compile a suitable syntax that covers
all bases it could be used as the basis of the standard definition or be
close to what ends up in the standard.

I'll bet you a very good dinner that the word SKYLINE will never be seen
in the standard.

To me, the proposed feature seems an extremely narrow, special-purpose
thing. The SQL committee have never been into that very much, and seem
even less interested in the last couple of revisions. They like
mechanisms that can be used to solve a wide variety of problems, and
are not afraid to introduce conceptual complexity to get there.
Two examples for you: outer joins and recursive queries. Oracle's
(+) syntax is more compact than what got into the spec, but less
precise and less functional. For recursive queries, CONNECT BY is
way simpler than what got into the spec, but again doesn't cover as
much ground. The SKYLINE clause seems to me to be right about on
par with CONNECT BY ... it does something useful, but only one thing.

I think the challenge for the SKYLINE authors is to recast what they did
as a general feature --- something feeling like, say, multi-argument
aggregates or window functions. The mechanisms that they want to put
into the executor sound like they can do a whole lot more than SKYLINE;
find a way to expose that power. And the fewer bespoke keywords needed,
the better ;-)

regards, tom lane