pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedQuota query with decent performance?
13+ messages / 5 participants
[nested] [flat]
* Quota query with decent performance?
@ 2003-11-11 22:58 Troels Arvin <troels@arvin.dk>
0 siblings, 2 replies; 13+ messages in thread
From: Troels Arvin @ 2003-11-11 22:58 UTC (permalink / raw)
To: pgsql-sql
Hello,
I'm researching how "quota queries" (a term used by Fabian Pascal) may be
performed in various DBMSes with acceptable performance:
http://troels.arvin.dk/db/rdbms/#select-limit-simple-note
An example of a quota query could be to get the top-3 youngest people from
a collection of people. The complicated part is that such a query might
return more than 3 rows in some tie situations.
In MSSQL and DB2 there are very efficient facilities for such queries, but
I can't find any well-performing declarative methods for PostgreSQL. I
have tried a couple of different strategies, and I currently get the best
results from a correlated subquery like
SELECT * FROM person AS px
WHERE (
SELECT COUNT(*)
FROM person AS py
WHERE py.age < px.age
) < 3;
When my base table has 4000 rows, my query takes 27 seconds in PostgreSQL
7.2.3 (PIII 1000MHz) which is clearly unacceptable, especially comparing
to the same query in DB2 which only takes 1.4 seconds (on the same server)
- or to this non-standard-SQL DB2-query which only takes 0.02 seconds to
calculate the same result:
SELECT *
FROM (
SELECT firstname,age,RANK() OVER (ORDER BY age ASC) AS rank
FROM person
) AS foo
WHERE rank<=3;
Test-files with table definitions and randomly generated rows:
http://troels.arvin.dk/db/tests/quota.1/
Any suggestions on how to perform fast "quota queries" in PostgreSQL?
--
Greetings from Troels Arvin, Copenhagen, Denmark
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-11 23:41 Josh Berkus <josh@agliodbs.com>
parent: Troels Arvin <troels@arvin.dk>
1 sibling, 1 reply; 13+ messages in thread
From: Josh Berkus @ 2003-11-11 23:41 UTC (permalink / raw)
To: Troels Arvin <troels@arvin.dk>; pgsql-sql
Troels,
Thank you for contacting us before publishing your results. Please ignore
any list-trolls who criticize your methodology; there are a few cranks on
every list. The important thing is your contacted us.
> In MSSQL and DB2 there are very efficient facilities for such queries, but
> I can't find any well-performing declarative methods for PostgreSQL. I
> have tried a couple of different strategies, and I currently get the best
> results from a correlated subquery like
>
> SELECT * FROM person AS px
> WHERE (
> SELECT COUNT(*)
> FROM person AS py
> WHERE py.age < px.age
> ) < 3;
>
> When my base table has 4000 rows, my query takes 27 seconds in PostgreSQL
> 7.2.3 (PIII 1000MHz) which is clearly unacceptable,
Well, first off 7.2.3 is a two-year old version. There have been performance
improvements specificially on these sorts of issues since then. Please use
at least 7.3.4, and we would prefer that you use 7.4RC2, which is available
now. 7.4, in particular, introduces significant improvements in "group by"
queries. If for some reason you have to compare against this old version,
please be fair to us and note somewhere that you were using an old version of
PostgreSQL.
Second, the query you post is one "SQL Standard" way, which is good for
portability but not for speed. Frankly, I'm not convinced that it's even the
best SQL standard way. On the other databases, you seem happy to use
non-SQL-standard syntax, so let me give you one such solution in PostgreSQL:
SELECT * FROM person
WHERE person.age >= (SELECT p2.age
from person p2
order by p2.age DESC LIMIT 1 OFFSET 2)
also try:
SELECT *
FROM person,
(SELECT p2.age
from person p2
order by p2.age DESC LIMIT 1 OFFSET 2) as prank
WHERE person.age >= prank.age
This should give you all of the rows whose ages are in the top 3 ranks much
faster.
--
-Josh Berkus
Aglio Database Solutions
San Francisco
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-11 23:49 Chester Kustarz <chester@arbor.net>
parent: Troels Arvin <troels@arvin.dk>
1 sibling, 3 replies; 13+ messages in thread
From: Chester Kustarz @ 2003-11-11 23:49 UTC (permalink / raw)
To: Troels Arvin <troels@arvin.dk>; +Cc: pgsql-sql
maybe:
select *
from person
where age <=
(select age from person order by age limit 1 offset 2);
7.20 msec
assuming it does what you want.
On Tue, 11 Nov 2003, Troels Arvin wrote:
> An example of a quota query could be to get the top-3 youngest people from
> a collection of people. The complicated part is that such a query might
> return more than 3 rows in some tie situations.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-12 05:17 Tom Lane <tgl@sss.pgh.pa.us>
parent: Josh Berkus <josh@agliodbs.com>
0 siblings, 0 replies; 13+ messages in thread
From: Tom Lane @ 2003-11-12 05:17 UTC (permalink / raw)
To: josh@agliodbs.com; +Cc: Troels Arvin <troels@arvin.dk>; pgsql-sql
Josh Berkus <josh@agliodbs.com> writes:
> Second, the query you post is one "SQL Standard" way, which is good for
> portability but not for speed. Frankly, I'm not convinced that it's even the
> best SQL standard way. On the other databases, you seem happy to use
> non-SQL-standard syntax, so let me give you one such solution in PostgreSQL:
> [snip]
I don't know of any very good solution in bog-standard SQL either.
Aside from the LIMIT-based solution that Josh offered, I recall that
Oleg Bartunov and Teodor Sigaev had some ideas about top-N-aggregate
solutions. We didn't accept those into the main distribution (yet)
but if you dig in the PG list archives I think there is working code
available. Try searching for "partial sorting".
regards, tom lane
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-12 09:32 Troels Arvin <troels@arvin.dk>
parent: Chester Kustarz <chester@arbor.net>
2 siblings, 0 replies; 13+ messages in thread
From: Troels Arvin @ 2003-11-12 09:32 UTC (permalink / raw)
To: pgsql-sql
On Tue, 11 Nov 2003 18:49:31 -0500, Chester Kustarz wrote:
[... cut efficient top-3 youngest query wanted ...]
> select *
> from person
> where age <=
> (select age from person order by age limit 1 offset 2);
Thanks - it works; why didn't I think of that?
--
Greetings from Troels Arvin, Copenhagen, Denmark
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-12 10:57 Troels Arvin <troels@arvin.dk>
parent: Chester Kustarz <chester@arbor.net>
2 siblings, 0 replies; 13+ messages in thread
From: Troels Arvin @ 2003-11-12 10:57 UTC (permalink / raw)
To: pgsql-sql
On Tue, 11 Nov 2003 18:49:31 -0500, Chester Kustarz wrote:
> select *
> from person
> where age <=
> (select age from person order by age limit 1 offset 2);
Integrated into http://troels.arvin.dk/db/rdbms/#select-top-n
--
Greetings from Troels Arvin, Copenhagen, Denmark
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-17 22:55 Troels Arvin <troels@arvin.dk>
parent: Chester Kustarz <chester@arbor.net>
2 siblings, 1 reply; 13+ messages in thread
From: Troels Arvin @ 2003-11-17 22:55 UTC (permalink / raw)
To: pgsql-sql
On Tue, 11 Nov 2003 18:49:31 -0500, Chester Kustarz wrote:
[... discussion of top-n query (where n=3) ...]
> select *
> from person
> where age <=
> (select age from person order by age limit 1 offset 2);
It fails when the cardinality of person is less than 3 (returns empty
set). My solution is this, which is not as beautiful any more:
SELECT *
FROM person
WHERE age <= COALESCE (
(
SELECT age FROM person
ORDER BY age ASC
LIMIT 1 OFFSET 2 -- 2=n-1
),(
SELECT age FROM person
ORDER BY age DESC -- note: opposite of ASC
LIMIT 1
)
);
--
Greetings from Troels Arvin, Copenhagen, Denmark
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-18 12:56 Bruno Wolff III <bruno@wolff.to>
parent: Troels Arvin <troels@arvin.dk>
0 siblings, 2 replies; 13+ messages in thread
From: Bruno Wolff III @ 2003-11-18 12:56 UTC (permalink / raw)
To: Troels Arvin <troels@arvin.dk>; +Cc: pgsql-sql
On Mon, Nov 17, 2003 at 23:55:53 +0100,
Troels Arvin <troels@arvin.dk> wrote:
> On Tue, 11 Nov 2003 18:49:31 -0500, Chester Kustarz wrote:
>
> [... discussion of top-n query (where n=3) ...]
>
> > select *
> > from person
> > where age <=
> > (select age from person order by age limit 1 offset 2);
>
> It fails when the cardinality of person is less than 3 (returns empty
> set). My solution is this, which is not as beautiful any more:
Used that way the subselect value will be null if there are no matching
rows. This should allow you to do something like:
select *
from person
where not isfalse (age <=
(select age from person order by age limit 1 offset 2));
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-18 13:24 Troels Arvin <troels@arvin.dk>
parent: Bruno Wolff III <bruno@wolff.to>
1 sibling, 0 replies; 13+ messages in thread
From: Troels Arvin @ 2003-11-18 13:24 UTC (permalink / raw)
To: pgsql-sql
On Tue, 18 Nov 2003 06:56:42 -0600, Bruno Wolff III wrote:
> select *
> from person
> where not isfalse (age <=
> (select age from person order by age limit 1 offset 2));
Thanks; much nicer than my COALESCE-variant.
http://troels.arvin.dk/db/rdbms/#select-top-n-postgresql updated.
--
Greetings from Troels Arvin, Copenhagen, Denmark
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-18 14:21 Troels Arvin <troels@arvin.dk>
parent: Bruno Wolff III <bruno@wolff.to>
1 sibling, 2 replies; 13+ messages in thread
From: Troels Arvin @ 2003-11-18 14:21 UTC (permalink / raw)
To: pgsql-sql
On Tue, 18 Nov 2003 06:56:42 -0600, Bruno Wolff III wrote:
[...]
> where not isfalse (age <=
[...]
Strange. I can't find the ISFALSE in neither PostgreSQL or standard SQL
documentation. How can that be?
--
Greetings from Troels Arvin, Copenhagen, Denmark
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-18 14:36 Bruno Wolff III <bruno@wolff.to>
parent: Troels Arvin <troels@arvin.dk>
1 sibling, 1 reply; 13+ messages in thread
From: Bruno Wolff III @ 2003-11-18 14:36 UTC (permalink / raw)
To: Troels Arvin <troels@arvin.dk>; +Cc: pgsql-sql
On Tue, Nov 18, 2003 at 15:21:43 +0100,
Troels Arvin <troels@arvin.dk> wrote:
> On Tue, 18 Nov 2003 06:56:42 -0600, Bruno Wolff III wrote:
>
> [...]
> > where not isfalse (age <=
> [...]
>
> Strange. I can't find the ISFALSE in neither PostgreSQL or standard SQL
> documentation. How can that be?
I didn't remember the exact syntax and found the isfalse function by
guessing. The standard syntax is expression is false instead of
isfalse(expression), though the function does work (in 7.4 at least).
area=> select isfalse(null);
isfalse
---------
f
(1 row)
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-18 14:45 Bruno Wolff III <bruno@wolff.to>
parent: Troels Arvin <troels@arvin.dk>
1 sibling, 0 replies; 13+ messages in thread
From: Bruno Wolff III @ 2003-11-18 14:45 UTC (permalink / raw)
To: Troels Arvin <troels@arvin.dk>; +Cc: pgsql-sql
On Tue, Nov 18, 2003 at 15:21:43 +0100,
Troels Arvin <troels@arvin.dk> wrote:
> On Tue, 18 Nov 2003 06:56:42 -0600, Bruno Wolff III wrote:
>
> [...]
> > where not isfalse (age <=
> [...]
>
> Strange. I can't find the ISFALSE in neither PostgreSQL or standard SQL
> documentation. How can that be?
I forgot to mention that the is false operator is described under
the section on comparison operators.
^ permalink raw reply [nested|flat] 13+ messages in thread
* Re: Quota query with decent performance?
@ 2003-11-18 15:06 Troels Arvin <troels@arvin.dk>
parent: Bruno Wolff III <bruno@wolff.to>
0 siblings, 0 replies; 13+ messages in thread
From: Troels Arvin @ 2003-11-18 15:06 UTC (permalink / raw)
To: pgsql-sql
On Tue, 18 Nov 2003 08:36:27 -0600, Bruno Wolff III wrote:
> The standard syntax is expression is false instead of
> isfalse(expression)
OK, so I guess that a 'better' (closer to standard) version of your query
would be:
SELECT *
FROM pview
WHERE (
age <= (
SELECT age FROM pview
ORDER BY age ASC
LIMIT 1 OFFSET 20 -- 2=n-1
)
) IS NOT FALSE;
--
Greetings from Troels Arvin, Copenhagen, Denmark
^ permalink raw reply [nested|flat] 13+ messages in thread
end of thread, other threads:[~2003-11-18 15:06 UTC | newest]
Thread overview: 13+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2003-11-11 22:58 Quota query with decent performance? Troels Arvin <troels@arvin.dk>
2003-11-11 23:41 ` Josh Berkus <josh@agliodbs.com>
2003-11-12 05:17 ` Tom Lane <tgl@sss.pgh.pa.us>
2003-11-11 23:49 ` Chester Kustarz <chester@arbor.net>
2003-11-12 09:32 ` Troels Arvin <troels@arvin.dk>
2003-11-12 10:57 ` Troels Arvin <troels@arvin.dk>
2003-11-17 22:55 ` Troels Arvin <troels@arvin.dk>
2003-11-18 12:56 ` Bruno Wolff III <bruno@wolff.to>
2003-11-18 13:24 ` Troels Arvin <troels@arvin.dk>
2003-11-18 14:21 ` Troels Arvin <troels@arvin.dk>
2003-11-18 14:36 ` Bruno Wolff III <bruno@wolff.to>
2003-11-18 15:06 ` Troels Arvin <troels@arvin.dk>
2003-11-18 14:45 ` Bruno Wolff III <bruno@wolff.to>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox