Gsoc2012 Idea --- Social Network database schema

On Sat, Mar 17, 2012 at 8:50 AM, HuangQi <huangqiyx@gmail.com> wrote:

    I'm quite glad if you could offer me some advices. Thanks a lot for your
help!

Thank you for your interest! However, I am a little confused precisely
what you are thinking about implementing. Are there particular access
methods or operators that you think are useful in this problem space,
or changes to the planner?

As long as you are soliciting for suggestions, I'll make one...

One that bites me (and my organization) all the time is the lack of
the access method skip scan (also called "loose index scan"). It's a
killer for append-mostly tables that track a much smaller number of
entities than the number of records in the table, and we have a
grotesque hack to do it right now. In the more "social" space the
problem reappears in the form of newsfeeds, so I think that work would
have good impact across a nice spectrum of users.

Another skip-related feature that would be very nice is the
SQL-standard TABLESAMPLE feature. I wonder if the notion of a
"SkipKind" could be taught to the executor that would provide cohesion
of implementation for most feature that involve skipping a lot of the
rows in a table while continuing a scan.

--
fdr

(Sorry, Daniel. Forgot to cc pgsql-hackers.)
Hi, Daniel
Thanks a lot for your response.
As I can see for now, in my FYP, as the acyclic schema has the property
that it has a join tree. I will check how many join trees it has and
investigate any best option for the RSN schema. If it does have, I will
modify the planner to just use this join tree if it detects a RSN database,
then no need to use System R to search through all possible join trees. The
implementation is narrow to only RSN schema. It might be too constraint for
Postgres as a generic database system.
For 'loose index join', I googled it and find the two sites useful to
understand.
http://dev.mysql.com/doc/refman/5.5/en/loose-index-scan.html
http://wiki.postgresql.org/wiki/Loose_indexscan
This is implemented in MySQL already, while Postgres only emulates the
access method. Do you have any mail thread talking about the current design
and progress?
About the second topic, so currently TABLESAMPLE is not implemented
inside Postgres? I didn't see this query before, but I googled it just now
and the query seems very weird and interesting.
http://www.fotia.co.uk/fotia/DY.18.TheTableSampleClause.aspx
Still, do you have any mail thread talking about this?
Thanks.

--
Best Regards
Huang Qi Victor

On Sat, Mar 17, 2012 at 8:48 PM, HuangQi <huangqiyx@gmail.com> wrote:

    About the second topic, so currently TABLESAMPLE is not implemented
inside Postgres? I didn't see this query before, but I googled it just now
and the query seems very weird and
interesting. http://www.fotia.co.uk/fotia/DY.18.TheTableSampleClause.aspx
    Still, do you have any mail thread talking about this?

I think there may be a few, but there's a nice implementation plan
discussed by Neil Conway and written into slides from a few years ago:
http://www.pgcon.org/2007/schedule/attachments/9-Introduction_to_Hacking_PostgreSQL_Neil_Conway.pdf

He also had his implementation, although at this point some of the
bitrot will be intense:

http://www.neilconway.org/talks/hacking/

