content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Subject: Re: Sort performance on large tables
Date: Tue, 8 Nov 2005 08:19:44 -0500
Message-ID: <2BCEB9A37A4D354AA276774EE13FB8C263B0BF@mailserver.sandvine.com>
Thread-Topic: [PERFORM] Sort performance on large tables
Thread-Index: AcXkQ4HduZ54PzCmQ7a8YaRl+VD55AAI1WcA
From: "Marc Morin" <marc@sandvine.com>
To: "Charlie Savage" <cfis@interserv.com>, <pgsql-performance@postgresql.org>

I have run into this type of query problem as well.  I solved it in my
application by the following type of query.

SELECT tlid
FROM completechain AS o
WHERE not exists (=20
	SELECT 1
	FROM completechain
	WHERE tlid=3Do.tlid and ogc_fid!=3Do.ogc_fid
);

Assumes of course that you have an index on tlid.

> -----Original Message-----
> From: pgsql-performance-owner@postgresql.org=20
> [mailto:pgsql-performance-owner@postgresql.org] On Behalf Of=20
> Charlie Savage
> Sent: Tuesday, November 08, 2005 2:05 AM
> To: pgsql-performance@postgresql.org
> Subject: [PERFORM] Sort performance on large tables
>=20
> Hi everyone,
>=20
> I have a question about the performance of sort.
>=20
> Setup: Dell Dimension 3000, Suse 10, 1GB ram, PostgreSQL 8.1=20
> RC 1 with PostGIS, 1 built-in 80 GB IDE drive, 1 SATA Seagate=20
> 400GB drive.  The IDE drive has the OS and the WAL files, the=20
> SATA drive the database.=20
>  From hdparm the max IO for the IDE drive is about 50Mb/s and=20
> the SATA drive is about 65Mb/s.  Thus a very low-end machine=20
> - but it used just for development (i.e., it is not a=20
> production machine) and the only thing it does is run a=20
> PostgresSQL database.
>=20
> I have a staging table called completechain that holds US=20
> tiger data (i.e., streets and addresses for the US).  The=20
> table is approximately 18GB.  Its big because there is a lot=20
> of data, but also because the table is not normalized (it=20
> comes that way).
>=20
> I want to extract data out of the file, with the most=20
> important values being stored in a column called tlid.  The=20
> tlid field is an integer, and the values are 98% unique. =20
> There is a second column called ogc_fid which is unique (it=20
> is a serial field).  I need to extract out unique TLID's=20
> (doesn't matter which duplicate I get rid of).  To do this I=20
> am running this query:
>=20
> SELECT tlid, min(ogc_fid)
> FROM completechain
> GROUP BY tlid;
>=20
> The results from explain analyze are:
>=20
> "GroupAggregate  (cost=3D10400373.80..11361807.88 rows=3D48071704=20
> width=3D8) (actual time=3D7311682.715..8315746.835 rows=3D47599910 =
loops=3D1)"
> "  ->  Sort  (cost=3D10400373.80..10520553.06 rows=3D48071704=20
> width=3D8) (actual time=3D7311682.682..7972304.777 rows=3D48199165 =
loops=3D1)"
> "        Sort Key: tlid"
> "        ->  Seq Scan on completechain  (cost=3D0.00..2228584.04=20
> rows=3D48071704 width=3D8) (actual time=3D27.514..773245.046=20
> rows=3D48199165 loops=3D1)"
> "Total runtime: 8486057.185 ms"
> =09
> Doing a similar query produces the same results:
>=20
> SELECT DISTINCT ON (tlid), tlid, ogc_fid FROM completechain;
>=20
> Note it takes over 10 times longer to do the sort than the=20
> full sequential scan.
>=20
> Should I expect results like this?  I realize that the=20
> computer is quite low-end and is very IO bound for this=20
> query, but I'm still surprised that the sort operation takes so long.
>=20
> Out of curiosity, I setup an Oracle database on the same=20
> machine with the same data and ran the same query.  Oracle=20
> was over an order of magnitude faster. Looking at its query=20
> plan, it avoided the sort by using "HASH GROUP BY."  Does=20
> such a construct exist in PostgreSQL (I see only hash joins)?
>=20
> Also as an experiment I forced oracle to do a sort by running=20
> this query:
>=20
> SELECT tlid, min(ogc_fid)
> FROM completechain
> GROUP BY tlid
> ORDER BY tlid;
>=20
> Even with this, it was more than a magnitude faster than Postgresql.=20
> Which makes me think I have somehow misconfigured postgresql=20
> (see the relevant parts of postgresql.conf below).
>=20
> Any idea/help appreciated.
>=20
> Thanks,
>=20
> Charlie
>=20
>=20
> -------------------------------
>=20
> #-------------------------------------------------------------
> --------------
> # RESOURCE USAGE (except WAL)
> #-------------------------------------------------------------
> --------------
>=20
> shared_buffers =3D 40000                  # 40000 buffers * 8192=20
> bytes/buffer =3D 327,680,000 bytes
> #shared_buffers =3D 1000			# min 16 or=20
> max_connections*2, 8KB each
>=20
> temp_buffers =3D 5000
> #temp_buffers =3D 1000			# min 100, 8KB each
> #max_prepared_transactions =3D 5		# can be 0 or more
> # note: increasing max_prepared_transactions costs ~600 bytes=20
> of shared memory # per transaction slot, plus lock space (see=20
> max_locks_per_transaction).
>=20
> work_mem =3D  16384                        # in Kb
> #work_mem =3D 1024			# min 64, size in KB
>=20
> maintenance_work_mem =3D 262144            # in kb
> #maintenance_work_mem =3D 16384		# min 1024, size in KB
> #max_stack_depth =3D 2048			# min 100, size in KB
>=20
> # - Free Space Map -
>=20
> max_fsm_pages =3D 60000=09
> #max_fsm_pages =3D 20000			# min=20
> max_fsm_relations*16, 6 bytes each
>=20
> #max_fsm_relations =3D 1000		# min 100, ~70 bytes each
>=20
> # - Kernel Resource Usage -
>=20
> #max_files_per_process =3D 1000		# min 25
> #preload_libraries =3D ''
>=20
> # - Cost-Based Vacuum Delay -
>=20
> #vacuum_cost_delay =3D 0			# 0-1000 milliseconds
> #vacuum_cost_page_hit =3D 1		# 0-10000 credits
> #vacuum_cost_page_miss =3D 10		# 0-10000 credits
> #vacuum_cost_page_dirty =3D 20		# 0-10000 credits
> #vacuum_cost_limit =3D 200		# 0-10000 credits
>=20
> # - Background writer -
>=20
> #bgwriter_delay =3D 200			# 10-10000 milliseconds=20
> between rounds
> #bgwriter_lru_percent =3D 1.0		# 0-100% of LRU buffers=20
> scanned/round
> #bgwriter_lru_maxpages =3D 5		# 0-1000 buffers max=20
> written/round
> #bgwriter_all_percent =3D 0.333		# 0-100% of all buffers=20
> scanned/round
> #bgwriter_all_maxpages =3D 5		# 0-1000 buffers max=20
> written/round
>=20
>=20
> #-------------------------------------------------------------
> --------------
> # WRITE AHEAD LOG
> #-------------------------------------------------------------
> --------------
>=20
> # - Settings -
>=20
> fsync =3D on				# turns forced=20
> synchronization on or off
> #wal_sync_method =3D fsync		# the default is the=20
> first option
> 					# supported by the=20
> operating system:
> 					#   open_datasync
> 					#   fdatasync
> 					#   fsync
> 					#   fsync_writethrough
> 					#   open_sync
> #full_page_writes =3D on			# recover from=20
> partial page writes
>=20
> wal_buffers =3D 128
> #wal_buffers =3D 8			# min 4, 8KB each
>=20
> #commit_delay =3D 0			# range 0-100000, in=20
> microseconds
> #commit_siblings =3D 5			# range 1-1000
>=20
> # - Checkpoints -
>=20
> checkpoint_segments =3D 256               # 256 * 16Mb =3D=20
> 4,294,967,296 bytes
> checkpoint_timeout =3D 1200		# 1200 seconds (20 minutes)
> checkpoint_warning =3D 30			# in seconds, 0 is off
>=20
> #checkpoint_segments =3D 3		# in logfile segments,=20
> min 1, 16MB each
> #checkpoint_timeout =3D 300		# range 30-3600, in seconds
> #checkpoint_warning =3D 30		# in seconds, 0 is off
>=20
> # - Archiving -
>=20
> #archive_command =3D ''			# command to use to=20
> archive a logfile
> 					# segment
>=20
>=20
> #-------------------------------------------------------------
> --------------
> # QUERY TUNING
> #-------------------------------------------------------------
> --------------
>=20
> # - Planner Method Configuration -
>=20
> #enable_bitmapscan =3D on
> #enable_hashagg =3D on
> #enable_hashjoin =3D on
> #enable_indexscan =3D on
> #enable_mergejoin =3D on
> #enable_nestloop =3D on
> #enable_seqscan =3D on
> #enable_sort =3D on
> #enable_tidscan =3D on
>=20
> # - Planner Cost Constants -
>=20
> effective_cache_size =3D 80000		# 80000 * 8192 =3D=20
> 655,360,000 bytes
> #effective_cache_size =3D 1000		# typically 8KB each
>=20
> random_page_cost =3D 2.5			# units are one=20
> sequential page fetch
> #random_page_cost =3D 4			# units are one=20
> sequential page fetch
> 					# cost
> #cpu_tuple_cost =3D 0.01			# (same)
> #cpu_index_tuple_cost =3D 0.001		# (same)
> #cpu_operator_cost =3D 0.0025		# (same)
>=20
> # - Genetic Query Optimizer -
>=20
> #geqo =3D on
> #geqo_threshold =3D 12
> #geqo_effort =3D 5			# range 1-10
> #geqo_pool_size =3D 0			# selects default based=20
> on effort
> #geqo_generations =3D 0			# selects default based=20
> on effort
> #geqo_selection_bias =3D 2.0		# range 1.5-2.0
>=20
> # - Other Planner Options -
>=20
> default_statistics_target =3D 100		# range 1-1000
> #default_statistics_target =3D 10		# range 1-1000
> #constraint_exclusion =3D off
> #from_collapse_limit =3D 8
> #join_collapse_limit =3D 8		# 1 disables collapsing=20
> of explicit
> 					# JOINs
>=20
>=20
> #-------------------------------------------------------------
> --------------
> #-------------------------------------------------------------
> --------------
> # RUNTIME STATISTICS
> #-------------------------------------------------------------
> --------------
>=20
> # - Statistics Monitoring -
>=20
> #log_parser_stats =3D off
> #log_planner_stats =3D off
> #log_executor_stats =3D off
> #log_statement_stats =3D off
>=20
> # - Query/Index Statistics Collector -
>=20
> stats_start_collector =3D on
> stats_command_string =3D on
> stats_block_level =3D on
> stats_row_level =3D on
>=20
> #stats_start_collector =3D on
> #stats_command_string =3D off
> #stats_block_level =3D off
> #stats_row_level =3D off
> #stats_reset_on_server_start =3D off
>=20
>=20
> #-------------------------------------------------------------
> --------------
> # AUTOVACUUM PARAMETERS
> #-------------------------------------------------------------
> --------------
>=20
> autovacuum =3D true
> autovacuum_naptime =3D 600
>=20
> #autovacuum =3D false			# enable autovacuum subprocess?
> #autovacuum_naptime =3D 60		# time between=20
> autovacuum runs, in secs
> #autovacuum_vacuum_threshold =3D 1000	# min # of tuple updates before
> 					# vacuum
> #autovacuum_analyze_threshold =3D 500	# min # of tuple updates before
> 					# analyze
> #autovacuum_vacuum_scale_factor =3D 0.4	# fraction of rel size before
> 					# vacuum
> #autovacuum_analyze_scale_factor =3D 0.2	# fraction of=20
> rel size before
> 					# analyze
> #autovacuum_vacuum_cost_delay =3D -1	# default vacuum cost delay for
> 					# autovac, -1 means use
> 					# vacuum_cost_delay
> #autovacuum_vacuum_cost_limit =3D -1	# default vacuum cost limit for
> 					# autovac, -1 means use
> 					# vacuum_cost_
>=20
>=20
> ----------------------
>=20
> CREATE TABLE tiger.completechain
> (
>    ogc_fid int4 NOT NULL DEFAULT
> nextval('completechain_ogc_fid_seq'::regclass),
>    module varchar(8) NOT NULL,
>    tlid int4 NOT NULL,
>    side1 int4,
>    source varchar(1) NOT NULL,
>    fedirp varchar(2),
>    fename varchar(30),
>    fetype varchar(4),
>    fedirs varchar(2),
>    cfcc varchar(3) NOT NULL,
>    fraddl varchar(11),
>    toaddl varchar(11),
>    fraddr varchar(11),
>    toaddr varchar(11),
>    friaddl varchar(1),
>    toiaddl varchar(1),
>    friaddr varchar(1),
>    toiaddr varchar(1),
>    zipl int4,
>    zipr int4,
>    aianhhfpl int4,
>    aianhhfpr int4,
>    aihhtlil varchar(1),
>    aihhtlir varchar(1),
>    census1 varchar(1),
>    census2 varchar(1),
>    statel int4,
>    stater int4,
>    countyl int4,
>    countyr int4,
>    cousubl int4,
>    cousubr int4,
>    submcdl int4,
>    submcdr int4,
>    placel int4,
>    placer int4,
>    tractl int4,
>    tractr int4,
>    blockl int4,
>    blockr int4,
>    wkb_geometry public.geometry NOT NULL,
>    CONSTRAINT enforce_dims_wkb_geometry CHECK=20
> (ndims(wkb_geometry) =3D 2),
>    CONSTRAINT enforce_geotype_wkb_geometry CHECK
> (geometrytype(wkb_geometry) =3D 'LINESTRING'::text OR=20
> wkb_geometry IS NULL),
>    CONSTRAINT enforce_srid_wkb_geometry CHECK=20
> (srid(wkb_geometry) =3D 4269)
> )
> WITHOUT OIDS;
> ALTER TABLE tiger.completechain OWNER TO postgres;
>=20
>=20
>=20
>=20
>=20
>=20
> ---------------------------(end of=20
> broadcast)---------------------------
> TIP 5: don't forget to increase your free space map settings
>=20
>=20