Performance-Problem

Hallo,

ich hab hier ein kleines Performance-Problem. Ich hab hier zwei
Tabellen, test1 und test2 die je eine Spalte id haben. Nun möchte ich
die jeweils größte id aus test2 haben, die kleiner als die id aus test1 ist.

Die folgende Query erfüllt im Prinzip ihren Zweck:

select id,(select id from test2 where test2.id limit 1) from test1

Aber sie ist viel zu langsam, obwohl auf der jeweiligen id einen Index
gibt. (Bei ca. 10000 Einträgen in den beiden Tabellen dauert die Abfrage
ca. 1000 Sekunden)

Verwendet wurde MySQL 5.0

Irgendwelche Vorschläge zur Geschwindigkeitsoptimierung?

Stefan

Re: Performance-Problem

Weinzierl Stefan wrote:

> Die folgende Query erfüllt im Prinzip ihren Zweck:
>
> select id,(select id from test2 where test2.id > desc limit 1) from test1
>
> Aber sie ist viel zu langsam, obwohl auf der jeweiligen id einen Index
> gibt. (Bei ca. 10000 Einträgen in den beiden Tabellen dauert die
> Abfrage ca. 1000 Sekunden)

Ui. Wie sind die Indizes gesetzt? (Wobei ich nicht weiß, ob die bei
Subselects wirklich eingesetzt werden.)

Da ich Subselects nicht sonderlich mag: Versuchs mal mit

select t1.id,max(t2.id) from test1 t1 join test2 t2 on t1.id>t2.id left
join test2 t0 on t0.id>t2.id where t0.id IS NULL group by t1.id

Kurze Erklärung: Durch das Dran-Outer-joinen von t0 und Wegwerfen jedes
Nicht-NULL-Ergebnisses werden nur t2s ausgegeben, bei denen kein t0
größer ist, also die größten.

HTH,


Thomas
--
Ich habe eine Menge Geld für Sauferei, leichte Mädchen und schnelle Autos
ausgegeben. Den Rest habe ich einfach verplempert. (George Best)

Re: Performance-Problem

Hallo nach LA,

Weinzierl Stefan wrote:
>
> Die folgende Query erfüllt im Prinzip ihren Zweck:
>
> select id,(select id from test2 where test2.id > limit 1) from test1
>
> Aber sie ist viel zu langsam, obwohl auf der jeweiligen id einen Index
> gibt. (Bei ca. 10000 Einträgen in den beiden Tabellen dauert die Abfrage
> ca. 1000 Sekunden)

Erste Frage: werden die Indicies auch verwendet?
Und wie sieht der Queryplan bzw. das EXPLAIN für diesen Query aus?


Bye

--
Andreas 'ads' Scherbaum
Failure is not an option. It comes bundled with your Microsoft product.
(Ferenc Mantfeld)

Re: Performance-Problem

Weinzierl Stefan wrote:
> Ich hab hier zwei
> Tabellen, test1 und test2 die je eine Spalte id haben. Nun möchte ich
> die jeweils größte id aus test2 haben, die kleiner als die id aus test1
> ist.

create table test1 ( id integer unsigned not null primary key
auto_increment );
create table test2 like test1;
insert into test1 (id) values (1), (2), (3), (4);
insert into test2 (id) values (2), (3), (5);


Finde alle maximalen id2 kleiner als id1:

select test1.id as id1,
max(test2.id) as id2
from test1 join test2 on test2.id < test1.id
group by id1;

explain select test1.id as id1, max(test2.id) as id2 from test1 join test2
on test2.id < test1.id group by id1\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: test2
type: index
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: NULL
rows: 3
Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: test1
type: index
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: NULL
rows: 4
Extra: Using where; Using index
2 rows in set (0.00 sec)

Finde alle id1, und liste das maximale id2 zu diesem id1 oder NULL, wenn
keines existiert:

select test1.id as id1,
max(test2.id) as id2
from test1 left join test2 on test2.id < test1.id
group by id1;

+-----+------+
| id1 | id2 |
+-----+------+
| 1 | NULL |
| 2 | NULL |
| 3 | 2 |
| 4 | 3 |
+-----+------+
4 rows in set (0.00 sec)


explain select test1.id as id1, max(test2.id) as id2 from test1 left join
test2 on test2.id < test1.id group by id1\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: test1
type: index
possible_keys: NULL
key: PRIMARY
key_len: 4
ref: NULL
rows: 4
Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: test2
type: index
possible_keys: PRIMARY
key: PRIMARY
key_len: 4
ref: NULL
rows: 3
Extra: Using index
2 rows in set (0.00 sec)


Kris

Re: Performance-Problem

