Horton

Thread

  1. [jules@jellybean.co.uk: Performance on inserts]

    Jules Bean <jules@jellybean.co.uk> — 2000-08-25T11:19:04Z

    Weird.  When I sent this 24 hours ago, it didn't go through to the
list, although I successfully sent a message to the list only an hour
or so before that.... as far as my mail-server can tell it went off in
the right direcion...


----- Forwarded message from Jules Bean <jules@jellybean.co.uk> -----

Date: Thu, 24 Aug 2000 11:04:25 +0100
From: Jules Bean <jules@jellybean.co.uk>
To: pgsql-hackers@postgresql.org
Subject: Performance on inserts
User-Agent: Mutt/1.2i

[Meta: Please advise if this is the wrong list.  I think, since this
observation relates to Pg internals, this might be the right one, but
feel free to move it back to -general if I'm wrong; I subscribe to
both in any case]

As some of you will have inferred if you've read my last couple of
posts, I'm working on a database with a structure like this (I'm
abstracting; I'm not unfortunately allowed to show you what my client
is really doing here)

A table called 'things' with two columns 'name' and 'category'. The
pair ('name','category') is a primary key.

There are ~ 10 000 000 rows in the table, and category takes values
from a more-or-less fixed set of ~1000 possibilities.  As previously
described the most popular category holds around half the rows, the
next most popular holds nearly half of those left, and most categories
occur very rarely indeed. The median is probably around 1000 (which is
less than the 10 000 you'd expect).

Anyhow, this question isn't about speeding up queries --- we already
have that in the histogram thread.  This question is about speeding up
inserts.

My standard configuration is to have a unique index on (name,category)
and a non-unique index on (category). The main table is ~ 2G on disk,
the index on (name,cat) is about the same size, the index on (cat) is
around 0.6G.

In this set-up inserts have dropped to the terrifyingly slow rate of
several hours per 10 000 insertions. This is not adequate to my needs,
I occasionally have to process 1 000 000 insertions or more!

I have several ideas for speeding this up at the SQL level (including
inserting into a temp table and then using INSERT ... SELECT to remove
the overhead of separate inserts) but that's not what I want to talk
about either...

What I did to day, which made a staggering difference, is dropping the
non-unique index on (category). Suddenly I can insert at approx 40 000
insertions per minute, which is fine for my needs!

So why is updating the huge (2G) unique index on (name,cat) not too
much of a problem, but updating the small (600M) non-unique index on
(cat) sufficient to increase speed by around two orders of magnitude?

A possible reason has occurred to me:

The real slow-down is noticeable when I'm doing a bulk insert where
all new rows belong to the most popular category.  I know that some
btree implementations don't behave particularly sanely with several
million rows in a single key.. is the btree implementation used too
slow in this case?

I haven't collected all the performance statistics I'd like to have,
due to external time pressures, but I can say that under the new
faster configuration, the insertion process is CPU bound, with disk
access far below the levels the machine is capable of.  If I have a chance
I'll collect these stats for the old method too.

Any ideas as to what's going on here appreciated (if not, perhaps it
will point you towards an optimisation you ought to make for 7.1)

Jules

----- End forwarded message -----

-- 
Jules Bean                          |        Any sufficiently advanced 
jules@debian.org                    |  technology is indistinguishable
jules@jellybean.co.uk               |               from a perl script

  2. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-25T15:13:08Z

    Jules Bean <jules@jellybean.co.uk> writes:
> So why is updating the huge (2G) unique index on (name,cat) not too
> much of a problem, but updating the small (600M) non-unique index on
> (cat) sufficient to increase speed by around two orders of magnitude?

> The real slow-down is noticeable when I'm doing a bulk insert where
> all new rows belong to the most popular category.  I know that some
> btree implementations don't behave particularly sanely with several
> million rows in a single key.. is the btree implementation used too
> slow in this case?

Indeed, the btree code used in 7.0 and before is pretty awful in the
face of large numbers of equal keys.  I have improved it somewhat,
but it's still got a problem once there are enough equal keys to span
many index pages.  I just did this experiment:

create table fill(f1 text);
create index filli on fill(f1);
insert into fill values('foo');
insert into fill values('bar');
insert into fill values('baz');

insert into fill select * from fill;	-- repeat this many times

The runtime of the insert/select scales in a pretty horrid fashion:

# tuples inserted		6.5		current

1536				<1sec		<1sec
3072				1.56		<1sec
6144				3.70		1.84
12288				9.73		4.07
24576				93.26		38.72
49152				363.23		231.56

