Message-ID: <45AE5519.50705@myemma.com>
Date: Wed, 17 Jan 2007 10:55:53 -0600
From: Kim <kim@myemma.com>
User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716)
MIME-Version: 1.0
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] unusual performance for vac following 8.2
References: <45A671CD.1050706@myemma.com> <27939.1168539652@sss.pgh.pa.us>
	<45A68C74.4080405@myemma.com> <28949.1168544710@sss.pgh.pa.us>
	<18336.1168557020@sss.pgh.pa.us>
In-Reply-To: <18336.1168557020@sss.pgh.pa.us>
Content-Type: multipart/alternative;
	boundary="------------030607080908080303030505"

This is a multi-part message in MIME format.
--------------030607080908080303030505
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hello again Tom,

We have our upgrade to 8.2.1 scheduled for this weekend, and we noticed 
your message regarding the vacuum patch being applied to 8.2 and 
back-patched. I expect I know the answer to this next question :) but I 
was wondering if the patch referenced below has also been bundled into 
the normal source download of 8.2.1 or if we would still need to 
manually apply it?

- Fix a performance problem in databases with large numbers of tables
  (or other types of pg_class entry): the function
  pgstat_vacuum_tabstat, invoked during VACUUM startup, had runtime
  proportional to the number of stats table entries times the number
  of pg_class rows; in other words O(N^2) if the stats collector's
  information is reasonably complete.  Replace list searching with a
  hash table to bring it back to O(N) behavior.  Per report from kim
  at myemma.com.  Back-patch as far as 8.1; 8.0 and before use
  different coding here.

Thanks,
Kim


Tom Lane wrote:

