You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-user@db.apache.org by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> on 2009/01/12 12:59:59 UTC
Bad performance with UPDATE on a nested SELECT
Hi list,
I am seeing some bad performance on an UPDATE on a nested SELECT. The
query in case takes about 30s, but I think it should be a lot faster
because the same query on a PostgresQL runs < 1 ms... Anyway, here's the
setup:
I have two tables 'records' and 'relations'.
The 'records' table stores a bunch of records along with some metadata.
It has a unique index 'i' on the 'id' column and a normal index 'm' on
the 'mtime' column. This table holds about 1.5M rows.
The 'relations' table stores parent/child relations between records and
has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
(parentId,childId) and a normal index 'c' on childId. This table holds
about 35k rows.
The problematic query looks like:
UPDATE records
SET base='my_base'
WHERE id IN (
SELECT parentId
FROM relations
WHERE childId='id_1');
The right SELECT returns two rows (and in general 0-3 or something like
that). If I instead of the SELECT hardcode two ids, making the right
part look like "IN ('id_2', 'id_3')" the query runs in < 1ms.
It would appear that Derby iterates over the entire 'records' table or
something like that. This also appears to be the case as far as I can
read from the attached query plan...
Any pointers or ideas on how to tackle this are most appreciated.
Cheers,
Mikkel
Re: Bad performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
On Tue, 2009-01-13 at 16:42 +0100, Knut Anders Hatlen wrote:
> ij> create table summa_records (id varchar(20), base varchar(10));
> 0 rows inserted/updated/deleted
> ij> create table summa_relations (parentId varchar(20), childId varchar(20));
> 0 rows inserted/updated/deleted
> ij> insert into summa_records(id) values 'test1', 'test2';
> 2 rows inserted/updated/deleted
> ij> insert into summa_relations values ('test1', 'test2');
> 1 row inserted/updated/deleted
> ij> create index c on summa_relations(childId);
> 0 rows inserted/updated/deleted
> ij> UPDATE summa_records SET base='my_base' WHERE id IN
> > (SELECT parentId FROM summa_relations --DERBY-PROPERTIES index=C
> > WHERE childId='test2');
> 1 row inserted/updated/deleted
Ok, thanks for you patience, I got it working just now... The query
still runs in about 4-5s (on 700k records) though...
It seems I might have to hack around this by doing the SELECT first and
then iterating over the result set and doing one UPDATE per row... It
should still perform fairly well, even though it makes me feel a bit
dirty...
If it will make any difference I can attach the query plan to
https://issues.apache.org/jira/browse/DERBY-4007. Likewise with the
results of the interger based ids in my discussion with Mike..?
Cheers,
Mikkel
Re: Bad performance with UPDATE on a nested SELECT
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> writes:
> On Tue, 2009-01-13 at 11:59 +0100, Knut Anders Hatlen wrote:
>> UPDATE summa_records SET base='my_base' WHERE id IN
>> (SELECT parentId FROM summa_relations --DERBY-PROPERTIES index=C
>> WHERE childId='horizon_2332668')
>
> Hmmm... I just get:
> ERROR 42X41: In the Properties clause of a FROM list, the property
> 'index' is not valid (the property was being set to 'C').
>
> Does this require Derby trunk or something?
No, I did this with 10.4.2.0:
ij> create table summa_records (id varchar(20), base varchar(10));
0 rows inserted/updated/deleted
ij> create table summa_relations (parentId varchar(20), childId varchar(20));
0 rows inserted/updated/deleted
ij> insert into summa_records(id) values 'test1', 'test2';
2 rows inserted/updated/deleted
ij> insert into summa_relations values ('test1', 'test2');
1 row inserted/updated/deleted
ij> create index c on summa_relations(childId);
0 rows inserted/updated/deleted
ij> UPDATE summa_records SET base='my_base' WHERE id IN
> (SELECT parentId FROM summa_relations --DERBY-PROPERTIES index=C
> WHERE childId='test2');
1 row inserted/updated/deleted
--
Knut Anders
Re: Bad performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
On Tue, 2009-01-13 at 11:59 +0100, Knut Anders Hatlen wrote:
> Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> writes:
>
> > On Mon, 2009-01-12 at 13:49 +0100, Knut Anders Hatlen wrote:
> >> Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> writes:
> >>
> >> > Hi list,
> >> >
> >> > I am seeing some bad performance on an UPDATE on a nested SELECT. The
> >> > query in case takes about 30s, but I think it should be a lot faster
> >> > because the same query on a PostgresQL runs < 1 ms... Anyway, here's the
> >> > setup:
> >> >
> >> > I have two tables 'records' and 'relations'.
> >> >
> >> > The 'records' table stores a bunch of records along with some metadata.
> >> > It has a unique index 'i' on the 'id' column and a normal index 'm' on
> >> > the 'mtime' column. This table holds about 1.5M rows.
> >> >
> >> > The 'relations' table stores parent/child relations between records and
> >> > has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
> >> > (parentId,childId) and a normal index 'c' on childId. This table holds
> >> > about 35k rows.
> >>
> >> Hi Mikkel,
> >>
> >> Derby sometimes has problems with the cardinality statistics getting
> >> stale in non-unique indexes, which may lead to bad decisions being made
> >> by the optimizer. Do you still see the problem if you compress the
> >> relations table (alternatively, you could drop the index on childId and
> >> recreate it)? If this speeds up the execution, you're probably
> >> experiencing these issues:
> >>
> >> https://issues.apache.org/jira/browse/DERBY-269
> >> https://issues.apache.org/jira/browse/DERBY-3788
> >>
> >
> > Hi Knut,
> >
> > I just tried compressing both the 'relations' and the 'records' table.
> > This makes the query run in about 20s. So a small win, but nothing
> > significant.
>
> Right, that suggests that you're seeing a different problem. Just to be
> sure that the old query plan isn't still lying around in the statement
> cache, it might be worth checking if clearing the statement cache
> changes anything:
>
> CALL SYSCS_UTIL.SYSCS_EMPTY_STATEMENT_CACHE()
That didn't change anything...
> 1) The IN clause is rewritten to a join with SUMMA_RECORDS as the outer
> table, and we have no information to limit the scan of the outer table,
> hence a full table scan is performed. It would probably have been better
> if SUMMA_RECORDS were the inner table. Then the C index could be used to
> enforce the restriction (childId='...') on the outer table,
> SUMMA_RELATIONS, and index I could be used to perform lookups in the
> inner table.
>
> 2) The index scan on SUMMA_RELATIONS uses the index PC. Since that index
> is on the columns (parentId, childId), it is primarily sorted on
> parentId, so the scan needs to go through the entire index, for each row
> in the outer table, in order to match childId with the criterion in the
> WHERE clause of the nested select. It would probably be better to use
> the index on childId (index C) instead of PC (or reverse the order of
> the columns in the PC index).
I just tried dropping the PC index (as suggested by Mike in another
thread) and replacing it with a non-unique index P only on the parentId
column of the relations table. This did not have any significant impact
on execution time (still ~20s).
I attached query plan and dblook dumps to
https://issues.apache.org/jira/browse/DERBY-4007 for anybody
interested...
> Derby allows you to override some of the optimizer's decisions, but it's
> not as easy for UPDATE statements as it is for SELECT statements, so I
> don't know how to tell it not to pick the table scan. Using the C index
> instead of the PC index should be easy enough, though:
>
> UPDATE summa_records SET base='my_base' WHERE id IN
> (SELECT parentId FROM summa_relations --DERBY-PROPERTIES index=C
> WHERE childId='horizon_2332668')
Hmmm... I just get:
ERROR 42X41: In the Properties clause of a FROM list, the property
'index' is not valid (the property was being set to 'C').
Does this require Derby trunk or something?
Cheers,
Mikkel
RE: Bad table design leads to bad performance...RE: Bad
performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
On Wed, 2009-01-14 at 14:15 +0100, derby@segel.com wrote:
>
> > -----Original Message-----
> > From: Mikkel Kamstrup Erlandsen [mailto:mke@statsbiblioteket.dk]
> > Sent: Wednesday, January 14, 2009 12:12 AM
> > To: Derby Discussion
> > Cc: msegel@segel.com
> > Subject: RE: Bad table design leads to bad performance...RE: Bad
> > performance with UPDATE on a nested SELECT
> [SNIP]
> > >
> > > As I said above, I just tried out your strategy. Using only integer
> > > handles the query runs in about 4s. I still need a factor 100 better
> > > than that...
> >
> > Sorry, forgot to add that this was on a base with ~700k rows only, not
> > the full 1,5M rows one...
> >
> > Cheers,
> > Mikkel
>
> Mikkel,
>
> Sorry if I'm being a bit slow...
>
> That 4 seconds was on 700K rows using integers instead of varchars?
> Does that also include the optimizer hint or was that without the optimizer
> hint?
Yes. And it was without the optimizer hint.
> The reason I ask is that if your query was the same and you just switched
> from varchar to integers, then there clearly is an issue with varchars and
> the optimizer.
Yeah, the query was the exact same, just with INTEGER instead of
VARCHAR(255) for the id column. For reference, the query we are talking
about:
UPDATE records
SET base='my_base'
WHERE id IN (
SELECT parentId
FROM relations
WHERE childId='id_1');
I am not sure that the issue is about varchars. As I stated in an
earlier mail I had a running time of 5-10s on the 700k row base when I
was using varchars. This means that an identity index on an integer
column gives a small speed up (maybe 30% if I am to pull a random number
out of my hat). What I was hoping for was more like 3000%...
> If I understood you correctly, it sounded like when you tried the optimizer
> hint, using varchars, you got the same result as the integers. Is that the
> case?
More or less... The integer case might be slightly faster, but I don't
have precise timings to back this up. In any case the difference here is
very small.
Generally I would say that the optimizer hint doesn't provide any real
difference.
> If you're going to loop through the result set, you may find it faster to
> delete the old row and then perform the insert. Updates are hard(er) on a
> database.
I am just doing a manual loop over the SELECT result set now (it usually
contains 0-5 rows) and doing an update for each row. It works at an
acceptable speed. < 1ms for each op.
> Derby isn't Postgres and there are some neat things you can do in C that you
> can't do in Java that could give a C based database an edge. (Pointers can
> be your friend. ;-) At the same time, there are design decisions that could
> have been made which are hampering performance now.
And C doesn't have a JIT compiler :-) Java programs can be blazingly
fast. Lucene impresses me on a daily basis :-)
I don't believe this issue is about Java. At this point I am quite
certain that it is a problem with the query optimizer in Derby.
Cheers,
Mikkel
RE: Bad table design leads to bad performance...RE: Bad performance with UPDATE on a nested SELECT
Posted by de...@segel.com.
> -----Original Message-----
> From: Mikkel Kamstrup Erlandsen [mailto:mke@statsbiblioteket.dk]
> Sent: Wednesday, January 14, 2009 12:12 AM
> To: Derby Discussion
> Cc: msegel@segel.com
> Subject: RE: Bad table design leads to bad performance...RE: Bad
> performance with UPDATE on a nested SELECT
[SNIP]
> >
> > As I said above, I just tried out your strategy. Using only integer
> > handles the query runs in about 4s. I still need a factor 100 better
> > than that...
>
> Sorry, forgot to add that this was on a base with ~700k rows only, not
> the full 1,5M rows one...
>
> Cheers,
> Mikkel
Mikkel,
Sorry if I'm being a bit slow...
That 4 seconds was on 700K rows using integers instead of varchars?
Does that also include the optimizer hint or was that without the optimizer
hint?
The reason I ask is that if your query was the same and you just switched
from varchar to integers, then there clearly is an issue with varchars and
the optimizer.
If I understood you correctly, it sounded like when you tried the optimizer
hint, using varchars, you got the same result as the integers. Is that the
case?
Again its evidence that supports the issue that there is something wrong
with the optimizer.
If you're going to loop through the result set, you may find it faster to
delete the old row and then perform the insert. Updates are hard(er) on a
database.
Derby isn't Postgres and there are some neat things you can do in C that you
can't do in Java that could give a C based database an edge. (Pointers can
be your friend. ;-) At the same time, there are design decisions that could
have been made which are hampering performance now.
-Mike
RE: Bad table design leads to bad performance...RE: Bad
performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
On Tue, 2009-01-13 at 23:47 +0100, Mikkel Kamstrup Erlandsen wrote:
> On Tue, 2009-01-13 at 16:59 +0100, Michael Segel wrote:
> > Yes. My point is that Derby isn't PostgresSQL and there are a lot of
> > internal factors that could cause the problems you are seeing. How database
> > engines handle varchars internally could be an issue when concerning
> > performance. In terms of languages, C is very different from Java. There are
> > things that you can do in C that you can't do in Java.
> >
> > With respect to your problem, I believe that there is an issue with the
> > query optimizer. By cleaning up your table design the optimizer may make a
> > better selection. As a last resort, you then apply the hint.
> >
> > What I am suggesting is that for testing purposes only, you create the table
> > that maps a varchar to an identity integer. Then for each row in your base
> > table, you insert a row in to a new table that stores the integer id instead
> > of the varchar. You then do the same for the relationship table.
> >
> > When you re-run the query you can either join the table in the inner select,
> > or you could just hardcode the integer value instead of the varchar value.
> >
> > Yes there is minimal cost for the join, but you're talking milliseconds.
> > Weigh that against the time spent on a sequential scan of 1.5million +
> > records...
>
> As I said above, I just tried out your strategy. Using only integer
> handles the query runs in about 4s. I still need a factor 100 better
> than that...
Sorry, forgot to add that this was on a base with ~700k rows only, not
the full 1,5M rows one...
Cheers,
Mikkel
RE: Bad table design leads to bad performance...RE: Bad
performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
On Tue, 2009-01-13 at 16:59 +0100, Michael Segel wrote:
> See my comments mixed in...
>
> Just a caveat, you're right, I don't know your entire application, I'm just
> looking at it from what little information you have shared in your posts....
I apologize if I am cryptic, there are no secrets at all[1], but we do
have a lot of odd requirements from the data model that I wont bore you
with if I can avoid it :-)
[1]: I am working on an open source project called Summa:
http://wiki.statsbiblioteket.dk/summa
More comments inlined below...
> > -----Original Message-----
> > From: Mikkel Kamstrup Erlandsen [mailto:mke@statsbiblioteket.dk]
> > Sent: Tuesday, January 13, 2009 8:51 AM
> > To: Derby Discussion; msegel@segel.com
> > Subject: Re: Bad table design leads to bad performance...RE: Bad
> > performance with UPDATE on a nested SELECT
> >
> [SNIP]
> >
> > It will not be trivial for us to "just" use integer ids. The problem is
> > that either end of a relation will not necessarily exist in the base.
> >
>
> In your update statement, as written, unless there is a parent to child
> relationship established, you will not update a base record. Your statement
> is matching the base record's id on a match to a parentId which has a
> specific child record.
>
> This means that you *can* have a base record that will not get updated.
Yes, this is intentional. In the "real" query I actually update the
timestamps of all parent records of a given record. I just used 'base'
here instead of timestamps because it is simpler in writing (and has the
exact same execution pattern).
<SNIP>
> > id: book_1
> > children: book_2, book_3
> > parents:
> >
> > 7 days later we receive metadata for book_2:
> >
> > id: book_2
> > children:
> > parents:
<SNIP>
> Yes! That is exactly what I am suggesting. I wasn't sure but you're
> indicating that 'book_1', 'book_2' and 'book_3' are all the same data types
> where the role is going to be table dependent. So you can create a simple
> table that maps a book varchar to an identity value. (A unique integer value
> with a backing index) This implies that there can only be one id for
> 'book_1'. Also you would then want an index on the varchar only for this
> table. (One fat index instead of 3)
>
> By doing this, you do not have any need for anything more than allowing
> nulls in the column.
Ok, I've tried this. More on this below...
> Using your example above, you say that book_1 has children (book_2 and
> book_3) Does this not imply that for book_2 that book_1 is its parent?
Yes.
> So do you add a parent child relationship, or do you keep it null until
> there is a metadata record and if the metadata record indicates that there
> are no relationships, do you then remove any relationships that might have
> been set prior to the new record?
When we put book_1 in the db we simply add the tuples (book_1,book_2)
and (book_1,book_3) to the relations table.
> Yes. My point is that Derby isn't PostgresSQL and there are a lot of
> internal factors that could cause the problems you are seeing. How database
> engines handle varchars internally could be an issue when concerning
> performance. In terms of languages, C is very different from Java. There are
> things that you can do in C that you can't do in Java.
>
> With respect to your problem, I believe that there is an issue with the
> query optimizer. By cleaning up your table design the optimizer may make a
> better selection. As a last resort, you then apply the hint.
>
> What I am suggesting is that for testing purposes only, you create the table
> that maps a varchar to an identity integer. Then for each row in your base
> table, you insert a row in to a new table that stores the integer id instead
> of the varchar. You then do the same for the relationship table.
>
> When you re-run the query you can either join the table in the inner select,
> or you could just hardcode the integer value instead of the varchar value.
>
> Yes there is minimal cost for the join, but you're talking milliseconds.
> Weigh that against the time spent on a sequential scan of 1.5million +
> records...
As I said above, I just tried out your strategy. Using only integer
handles the query runs in about 4s. I still need a factor 100 better
than that...
Instead of using Derby properties we will probably resolve to hacking
around this in the code by doing the SELECT first and then iterating
manually over the result set doing one UPDATE per row... Before it gets
to that I'll give it a final stab tomorrow when I am rested.
Cheers,
Mikkel
RE: Bad table design leads to bad performance...RE: Bad performance with UPDATE on a nested SELECT
Posted by Michael Segel <ms...@segel.com>.
See my comments mixed in...
Just a caveat, you're right, I don't know your entire application, I'm just
looking at it from what little information you have shared in your posts....
> -----Original Message-----
> From: Mikkel Kamstrup Erlandsen [mailto:mke@statsbiblioteket.dk]
> Sent: Tuesday, January 13, 2009 8:51 AM
> To: Derby Discussion; msegel@segel.com
> Subject: Re: Bad table design leads to bad performance...RE: Bad
> performance with UPDATE on a nested SELECT
>
[SNIP]
>
> It will not be trivial for us to "just" use integer ids. The problem is
> that either end of a relation will not necessarily exist in the base.
>
In your update statement, as written, unless there is a parent to child
relationship established, you will not update a base record. Your statement
is matching the base record's id on a match to a parentId which has a
specific child record.
This means that you *can* have a base record that will not get updated.
> This means that if we use proxy integer ids we'd have to insert a
> dummy-id in the relations table that me later must pair up to the real
> id if a record with linked id shows up.
>
No.
This is not the case.
(See below)
> To be concrete; I am working at a library and the "records" are books
> linking each other. A case could be that we are instructed to put the
> following metadata in the base:
>
> id: book_1
> children: book_2, book_3
> parents:
>
> 7 days later we receive metadata for book_2:
>
> id: book_2
> children:
> parents:
>
> Note that book_2 does not mention its relation to book_1. This is
> (sadly) legal in our world.
>
> I can see that your strategy can work out if we store
> integer_id->varchar_id in a separate table. Ids for non-existing records
> can just be added here as well. I am just concerned that this will bring
> even more JOIN overhead than we already have...
>
Yes! That is exactly what I am suggesting. I wasn't sure but you're
indicating that 'book_1', 'book_2' and 'book_3' are all the same data types
where the role is going to be table dependent. So you can create a simple
table that maps a book varchar to an identity value. (A unique integer value
with a backing index) This implies that there can only be one id for
'book_1'. Also you would then want an index on the varchar only for this
table. (One fat index instead of 3)
By doing this, you do not have any need for anything more than allowing
nulls in the column.
Using your example above, you say that book_1 has children (book_2 and
book_3) Does this not imply that for book_2 that book_1 is its parent?
So do you add a parent child relationship, or do you keep it null until
there is a metadata record and if the metadata record indicates that there
are no relationships, do you then remove any relationships that might have
been set prior to the new record?
> > Also do not use query optimization statements except as a last resort.
> >
> > Again I *highly* recommend creating a table where you assign a unique id
> to
> > a given 'parentId'/'id'/'childId' and then use that id in these tables
> > instead of the varchar. 1.5 million rows of an index on a varchar column
> > means a lot of wasted space and overhead. (Just to re-iterate the point
> made
> > above.)
> >
> > Look, no disrespect... But a lot of times, improving your table design
> will
> > improve your performance and at the same time keeping your solution
> database
> > agnostic.
>
> Your input is much appreciated and provides good food for thought :-)
> The problem is just that we have a PostgresQL doing this exact query (on
> the same data amounts) in < 1ms, but we would really, _really_ like to
> use Derby instead.
>
> Cheers,
> Mikkel
Yes. My point is that Derby isn't PostgresSQL and there are a lot of
internal factors that could cause the problems you are seeing. How database
engines handle varchars internally could be an issue when concerning
performance. In terms of languages, C is very different from Java. There are
things that you can do in C that you can't do in Java.
With respect to your problem, I believe that there is an issue with the
query optimizer. By cleaning up your table design the optimizer may make a
better selection. As a last resort, you then apply the hint.
What I am suggesting is that for testing purposes only, you create the table
that maps a varchar to an identity integer. Then for each row in your base
table, you insert a row in to a new table that stores the integer id instead
of the varchar. You then do the same for the relationship table.
When you re-run the query you can either join the table in the inner select,
or you could just hardcode the integer value instead of the varchar value.
Yes there is minimal cost for the join, but you're talking milliseconds.
Weigh that against the time spent on a sequential scan of 1.5million +
records...
-Mike
Re: Bad table design leads to bad performance...RE: Bad
performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
On Tue, 2009-01-13 at 15:19 +0100, Michael Segel wrote:
>
> > -----Original Message-----
> > From: Knut.Hatlen@Sun.COM [mailto:Knut.Hatlen@Sun.COM]
> > Sent: Tuesday, January 13, 2009 4:59 AM
> > To: Derby Discussion
> > Subject: Re: Bad performance with UPDATE on a nested SELECT
> [SNIP]
> > Yes, it looks like the same query plan. I see the following problems
> > with this query plan:
> >
> > 1) The IN clause is rewritten to a join with SUMMA_RECORDS as the outer
> > table, and we have no information to limit the scan of the outer table,
> > hence a full table scan is performed. It would probably have been better
> > if SUMMA_RECORDS were the inner table. Then the C index could be used to
> > enforce the restriction (childId='...') on the outer table,
> > SUMMA_RELATIONS, and index I could be used to perform lookups in the
> > inner table.
> >
> > 2) The index scan on SUMMA_RELATIONS uses the index PC. Since that index
> > is on the columns (parentId, childId), it is primarily sorted on
> > parentId, so the scan needs to go through the entire index, for each row
> > in the outer table, in order to match childId with the criterion in the
> > WHERE clause of the nested select. It would probably be better to use
> > the index on childId (index C) instead of PC (or reverse the order of
> > the columns in the PC index).
> >
> > Derby allows you to override some of the optimizer's decisions, but it's
> > not as easy for UPDATE statements as it is for SELECT statements, so I
> > don't know how to tell it not to pick the table scan. Using the C index
> > instead of the PC index should be easy enough, though:
> >
> > UPDATE summa_records SET base='my_base' WHERE id IN
> > (SELECT parentId FROM summa_relations --DERBY-PROPERTIES index=C
> > WHERE childId='horizon_2332668')
> >
> > --
> > Knut Anders
>
> I think that you're missing something.
>
> First without knowing the whole application, why is there an index PC
> instead of an Index P and then an index C? The relationship match table has
> just two columns. So why do you need a compound index? It doesn't make
> sense.
The idea was to have a unique index on the 'relations' table, but maybe
you are right...
> Will a parent have over 10,000 children? Then maybe it might make sense.
> (Well not really. If that was the case, you'd probably want to use a temp
> table. Assuming that Derby support the dynamic creation of temp tables like
> Informix, but not like Oracle or DB2... )
A typical case is that parents might have 0-10 children (and reverse -
children might have 0-10 parents).
> I suggested that you redesign your tables so that instead of working with
> varchars and indexing varchars all over the place, you instead create a
> table so you can do a lookup of the varchar, matching to an integer ID.
>
> Indexing varchars in a main table is a *bad* idea. You end up with a lot of
> fat indexes. Fat indexs don't perform as well as skinny indexes, especially
> when you're talking about tables with millions plus rows.
It will not be trivial for us to "just" use integer ids. The problem is
that either end of a relation will not necessarily exist in the base.
This means that if we use proxy integer ids we'd have to insert a
dummy-id in the relations table that me later must pair up to the real
id if a record with linked id shows up.
To be concrete; I am working at a library and the "records" are books
linking each other. A case could be that we are instructed to put the
following metadata in the base:
id: book_1
children: book_2, book_3
parents:
7 days later we receive metadata for book_2:
id: book_2
children:
parents:
Note that book_2 does not mention its relation to book_1. This is
(sadly) legal in our world.
I can see that your strategy can work out if we store
integer_id->varchar_id in a separate table. Ids for non-existing records
can just be added here as well. I am just concerned that this will bring
even more JOIN overhead than we already have...
> Also do not use query optimization statements except as a last resort.
>
> Again I *highly* recommend creating a table where you assign a unique id to
> a given 'parentId'/'id'/'childId' and then use that id in these tables
> instead of the varchar. 1.5 million rows of an index on a varchar column
> means a lot of wasted space and overhead. (Just to re-iterate the point made
> above.)
>
> Look, no disrespect... But a lot of times, improving your table design will
> improve your performance and at the same time keeping your solution database
> agnostic.
Your input is much appreciated and provides good food for thought :-)
The problem is just that we have a PostgresQL doing this exact query (on
the same data amounts) in < 1ms, but we would really, _really_ like to
use Derby instead.
Cheers,
Mikkel
Bad table design leads to bad performance...RE: Bad performance with UPDATE on a nested SELECT
Posted by Michael Segel <ms...@segel.com>.
> -----Original Message-----
> From: Knut.Hatlen@Sun.COM [mailto:Knut.Hatlen@Sun.COM]
> Sent: Tuesday, January 13, 2009 4:59 AM
> To: Derby Discussion
> Subject: Re: Bad performance with UPDATE on a nested SELECT
[SNIP]
> Yes, it looks like the same query plan. I see the following problems
> with this query plan:
>
> 1) The IN clause is rewritten to a join with SUMMA_RECORDS as the outer
> table, and we have no information to limit the scan of the outer table,
> hence a full table scan is performed. It would probably have been better
> if SUMMA_RECORDS were the inner table. Then the C index could be used to
> enforce the restriction (childId='...') on the outer table,
> SUMMA_RELATIONS, and index I could be used to perform lookups in the
> inner table.
>
> 2) The index scan on SUMMA_RELATIONS uses the index PC. Since that index
> is on the columns (parentId, childId), it is primarily sorted on
> parentId, so the scan needs to go through the entire index, for each row
> in the outer table, in order to match childId with the criterion in the
> WHERE clause of the nested select. It would probably be better to use
> the index on childId (index C) instead of PC (or reverse the order of
> the columns in the PC index).
>
> Derby allows you to override some of the optimizer's decisions, but it's
> not as easy for UPDATE statements as it is for SELECT statements, so I
> don't know how to tell it not to pick the table scan. Using the C index
> instead of the PC index should be easy enough, though:
>
> UPDATE summa_records SET base='my_base' WHERE id IN
> (SELECT parentId FROM summa_relations --DERBY-PROPERTIES index=C
> WHERE childId='horizon_2332668')
>
> --
> Knut Anders
I think that you're missing something.
First without knowing the whole application, why is there an index PC
instead of an Index P and then an index C? The relationship match table has
just two columns. So why do you need a compound index? It doesn't make
sense.
Will a parent have over 10,000 children? Then maybe it might make sense.
(Well not really. If that was the case, you'd probably want to use a temp
table. Assuming that Derby support the dynamic creation of temp tables like
Informix, but not like Oracle or DB2... )
I suggested that you redesign your tables so that instead of working with
varchars and indexing varchars all over the place, you instead create a
table so you can do a lookup of the varchar, matching to an integer ID.
Indexing varchars in a main table is a *bad* idea. You end up with a lot of
fat indexes. Fat indexs don't perform as well as skinny indexes, especially
when you're talking about tables with millions plus rows.
Also do not use query optimization statements except as a last resort.
Again I *highly* recommend creating a table where you assign a unique id to
a given 'parentId'/'id'/'childId' and then use that id in these tables
instead of the varchar. 1.5 million rows of an index on a varchar column
means a lot of wasted space and overhead. (Just to re-iterate the point made
above.)
Look, no disrespect... But a lot of times, improving your table design will
improve your performance and at the same time keeping your solution database
agnostic.
HTH
-Mike
But hey! What do I know?
I'm not the guy who spent a billion dollars on MySQL when they could have
bought Informix for the same price almost a decade ago. ;-)
Re: Bad performance with UPDATE on a nested SELECT
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> writes:
> On Mon, 2009-01-12 at 13:49 +0100, Knut Anders Hatlen wrote:
>> Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> writes:
>>
>> > Hi list,
>> >
>> > I am seeing some bad performance on an UPDATE on a nested SELECT. The
>> > query in case takes about 30s, but I think it should be a lot faster
>> > because the same query on a PostgresQL runs < 1 ms... Anyway, here's the
>> > setup:
>> >
>> > I have two tables 'records' and 'relations'.
>> >
>> > The 'records' table stores a bunch of records along with some metadata.
>> > It has a unique index 'i' on the 'id' column and a normal index 'm' on
>> > the 'mtime' column. This table holds about 1.5M rows.
>> >
>> > The 'relations' table stores parent/child relations between records and
>> > has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
>> > (parentId,childId) and a normal index 'c' on childId. This table holds
>> > about 35k rows.
>>
>> Hi Mikkel,
>>
>> Derby sometimes has problems with the cardinality statistics getting
>> stale in non-unique indexes, which may lead to bad decisions being made
>> by the optimizer. Do you still see the problem if you compress the
>> relations table (alternatively, you could drop the index on childId and
>> recreate it)? If this speeds up the execution, you're probably
>> experiencing these issues:
>>
>> https://issues.apache.org/jira/browse/DERBY-269
>> https://issues.apache.org/jira/browse/DERBY-3788
>>
>
> Hi Knut,
>
> I just tried compressing both the 'relations' and the 'records' table.
> This makes the query run in about 20s. So a small win, but nothing
> significant.
Right, that suggests that you're seeing a different problem. Just to be
sure that the old query plan isn't still lying around in the statement
cache, it might be worth checking if clearing the statement cache
changes anything:
CALL SYSCS_UTIL.SYSCS_EMPTY_STATEMENT_CACHE()
> I have attached the query plan that I got when running with compressed
> indexes. To me it looks just like the first one i attached, but I don't
> speak fluent "query plan".
Yes, it looks like the same query plan. I see the following problems
with this query plan:
1) The IN clause is rewritten to a join with SUMMA_RECORDS as the outer
table, and we have no information to limit the scan of the outer table,
hence a full table scan is performed. It would probably have been better
if SUMMA_RECORDS were the inner table. Then the C index could be used to
enforce the restriction (childId='...') on the outer table,
SUMMA_RELATIONS, and index I could be used to perform lookups in the
inner table.
2) The index scan on SUMMA_RELATIONS uses the index PC. Since that index
is on the columns (parentId, childId), it is primarily sorted on
parentId, so the scan needs to go through the entire index, for each row
in the outer table, in order to match childId with the criterion in the
WHERE clause of the nested select. It would probably be better to use
the index on childId (index C) instead of PC (or reverse the order of
the columns in the PC index).
Derby allows you to override some of the optimizer's decisions, but it's
not as easy for UPDATE statements as it is for SELECT statements, so I
don't know how to tell it not to pick the table scan. Using the C index
instead of the PC index should be easy enough, though:
UPDATE summa_records SET base='my_base' WHERE id IN
(SELECT parentId FROM summa_relations --DERBY-PROPERTIES index=C
WHERE childId='horizon_2332668')
--
Knut Anders
Re: Bad performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
On Mon, 2009-01-12 at 13:49 +0100, Knut Anders Hatlen wrote:
> Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> writes:
>
> > Hi list,
> >
> > I am seeing some bad performance on an UPDATE on a nested SELECT. The
> > query in case takes about 30s, but I think it should be a lot faster
> > because the same query on a PostgresQL runs < 1 ms... Anyway, here's the
> > setup:
> >
> > I have two tables 'records' and 'relations'.
> >
> > The 'records' table stores a bunch of records along with some metadata.
> > It has a unique index 'i' on the 'id' column and a normal index 'm' on
> > the 'mtime' column. This table holds about 1.5M rows.
> >
> > The 'relations' table stores parent/child relations between records and
> > has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
> > (parentId,childId) and a normal index 'c' on childId. This table holds
> > about 35k rows.
>
> Hi Mikkel,
>
> Derby sometimes has problems with the cardinality statistics getting
> stale in non-unique indexes, which may lead to bad decisions being made
> by the optimizer. Do you still see the problem if you compress the
> relations table (alternatively, you could drop the index on childId and
> recreate it)? If this speeds up the execution, you're probably
> experiencing these issues:
>
> https://issues.apache.org/jira/browse/DERBY-269
> https://issues.apache.org/jira/browse/DERBY-3788
>
Hi Knut,
I just tried compressing both the 'relations' and the 'records' table.
This makes the query run in about 20s. So a small win, but nothing
significant.
I have attached the query plan that I got when running with compressed
indexes. To me it looks just like the first one i attached, but I don't
speak fluent "query plan".
Cheers,
Mikkel
Re: Bad performance with UPDATE on a nested SELECT
Posted by Knut Anders Hatlen <Kn...@Sun.COM>.
Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk> writes:
> Hi list,
>
> I am seeing some bad performance on an UPDATE on a nested SELECT. The
> query in case takes about 30s, but I think it should be a lot faster
> because the same query on a PostgresQL runs < 1 ms... Anyway, here's the
> setup:
>
> I have two tables 'records' and 'relations'.
>
> The 'records' table stores a bunch of records along with some metadata.
> It has a unique index 'i' on the 'id' column and a normal index 'm' on
> the 'mtime' column. This table holds about 1.5M rows.
>
> The 'relations' table stores parent/child relations between records and
> has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
> (parentId,childId) and a normal index 'c' on childId. This table holds
> about 35k rows.
Hi Mikkel,
Derby sometimes has problems with the cardinality statistics getting
stale in non-unique indexes, which may lead to bad decisions being made
by the optimizer. Do you still see the problem if you compress the
relations table (alternatively, you could drop the index on childId and
recreate it)? If this speeds up the execution, you're probably
experiencing these issues:
https://issues.apache.org/jira/browse/DERBY-269
https://issues.apache.org/jira/browse/DERBY-3788
--
Knut Anders
RE: Bad performance with UPDATE on a nested SELECT
Posted by de...@segel.com.
Sorry to cut the message down...
In a different post, when you've updated the statistics (rebuilt the index),
you saw your time go from 30 seconds down to 20 seconds.
When I asked you to cut the amount of data from 1.5m records to a smaller
number, the time reduction seems to be linear with respect to the number of
records.
This is a good indication that your query (below) is performing a sequential
scan on the outer table (1.5 million records).
The fact that there is a performance problem because you have variables in
the inner select instead of hard coded values, is an indication of an issue
with Derby.
There is another thing I would like you to try.
You're using id, parent_id, child_id as VARCHARS. This could part of the
problem too.
What I suggest that you do is create a table, lets call it foo which will
represent an integer id and an associated id_name (varchar).
I'm going to assume that your parent_id and child_id are both the same data
types where one record's child_id could be another record's parent_id and of
course you would have to change the data type of id in the records table.
And you would have an identity index on id and maybe a uniqueness id on
id_name. (I'm not sure if you need this or not.)
Then your relations table would be the same, only parentId and childId would
be integers. So you'd have a map of 3 integer values and the indexing could
be the same.
Then rerun your query and see what happens to the performance.
My gut feel is that you will see much better performance, and that by doing
this exercise you might be able to pinpoint the area of the bug in derby.
I hope this makes sense.
-Mike
> > > The 'records' table stores a bunch of records along with some
> metadata.
> > > It has a unique index 'i' on the 'id' column and a normal index 'm' on
> > > the 'mtime' column. This table holds about 1.5M rows.
> > >
> > > The 'relations' table stores parent/child relations between records
> and
> > > has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
> > > (parentId,childId) and a normal index 'c' on childId. This table holds
> > > about 35k rows.
> > >
> > > The problematic query looks like:
> > >
> > > UPDATE records
> > > SET base='my_base'
> > > WHERE id IN (
> > > SELECT parentId
> > > FROM relations
> > > WHERE childId='id_1');
> > >
> > > The right SELECT returns two rows (and in general 0-3 or something
> like
> > > that). If I instead of the SELECT hardcode two ids, making the right
> > > part look like "IN ('id_2', 'id_3')" the query runs in < 1ms.
> I just tried on a base half the size (~700k rows) and it runs in about
> 5-10s. The really creepy about this case is that my test run was a case
> where the nested SELECT was empty!..
RE: Bad performance with UPDATE on a nested SELECT
Posted by Mikkel Kamstrup Erlandsen <mk...@statsbiblioteket.dk>.
Hi Mike,
> What data type are you using for 'child_id' and 'parent_id'?
> It seems that the way you've written the query that they are character
> strings and not integers.
> (Not that it would cause the delay.)
They are VARCHAR(255).
> If you run the inner select by itself as written, how long does it take?
About 1ms.
> There was a bug several releases ago concerning the IN clause performance,
> this could be related.
This problem is on 10.4.2
> It would not be a good thing if you are doing a sequential scan on the
> entire 1.5 mil rows, which is what you could be seeing in the 30 sec run.
>
> Another test that you can use to confirm the problem is to create a subset
> of the records table with 10,000 rows. If the same query runs with a low
> (sub second) response, then you've verified that you're doing a table scan.
I just tried on a base half the size (~700k rows) and it runs in about
5-10s. The really creepy about this case is that my test run was a case
where the nested SELECT was empty!..
> Assuming that this is a bug, and assuming that your id's are character
> strings and not integers, try creating them as integers and see if that
> helps the IN clause performance. (It's a gut feel, a hunch).
This will be a substantial amount of work and will not be acceptable as
an end solution, so I will prefer not going down that path...
Cheers,
Mikkel
> > -----Original Message-----
> > From: Mikkel Kamstrup Erlandsen [mailto:mke@statsbiblioteket.dk]
> > Sent: Monday, January 12, 2009 6:00 AM
> > To: derby-user@db.apache.org
> > Subject: Bad performance with UPDATE on a nested SELECT
> >
> > Hi list,
> >
> > I am seeing some bad performance on an UPDATE on a nested SELECT. The
> > query in case takes about 30s, but I think it should be a lot faster
> > because the same query on a PostgresQL runs < 1 ms... Anyway, here's the
> > setup:
> >
> > I have two tables 'records' and 'relations'.
> >
> > The 'records' table stores a bunch of records along with some metadata.
> > It has a unique index 'i' on the 'id' column and a normal index 'm' on
> > the 'mtime' column. This table holds about 1.5M rows.
> >
> > The 'relations' table stores parent/child relations between records and
> > has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
> > (parentId,childId) and a normal index 'c' on childId. This table holds
> > about 35k rows.
> >
> > The problematic query looks like:
> >
> > UPDATE records
> > SET base='my_base'
> > WHERE id IN (
> > SELECT parentId
> > FROM relations
> > WHERE childId='id_1');
> >
> > The right SELECT returns two rows (and in general 0-3 or something like
> > that). If I instead of the SELECT hardcode two ids, making the right
> > part look like "IN ('id_2', 'id_3')" the query runs in < 1ms.
> >
> > It would appear that Derby iterates over the entire 'records' table or
> > something like that. This also appears to be the case as far as I can
> > read from the attached query plan...
> >
> > Any pointers or ideas on how to tackle this are most appreciated.
> >
> > Cheers,
> > Mikkel
>
>
RE: Bad performance with UPDATE on a nested SELECT
Posted by de...@segel.com.
Just a quick question...
What data type are you using for 'child_id' and 'parent_id'?
It seems that the way you've written the query that they are character
strings and not integers.
(Not that it would cause the delay.)
If you run the inner select by itself as written, how long does it take?
There was a bug several releases ago concerning the IN clause performance,
this could be related.
It would not be a good thing if you are doing a sequential scan on the
entire 1.5 mil rows, which is what you could be seeing in the 30 sec run.
Another test that you can use to confirm the problem is to create a subset
of the records table with 10,000 rows. If the same query runs with a low
(sub second) response, then you've verified that you're doing a table scan.
Assuming that this is a bug, and assuming that your id's are character
strings and not integers, try creating them as integers and see if that
helps the IN clause performance. (It's a gut feel, a hunch).
-Mike
> -----Original Message-----
> From: Mikkel Kamstrup Erlandsen [mailto:mke@statsbiblioteket.dk]
> Sent: Monday, January 12, 2009 6:00 AM
> To: derby-user@db.apache.org
> Subject: Bad performance with UPDATE on a nested SELECT
>
> Hi list,
>
> I am seeing some bad performance on an UPDATE on a nested SELECT. The
> query in case takes about 30s, but I think it should be a lot faster
> because the same query on a PostgresQL runs < 1 ms... Anyway, here's the
> setup:
>
> I have two tables 'records' and 'relations'.
>
> The 'records' table stores a bunch of records along with some metadata.
> It has a unique index 'i' on the 'id' column and a normal index 'm' on
> the 'mtime' column. This table holds about 1.5M rows.
>
> The 'relations' table stores parent/child relations between records and
> has two rows 'parentId' and 'childId'. There is a unique index 'pc' on
> (parentId,childId) and a normal index 'c' on childId. This table holds
> about 35k rows.
>
> The problematic query looks like:
>
> UPDATE records
> SET base='my_base'
> WHERE id IN (
> SELECT parentId
> FROM relations
> WHERE childId='id_1');
>
> The right SELECT returns two rows (and in general 0-3 or something like
> that). If I instead of the SELECT hardcode two ids, making the right
> part look like "IN ('id_2', 'id_3')" the query runs in < 1ms.
>
> It would appear that Derby iterates over the entire 'records' table or
> something like that. This also appears to be the case as far as I can
> read from the attached query plan...
>
> Any pointers or ideas on how to tackle this are most appreciated.
>
> Cheers,
> Mikkel