At the end of this process we have about 100 pages of index entries
for each of the three distinct key values, with about 330 items per page.
The fixes that I applied a month or two back improve behavior for
multiple equal keys within a page, but they do little for multiple
pages full of the same key value.  Here's the problem: the code for
INSERT starts by finding the first occurrence of the target key (using
btree descent, so that's fast enough).  But then it does this:

        /*
         * If we will need to split the page to put the item here,
         * check whether we can put the tuple somewhere to the right,
         * instead.  Keep scanning until we find enough free space or
         * reach the last page where the tuple can legally go.
         */
        while (PageGetFreeSpace(page) < itemsz &&
               !P_RIGHTMOST(lpageop) &&
               _bt_compare(rel, keysz, scankey, page, P_HIKEY) == 0)
        {
            /* step right one page */
            BlockNumber        rblkno = lpageop->btpo_next;

            _bt_relbuf(rel, buf, BT_WRITE);
            buf = _bt_getbuf(rel, rblkno, BT_WRITE);
            page = BufferGetPage(buf);
            lpageop = (BTPageOpaque) PageGetSpecialPointer(page);
        }

In other words, we do a linear scan over all the pages containing equal
key values, in the hope of finding one where we can shoehorn in the new
entry.  If the keys are roughly equal-sized, that hope is usually vain,
and we end up splitting the rightmost page that contains any keys
equal to the target key.  Subsequent inserts of the same key value fill
first the left-half split page, then the right-half, then split the
right-half page again and repeat --- but for each insert we first had
to scan over all the preceding pages containing equal keys.  That means
inserting N equal keys takes O(N^2) time, for large enough N.

After thinking about this for a while, I propose a probabilistic
solution.  Suppose that we add to the above loop a random-number check
that causes us to fall out of the loop with probability 1/3 or so;
that is, if the current page is full of the target key, then we move
right to check the next page with probability 2/3, but with probability
1/3 we give up and split the current page to insert the new key.

With this approach we'd hardly ever move more than, say, 10 pages before
splitting, so the time to insert a new key is bounded no matter how many
duplicates it has.

The reason for using a random decision is that if we always stopped
after scanning a fixed number of pages, then the space freed up by the
previous decision to split would always be just out of reach, and we'd
end up with lots of half-full pages of the same key.  With a random
decision we will visit and fill both the left and right halves of a
previously split page.

Comments?  Is there a better way?  What's the best probability to use?

			regards, tom lane

  3. Re: Performance on inserts

    Alfred Perlstein <bright@wintelcom.net> — 2000-08-25T15:52:19Z

    * Tom Lane <tgl@sss.pgh.pa.us> [000825 08:25] wrote:
> 
> In other words, we do a linear scan over all the pages containing equal
> key values, in the hope of finding one where we can shoehorn in the new
> entry.  If the keys are roughly equal-sized, that hope is usually vain,
> and we end up splitting the rightmost page that contains any keys
> equal to the target key.  Subsequent inserts of the same key value fill
> first the left-half split page, then the right-half, then split the
> right-half page again and repeat --- but for each insert we first had
> to scan over all the preceding pages containing equal keys.  That means
> inserting N equal keys takes O(N^2) time, for large enough N.
> 
> After thinking about this for a while, I propose a probabilistic
> solution.  Suppose that we add to the above loop a random-number check
> that causes us to fall out of the loop with probability 1/3 or so;
> that is, if the current page is full of the target key, then we move
> right to check the next page with probability 2/3, but with probability
> 1/3 we give up and split the current page to insert the new key.
> 
> With this approach we'd hardly ever move more than, say, 10 pages before
> splitting, so the time to insert a new key is bounded no matter how many
> duplicates it has.
> 
> The reason for using a random decision is that if we always stopped
> after scanning a fixed number of pages, then the space freed up by the
> previous decision to split would always be just out of reach, and we'd
> end up with lots of half-full pages of the same key.  With a random
> decision we will visit and fill both the left and right halves of a
> previously split page.
> 
> Comments?  Is there a better way?  What's the best probability to use?


I'm unsure if it's possible, but somehow storing the last place one
'gave up' and decided to split the page could offer a useful next-start
for the next insert.  Sort of attempting the split work amongst multiple
requests.  For some reason it looks like your algorithm might cause
problems because it plain gives up after 10 pages?
                        
hope this helps,
-Alfred

  4. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-25T18:25:37Z

    Alfred Perlstein <bright@wintelcom.net> writes:
> I'm unsure if it's possible, but somehow storing the last place one
> 'gave up' and decided to split the page could offer a useful next-start
> for the next insert.

I think that that would create problems with concurrency --- the
Lehman-Yao btree algorithm is designed around the assumption that
writers only move right and never want to go back left to change
a prior page.  So once we've moved right we don't get to go back to
the start of the chain of duplicates.

> For some reason it looks like your algorithm might cause
> problems because it plain gives up after 10 pages?

"Give up" just means "stop looking for already-existing free space,
and make some the hard way".  The steady-state average space utilization
of this way would be somewhat worse than the existing code, probably,
but I don't see that as a big problem.

			regards, tom lane

  5. Re: Performance on inserts

    Alfred Perlstein <bright@wintelcom.net> — 2000-08-25T18:35:49Z

    * Tom Lane <tgl@sss.pgh.pa.us> [000825 11:30] wrote:
> Alfred Perlstein <bright@wintelcom.net> writes:
> > I'm unsure if it's possible, but somehow storing the last place one
> > 'gave up' and decided to split the page could offer a useful next-start
> > for the next insert.
> 
> I think that that would create problems with concurrency --- the
> Lehman-Yao btree algorithm is designed around the assumption that
> writers only move right and never want to go back left to change
> a prior page.  So once we've moved right we don't get to go back to
> the start of the chain of duplicates.

Yes, but inconsistancies about the starting page should be handled
because i'm sure the code takes care of multiple scans from the
start.  A slightly incorrect startscan point is better than starting
from the beginning every time.  It's a hack, but no more than a random
guess where in my situation (if it's do-able) will eventually get
past the first bunch of full pages.

> > For some reason it looks like your algorithm might cause
> > problems because it plain gives up after 10 pages?
> 
> "Give up" just means "stop looking for already-existing free space,
> and make some the hard way".  The steady-state average space utilization
> of this way would be somewhat worse than the existing code, probably,
> but I don't see that as a big problem.

Well there's a possibility of the end of the sequence containing
free space, allowing previous failures to be accounted for can make
a difference.

But it's just a suggestion from someone who really ought to be
studying the internals a bit more. :)

-- 
-Alfred Perlstein - [bright@wintelcom.net|alfred@freebsd.org]
"I have the heart of a child; I keep it in a jar on my desk."

  6. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-25T23:00:22Z

    Alfred Perlstein <bright@wintelcom.net> writes:
> A slightly incorrect startscan point is better than starting
> from the beginning every time.

Not for lookups, it isn't ;-).

I did think about making the btree-descending code act differently
for inserts than lookups, but AFAICS that wouldn't buy anything for
this problem, since until you get down to the leaf level you can't
see where there's free space anyway.  You'd simply be exchanging the
problem of missing free space that's too far to the right for the
problem of missing free space that's to the left of where you chose
to start looking.

The algorithm does seem to work quite nicely just the way I described
it, although it turns out I was off base about a good probability
setting.  I find that something up around 0.99 seems to be good.
Using the same (perhaps overly simplistic) test case:

# tuples inserted		6.5		current+random hack @ 0.99
			Time	index size	Time	index size
1536			<1sec	90112		<1sec	106496
3072			1.56	163840		<1sec	188416
6144			3.70	286720		1.40	376832
12288			9.73	532480		2.65	688128
24576			93.26	1024000		5.22	1368064
49152			363.23	2007040		10.34	2727936
98304						22.07	5545984
196608						45.60	11141120
393216						92.53	22290432

I tried probabilities from 0.67 to 0.999 and found that runtimes didn't
vary a whole lot (though this is near the minimum), while index size
consistently got larger as the probability of moving right decreased.
The runtime is nicely linear throughout the range.

The index size increase might look like a bit of a jump, but actually
this is right where we want it to be.  The old code was effectively
packing each page as full as it could be under these conditions.  That's
not what you want for a btree.  Steady-state load factor for btrees is
usually quoted as somewhere around 70%, and this method manages to
approximate that pretty well with a move-right probability of 0.99 or
a bit less.

			regards, tom lane

  7. Re: Performance on inserts

    Thomas Lockhart <lockhart@alumni.caltech.edu> — 2000-08-26T01:36:57Z

    > Comments?  Is there a better way?  What's the best probability to use?

For this particular example, "partial indices" seems to be the best fit.
The index can be chosen to omit the most common value(s), since those
would indicate a sequential scan anyway.

Other DBs allow a parameter to set the "fill ratio" of index pages,
which might also help. But probably not as much as you might like when
one is doing a large number of inserts at a time.

Your "randomized" algorithm looks very promising. What is the status of
partial indices? Are they functional now, or have they been broken
forever (I'm not recalling)?

                 - Thomas

  8. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-26T01:44:36Z

    Thomas Lockhart <lockhart@alumni.caltech.edu> writes:
> What is the status of
> partial indices? Are they functional now, or have they been broken
> forever (I'm not recalling)?

They've been diked out of gram.y's syntax for CREATE INDEX at least
since Postgres95.  No way to tell who did that, why or when, AFAIK.
There is still an awful lot of support code for them, however.

I have no good way to guess how much bit-rot has occurred in all that
unexercised code ... but it'd be interesting to try to get it going
again.

			regards, tom lane

  9. Re: Performance on inserts

    Hannu Krosing <hannu@tm.ee> — 2000-08-26T07:26:26Z

    Tom Lane wrote:
> 
> Thomas Lockhart <lockhart@alumni.caltech.edu> writes:
> > What is the status of
> > partial indices? Are they functional now, or have they been broken
> > forever (I'm not recalling)?
> 
> They've been diked out of gram.y's syntax for CREATE INDEX at least
> since Postgres95.  No way to tell who did that, why or when, AFAIK.
> There is still an awful lot of support code for them, however.

I suspect that current indexes don't store nulls (and are thereby 
partial indexes in relation to nulls ;)

At least the following suggests it:
---8<------------8<------------8<------------8<---------
hannu=> explain select * from test1 where i=777;
NOTICE:  QUERY PLAN:

Index Scan using test1_i_ndx on test1  (cost=2.05 rows=2 width=8)

EXPLAIN
hannu=> explain select * from test1 where i is null;
NOTICE:  QUERY PLAN:

Seq Scan on test1  (cost=3144.36 rows=27307 width=8)
---8<------------8<------------8<------------8<---------

As the logic to include or not include something in index seems to be
there 
for nulls (and thus can't be very badly bit-rotten) it should be
possible to 
extend it for simpler =x or in(x,y,z) conditions.

> I have no good way to guess how much bit-rot has occurred in all that
> unexercised code ... but it'd be interesting to try to get it going
> again.

Of course the IS NULL case may just be hard-wired in the optimiser in
which 
case there may be not much use of current code. 

IIRC Postgres95 was the first postgres with SQL, so if already that did
not 
have partial indexes then no SQL-grammar for postgreSQL had. (Or maybe 
Illustra did but it was a separate effort anyway ;)

---------------
Hannu

  10. Re: Performance on inserts

    Thomas Lockhart <lockhart@alumni.caltech.edu> — 2000-08-26T07:27:28Z

    > I have no good way to guess how much bit-rot has occurred in all that
> unexercised code ... but it'd be interesting to try to get it going
> again.

Yes, it is a *great* feature, since it directly addresses the problems
associates with one of the most common non-random data distributions
(the index can be constructed to completely ignore those most common
values, and hence be smaller, less often updated, and holding only those
values which might actually be used in an index scan). If we don't get
to outer joins, this would be a good second choice for 7.1 ;)

                     - Thomas

  11. Re: Performance on inserts

    Jules Bean <jules@jellybean.co.uk> — 2000-08-26T10:48:58Z

    On Fri, Aug 25, 2000 at 07:00:22PM -0400, Tom Lane wrote:
> The algorithm does seem to work quite nicely just the way I described
> it, although it turns out I was off base about a good probability
> setting.  I find that something up around 0.99 seems to be good.
> Using the same (perhaps overly simplistic) test case:
> 
> # tuples inserted		6.5		current+random hack @ 0.99
> 			Time	index size	Time	index size
> 1536			<1sec	90112		<1sec	106496
> 3072			1.56	163840		<1sec	188416
> 6144			3.70	286720		1.40	376832
> 12288			9.73	532480		2.65	688128
> 24576			93.26	1024000		5.22	1368064
> 49152			363.23	2007040		10.34	2727936
> 98304						22.07	5545984
> 196608						45.60	11141120
> 393216						92.53	22290432
> 
> I tried probabilities from 0.67 to 0.999 and found that runtimes didn't
> vary a whole lot (though this is near the minimum), while index size
> consistently got larger as the probability of moving right decreased.
> The runtime is nicely linear throughout the range.

That looks brilliant!! (Bearing in mind that I have over 10 million
tuples in my table, you can imagine what performance was like for me!)
Is there any chance you could generate a patch against released 7.0.2
to add just this functionality... It would be the kiss of life for my
code!

(Not in a hurry, I'm not back in work until Wednesday, as it happens)

And, of course, what would /really/ get my code going speedily would
be the partial indices mentioned elsewhere in this thread.  If the
backend could automagically drop keys containing > 10% (tunable) of
the rows from the index, then my index would be (a) about 70% smaller!
and (b) only used when it's faster. [This means it would have to
update some simple histogram data.  However, I can't see that being
much of an overhead]

For the short term, if I can get a working version of the above
randomisation patch, I think I shall 'fake' a partial index by
manually setting 'enable_seqscan=off' for all but the 4 or 5 most
common categories. Those two factors combined will speed up my bulk
inserts a lot.

One other idea, though:

Is there any simple way for Pg to combine inserts into one bulk?
Specifically, their effect on the index files.  It has always seemed
to me to be one of the (many) glaring flaws in SQL that the INSERT
statement only takes one row at a time.  But, using INSERT ... SELECT,
I can imagine that it might be possible to do 'bulk' index
updating. so that scanning process is done once per 'batch'.

If I can make an analogy with sorted files (which indices are rather
like), if I wanted to add another 100 lines to a 1000 line sorted
file, I'd sort the 100 first, and then 'merge' them in.  Whilst I
realise that indices aren't stored sorted (no need), I think it ought
to be possible to construct an efficient algorithm for merging two
btrees?

Jules

-- 
Jules Bean                          |        Any sufficiently advanced 
jules@debian.org                    |  technology is indistinguishable
jules@jellybean.co.uk               |               from a perl script

  12. Re: Performance on inserts

    Matthew Kirkwood <matthew@hairy.beasts.org> — 2000-08-26T11:14:06Z

    On Sat, 26 Aug 2000, Jules Bean wrote:

> Is there any simple way for Pg to combine inserts into one bulk?
> Specifically, their effect on the index files.  It has always seemed
> to me to be one of the (many) glaring flaws in SQL that the INSERT
> statement only takes one row at a time.

One of MySQL's little syntax abuses allows:

INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);

which is nice for avoiding database round trips.  It's one
of the reasons that mysql can do a bulk import so quickly.

> But, using INSERT ... SELECT, I can imagine that it might be possible
> to do 'bulk' index updating. so that scanning process is done once per
> 'batch'.

Logic for these two cases would be excellent.

Matthew.

  13. Re: Performance on inserts

    Alfred Perlstein <bright@wintelcom.net> — 2000-08-26T11:32:51Z

    * Matthew Kirkwood <matthew@hairy.beasts.org> [000826 04:22] wrote:
> On Sat, 26 Aug 2000, Jules Bean wrote:
> 
> > Is there any simple way for Pg to combine inserts into one bulk?
> > Specifically, their effect on the index files.  It has always seemed
> > to me to be one of the (many) glaring flaws in SQL that the INSERT
> > statement only takes one row at a time.
> 
> One of MySQL's little syntax abuses allows:
> 
> INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);
> 
> which is nice for avoiding database round trips.  It's one
> of the reasons that mysql can do a bulk import so quickly.

That would be an _extremely_ useful feature if it made a difference
in postgresql's insert speed.

> 
> > But, using INSERT ... SELECT, I can imagine that it might be possible
> > to do 'bulk' index updating. so that scanning process is done once per
> > 'batch'.
> 
> Logic for these two cases would be excellent.

We do this sometimes, works pretty nicely.

-- 
-Alfred Perlstein - [bright@wintelcom.net|alfred@freebsd.org]
"I have the heart of a child; I keep it in a jar on my desk."

  14. Re: Performance on inserts

    Oliver Teuber <teuber@abyss.devicen.de> — 2000-08-26T11:52:01Z

    On Sat, Aug 26, 2000 at 12:14:06PM +0100, Matthew Kirkwood wrote:
> On Sat, 26 Aug 2000, Jules Bean wrote:
> 
> > Is there any simple way for Pg to combine inserts into one bulk?
> > Specifically, their effect on the index files.  It has always seemed
> > to me to be one of the (many) glaring flaws in SQL that the INSERT
> > statement only takes one row at a time.
> 
> One of MySQL's little syntax abuses allows:
> 
> INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);
> 
> which is nice for avoiding database round trips.  It's one
> of the reasons that mysql can do a bulk import so quickly.
>
copy seems to be very fast ... i dont know why all people use
multiple inserts ??? just use copy ...

yours, oliver teuber

  15. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-26T15:45:48Z

    Matthew Kirkwood <matthew@hairy.beasts.org> writes:
> One of MySQL's little syntax abuses allows:
> INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);

Actually, that's perfectly standard SQL92, just an item we haven't
got round to supporting yet.  (Until we do the fabled querytree
restructuring, it seems a lot harder than it is worth.)

COPY FROM stdin is definitely the fastest way of inserting data,
however, since you avoid a ton of parse/plan overhead that way.
Of course you also lose the ability to have column defaults
computed for you, etc ... there's no free lunch ...

			regards, tom lane

  16. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-26T16:32:20Z

    Jules Bean <jules@jellybean.co.uk> writes:
> Is there any chance you could generate a patch against released 7.0.2
> to add just this functionality... It would be the kiss of life for my
> code!

Will look at it.  Are you brave enough to want to try the rest of the
7.1 rewrite of the btree code, or do you just want this one hack?

> And, of course, what would /really/ get my code going speedily would
> be the partial indices mentioned elsewhere in this thread.  If the
> backend could automagically drop keys containing > 10% (tunable) of
> the rows from the index, then my index would be (a) about 70% smaller!

I don't think anyone was envisioning "automagic" drop of most common
values.  The partial-index support that's partially there ;-) is
designed around manual specification of a predicate, ie, you'd say

	CREATE INDEX mypartialindex ON table (column)
		WHERE column != 42 AND column != 1066