>I wrote:
>  
>
>>What I think we need to do about this is
>>(1) fix pgstat_vacuum_tabstats to have non-O(N^2) behavior; I'm thinking
>>of using a hash table for the OIDs instead of a linear list.  Should be
>>a pretty small change; I'll work on it today.
>>    
>>
>
>I've applied the attached patch to 8.2 to do the above.  Please give it
>a try and see how much it helps for you.  Some limited testing here
>confirms a noticeable improvement in VACUUM startup time at 10000
>tables, and of course it should be 100X worse with 100000 tables.
>
>I am still confused why you didn't see the problem in 8.1, though.
>This code is just about exactly the same in 8.1.  Maybe you changed
>your stats collector settings when moving to 8.2?
>
>			regards, tom lane
>
>  
>
>------------------------------------------------------------------------
>
>Index: pgstat.c
>===================================================================
>RCS file: /cvsroot/pgsql/src/backend/postmaster/pgstat.c,v
>retrieving revision 1.140
>diff -c -r1.140 pgstat.c
>*** pgstat.c	21 Nov 2006 20:59:52 -0000	1.140
>--- pgstat.c	11 Jan 2007 22:32:30 -0000
>***************
>*** 159,164 ****
>--- 159,165 ----
>  static void pgstat_read_statsfile(HTAB **dbhash, Oid onlydb);
>  static void backend_read_statsfile(void);
>  static void pgstat_read_current_status(void);
>+ static HTAB *pgstat_collect_oids(Oid catalogid);
>  
>  static void pgstat_setheader(PgStat_MsgHdr *hdr, StatMsgType mtype);
>  static void pgstat_send(void *msg, int len);
>***************
>*** 657,666 ****
>  void
>  pgstat_vacuum_tabstat(void)
>  {
>! 	List	   *oidlist;
>! 	Relation	rel;
>! 	HeapScanDesc scan;
>! 	HeapTuple	tup;
>  	PgStat_MsgTabpurge msg;
>  	HASH_SEQ_STATUS hstat;
>  	PgStat_StatDBEntry *dbentry;
>--- 658,664 ----
>  void
>  pgstat_vacuum_tabstat(void)
>  {
>! 	HTAB	   *htab;
>  	PgStat_MsgTabpurge msg;
>  	HASH_SEQ_STATUS hstat;
>  	PgStat_StatDBEntry *dbentry;
>***************
>*** 679,693 ****
>  	/*
>  	 * Read pg_database and make a list of OIDs of all existing databases
>  	 */
>! 	oidlist = NIL;
>! 	rel = heap_open(DatabaseRelationId, AccessShareLock);
>! 	scan = heap_beginscan(rel, SnapshotNow, 0, NULL);
>! 	while ((tup = heap_getnext(scan, ForwardScanDirection)) != NULL)
>! 	{
>! 		oidlist = lappend_oid(oidlist, HeapTupleGetOid(tup));
>! 	}
>! 	heap_endscan(scan);
>! 	heap_close(rel, AccessShareLock);
>  
>  	/*
>  	 * Search the database hash table for dead databases and tell the
>--- 677,683 ----
>  	/*
>  	 * Read pg_database and make a list of OIDs of all existing databases
>  	 */
>! 	htab = pgstat_collect_oids(DatabaseRelationId);
>  
>  	/*
>  	 * Search the database hash table for dead databases and tell the
>***************
>*** 698,709 ****
>  	{
>  		Oid			dbid = dbentry->databaseid;
>  
>! 		if (!list_member_oid(oidlist, dbid))
>  			pgstat_drop_database(dbid);
>  	}
>  
>  	/* Clean up */
>! 	list_free(oidlist);
>  
>  	/*
>  	 * Lookup our own database entry; if not found, nothing more to do.
>--- 688,701 ----
>  	{
>  		Oid			dbid = dbentry->databaseid;
>  
>! 		CHECK_FOR_INTERRUPTS();
>! 
>! 		if (hash_search(htab, (void *) &dbid, HASH_FIND, NULL) == NULL)
>  			pgstat_drop_database(dbid);
>  	}
>  
>  	/* Clean up */
>! 	hash_destroy(htab);
>  
>  	/*
>  	 * Lookup our own database entry; if not found, nothing more to do.
>***************
>*** 717,731 ****
>  	/*
>  	 * Similarly to above, make a list of all known relations in this DB.
>  	 */
>! 	oidlist = NIL;
>! 	rel = heap_open(RelationRelationId, AccessShareLock);
>! 	scan = heap_beginscan(rel, SnapshotNow, 0, NULL);
>! 	while ((tup = heap_getnext(scan, ForwardScanDirection)) != NULL)
>! 	{
>! 		oidlist = lappend_oid(oidlist, HeapTupleGetOid(tup));
>! 	}
>! 	heap_endscan(scan);
>! 	heap_close(rel, AccessShareLock);
>  
>  	/*
>  	 * Initialize our messages table counter to zero
>--- 709,715 ----
>  	/*
>  	 * Similarly to above, make a list of all known relations in this DB.
>  	 */
>! 	htab = pgstat_collect_oids(RelationRelationId);
>  
>  	/*
>  	 * Initialize our messages table counter to zero
>***************
>*** 738,750 ****
>  	hash_seq_init(&hstat, dbentry->tables);
>  	while ((tabentry = (PgStat_StatTabEntry *) hash_seq_search(&hstat)) != NULL)
>  	{
>! 		if (list_member_oid(oidlist, tabentry->tableid))
>  			continue;
>  
>  		/*
>  		 * Not there, so add this table's Oid to the message
>  		 */
>! 		msg.m_tableid[msg.m_nentries++] = tabentry->tableid;
>  
>  		/*
>  		 * If the message is full, send it out and reinitialize to empty
>--- 722,738 ----
>  	hash_seq_init(&hstat, dbentry->tables);
>  	while ((tabentry = (PgStat_StatTabEntry *) hash_seq_search(&hstat)) != NULL)
>  	{
>! 		Oid			tabid = tabentry->tableid;
>! 
>! 		CHECK_FOR_INTERRUPTS();
>! 
>! 		if (hash_search(htab, (void *) &tabid, HASH_FIND, NULL) != NULL)
>  			continue;
>  
>  		/*
>  		 * Not there, so add this table's Oid to the message
>  		 */
>! 		msg.m_tableid[msg.m_nentries++] = tabid;
>  
>  		/*
>  		 * If the message is full, send it out and reinitialize to empty
>***************
>*** 776,782 ****
>  	}
>  
>  	/* Clean up */
>! 	list_free(oidlist);
>  }
>  
>  
>--- 764,813 ----
>  	}
>  
>  	/* Clean up */
>! 	hash_destroy(htab);
>! }
>! 
>! 
>! /* ----------
>!  * pgstat_collect_oids() -
>!  *
>!  *	Collect the OIDs of either all databases or all tables, according to
>!  *	the parameter, into a temporary hash table.  Caller should hash_destroy
>!  *	the result when done with it.
>!  * ----------
>!  */
>! static HTAB *
>! pgstat_collect_oids(Oid catalogid)
>! {
>! 	HTAB	   *htab;
>! 	HASHCTL		hash_ctl;
>! 	Relation	rel;
>! 	HeapScanDesc scan;
>! 	HeapTuple	tup;
>! 
>! 	memset(&hash_ctl, 0, sizeof(hash_ctl));
>! 	hash_ctl.keysize = sizeof(Oid);
>! 	hash_ctl.entrysize = sizeof(Oid);
>! 	hash_ctl.hash = oid_hash;
>! 	htab = hash_create("Temporary table of OIDs",
>! 					   PGSTAT_TAB_HASH_SIZE,
>! 					   &hash_ctl,
>! 					   HASH_ELEM | HASH_FUNCTION);
>! 
>! 	rel = heap_open(catalogid, AccessShareLock);
>! 	scan = heap_beginscan(rel, SnapshotNow, 0, NULL);
>! 	while ((tup = heap_getnext(scan, ForwardScanDirection)) != NULL)
>! 	{
>! 		Oid		thisoid = HeapTupleGetOid(tup);
>! 
>! 		CHECK_FOR_INTERRUPTS();
>! 
>! 		(void) hash_search(htab, (void *) &thisoid, HASH_ENTER, NULL);
>! 	}
>! 	heap_endscan(scan);
>! 	heap_close(rel, AccessShareLock);
>! 
>! 	return htab;
>  }
>  
>  
>  
>

--------------030607080908080303030505
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Hello again Tom,<br>
<br>
We have our upgrade to 8.2.1 scheduled for this weekend, and we noticed
your message regarding the vacuum patch being applied to 8.2 and
back-patched. I expect I know the answer to this next question :) but I
was wondering if the patch referenced below has also been bundled into
the normal source download of 8.2.1 or if we would still need to
manually apply it? <br>
<br>
<div style="margin: 0px;">- Fix a performance problem in databases with
large numbers of tables</div>
<div style="margin: 0px;">&nbsp; (or other types of pg_class entry): the
function</div>
<div style="margin: 0px;">&nbsp; pgstat_vacuum_tabstat, invoked during
VACUUM startup, had runtime</div>
<div style="margin: 0px;">&nbsp; proportional to the number of stats table
entries times the number</div>
<div style="margin: 0px;">&nbsp; of pg_class rows; in other words O(N^2) if
the stats collector's</div>
<div style="margin: 0px;">&nbsp; information is reasonably complete.&nbsp;
Replace list searching with a</div>
<div style="margin: 0px;">&nbsp; hash table to bring it back to O(N)
behavior.&nbsp; Per report from kim</div>
<div style="margin: 0px;">&nbsp; at myemma.com.&nbsp; Back-patch as far as 8.1;
8.0 and before use</div>
<div style="margin: 0px;">&nbsp; different coding here.</div>
<br>
Thanks,<br>
Kim<br>
<br>
<br>
Tom Lane wrote:
<blockquote cite="mid18336.1168557020@sss.pgh.pa.us" type="cite">
  <pre wrap="">I wrote:
  </pre>
  <blockquote type="cite">
    <pre wrap="">What I think we need to do about this is
