pg.ddx.io pgsql-sql@postgresql.org mailing list archive
help / color / mirror / Atom feedoptimizing 2-table join w/millions of rows
6+ messages / 3 participants
[nested] [flat]
* optimizing 2-table join w/millions of rows
@ 1998-11-20 02:26 Michael Olivier <molivier@yahoo.com>
1998-11-22 11:18 ` Re: [SQL] optimizing 2-table join w/millions of rows Herouth Maoz <herouth@oumail.openu.ac.il>
0 siblings, 1 reply; 6+ messages in thread
From: Michael Olivier @ 1998-11-20 02:26 UTC (permalink / raw)
To: pgsql-sql; +Cc: molivier@yahoo.com
Hi,
I'm trying to optimize a query between two large tables, which
ultimately will have millions of entries each. I'd appreciate any
suggestions folks have on optimizing. I've tried several things but
haven't gotten the performance I need yet.
The tables are a user table and a background table. Each user can have
multiple backgrounds, that's why they're separate tables. Relationship
is:
1 user <--------> many backgrounds
+------------------+----------------------------------+----------+
| Owner | Relation | Type |
+------------------+----------------------------------+----------+
| michael | bgndtest | table |
| michael | bgndacctname_key | index |
| michael | bgndage_key | index |
| michael | bgndloc_key | index |
| michael | usertest | table |
| michael | userage_key | index |
| michael | userloc_key | index |
| michael | usertestkey | index |
+------------------+----------------------------------+----------+
Table = bgndtest
+------------------------+---------------------------------+-------+
| Field | Type | Length|
+------------------------+---------------------------------+-------+
| acctname | text | var |*
| part_needed | int4 | 4 |*
| loc_needed | int4 | 4 |*
+------------- ----------+---------------------------------+-------+
Table = usertest
+-------------------------+---------------------------------+-------+
| Field | Type | Length|
+-------------------------+---------------------------------+-------+
| acctname | text | var |*
| email | text | var |
| part | int4 | 4 |*
| loc | int4 | 4 |*
+-------------------------+---------------------------------+-------+
* indicates a single column index is available
select U.acctname from usertest U, bgndtest B where
B.part_needed=3 and B.loc_needed=5 and
B.acctname=U.acctname and U.acctname in
(select acctname from usertest where part=2 and loc=3)
(query plan at bottom of this message)
There are other similar queries I'll need to do which will have even
more conditions in the where clause than this...
I noticed it's about 4x slower when I change just one of the =
comparisons to a < ... but I thought with btree indexes, < comparisons
would run fast. Aren't btrees the default for indexes? I ultimately
will be doing a lot of range comparisons, not equality.
If I change "U.acctname in (select...)" to "B.acctname in
(select...)", is there any difference in performance? Seems to be but
I don't know why.
I'm currently benchmarking performance that degrades 4x for every 2x
growth in the tables. Presumably the performance is linear to (users *
backgrounds), and in my tests the number of users rows and backgrounds
rows is the same. But this won't be acceptable once I get to millions
of users, when 20k users costs 3.4 secs on this query (RH 5.1,
Postgres 6.3.2-10, 350 MHz Pentium II).
Re. optimization tips from the FAQ:
* vacuum analyze made a world of difference (10x) after creating indexes
and adding tons of test data
* I've tried running postmaster with -o -F to get rid of fsync(), didn't
seem to help much
* I've tried using -B 1280 because I'm happy to eat up memory for
performance, didn't notice a big difference - where can I read
more about using this parameter?
* I'm not doing a lot of sorts, so increasing memory for sorts
won't help, I don't think
* Cluster doesn't seem like it will help because I'm finding rows
based on several parameters
* returning OID from subquery and indexing OID column didn't seem to
help performance
Is there any way to get postgres to load a whole table into memory?
I'd like to do some benchmarking with small number of table entries to
find out how it's going to scale. In production, I can buy a machine
with lots of memory and take the altavista approach, but this requires
a DB that will hold tables in memory.
If you think I'd be better off with another DBMS (could be Linux or
NT, must have eval period of 60 days or more, or be cheap or free) --
please let me know.
Thanks very much for any input, pointers to docs, etc! I'm new to
query optimization and I'm working hard to get an understanding of how
PostgreSQL will scale for my project.
--Michael
----------------
query plan:
Nested Loop (cost=11.09 size=1 width=24)
-> Index Scan on b (cost=9.04 size=1 width=12)
SubPlan
-> Index Scan on usertest (cost=2.05 size=1 width=12)
-> Index Scan on u (cost=2.05 size=10200 width=12)
verbose query plan:
{NESTLOOP :cost 11.0861 :size 1 :width 24 :state <> :qptargetlist
({TLE :resdom {RESDOM :resno 1 :restype 25 :restypmod -1 :resname
acctname :reskey 0 :reskeyop 0 :resjunk 0 } :expr {VAR :varno 65001
:varattno 1 :vartype 25 :vartypmod -1 :varlevelsup 0 :varnoold 1
:varoattno 1 }}) :qpqual <> :lefttree {INDEXSCAN :cost 9.03614 :size
1 :width 12 :state <> :qptargetlist ({TLE :resdom {RESDOM :resno 1
:restype 25 :restypmod -1 :resname <> :reskey 0 :reskeyop 0
:resjunk 0 } :expr {VAR :varno 1 :varattno 1 :vartype 25 :vartypmod
-1 :varlevelsup 0 :varnoold 1 :varoattno 1 }}) :qpqual ({EXPR
:typeOid 0 :opType op :oper {OPER :opno 96 :opid 65 :opresulttype
16 } :args ({VAR :varno 1 :varattno 2 :vartype 23 :vartypmod -1
:varlevelsup 0 :varnoold 1 :varoattno 2 } {CONST :consttype 23
:constlen 4 :constisnull false :constvalue 4 [ 26 0 0 0 ]
:constbyval true})} {EXPR :typeOid 16 :opType subp :oper {SUBPLAN
:plan {INDEXSCAN :cost 2.05 :size 1 :width 12 :state <>
:qptargetlist ({TLE :resdom {RESDOM :resno 1 :restype 25 :restypmod
-1 :resname acctname :reskey 0 :reskeyop 0 :resjunk 0 } :expr {VAR
:varno 1 :varattno 1 :vartype 25 :vartypmod -1 :varlevelsup 0
:varnoold 1 :varoattno 1 }}) :qpqual ({EXPR :typeOid 0 :opType op
:oper {OPER :opno 96 :opid 65 :opresulttype 16 } :args ({VAR :varno
1 :varattno 3 :vartype 23 :vartypmod -1 :varlevelsup 0 :varnoold
1 :varoattno 3 } {CONST :consttype 23 :constlen 4 :constisnull
false :constvalue 4 [ 12 0 0 0 ] :constbyval true})}) :lefttree
<> :righttree <> :extprm () :locprm () :initplan <> :nprm 0
:scanrelid 1 :indxid ( 189085 ) :indxqual (({EXPR :typeOid 0 :opType
op :oper {OPER :opno 96 :opid 65 :opresulttype 16 } :args ({VAR
:varno 1 :varattno 1 :vartype 23 :vartypmod -1 :varlevelsup 0
:varnoold 1 :varoattno 4 } {CONST :consttype 23 :constlen 4
:constisnull false :constvalue 4 [ 27 0 0 0 ] :constbyval
true})}))} :planid 0 :rtable ({RTE :relname usertest :refname
usertest :relid 189056 :inh false :inFromCl true :skipAcl false})
:setprm () :parprm () :slink {SUBLINK :subLinkType 2 :useor false
:lefthand ({VAR :varno 1 :varattno 1 :vartype 25 :vartypmod -1
:varlevelsup 0 :varnoold 1 :varoattno 1 }) :oper ({EXPR :typeOid 16
:opType op :oper {OPER :opno 98 :opid 67 :opresulttype 16 } :args
({VAR :varno 1 :varattno 1 :vartype 25 :vartypmod -1 :varlevelsup
0 :varnoold 1 :varoattno 1 } {CONST :consttype 25 :constlen 0
:constisnull true :constvalue <> :constbyval true})}) :subselect <>}}
:args <>}) :lefttree <> :righttree <> :extprm () :locprm () :initplan
<> :nprm 0 :scanrelid 1 :indxid ( 189094 ) :indxqual (({EXPR
:typeOid 0 :opType op :oper {OPER :opno 96 :opid 65 :opresulttype
16 } :args ({VAR :varno 1 :varattno 1 :vartype 23 :vartypmod -1
:varlevelsup 0 :varnoold 1 :varoattno 3 } {CONST :consttype 23
:constlen 4 :constisnull false :constvalue 4 [ 5 0 0 0 ]
:constbyval true})}))} :righttree {INDEXSCAN :cost 2.05 :size 10200
:width 12 :state <> :qptargetlist ({TLE :resdom {RESDOM :resno 1
:restype 25 :restypmod -1 :resname <> :reskey 0 :reskeyop 0
:resjunk 0 } :expr {VAR :varno 2 :varattno 1 :vartype 25 :vartypmod
-1 :varlevelsup 0 :varnoold 2 :varoattno 1 }}) :qpqual <> :lefttree
<> :righttree <> :extprm () :locprm () :initplan <> :nprm 0
:scanrelid 2 :indxid ( 189079 ) :indxqual (({EXPR :typeOid 0 :opType
op :oper {OPER :opno 98 :opid 67 :opresulttype 16 } :args ({VAR
:varno 65001 :varattno 1 :vartype 25 :vartypmod -1 :varlevelsup 0
:varnoold 1 :varoattno 1 } {VAR :varno 2 :varattno 1 :vartype 25
:vartypmod -1 :varlevelsup 0 :varnoold 2 :varoattno 1 })}))}
:extprm () :locprm () :initplan <> :nprm 0 }
_________________________________________________________
DO YOU YAHOO!?
Get your free @yahoo.com address at http://mail.yahoo.com
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [SQL] optimizing 2-table join w/millions of rows
1998-11-20 02:26 optimizing 2-table join w/millions of rows Michael Olivier <molivier@yahoo.com>
@ 1998-11-22 11:18 ` Herouth Maoz <herouth@oumail.openu.ac.il>
0 siblings, 0 replies; 6+ messages in thread
From: Herouth Maoz @ 1998-11-22 11:18 UTC (permalink / raw)
To: Michael Olivier <molivier@yahoo.com>; pgsql-sql
At 4:26 +0200 on 20/11/98, Michael Olivier wrote:
>
> select U.acctname from usertest U, bgndtest B where
> B.part_needed=3 and B.loc_needed=5 and
> B.acctname=U.acctname and U.acctname in
> (select acctname from usertest where part=2 and loc=3)
Can you explain *verbally* what you meant to do here? It seems as if the
subselect is redundant. How about:
SELECT U.acctname
FROM usertest U, bgndtest B
WHERE B.acctname = U.acctname
AND B.part_needed=3 AND B.loc_needed=5
AND U.part=2 AND U.loc=3;
Herouth
--
Herouth Maoz, Internet developer.
Open University of Israel - Telem project
http://telem.openu.ac.il/~herutma
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [SQL] optimizing 2-table join w/millions of rows
@ 1998-11-23 03:05 Michael Olivier <molivier@yahoo.com>
1998-11-23 13:09 ` Re: [SQL] optimizing 2-table join w/millions of rows Herouth Maoz <herouth@oumail.openu.ac.il>
0 siblings, 1 reply; 6+ messages in thread
From: Michael Olivier @ 1998-11-23 03:05 UTC (permalink / raw)
To: Herouth Maoz <herouth@oumail.openu.ac.il>; pgsql-sql
---Herouth Maoz <herouth@oumail.openu.ac.il> wrote:
>
> At 4:26 +0200 on 20/11/98, Michael Olivier wrote:
>
>
> >
> > select U.acctname from usertest U, bgndtest B where
> > B.part_needed=3 and B.loc_needed=5 and
> > B.acctname=U.acctname and U.acctname in
> > (select acctname from usertest where part=2 and loc=3)
>
> Can you explain *verbally* what you meant to do here? It seems as if
the
> subselect is redundant.
It's not redundant, but an attempt to optimize the overall query
performance by using a subquery. What this does is compare two users
parameters against each other: "find all users who need part 3 and
need loc 5 and who have part 2 and loc 3"
> How about:
>
> SELECT U.acctname
> FROM usertest U, bgndtest B
> WHERE B.acctname = U.acctname
> AND B.part_needed=3 AND B.loc_needed=5
> AND U.part=2 AND U.loc=3;
Yes, that looks equivalent. My problem is this is too slow an
operation as I'm benchmarking it right now. And if I add less-than or
greater-than comparisons, the performance goes _way_ down from there.
How can I get the best performance out of this kind of operation?
Is there any way to force postgres to hold certain tables in memory
all the time? As I said, cost of memory isn't an issue, but
performance is.
thanks,
Michael
_________________________________________________________
DO YOU YAHOO!?
Get your free @yahoo.com address at http://mail.yahoo.com
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [SQL] optimizing 2-table join w/millions of rows
1998-11-23 03:05 Re: [SQL] optimizing 2-table join w/millions of rows Michael Olivier <molivier@yahoo.com>
@ 1998-11-23 13:09 ` Herouth Maoz <herouth@oumail.openu.ac.il>
0 siblings, 0 replies; 6+ messages in thread
From: Herouth Maoz @ 1998-11-23 13:09 UTC (permalink / raw)
To: Michael Olivier <molivier@yahoo.com>; +Cc: pgsql-sql
At 5:05 +0200 on 23/11/98, Michael Olivier wrote:
>
> > How about:
> >
> > SELECT U.acctname
> > FROM usertest U, bgndtest B
> > WHERE B.acctname = U.acctname
> > AND B.part_needed=3 AND B.loc_needed=5
> > AND U.part=2 AND U.loc=3;
>
> Yes, that looks equivalent. My problem is this is too slow an
> operation as I'm benchmarking it right now. And if I add less-than or
> greater-than comparisons, the performance goes _way_ down from there.
> How can I get the best performance out of this kind of operation?
>
> Is there any way to force postgres to hold certain tables in memory
> all the time? As I said, cost of memory isn't an issue, but
> performance is.
This is very strange. As a general rule, a simple join should always be
faster than a query with a subquery. Especially when that subquery is "in"
and not "exists".
In principle, if there is an index on the part, loc and acctname (separate
indices) in usertest, and on part_needed, loc_needed and acctname in
bgndtest, the most optimal query should be: restrict each of the tables by
the literal comparisons, and then match the acctname.
I don't know who wrote the optimiser, and I'm not sure he is on this list.
There are optimizer settings which can be changed, such as SET R_PLANS ON.
In any case, if you see in "real life" that a subquery actually works
better for you, then avoid the join. No reason to do both:
SELECT acctname
FROM bgndtest
WHERE part_needed=3 and loc_needed=5
AND acctname IN (
SELECT acctname
FROM usertest
WHERE part=2 AND loc=3
);
Or better yet:
SELECT acctname
FROM bgndtest B
WHERE part_needed=3 and loc_needed=5
AND EXISTS (
SELECT *
FROM usertest U
WHERE part=2 AND loc=3
AND U.acctname = B.acctname
);
Of course, you may do it the other way around. It depends on which of your
tables is supposed to have more records, and which of the comparisons is
actually a "=" comparison, which is very important, because less-than and
greater-than don't use the indices.
What I mean by "the other way around" is:
SELECT acctname
FROM usertest U
WHERE part=2 and loc=3
AND EXISTS (
SELECT *
FROM bgndtest B
WHERE part_needed=3 and loc_needed=5
AND U.acctname = B.acctname
);
As for your question - there is no way to keep an entire table in memory,
unless you have a ram disk.
Herouth
--
Herouth Maoz, Internet developer.
Open University of Israel - Telem project
http://telem.openu.ac.il/~herutma
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [SQL] optimizing 2-table join w/millions of rows
@ 1998-11-23 16:10 ` Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 6+ messages in thread
From: Tom Lane @ 1998-11-23 16:10 UTC (permalink / raw)
To: Michael Olivier <molivier@yahoo.com>; +Cc: pgsql-sql@hub.org
Michael Olivier <molivier@yahoo.com> writes:
>> How about:
>> SELECT U.acctname
>> FROM usertest U, bgndtest B
>> WHERE B.acctname = U.acctname
>> AND B.part_needed=3 AND B.loc_needed=5
>> AND U.part=2 AND U.loc=3;
> Yes, that looks equivalent. My problem is this is too slow an
> operation as I'm benchmarking it right now. And if I add less-than or
> greater-than comparisons, the performance goes _way_ down from there.
> How can I get the best performance out of this kind of operation?
The main thing is to make sure you have appropriate indexes and that
the query optimizer is making reasonable use of them. My guess here
is that you want b-tree indexes on B.acctname and U.acctname, which
the optimizer can use to drive a merge join. (Use EXPLAIN with the
query to see what plan the optimizer will actually use; don't forget
that if you haven't VACUUMed the tables lately, the optimizer may be
working from bogus statistics.)
A different possibility is to do the primary search on the part number,
ie rewrite to
SELECT U.acctname
FROM usertest U, bgndtest B
WHERE B.part_needed=3
AND U.part=2
AND B.loc_needed=5
AND B.acctname = U.acctname
AND U.loc=3;
Here, indexes on the part number would be stressed. You'd have to
experiment to see which is faster on your data. (As far as I know,
the Postgres optimizer will always evaluate your AND clauses left to
right, which means that the key to performance is to make the leftmost
clause reject as large a fraction of candidate rows as possible.)
It's possible that indexes on some of the secondary fields would help,
depending on what the statistics of your data are. But every index
you add slows down insert/update performance, so keep an eye on that
when you're deciding how many indexes are worth having.
> Is there any way to force postgres to hold certain tables in memory
> all the time? As I said, cost of memory isn't an issue, but
> performance is.
I don't think you can lock a specific table into memory. What you can
do is increase the size of the shared buffer area used by the backends
(-B switch during postmaster startup, IIRC). This should give you
pretty much the same result, if you're always hitting the same table,
and it's much more flexible if your access patterns change over time.
regards, tom lane
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: [SQL] optimizing 2-table join w/millions of rows
@ 1998-11-23 16:36 ` Herouth Maoz <herouth@oumail.openu.ac.il>
1 sibling, 0 replies; 6+ messages in thread
From: Herouth Maoz @ 1998-11-23 16:36 UTC (permalink / raw)
To: pgsql-sql
At 18:10 +0200 on 23/11/98, Tom Lane wrote:
> Here, indexes on the part number would be stressed. You'd have to
> experiment to see which is faster on your data. (As far as I know,
> the Postgres optimizer will always evaluate your AND clauses left to
> right, which means that the key to performance is to make the leftmost
> clause reject as large a fraction of candidate rows as possible.)
I thought the optimizer canonized the where clause into an ANDing of ORs,
and then sought the best solution. That is, that the order of the clauses
did not matter, because the optimizer would know that comparison to a
literal on an indexed column is better than comparison to a field.
Herouth
--
Herouth Maoz, Internet developer.
Open University of Israel - Telem project
http://telem.openu.ac.il/~herutma
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~1998-11-23 16:36 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
1998-11-20 02:26 optimizing 2-table join w/millions of rows Michael Olivier <molivier@yahoo.com>
1998-11-22 11:18 ` Herouth Maoz <herouth@oumail.openu.ac.il>
1998-11-23 03:05 Re: [SQL] optimizing 2-table join w/millions of rows Michael Olivier <molivier@yahoo.com>
1998-11-23 13:09 ` Herouth Maoz <herouth@oumail.openu.ac.il>
1998-11-23 16:10 ` Tom Lane <tgl@sss.pgh.pa.us>
1998-11-23 16:36 ` Herouth Maoz <herouth@oumail.openu.ac.il>
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