if you wanted a partial index omitting values 42 and 1066.  The backend
would then consider using the index to process queries wherein it can
prove that the query's WHERE implies the index predicate.  For example

	SELECT * FROM table WHERE column = 11

would be able to use this index but

	SELECT * FROM table WHERE column < 100

would not.

You could certainly write a little periodic-maintenance script to
determine the most common values in your tables and recreate your
partial indexes accordingly ... but I doubt it'd make sense to try
to get the system to do that automatically on-the-fly.

> For the short term, if I can get a working version of the above
> randomisation patch, I think I shall 'fake' a partial index by
> manually setting 'enable_seqscan=off' for all but the 4 or 5 most
> common categories. Those two factors combined will speed up my bulk
> inserts a lot.

Uh, enable_seqscan has nothing to do with how inserts are handled...

> Is there any simple way for Pg to combine inserts into one bulk?

COPY.

> Specifically, their effect on the index files.

This particular problem couldn't be cured by batching inserts anyway.
The performance problem was coming from the actual act of inserting
a key (or more specifically, making room for the key) and that's just
got to be done for each key AFAICS.

			regards, tom lane

  17. Re: Performance on inserts

    Jules Bean <jules@jellybean.co.uk> — 2000-08-26T16:57:38Z

    On Sat, Aug 26, 2000 at 12:32:20PM -0400, Tom Lane wrote:
> Jules Bean <jules@jellybean.co.uk> writes:
> > Is there any chance you could generate a patch against released 7.0.2
> > to add just this functionality... It would be the kiss of life for my
> > code!
> 
> Will look at it.  Are you brave enough to want to try the rest of the
> 7.1 rewrite of the btree code, or do you just want this one hack?

Hmm.  I don't know :-) because I don't really know the scope of the
changes... I do need this database to be stable, but OTOH, changes to
the index code are unlikely to corrupt my data.