(1) fix pgstat_vacuum_tabstats to have non-O(N^2) behavior; I'm thinking
of using a hash table for the OIDs instead of a linear list.  Should be
a pretty small change; I'll work on it today.
    </pre>
  </blockquote>
  <pre wrap=""><!---->
I've applied the attached patch to 8.2 to do the above.  Please give it
a try and see how much it helps for you.  Some limited testing here
confirms a noticeable improvement in VACUUM startup time at 10000
tables, and of course it should be 100X worse with 100000 tables.

I am still confused why you didn't see the problem in 8.1, though.
This code is just about exactly the same in 8.1.  Maybe you changed
your stats collector settings when moving to 8.2?

			regards, tom lane

  </pre>
  <pre wrap="">
<hr size="4" width="90%">
Index: pgstat.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/postmaster/pgstat.c,v
retrieving revision 1.140
diff -c -r1.140 pgstat.c
*** pgstat.c	21 Nov 2006 20:59:52 -0000	1.140
--- pgstat.c	11 Jan 2007 22:32:30 -0000
***************
*** 159,164 ****
--- 159,165 ----
  static void pgstat_read_statsfile(HTAB **dbhash, Oid onlydb);
  static void backend_read_statsfile(void);
  static void pgstat_read_current_status(void);
+ static HTAB *pgstat_collect_oids(Oid catalogid);
  
  static void pgstat_setheader(PgStat_MsgHdr *hdr, StatMsgType mtype);
  static void pgstat_send(void *msg, int len);
***************
*** 657,666 ****
  void
  pgstat_vacuum_tabstat(void)
  {
! 	List	   *oidlist;
! 	Relation	rel;
! 	HeapScanDesc scan;
! 	HeapTuple	tup;
  	PgStat_MsgTabpurge msg;
  	HASH_SEQ_STATUS hstat;
  	PgStat_StatDBEntry *dbentry;
--- 658,664 ----
  void
  pgstat_vacuum_tabstat(void)
  {
! 	HTAB	   *htab;
  	PgStat_MsgTabpurge msg;
  	HASH_SEQ_STATUS hstat;
  	PgStat_StatDBEntry *dbentry;
***************
*** 679,693 ****
  	/*
  	 * Read pg_database and make a list of OIDs of all existing databases
  	 */
! 	oidlist = NIL;
! 	rel = heap_open(DatabaseRelationId, AccessShareLock);
! 	scan = heap_beginscan(rel, SnapshotNow, 0, NULL);
! 	while ((tup = heap_getnext(scan, ForwardScanDirection)) != NULL)
! 	{
! 		oidlist = lappend_oid(oidlist, HeapTupleGetOid(tup));
! 	}
! 	heap_endscan(scan);
! 	heap_close(rel, AccessShareLock);
  
  	/*
  	 * Search the database hash table for dead databases and tell the
--- 677,683 ----
  	/*
  	 * Read pg_database and make a list of OIDs of all existing databases
  	 */
! 	htab = pgstat_collect_oids(DatabaseRelationId);
  
  	/*
  	 * Search the database hash table for dead databases and tell the
***************
*** 698,709 ****
  	{
  		Oid			dbid = dbentry-&gt;databaseid;
  
! 		if (!list_member_oid(oidlist, dbid))
  			pgstat_drop_database(dbid);
  	}
  
  	/* Clean up */
! 	list_free(oidlist);
  
  	/*
  	 * Lookup our own database entry; if not found, nothing more to do.
--- 688,701 ----
  	{
  		Oid			dbid = dbentry-&gt;databaseid;
  
! 		CHECK_FOR_INTERRUPTS();
! 
! 		if (hash_search(htab, (void *) &amp;dbid, HASH_FIND, NULL) == NULL)
  			pgstat_drop_database(dbid);
  	}
  
  	/* Clean up */
! 	hash_destroy(htab);
  
  	/*
  	 * Lookup our own database entry; if not found, nothing more to do.
***************
*** 717,731 ****
  	/*
  	 * Similarly to above, make a list of all known relations in this DB.
  	 */
! 	oidlist = NIL;
! 	rel = heap_open(RelationRelationId, AccessShareLock);
! 	scan = heap_beginscan(rel, SnapshotNow, 0, NULL);
! 	while ((tup = heap_getnext(scan, ForwardScanDirection)) != NULL)
! 	{
! 		oidlist = lappend_oid(oidlist, HeapTupleGetOid(tup));
! 	}
! 	heap_endscan(scan);
! 	heap_close(rel, AccessShareLock);
  
  	/*
  	 * Initialize our messages table counter to zero
--- 709,715 ----
  	/*
  	 * Similarly to above, make a list of all known relations in this DB.
  	 */
! 	htab = pgstat_collect_oids(RelationRelationId);
  
  	/*
  	 * Initialize our messages table counter to zero
***************
*** 738,750 ****
  	hash_seq_init(&amp;hstat, dbentry-&gt;tables);
  	while ((tabentry = (PgStat_StatTabEntry *) hash_seq_search(&amp;hstat)) != NULL)
  	{
! 		if (list_member_oid(oidlist, tabentry-&gt;tableid))
  			continue;
  
  		/*
  		 * Not there, so add this table's Oid to the message
  		 */
! 		msg.m_tableid[msg.m_nentries++] = tabentry-&gt;tableid;
  
  		/*
  		 * If the message is full, send it out and reinitialize to empty
--- 722,738 ----
  	hash_seq_init(&amp;hstat, dbentry-&gt;tables);
  	while ((tabentry = (PgStat_StatTabEntry *) hash_seq_search(&amp;hstat)) != NULL)
  	{
! 		Oid			tabid = tabentry-&gt;tableid;
! 
! 		CHECK_FOR_INTERRUPTS();
! 
! 		if (hash_search(htab, (void *) &amp;tabid, HASH_FIND, NULL) != NULL)
  			continue;
  
  		/*
  		 * Not there, so add this table's Oid to the message
  		 */
! 		msg.m_tableid[msg.m_nentries++] = tabid;
  
  		/*
  		 * If the message is full, send it out and reinitialize to empty
***************
*** 776,782 ****
  	}
  
  	/* Clean up */
! 	list_free(oidlist);
  }
  
  
--- 764,813 ----
  	}
  
  	/* Clean up */