Andreas
--
q: why do so many people take an instant dislike to mysql?
a: it saves time (oicu in #postgresql)
Explaining the concept of referential integrity to a mysql user is like
explaining condoms to a catholic (Shadda in #postgresql)

Re: Performance-Problem

Andreas
--
q: why do so many people take an instant dislike to mysql?
a: it saves time (oicu in #postgresql)
Explaining the concept of referential integrity to a mysql user is like
explaining condoms to a catholic (Shadda in #postgresql)

Re: Performance-Problem

Andreas Scherbaum wrote:
> Hallo nach LA,
>
> Weinzierl Stefan wrote:
>> Die folgende Query erfüllt im Prinzip ihren Zweck:
>>
>> select id,(select id from test2 where test2.id >> limit 1) from test1
>>
>> Aber sie ist viel zu langsam, obwohl auf der jeweiligen id einen Index
>> gibt. (Bei ca. 10000 Einträgen in den beiden Tabellen dauert die Abfrage
>> ca. 1000 Sekunden)
>
> Erste Frage: werden die Indicies auch verwendet?
> Und wie sieht der Queryplan bzw. das EXPLAIN für diesen Query aus?

Die Indicies werden anscheinend verwendet:

*************************** 1. row ***************************
id: 1
select_type: PRIMARY
table: test1
type: index
possible_keys: NULL
key: test1_id
key_len: 5
ref: NULL
rows: 10240
Extra: Using index
*************************** 2. row ***************************
id: 2
select_type: DEPENDENT SUBQUERY
table: test2
type: index
possible_keys: test2_id
key: test2_id
key_len: 5
ref: NULL
rows: 10001
Extra: Using where; Using index


Stefan

Re: Performance-Problem

Andreas Kretschmer wrote:
> begin Weinzierl Stefan wrote:
>> Aber sie ist viel zu langsam, obwohl auf der jeweiligen id einen Index
>> gibt. (Bei ca. 10000 Einträgen in den beiden Tabellen dauert die Abfrage
>> ca. 1000 Sekunden)
>
> Bist Du _sicher_, daß die Indexe greifen?
>
>> Verwendet wurde MySQL 5.0
>
> Unter PostgreSQL mit 2 Tabellen t1 und t2, je 10.000 Zeilen mit
> Zufallszahlen, ohne Index:
>
> test=# explain analyse select id,(select id from t2 where t2.id > QUERY PLAN
> ------------------------------------------------------------ ------------------------------------------------------------ -----
> Seq Scan on t1 (cost=0.00..4248713.27 rows=10670 width=8) (actual time=77.124..413760.477 rows=10000 loops=1)
> SubPlan
> -> Limit (cost=398.17..398.18 rows=1 width=8) (actual time=41.353..41.356 rows=1 loops=10000)
> -> Sort (cost=398.17..407.07 rows=3557 width=8) (actual time=40.542..40.542 rows=1 loops=10000)
> Sort Key: id
> -> Seq Scan on t2 (cost=0.00..188.38 rows=3557 width=8) (actual time=0.017..17.911 rows=5050 loops=10000)
> Filter: (id < $0)
> Total runtime: 413788.725 ms
> (8 rows)
>
> und mit Index:
>
> test=# explain analyse select id,(select id from t2 where t2.id > QUERY PLAN
> ------------------------------------------------------------ ------------------------------------------------------------ -------------------
> Seq Scan on t1 (cost=0.00..983.07 rows=10000 width=8) (actual time=0.156..219.531 rows=10000 loops=1)
> SubPlan
> -> Limit (cost=0.00..0.08 rows=1 width=8) (actual time=0.013..0.014 rows=1 loops=10000)
> -> Index Scan Backward using idx_t2 on t2 (cost=0.00..276.00 rows=3333 width=8) (actual time=0.008..0.008 rows=1 loops=10000)
> Index Cond: (id < $0)
> Total runtime: 238.433 ms
> (6 rows)

Die Performance von PostgreSQL waren mir bekannt, nur danach hatte ich
nicht gefragt...

Stefan

Re: Performance-Problem

Kristian Köhntopp wrote:
> Weinzierl Stefan wrote:
>> Ich hab hier zwei
>> Tabellen, test1 und test2 die je eine Spalte id haben. Nun möchte ich
>> die jeweils größte id aus test2 haben, die kleiner als die id aus test1
>> ist.
[...]
> explain select test1.id as id1, max(test2.id) as id2 from test1 left join
> test2 on test2.id < test1.id group by id1\G
[...]

Danke, damit liege ich aber bei jeweils 10000 Einträgen immer noch bei
knapp 3 Minuten.

Und wie Andreas schon gesagt hat, ist PostgreSQL in diesem Falle viel
schneller...

Stefan

Re: Performance-Problem

Andreas
--
q: why do so many people take an instant dislike to mysql?
a: it saves time (oicu in #postgresql)
Explaining the concept of referential integrity to a mysql user is like
explaining condoms to a catholic (Shadda in #postgresql)

Re: Performance-Problem

Thomas Rachel wrote:
> Weinzierl Stefan wrote:
>
>> Die folgende Query erfüllt im Prinzip ihren Zweck:
>>
>> select id,(select id from test2 where test2.id >> desc limit 1) from test1
>>
>> Aber sie ist viel zu langsam, obwohl auf der jeweiligen id einen Index
>> gibt. (Bei ca. 10000 Einträgen in den beiden Tabellen dauert die
>> Abfrage ca. 1000 Sekunden)
>
> Ui. Wie sind die Indizes gesetzt? (Wobei ich nicht weiß, ob die bei
> Subselects wirklich eingesetzt werden.)
>
> Da ich Subselects nicht sonderlich mag: Versuchs mal mit
>
> select t1.id,max(t2.id) from test1 t1 join test2 t2 on t1.id>t2.id left
> join test2 t0 on t0.id>t2.id where t0.id IS NULL group by t1.id
>
> Kurze Erklärung: Durch das Dran-Outer-joinen von t0 und Wegwerfen jedes
> Nicht-NULL-Ergebnisses werden nur t2s ausgegeben, bei denen kein t0
> größer ist, also die größten.

Leider bringt diese Abfrage ebenfalls keinen Geschwindigkeitsvorteil

*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: t2
type: index
possible_keys: test2_id
key: test2_id
key_len: 5
ref: NULL
rows: 10001
Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: t0
type: index
possible_keys: test2_id
key: test2_id
key_len: 5
ref: NULL
rows: 10001
Extra: Using where; Using index
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: t1
type: index
possible_keys: test1_id
key: test1_id
key_len: 5
ref: NULL
rows: 10240
Extra: Using where; Using index


Stefan

Re: Performance-Problem

Andreas
--
q: why do so many people take an instant dislike to mysql?
a: it saves time (oicu in #postgresql)
Explaining the concept of referential integrity to a mysql user is like
explaining condoms to a catholic (Shadda in #postgresql)

Re: Performance-Problem

Weinzierl Stefan wrote:
> Die Indicies werden anscheinend verwendet:
>

> type: index
> possible_keys: NULL
> key: test1_id


> type: index
> possible_keys: test2_id
> key: test2_id

Das sind index-Scans. Index-Scans sind wie Full Table Scans ("type: ALL"),
nur daß sie auf dem Index und nicht auf den Daten durchgeführt wird, weil
Index-Records oft kleiner sind als Daten-Records und so weniger Blöcke
gelesen werden müssen.

Kris

Re: Performance-Problem

Weinzierl Stefan wrote:
> Danke, damit liege ich aber bei jeweils 10000 Einträgen immer noch bei
> knapp 3 Minuten.

http://jan.kneschke.de/projects/mysql/groupwise-max/ dekliniert ein Deinem
Problem verwandtes Problem auf 10 verschiedene Arten durch.

Kris

Re: Performance-Problem

Andreas Kretschmer wrote:

>> select t1.id,max(t2.id) from test1 t1 join test2 t2 on t1.id>t2.id left
>> join test2 t0 on t0.id>t2.id where t0.id IS NULL group by t1.id
>
> Ich glaube, Du hast schon bessere Ratschläge erteilt:
>
> template1=*# select query_start, current_query from pg_stat_activity ;
> query_start | current_query
> -------------------------------+---------------------------- ------------------------------------------------------------ -----------------------------------
> 2006-10-03 09:51:43.312354+02 | select t1.id,max(t2.id) from t1 join t2 on t1.id>t2.id left join t2 t0 on t0.id>t2.id where t0.id IS NULL group by t1.id;
>
>
> Man beachte die Startzeit und die Tatsache, daß das noch immer läuft...
> Vielleicht hab ich mich auch irknwo vertippt, kann aber keinen
> prinzipiellen Unterschied zu Deiner Lösung finden. Indexe sind da,
> t1 und t2 jeweils 10.000 Rows.

Na ja, dürfte in etwa vergleichbar sein mit einem Cross-Join von
10000*5000*5000 Rows :-)

Dieter

Re: Performance-Problem

Andreas
--
q: why do so many people take an instant dislike to mysql?
a: it saves time (oicu in #postgresql)
Explaining the concept of referential integrity to a mysql user is like
explaining condoms to a catholic (Shadda in #postgresql)

Re: Performance-Problem

Andreas Kretschmer wrote:

>> Na ja, dürfte in etwa vergleichbar sein mit einem Cross-Join von
>> 10000*5000*5000 Rows :-)
>
> Vermute ich auch. Es läuft im übrigen noch immer...
> Aber Danke, daß Du meine Vermutung bestätigst.

Wird auch noch länger laufen.
Na ja, kein Wunder, wenn man keine performante Lösung mit SQL:1999
OLAP-Funktionen schreiben kann, weil man nur "Drittklassewelt-Software"
wie mysql oder postgresql zur Verfügung hat :-)

SELECT
id,
id2
FROM
(
SELECT
x,
id,
MAX(CASE WHEN x = 2 THEN id END) OVER (
ORDER BY id, x ROWS UNBOUNDED PRECEDING) AS id2
FROM
(
SELECT id, 1 AS x FROM test1
UNION ALL
SELECT id, 2 FROM test2
) dt
) dt

Läuft 0.14 Sekunden auf jeweils 10000 Rows auf meinem Notebook mit
Teradata. Oracle, DB2 und sogar MS SQL Server 2005 sind da vergleichbar
schnell.

Warum hat eigentlich keiner die klassische Lösung mit MAX statt
proprietärem LIMIT getestet?

select
id,
(select max(id) from test2 where test2.id from test1

Sollte ein guter Optimizer über'n Lookup auf den Index machen.

Und wenn's immer noch zu langsam ist, wäre das einer der wenigen Fälle
für einen Cursor...

Dieter

Re: Performance-Problem

Dieter Noeth wrote:
[...]
> Warum hat eigentlich keiner die klassische Lösung mit MAX statt
> proprietärem LIMIT getestet?
>
> select
> id,
> (select max(id) from test2 where test2.id > from test1
Ist unter MySQL auch zu langsam, das war mein allererster Lösungsansatz.
Unter PostgreSQL läufts mit MAX() und mit LIMIT sehr schnell, nur brauch
ich es halt unter MySQL. (Zeiten kann ich keine sagen, da psql keine
Zeit anzeigt...)

Stefan

Re: Performance-Problem

Weinzierl Stefan wrote:
>
> (Zeiten kann ich keine sagen, da psql keine Zeit anzeigt...)

\timing

auf der psql Konsole.


Bye

--
Andreas 'ads' Scherbaum
Failure is not an option. It comes bundled with your Microsoft product.
(Ferenc Mantfeld)

Re: Performance-Problem

Andreas Kretschmer wrote:

>> Da ich Subselects nicht sonderlich mag: Versuchs mal mit
>
> Warum? Weil MySQL es bis vor kurzem nicht konnte?

Vermutlich. Und um maximale Kompatibilität zu erhalten. Oder... keine
Ahnung warum.


>> select t1.id,max(t2.id) from test1 t1 join test2 t2 on t1.id>t2.id
>> left join test2 t0 on t0.id>t2.id where t0.id IS NULL group by t1.id
>
> Ich glaube, Du hast schon bessere Ratschläge erteilt:

Kann durchaus sein; war eine eher schnellschuß-ähnliche Aktion. Habe es
selbst nicht getestet...


Thomas
--
Napoleon trug immer Rot, damit seine Soldaten nicht sehen konnten, wenn
er verwundet wurde. Die Nazis trugen braune Hosen... (unbekannte Quelle)

Re: Performance-Problem

Thomas Rachel wrote:

>>> select t1.id,max(t2.id) from test1 t1 join test2 t2 on t1.id>t2.id
>>> left join test2 t0 on t0.id>t2.id where t0.id IS NULL group by t1.id
>>
>> Ich glaube, Du hast schon bessere Ratschläge erteilt:
>
> Kann durchaus sein; war eine eher schnellschuß-ähnliche Aktion. Habe es
> selbst nicht getestet...

Und ein Test mit entsprechend vielen Zeilen gab noch schlechtere
Performance: n^3 statt n^2. Trotz Index. Aber auf lineare Performance
komme ich leider mit keiner Lösung - liegt wohl an dem <-Operator, der
bei gegebenem test1.id (also für jede dortige Zeile) eine
"Volluntersuchung" von test2 machen will - sei es durch Ausführung des
Subquery oder durch Ausführung der Join-Bedingung...


Thomas
--
Fernsehen ist die aktive Form des Faulenzens. (Henning Venske)

Re: Performance-Problem

Andreas
--
q: why do so many people take an instant dislike to mysql?
a: it saves time (oicu in #postgresql)
Explaining the concept of referential integrity to a mysql user is like
explaining condoms to a catholic (Shadda in #postgresql)