I also seem to remember writing this (to some degree) as a student as
part of a class project, so a full-blown production implementation in
a summer sounds reasonable, unless someone has thought more about this
and ran into some icebergs. I'm not sure exactly what the blockers
were to this being committed back in 2007 (not to suggest there
weren't any).

I haven't thought enough about skipscan, but there a number more
unknowns there to me...

--
fdr

The implementation seems to be done quite fully. There is even a patch
file. Why is the implementation not added into the release of Postgres? As
so much has already being done, what could I do in this case for the Gsoc?

On Sun, Mar 18, 2012 at 6:38 PM, Daniel Farina <daniel@heroku.com> wrote:

On Sat, Mar 17, 2012 at 8:48 PM, HuangQi <huangqiyx@gmail.com> wrote:

About the second topic, so currently TABLESAMPLE is not implemented
inside Postgres? I didn't see this query before, but I googled it just

now

and the query seems very weird and
interesting.

http://www.fotia.co.uk/fotia/DY.18.TheTableSampleClause.aspx

Still, do you have any mail thread talking about this?

I think there may be a few, but there's a nice implementation plan
discussed by Neil Conway and written into slides from a few years ago:

http://www.pgcon.org/2007/schedule/attachments/9-Introduction_to_Hacking_PostgreSQL_Neil_Conway.pdf

He also had his implementation, although at this point some of the
bitrot will be intense:

http://www.neilconway.org/talks/hacking/

I also seem to remember writing this (to some degree) as a student as
part of a class project, so a full-blown production implementation in
a summer sounds reasonable, unless someone has thought more about this
and ran into some icebergs. I'm not sure exactly what the blockers
were to this being committed back in 2007 (not to suggest there
weren't any).

I haven't thought enough about skipscan, but there a number more
unknowns there to me...

--
fdr

--
Best Regards
Huang Qi Victor

On 3/18/12 8:11 PM, HuangQi wrote:

The implementation seems to be done quite fully. There is even a patch
file. Why is the implementation not added into the release of Postgres? As
so much has already being done, what could I do in this case for the Gsoc?

That would be good for you to research. archives.postgresql.org will
help you find the discussions around that.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On Mon, Mar 19, 2012 at 6:17 PM, Josh Berkus <josh@agliodbs.com> wrote:

On 3/18/12 8:11 PM, HuangQi wrote:

The implementation seems to be done quite fully. There is even a patch
file. Why is the implementation not added into the release of Postgres? As
so much has already being done, what could I do in this case for the Gsoc?

That would be good for you to research.  archives.postgresql.org will
help you find the discussions around that.

I actually tried to find out, personally...not sure if I was searching
wrongly, but searching for TABLESAMPLE did not yield a cornucopia of
useful conversations at the right time in history (~2007), even when
the search is given a broad date-horizon (all), so I, too, an
uninformed as to the specific objections.

http://www.postgresql.org/search/?m=1&amp;q=TABLESAMPLE&amp;l=&amp;d=-1&amp;s=d

--
fdr

On Mon, Mar 19, 2012 at 6:17 PM, Josh Berkus <josh@agliodbs.com> wrote:

On 3/18/12 8:11 PM, HuangQi wrote:

The implementation seems to be done quite fully. There is even a patch
file. Why is the implementation not added into the release of Postgres? As
so much has already being done, what could I do in this case for the Gsoc?

That would be good for you to research. archives.postgresql.org will
help you find the discussions around that.

I actually tried to find out, personally...not sure if I was searching
wrongly, but searching for TABLESAMPLE did not yield a cornucopia of
useful conversations at the right time in history (~2007), even when
the search is given a broad date-horizon (all), so I, too, an
uninformed as to the specific objections.

http://www.postgresql.org/search/?m=1&amp;q=TABLESAMPLE&amp;l=&amp;d=-1&amp;s=d

I sent a mail to Nail Conway asking him about this. Hope he could give a good answer. While waiting for the response, how about the skip scan? Daniel mentioned there is still some unknown.I searched this mail thread suggesting the skip scan to TODO list. http://archives.postgresql.org/pgsql-bugs/2010-03/msg00144.phpAlso this thread talking about http://archives.postgresql.org/pgsql-hackers/2010-03/msg00328.php
Not sure whether this is feasible for Gsoc....

Best RegardsHuang Qi Victor

2012/3/19 Qi Huang <huangqiyx@hotmail.com>:

I actually tried to find out, personally...not sure if I was searching
wrongly, but searching for TABLESAMPLE did not yield a cornucopia of
useful conversations at the right time in history (~2007), even when
the search is given a broad date-horizon (all), so I, too, an
uninformed as to the specific objections.

http://www.postgresql.org/search/?m=1&amp;q=TABLESAMPLE&amp;l=&amp;d=-1&amp;s=d

I sent a mail to Nail Conway asking him about this. Hope he could give a
good answer.

I never tried to get TABLESAMPLE support into the main PostgreSQL tree
-- I just developed the original code as an exercise for the purposes
of the talk. Implementing TABLESAMPLE would probably be a reasonable
GSoc project.

My memory of the details is fuzzy, but one thing to check is whether
the approach taken by my patch (randomly choose heap pages and then
return all the live tuples in a chosen page) actually meets the
standard's requirements -- obviously it is not true that each heap
page has the same number of live tuples, so you aren't getting a truly
random sample.

Neil

Date: Tue, 20 Mar 2012 14:12:45 -0700> Subject: Re: [HACKERS] Gsoc2012 Idea --- Social Network database schema
From: neil.conway@gmail.com
To: huangqiyx@hotmail.com
CC: daniel@heroku.com; josh@agliodbs.com; pgsql-hackers@postgresql.org

2012/3/19 Qi Huang <huangqiyx@hotmail.com>:

I actually tried to find out, personally...not sure if I was searching
wrongly, but searching for TABLESAMPLE did not yield a cornucopia of
useful conversations at the right time in history (~2007), even when
the search is given a broad date-horizon (all), so I, too, an
uninformed as to the specific objections.

http://www.postgresql.org/search/?m=1&amp;q=TABLESAMPLE&amp;l=&amp;d=-1&amp;s=d

I sent a mail to Nail Conway asking him about this. Hope he could give a
good answer.

I never tried to get TABLESAMPLE support into the main PostgreSQL tree
-- I just developed the original code as an exercise for the purposes
of the talk. Implementing TABLESAMPLE would probably be a reasonable
GSoc project.

My memory of the details is fuzzy, but one thing to check is whether
the approach taken by my patch (randomly choose heap pages and then
return all the live tuples in a chosen page) actually meets the
standard's requirements -- obviously it is not true that each heap
page has the same number of live tuples, so you aren't getting a truly
random sample.

Neil

Thanks so much, Neil. I think I kind of understand the situation for now. The implementation posted by Neil was for the purpose of the talk, thus rushed and may not be up to standard of Postgres Community. Also Neil mentioned the PRNG state in the patch is buggy, and maybe also some others. Thus, in the Gsoc project, I could understand the details of Neil's implementation, fix the bugs, make the code fit for the community standard, and test. Is there any comment on this?

Best Regards and ThanksHuang Qi VictorComputer Science of National University of Singapore

On Tue, Mar 20, 2012 at 10:22 PM, Qi Huang <huangqiyx@hotmail.com> wrote:

Thanks so much, Neil.
I think I kind of understand the situation for now. The implementation
posted by Neil was for the purpose of the talk, thus rushed and may not be
up to st andard of Postgres Community. Also Neil mentioned the PRNG state in
the patch is buggy, and maybe also some others. Thus, in the Gsoc project, I
could understand the details of Neil's implementation, fix the bugs, make
the code fit for the community standard, and test.
Is there any comment on this?

In addition to that, you'll probably find that the old patch doesn't
apply any more, and you'll need to fix a lot of things to get it
working again. The code has changed a lot in the meantime.

One thing we should probably try to establish before you get started
working on this is whether people want the feature, which is basically
the ability to write something like this in the FROM clause of a
query:

table_name TABLESAMPLE { BERNOULLI | SYSTEM } ( sample_percent ) [
REPEATABLE ( repeat_seed ) ] ]

I have at present no position on whether we want that or not, but
maybe someone else does. The upside is that would be a more efficient
replacement for the ORDER BY random() trick that is often used today;
the downside is that it requires dedicated syntax and a whole new
executor node for something that, realistically, isn't going to come
up very often.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:

One thing we should probably try to establish before you get started
working on this is whether people want the feature, which is basically
the ability to write something like this in the FROM clause of a
query:

table_name TABLESAMPLE { BERNOULLI | SYSTEM } ( sample_percent ) [
REPEATABLE ( repeat_seed ) ] ]

I have at present no position on whether we want that or not, but
maybe someone else does. The upside is that would be a more efficient
replacement for the ORDER BY random() trick that is often used today;
the downside is that it requires dedicated syntax and a whole new
executor node for something that, realistically, isn't going to come
up very often.

Yeah --- you're talking about chunks of new code in both planner and
executor. A very rough estimate is that this might be about as
complicated to do properly as MergeAppend was (and we're still shaking
out the bugs in that :-().

Now that would all be fine if this were a widely-desired feature, but
AFAIR the user demand for it has been about nil. So I'm leaning to
the position that we don't want it.

regards, tom lane

Excerpts from Tom Lane's message of mié mar 21 11:35:54 -0300 2012:

Now that would all be fine if this were a widely-desired feature, but
AFAIR the user demand for it has been about nil. So I'm leaning to
the position that we don't want it.

I disagree with there being zero interest ... the "order by random()"
stuff does come up occasionally.

--
Álvaro Herrera <alvherre@commandprompt.com>
The PostgreSQL Company - Command Prompt, Inc.
PostgreSQL Replication, Consulting, Custom Development, 24x7 support

On Wednesday, March 21, 2012 03:47:23 PM Alvaro Herrera wrote:

Excerpts from Tom Lane's message of mié mar 21 11:35:54 -0300 2012:

Now that would all be fine if this were a widely-desired feature, but
AFAIR the user demand for it has been about nil. So I'm leaning to
the position that we don't want it.

I disagree with there being zero interest ... the "order by random()"
stuff does come up occasionally.

Yes.

I wonder if could be hacked ontop of a plain seqscan node instead of building
a completely separate infrastructure. The standards syntax would then simply
be transformed into a select with some special ORDER BY

Andres

On 03/21/2012 10:47 AM, Alvaro Herrera wrote:

Excerpts from Tom Lane's message of mié mar 21 11:35:54 -0300 2012:

Now that would all be fine if this were a widely-desired feature, but
AFAIR the user demand for it has been about nil. So I'm leaning to
the position that we don't want it.

I disagree with there being zero interest ... the "order by random()"
stuff does come up occasionally.

Presumably the reason that's not good enough is that is scans the whole
table (as well as being non-portable)? Maybe we could find some less
invasive way of avoiding that.

cheers

andrew

On Wed, Mar 21, 2012 at 10:57 AM, Andres Freund <andres@anarazel.de> wrote:

On Wednesday, March 21, 2012 03:47:23 PM Alvaro Herrera wrote:

Excerpts from Tom Lane's message of mié mar 21 11:35:54 -0300 2012:

Now that would all be fine if this were a widely-desired feature, but
AFAIR the user demand for it has been about nil.  So I'm leaning to
the position that we don't want it.

I disagree with there being zero interest ... the "order by random()"
stuff does come up occasionally.

Yes.

I wonder if could be hacked ontop of a plain seqscan node instead of building
a completely separate infrastructure. The standards syntax would then simply
be transformed into a select with some special ORDER BY

Well, the standard syntax apparently aims to reduce the number of
returned rows, which ORDER BY does not. Maybe you could do it with
ORDER BY .. LIMIT, but the idea here I think is that we'd like to
sample the table without reading all of it first, so that seems to
miss the point.

I have to admit I'm not very impressed by the argument that we
shouldn't do this because we'll need a new executor node. Creating a
new executor node is not really that big of a deal; and in any case I
don't think Tom will like hacking another bit of functionality into
seq-scan any better, since he refactored both the Merge Append and
Index-Only Scan patches to avoid doing exactly that, and those were
more similar than this probably would be.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Andrew Dunstan <andrew@dunslane.net> writes:

On 03/21/2012 10:47 AM, Alvaro Herrera wrote:

I disagree with there being zero interest ... the "order by random()"
stuff does come up occasionally.

Presumably the reason that's not good enough is that is scans the whole
table (as well as being non-portable)?

The reason I'm concerned about the implementation effort is precisely
that I'm afraid people will have high expectations for the intelligence
of the feature. If it's not materially better than you can get today
with "order by random()", it's not worth doing. That will mean for
example that it can't just be something we bolt onto seqscans and be
done with --- it'll need to interact with indexscans, maybe joins, etc
etc. And no shortcuts on the quality of the sampling, either.

regards, tom lane

Robert Haas <robertmhaas@gmail.com> writes:

Well, the standard syntax apparently aims to reduce the number of
returned rows, which ORDER BY does not. Maybe you could do it with
ORDER BY .. LIMIT, but the idea here I think is that we'd like to
sample the table without reading all of it first, so that seems to
miss the point.

I think actually the traditional locution is more like
WHERE random() < constant
where the constant is the fraction of the table you want. And yeah,
the presumption is that you'd like it to not actually read every row.
(Though unless the sampling density is quite a bit less than 1 row
per page, it's not clear how much you're really going to win.)

regards, tom lane

Date: Wed, 21 Mar 2012 11:00:59 -0400
From: andrew@dunslane.net
To: alvherre@commandprompt.com
CC: tgl@sss.pgh.pa.us; robertmhaas@gmail.com; huangqiyx@hotmail.com; neil.conway@gmail.com; daniel@heroku.com; josh@agliodbs.com; pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] Gsoc2012 Idea --- Social Network database schema