> 
> I don't think anyone was envisioning "automagic" drop of most common
> values.  The partial-index support that's partially there ;-) is
> designed around manual specification of a predicate, ie, you'd say
> 
> 	CREATE INDEX mypartialindex ON table (column)
> 		WHERE column != 42 AND column != 1066

Fair enough.

> 
> > For the short term, if I can get a working version of the above
> > randomisation patch, I think I shall 'fake' a partial index by
> > manually setting 'enable_seqscan=off' for all but the 4 or 5 most
> > common categories. Those two factors combined will speed up my bulk
> > inserts a lot.
> 
> Uh, enable_seqscan has nothing to do with how inserts are handled...

Um, that was a thinko!  What I was trying to say is: the randomisation
will speed up my bulk inserts, whereas enable_seqscan=off will speed
up the other slow queries in my application, namely "SELECT * where
category='foo'" type queries.

> > Specifically, their effect on the index files.
> 
> This particular problem couldn't be cured by batching inserts anyway.
> The performance problem was coming from the actual act of inserting
> a key (or more specifically, making room for the key) and that's just
> got to be done for each key AFAICS.

In principle, it could be helpful to know you're inserting 10000
tuples with category='xyz'.  Then you only make the left-to-right
scan once, and you fill up every hole you see, before finally
splitting the last page and inserting approx (10000)/(num_per_page)
new pages all at once.  This is surely quicker that doing the
left-to-right scan for each tuple (even though the difference would be
far less noticeable in the presence of your probablistic patch).

Jules

-- 
Jules Bean                          |        Any sufficiently advanced 
jules@debian.org                    |  technology is indistinguishable
jules@jellybean.co.uk               |               from a perl script

  18. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-26T21:09:53Z

    Tom Lane <tgl@sss.pgh.pa.us> writes:
> Jules Bean <jules@jellybean.co.uk> writes:
>> Is there any chance you could generate a patch against released 7.0.2
>> to add just this functionality... It would be the kiss of life for my
>> code!

> Will look at it.

I looked at it and decided that I don't want to mess with it.  The
BTP_CHAIN logic in 7.0 is so weird and fragile that it's hard to tell
what will happen if we try to split anything but the last page of a
chain of duplicates.  The idea I'd had of just dropping in the whole
btree module from current sources doesn't look very practical either;
a lot of changes that span module boundaries would have to be backed out
of it.

My recommendation is to try out current sources (from a nightly snapshot
or CVS).  I realize that running a non-released version might make you
uncomfortable, and rightly so; but I believe that current sources are in
pretty good shape right now.  In any case, working out any bugs lurking
in current strikes me as a much more profitable activity than trying to
back-patch the old btree code.

			regards, tom lane

  19. Re: Performance on inserts

    Chris Bitmead <chrisb@nimrod.itg.telstra.com.au> — 2000-08-27T23:11:49Z

    Matthew Kirkwood wrote:
> 
> On Sat, 26 Aug 2000, Jules Bean wrote:
> 
> > Is there any simple way for Pg to combine inserts into one bulk?
> > Specifically, their effect on the index files.  It has always seemed
> > to me to be one of the (many) glaring flaws in SQL that the INSERT
> > statement only takes one row at a time.
> 
> One of MySQL's little syntax abuses allows:
> 
> INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);

Wouldn't....

INSERT INTO tab (col1, ..); INSERT INTO tab VALUES (val1, ..); INSERT
INTO tab (val2, ..);

also avoid a database round trip??

  20. SQL COPY syntax extension (was: Performance on inserts)

    Hannu Krosing <hannu@tm.ee> — 2000-08-28T10:05:19Z

    Oliver Teuber wrote:
> 
> On Sat, Aug 26, 2000 at 12:14:06PM +0100, Matthew Kirkwood wrote:
> > On Sat, 26 Aug 2000, Jules Bean wrote:
> >
> > > Is there any simple way for Pg to combine inserts into one bulk?
> > > Specifically, their effect on the index files.  It has always seemed
> > > to me to be one of the (many) glaring flaws in SQL that the INSERT
> > > statement only takes one row at a time.
> >
> > One of MySQL's little syntax abuses allows:
> >
> > INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);
> >
> > which is nice for avoiding database round trips.  It's one
> > of the reasons that mysql can do a bulk import so quickly.
> >
> copy seems to be very fast ... i dont know why all people use
> multiple inserts ??? just use copy ...
>

Could copy be extended to support a more SQL-friendly syntax. like

COPY tablename FROM VALUES(
 (x1,y1,z1),
 (x2,y2,z2),
 (x3,y3,z3)
);

The main reason I have not used COPY very much is it's non-SQL syntax 
for field values.

Extending the COPY command would probably be much easier than speeding up
INSERTS.

-------------
Hannu

  21. Re: SQL COPY syntax extension (was: Performance on inserts)

    Thomas Lockhart <lockhart@alumni.caltech.edu> — 2000-08-28T15:39:53Z

    > Could copy be extended to support a more SQL-friendly syntax. like
> COPY tablename FROM VALUES(
>  (x1,y1,z1),
>  (x2,y2,z2),
>  (x3,y3,z3)
> );
> Extending the COPY command would probably be much easier than speeding up
> INSERTS.

That syntax is a lot like a real SQL9x INSERT. Supporting multiple rows
for inserts is probably not that difficult; but since INSERT is used so
much we would have to make sure we don't screw up something else. At the
moment, expanding a line of SQL into multiple internal querytree nodes
is a bit crufty but is possible.

                  - Thomas

  22. Re: SQL COPY syntax extension (was: Performance on inserts)

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-28T17:48:43Z

    Thomas Lockhart <lockhart@alumni.caltech.edu> writes:
> That syntax is a lot like a real SQL9x INSERT.

Multiple row constructors in INSERT is one of my to-do items for the
planned querytree redesign.  I have not thought it was worth messing
with until we're ready to bite that bullet, however.

			regards, tom lane

  23. Re: SQL COPY syntax extension (was: Performance on inserts)

    Hannu Krosing <hannu@tm.ee> — 2000-08-28T18:20:27Z

    Thomas Lockhart wrote:
> 
> > Could copy be extended to support a more SQL-friendly syntax. like
> > COPY tablename FROM VALUES(
> >  (x1,y1,z1),
> >  (x2,y2,z2),
> >  (x3,y3,z3)
> > );
> > Extending the COPY command would probably be much easier than speeding up
> > INSERTS.
> 
> That syntax is a lot like a real SQL9x INSERT. Supporting multiple rows
> for inserts is probably not that difficult; but since INSERT is used so
> much we would have to make sure we don't screw up something else. At the
> moment, expanding a line of SQL into multiple internal querytree nodes
> is a bit crufty but is possible.