! 	hash_destroy(htab);
! }
! 
! 
! /* ----------
!  * pgstat_collect_oids() -
!  *
!  *	Collect the OIDs of either all databases or all tables, according to
!  *	the parameter, into a temporary hash table.  Caller should hash_destroy
!  *	the result when done with it.
!  * ----------
!  */
! static HTAB *
! pgstat_collect_oids(Oid catalogid)
! {
! 	HTAB	   *htab;
! 	HASHCTL		hash_ctl;
! 	Relation	rel;
! 	HeapScanDesc scan;
! 	HeapTuple	tup;
! 
! 	memset(&amp;hash_ctl, 0, sizeof(hash_ctl));
! 	hash_ctl.keysize = sizeof(Oid);
! 	hash_ctl.entrysize = sizeof(Oid);
! 	hash_ctl.hash = oid_hash;
! 	htab = hash_create("Temporary table of OIDs",
! 					   PGSTAT_TAB_HASH_SIZE,
! 					   &amp;hash_ctl,
! 					   HASH_ELEM | HASH_FUNCTION);
! 
! 	rel = heap_open(catalogid, AccessShareLock);
! 	scan = heap_beginscan(rel, SnapshotNow, 0, NULL);
! 	while ((tup = heap_getnext(scan, ForwardScanDirection)) != NULL)
! 	{
! 		Oid		thisoid = HeapTupleGetOid(tup);
! 
! 		CHECK_FOR_INTERRUPTS();
! 
! 		(void) hash_search(htab, (void *) &amp;thisoid, HASH_ENTER, NULL);
! 	}
! 	heap_endscan(scan);
! 	heap_close(rel, AccessShareLock);
! 
! 	return htab;
  }
  
  
  </pre>
</blockquote>
</body>
</html>

--------------030607080908080303030505--