On 03/21/2012 10:47 AM, Alvaro Herrera wrote:

Excerpts from Tom Lane's message of mi锟斤拷 mar 21 11:35:54 -0300 2012:

Now that would all be fine if this were a widely-desired feature, but
AFAIR the user demand for it has been about nil. So I'm leaning to
the position that we don't want it.

I disagree with there being zero interest ... the "order by random()"
stuff does come up occasionally.

Presumably the reason that's not good enough is that is scans the whole
table (as well as being non-portable)? Maybe we could find some less
invasive way of avoiding that.

cheers

andrew

Thanks for your discussion and ideas. As I checked, MS SQL Server and DB2 implemented tablesample for now. At least, it is useful for QUICK sample retrieval for large dataset. I suppose this clause itself will be much faster for using random().About implementation, will the code change be really very large? But the general structure should still be about the same, right?
Best Regards and ThanksHuang Qi VictorComputer Science of National University of Singapore

On Wed, Mar 21, 2012 at 11:34 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Robert Haas <robertmhaas@gmail.com> writes:

Well, the standard syntax apparently aims to reduce the number of
returned rows, which ORDER BY does not.  Maybe you could do it with
ORDER BY .. LIMIT, but the idea here I think is that we'd like to
sample the table without reading all of it first, so that seems to
miss the point.

I think actually the traditional locution is more like
       WHERE random() < constant
where the constant is the fraction of the table you want.  And yeah,
the presumption is that you'd like it to not actually read every row.
(Though unless the sampling density is quite a bit less than 1 row
per page, it's not clear how much you're really going to win.)

Well, there's something mighty tempting about having a way to say
"just give me a random sample of the blocks and I'll worry about
whether that represents a random sample of the rows".

It's occurred to me a few times that it's pretty unfortunate you can't
do that with a TID condition.

rhaas=# explain select * from randomtext where ctid >= '(500,1)' and
ctid < '(501,1)';
QUERY PLAN
--------------------------------------------------------------------
Seq Scan on randomtext (cost=0.00..111764.90 rows=25000 width=31)
Filter: ((ctid >= '(500,1)'::tid) AND (ctid < '(501,1)'::tid))
(2 rows)

The last time this came up for me was when I was trying to find which
row in a large table as making the SELECT blow up; but it seems like
it could be used to implement a poor man's sampling method, too... it
would be nicer, in either case, to be able to specify the block
numbers you'd like to be able to read, rather than bounding the CTID
from both ends as in the above example.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company