What I actually had in mind was a more SQL-like syntax for copy, i.e. no 
default arguments, all fields required etc. that would we easy to bolt
on 
current copy machinery but still use 'SQL' syntax (no . or \. or \\. for
EOD, 
NULL for NULL values, quotes around strings ...)

------------
Hannu

  24. Re: SQL COPY syntax extension (was: Performance on inserts)

    Hannu Krosing <hannu@tm.ee> — 2000-08-28T18:29:17Z

    Tom Lane wrote:
> 
> Thomas Lockhart <lockhart@alumni.caltech.edu> writes:
> > That syntax is a lot like a real SQL9x INSERT.
> 
> Multiple row constructors in INSERT is one of my to-do items for the
> planned querytree redesign.  I have not thought it was worth messing
> with until we're ready to bite that bullet, however.

What is the status of this querytree redesign ?

I'v spent some time trying to get a grip ofthe _exact_ meaning of the
WITH RECURSIVE syntax in SQL3/99 as I badly need it in a project of
mine.

(I know the _general_ meaning - it is for querying tree-structured data
;)

The things the new querytree should address sould be (at least ;) - 

1. OUTER JOINS
2. WITH RECURSIVE
3. Support for positioned UPDATE & DELETE (requires probably lot more
than
  just querytree redesign)
4. Easyer special-casing of optimisations (like using an index on x for 
  'select max(x) from t', but not for 'select max(x) from t where n=7'

Is the special mailing-list for querytree redesing active ?

--------------
Hannu

  25. Re: SQL COPY syntax extension (was: Performance on inserts)

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-28T21:05:10Z

    Hannu Krosing <hannu@tm.ee> writes:
> What is the status of this querytree redesign ?

Waiting for 7.2 cycle, as far as I know.

> The things the new querytree should address sould be (at least ;) - 
> 2. WITH RECURSIVE

I don't think RECURSIVE is a querytree issue --- it looks like a much
bigger problem than that :-(

The things I'm concerned about fixing with querytree redesign are
	* full SQL92 joins
	* subselects in FROM
	* view bugs (grouping and aggregates in views)
	* INSERT ... SELECT bugs
	* reimplement UNION/INTERSECT/EXCEPT in a less hacky way,
	  make cases like SELECT ... UNION ... ORDER BY work.
	  Not to mention UNION etc in a subselect or in INSERT/SELECT.
	* convert WHERE x IN (subselect) to a join-like representation

These are all things that have gone unfixed for years because they're
essentially unfixable with the current single-level representation of
a query.

			regards, tom lane

  26. Re: SQL COPY syntax extension (was: Performance on inserts)

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-08-28T21:14:30Z

    Hannu Krosing <hannu@tm.ee> writes:
> What I actually had in mind was a more SQL-like syntax for copy,
> i.e. no default arguments, all fields required etc. that would we easy
> to bolt on current copy machinery but still use 'SQL' syntax (no . or
> \. or \\. for EOD, NULL for NULL values, quotes around strings ...)

Seems like a reasonable idea, although I'd recommend sticking to the
convention that \. on a line means EOD, to avoid having to hack the
client-side libraries.  As long as you leave that alone, libpq,
libpgtcl, etc etc should be transparent to the copy data format.

			regards, tom lane

  27. Re: SQL COPY syntax extension (was: Performance on inserts)

    Thomas Lockhart <lockhart@alumni.caltech.edu> — 2000-08-29T04:10:51Z

    > The things I'm concerned about fixing with querytree redesign are
...

And it will be a building block for

  *distributed databases
  *replication
  *CORBA/alternate protocols
  *other cool stuff ;)

                - Thomas

  28. Re: Performance on inserts

    Jules Bean <jules@jellybean.co.uk> — 2000-08-31T11:40:42Z

    On Sat, Aug 26, 2000 at 05:09:53PM -0400, Tom Lane wrote:
> Tom Lane <tgl@sss.pgh.pa.us> writes:
> > Jules Bean <jules@jellybean.co.uk> writes:
> >> Is there any chance you could generate a patch against released 7.0.2
> >> to add just this functionality... It would be the kiss of life for my
> >> code!
> 
> > Will look at it.
> 
> I looked at it and decided that I don't want to mess with it.  The
> BTP_CHAIN logic in 7.0 is so weird and fragile that it's hard to tell
> what will happen if we try to split anything but the last page of a
> chain of duplicates.  The idea I'd had of just dropping in the whole
> btree module from current sources doesn't look very practical either;
> a lot of changes that span module boundaries would have to be backed out
> of it.
> 
> My recommendation is to try out current sources (from a nightly snapshot
> or CVS).  I realize that running a non-released version might make you
> uncomfortable, and rightly so; but I believe that current sources are in
> pretty good shape right now.  In any case, working out any bugs lurking
> in current strikes me as a much more profitable activity than trying to
> back-patch the old btree code.

OK.  Thanks very much for going through this with me.

I'm actually going to simply do without the index for this release of
my software -- it's an internal project, and the speed problems of
having no index aren't disastrous. However, I'd rather not fight any
instabilities, this project runs long-term and mostly unattended.

I'll certainly keenly upgrade to 7.1 when it comes out, though, with
the new btree logic.

Jules

  29. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-15T21:37:50Z

    > Thomas Lockhart <lockhart@alumni.caltech.edu> writes:
> > What is the status of
> > partial indices? Are they functional now, or have they been broken
> > forever (I'm not recalling)?
> 
> They've been diked out of gram.y's syntax for CREATE INDEX at least
> since Postgres95.  No way to tell who did that, why or when, AFAIK.
> There is still an awful lot of support code for them, however.

It may have been me.  Not sure.  At the time, no one was sure what they
did, or if we even wanted them.  They were broken, I think.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  30. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-15T21:44:52Z

    > > 98304						22.07	5545984
> > 196608						45.60	11141120
> > 393216						92.53	22290432
> > 
> > I tried probabilities from 0.67 to 0.999 and found that runtimes didn't
> > vary a whole lot (though this is near the minimum), while index size
> > consistently got larger as the probability of moving right decreased.
> > The runtime is nicely linear throughout the range.
> 
> That looks brilliant!! (Bearing in mind that I have over 10 million
> tuples in my table, you can imagine what performance was like for me!)
> Is there any chance you could generate a patch against released 7.0.2
> to add just this functionality... It would be the kiss of life for my
> code!
> 
> (Not in a hurry, I'm not back in work until Wednesday, as it happens)
> 
> And, of course, what would /really/ get my code going speedily would
> be the partial indices mentioned elsewhere in this thread.  If the
> backend could automagically drop keys containing > 10% (tunable) of
> the rows from the index, then my index would be (a) about 70% smaller!
> and (b) only used when it's faster. [This means it would have to
> update some simple histogram data.  However, I can't see that being
> much of an overhead]
> 
> For the short term, if I can get a working version of the above
> randomisation patch, I think I shall 'fake' a partial index by
> manually setting 'enable_seqscan=off' for all but the 4 or 5 most
> common categories. Those two factors combined will speed up my bulk
> inserts a lot.

What would be really nifty is to take the most common value found by
VACUUM ANALYZE, and cause sequential scans if that value represents more
than 50% of the entries in the table.

Added to TODO:

* Prevent index lookups (or index entries using partial index) on most
  common values; instead use sequential scan 

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  31. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-15T21:50:35Z

    > Matthew Kirkwood <matthew@hairy.beasts.org> writes:
> > One of MySQL's little syntax abuses allows:
> > INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);
> 
> Actually, that's perfectly standard SQL92, just an item we haven't
> got round to supporting yet.  (Until we do the fabled querytree
> restructuring, it seems a lot harder than it is worth.)

Added to TODO:

	INSERT INTO tab (col1, ..) VALUES (val1, ..), (val2, ..);

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  32. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-10-15T21:51:02Z

    > * Prevent index lookups (or index entries using partial index) on most
>   common values; instead use sequential scan 

This behavior already exists for the most common value, and would
exist for any additional values that we had stats for.  Don't see
why you think a separate TODO item is needed.

			regards, tom lane

  33. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-15T21:51:48Z

    > > * Prevent index lookups (or index entries using partial index) on most
> >   common values; instead use sequential scan 
> 
> This behavior already exists for the most common value, and would
> exist for any additional values that we had stats for.  Don't see
> why you think a separate TODO item is needed.

You mean the optimizer already skips an index lookup for the most common
value, and instead does a sequential scan?  Seems you are way ahead of
me.


-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  34. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-10-15T21:52:52Z

    Bruce Momjian <pgman@candle.pha.pa.us> writes:
>> Thomas Lockhart <lockhart@alumni.caltech.edu> writes:
>>>> What is the status of partial indices?
>>
>> They've been diked out of gram.y's syntax for CREATE INDEX at least
>> since Postgres95.  No way to tell who did that, why or when, AFAIK.
>> There is still an awful lot of support code for them, however.

> It may have been me.  Not sure.  At the time, no one was sure what they
> did, or if we even wanted them.  They were broken, I think.

Wasn't you unless you were hacking the code before it entered our CVS
system.  I checked the oldest CVS version (Postgres95 release) and saw
that partial indexes were disabled in gram.y in that version.

			regards, tom lane

  35. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-10-15T21:59:22Z

    Bruce Momjian <pgman@candle.pha.pa.us> writes:
>>>> * Prevent index lookups (or index entries using partial index) on most
>>>> common values; instead use sequential scan 
>> 
>> This behavior already exists for the most common value, and would
>> exist for any additional values that we had stats for.  Don't see
>> why you think a separate TODO item is needed.

> You mean the optimizer already skips an index lookup for the most common
> value, and instead does a sequential scan?

No, it goes for the sequential scan if it estimates the cost of the
indexscan as more than sequential.  Indexscan cost depends on estimated
number of retrieved rows --- which it can estimate from pg_statistic
if the query is WHERE column = mostcommonvalue.  So which plan you get
depends on just how common the most common value is.

Hard-wiring either choice of plan for the most common value would be
inferior to what the code already does, AFAICS.  But for values other
than the-most-common, we don't have adequate stats in pg_statistic,
and so you may or may not get a good estimated row count and hence
a good choice of plan.  That's what needs to be fixed.

			regards, tom lane

  36. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-15T22:22:28Z

    > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> >>>> * Prevent index lookups (or index entries using partial index) on most
> >>>> common values; instead use sequential scan 
> >> 
> >> This behavior already exists for the most common value, and would
> >> exist for any additional values that we had stats for.  Don't see
> >> why you think a separate TODO item is needed.
> 
> > You mean the optimizer already skips an index lookup for the most common
> > value, and instead does a sequential scan?
> 
> No, it goes for the sequential scan if it estimates the cost of the
> indexscan as more than sequential.  Indexscan cost depends on estimated
> number of retrieved rows --- which it can estimate from pg_statistic
> if the query is WHERE column = mostcommonvalue.  So which plan you get
> depends on just how common the most common value is.
> 
> Hard-wiring either choice of plan for the most common value would be
> inferior to what the code already does, AFAICS.  But for values other
> than the-most-common, we don't have adequate stats in pg_statistic,
> and so you may or may not get a good estimated row count and hence
> a good choice of plan.  That's what needs to be fixed.

OK, I remember now.  If the most common value is used as a constant, it
uses the value from pg_statistic for most common, rather than use
the dispersion value.  That is great.

What I am more concerned about is a join that uses the most common
value.  We do an index scan in that case.  I wonder of we could get
something into the executor that would switch to sequential scan when
the most common value is hit.  Is that worth persuing?




-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  37. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-10-15T22:30:54Z

    Bruce Momjian <pgman@candle.pha.pa.us> writes:
> What I am more concerned about is a join that uses the most common
> value.  We do an index scan in that case.

No, we do whichever plan looks cheapest.  Again, it's all about
statistics.

Right now, eqjoinsel() is just a stub that returns a constant
selectivity estimate.  It might be useful to compute some more
sophisticated value based on pg_statistic entries for the two
columns, but right now I doubt you could tell much.  Should keep
the join case in mind when we extend the statistics...

			regards, tom lane

  38. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-15T23:20:35Z

    > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > What I am more concerned about is a join that uses the most common
> > value.  We do an index scan in that case.
> 
> No, we do whichever plan looks cheapest.  Again, it's all about
> statistics.
> 
> Right now, eqjoinsel() is just a stub that returns a constant
> selectivity estimate.  It might be useful to compute some more
> sophisticated value based on pg_statistic entries for the two
> columns, but right now I doubt you could tell much.  Should keep
> the join case in mind when we extend the statistics...

OK, let me be more specific. Suppose the most common value in a column
is 3.  For a query "col = 3", we know 3 is most common, and use the most
common statistics rather than the dispersion statistic, right?

OK, let's assume use of the most common statistic causes a sequential
scan, but use of dispersion causes an index scan.

The query "col = 3" uses sequential scan. In the query "col = tab2.col2",
the dispersion statistic is used, causing an index scan.  

However, assume tab2.col2 equals 3.  I assume this would cause an index
scan because the executor doesn't know about the most common value,
right? Is it worth trying to improve that?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  39. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-10-15T23:33:36Z

    Bruce Momjian <pgman@candle.pha.pa.us> writes:
> However, assume tab2.col2 equals 3.  I assume this would cause an index
> scan because the executor doesn't know about the most common value,
> right? Is it worth trying to improve that?

Oh, I see: you are assuming that a nestloop join is being done, and
wondering if it's worthwhile to switch dynamically between seqscan
and indexscan for each scan of the inner relation, depending on exactly
what value is being supplied from the outer relation for that scan.
Hmm.

Not sure if it's worth the trouble or not.  Nestloop is usually a
last-resort join strategy anyway, and is unlikely to be picked when the
tables are large enough to make performance be a big issue.

			regards, tom lane

  40. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-16T03:18:16Z

    > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > However, assume tab2.col2 equals 3.  I assume this would cause an index
> > scan because the executor doesn't know about the most common value,
> > right? Is it worth trying to improve that?
> 
> Oh, I see: you are assuming that a nestloop join is being done, and
> wondering if it's worthwhile to switch dynamically between seqscan
> and indexscan for each scan of the inner relation, depending on exactly
> what value is being supplied from the outer relation for that scan.
> Hmm.
> 
> Not sure if it's worth the trouble or not.  Nestloop is usually a
> last-resort join strategy anyway, and is unlikely to be picked when the
> tables are large enough to make performance be a big issue.

Yes, I realize only nested loop has this problem.  Mergejoin and
Hashjoin actually would grab the whole table via sequential scan, so the
index is not involved, right?

Let me ask, if I do the query, "tab1.col = tab2.col and tab2.col = 3",
the system would use an index to get tab2.col, but then what method
would it use to join to tab1?  Nested loop because it thinks it is going
to get only one row from tab1.col1.  If 3 is the most common value in
tab1.col, it is going to get lots more than one row, right?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  41. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-10-16T04:12:58Z

    Bruce Momjian <pgman@candle.pha.pa.us> writes:
> Yes, I realize only nested loop has this problem.  Mergejoin and
> Hashjoin actually would grab the whole table via sequential scan, so the
> index is not involved, right?

They'd grab the whole table after applying restriction clauses.  An
indexscan might be used if there's an appropriate restriction clause
for either table, or to sort a table for merge join...

> Let me ask, if I do the query, "tab1.col = tab2.col and tab2.col = 3",
> the system would use an index to get tab2.col, but then what method
> would it use to join to tab1?  Nested loop because it thinks it is going
> to get only one row from tab1.col1.

I don't think it'd think that.  The optimizer is not presently smart
enough to make the transitive deduction that tab1.col = 3 (it does
recognize transitive equality of Vars, but doesn't extend that to
non-variable values).  So it won't see any restriction clause for
tab1 here.

If it thinks that tab2.col = 3 will yield one row, it might well choose
a nested loop with tab2 as the outer, rather than merge or hash join.
So an inner indexscan for tab1 is definitely a possible plan.

			regards, tom lane

  42. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-16T04:41:49Z

    > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > Yes, I realize only nested loop has this problem.  Mergejoin and
> > Hashjoin actually would grab the whole table via sequential scan, so the
> > index is not involved, right?
> 
> They'd grab the whole table after applying restriction clauses.  An
> indexscan might be used if there's an appropriate restriction clause
> for either table, or to sort a table for merge join...
> 
> > Let me ask, if I do the query, "tab1.col = tab2.col and tab2.col = 3",
> > the system would use an index to get tab2.col, but then what method
> > would it use to join to tab1?  Nested loop because it thinks it is going
> > to get only one row from tab1.col1.
> 
> I don't think it'd think that.  The optimizer is not presently smart
> enough to make the transitive deduction that tab1.col = 3 (it does
> recognize transitive equality of Vars, but doesn't extend that to
> non-variable values).  So it won't see any restriction clause for
> tab1 here.
> 
> If it thinks that tab2.col = 3 will yield one row, it might well choose
> a nested loop with tab2 as the outer, rather than merge or hash join.
> So an inner indexscan for tab1 is definitely a possible plan.

Yes, that was my point, that a nested loop could easily be involved if
the joined table has a restriction.  Is there a TODO item here?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  43. Re: Performance on inserts

    Tom Lane <tgl@sss.pgh.pa.us> — 2000-10-16T04:48:56Z

    Bruce Momjian <pgman@candle.pha.pa.us> writes:
>> So an inner indexscan for tab1 is definitely a possible plan.

> Yes, that was my point, that a nested loop could easily be involved if
> the joined table has a restriction.  Is there a TODO item here?

More like a "to investigate" --- I'm not sold on the idea that a
dynamic switch in plan types would be a win.  Maybe it would be,
but...

One thing to think about is that it'd be critically dependent on having
accurate statistics.  Currently, the planner only places bets on the
average behavior over a whole join.  If you make a separate bet on each
scan, then you open up the risk of betting wrong every time, should
your stats be out-of-date or otherwise misleading.

			regards, tom lane

  44. Re: Performance on inserts

    Bruce Momjian <pgman@candle.pha.pa.us> — 2000-10-16T04:59:47Z

    > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> >> So an inner indexscan for tab1 is definitely a possible plan.
> 
> > Yes, that was my point, that a nested loop could easily be involved if
> > the joined table has a restriction.  Is there a TODO item here?
> 
> More like a "to investigate" --- I'm not sold on the idea that a
> dynamic switch in plan types would be a win.  Maybe it would be,
> but...
> 
> One thing to think about is that it'd be critically dependent on having
> accurate statistics.  Currently, the planner only places bets on the
> average behavior over a whole join.  If you make a separate bet on each
> scan, then you open up the risk of betting wrong every time, should
> your stats be out-of-date or otherwise misleading.

I agree.  Not sure how to approach this, but I am sure it is dealt with
by most database systems.  Can someone find out how other db's handle
this?  Is there any research on it?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026