Re: 5 minutes to pg_dump nothing

I wrote:
> "Nikita The Spider The Spider" <nikitathespider@gmail.com> writes:
>> Thanks for your help! Given that this problem seems to be triggered by
>> a sort of edge case and the fix is non-trivial, I guess I should not
>> expect a new version of pg_dump soon?

> We might look into fixing it for 8.3, but I doubt we'd risk back-patching
> such a change to older branches.

Actually, it doesn't look that hard --- want to try the attached patch?
I couldn't measure any speed difference at all on the standard PG
regression-test database, but there are not huge numbers of objects
in that.

            regards, tom lane


Index: common.c
===================================================================
RCS file: /cvsroot/pgsql/src/bin/pg_dump/common.c,v
retrieving revision 1.97
diff -c -r1.97 common.c
*** common.c    21 Aug 2007 01:11:20 -0000    1.97
--- common.c    23 Sep 2007 23:37:32 -0000
***************
*** 41,47 ****

  /*
   * These variables are static to avoid the notational cruft of having to pass
!  * them into findTableByOid() and friends.
   */
  static TableInfo *tblinfo;
  static TypeInfo *typinfo;
--- 41,51 ----

  /*
   * These variables are static to avoid the notational cruft of having to pass
!  * them into findTableByOid() and friends.  For each of these arrays, we
!  * build a sorted-by-OID index array immediately after it's built, and then
!  * we use binary search in findTableByOid() and friends.  (qsort'ing the base
!  * arrays themselves would be simpler, but it doesn't work because pg_dump.c
!  * may have already established pointers between items.)
   */
  static TableInfo *tblinfo;
  static TypeInfo *typinfo;
***************
*** 51,62 ****
--- 55,72 ----
  static int    numTypes;
  static int    numFuncs;
  static int    numOperators;
+ static DumpableObject **tblinfoindex;
+ static DumpableObject **typinfoindex;
+ static DumpableObject **funinfoindex;
+ static DumpableObject **oprinfoindex;


  static void flagInhTables(TableInfo *tbinfo, int numTables,
                InhInfo *inhinfo, int numInherits);
  static void flagInhAttrs(TableInfo *tbinfo, int numTables,
               InhInfo *inhinfo, int numInherits);
+ static DumpableObject **buildIndexArray(void *objArray, int numObjs,
+                                         Size objSize);
  static int    DOCatalogIdCompare(const void *p1, const void *p2);
  static void findParentsByOid(TableInfo *self,
                   InhInfo *inhinfo, int numInherits);
***************
*** 104,114 ****
--- 114,126 ----
      if (g_verbose)
          write_msg(NULL, "reading user-defined functions\n");
      funinfo = getFuncs(&numFuncs);
+     funinfoindex = buildIndexArray(funinfo, numFuncs, sizeof(FuncInfo));

      /* this must be after getFuncs */
      if (g_verbose)
          write_msg(NULL, "reading user-defined types\n");
      typinfo = getTypes(&numTypes);
+     typinfoindex = buildIndexArray(typinfo, numTypes, sizeof(TypeInfo));

      /* this must be after getFuncs, too */
      if (g_verbose)
***************
*** 122,127 ****
--- 134,140 ----
      if (g_verbose)
          write_msg(NULL, "reading user-defined operators\n");
      oprinfo = getOperators(&numOperators);
+     oprinfoindex = buildIndexArray(oprinfo, numOperators, sizeof(OprInfo));

      if (g_verbose)
          write_msg(NULL, "reading user-defined operator classes\n");
***************
*** 154,159 ****
--- 167,173 ----
      if (g_verbose)
          write_msg(NULL, "reading user-defined tables\n");
      tblinfo = getTables(&numTables);
+     tblinfoindex = buildIndexArray(tblinfo, numTables, sizeof(TableInfo));

      if (g_verbose)
          write_msg(NULL, "reading table inheritance information\n");
***************
*** 540,545 ****
--- 554,623 ----
      return NULL;
  }

+ /*
+  * Find a DumpableObject by OID, in a pre-sorted array of one type of object
+  *
+  * Returns NULL for unknown OID
+  */
+ static DumpableObject *
+ findObjectByOid(Oid oid, DumpableObject **indexArray, int numObjs)
+ {
+     DumpableObject **low;
+     DumpableObject **high;
+
+     /*
+      * This is the same as findObjectByCatalogId except we assume we need
+      * not look at table OID because the objects are all the same type.
+      *
+      * We could use bsearch() here, but the notational cruft of calling
+      * bsearch is nearly as bad as doing it ourselves; and the generalized
+      * bsearch function is noticeably slower as well.
+      */
+     if (numObjs <= 0)
+         return NULL;
+     low = indexArray;
+     high = indexArray + (numObjs - 1);
+     while (low <= high)
+     {
+         DumpableObject **middle;
+         int            difference;
+
+         middle = low + (high - low) / 2;
+         difference = oidcmp((*middle)->catId.oid, oid);
+         if (difference == 0)
+             return *middle;
+         else if (difference < 0)
+             low = middle + 1;
+         else
+             high = middle - 1;
+     }
+     return NULL;
+ }
+
+ /*
+  * Build an index array of DumpableObject pointers, sorted by OID
+  */
+ static DumpableObject **
+ buildIndexArray(void *objArray, int numObjs, Size objSize)
+ {
+     DumpableObject **ptrs;
+     int        i;
+
+     ptrs = (DumpableObject **) malloc(numObjs * sizeof(DumpableObject *));
+     for (i = 0; i < numObjs; i++)
+         ptrs[i] = (DumpableObject *) ((char *) objArray + i * objSize);
+
+     /* We can use DOCatalogIdCompare to sort since its first key is OID */
+     if (numObjs > 1)
+         qsort((void *) ptrs, numObjs, sizeof(DumpableObject *),
+               DOCatalogIdCompare);
+
+     return ptrs;
+ }
+
+ /*
+  * qsort comparator for pointers to DumpableObjects
+  */
  static int
  DOCatalogIdCompare(const void *p1, const void *p2)
  {
***************
*** 630,709 ****
   * findTableByOid
   *      finds the entry (in tblinfo) of the table with the given oid
   *      returns NULL if not found
-  *
-  * NOTE:  should hash this, but just do linear search for now
   */
  TableInfo *
  findTableByOid(Oid oid)
  {
!     int            i;
!
!     for (i = 0; i < numTables; i++)
!     {
!         if (tblinfo[i].dobj.catId.oid == oid)
!             return &tblinfo[i];
!     }
!     return NULL;
  }

  /*
   * findTypeByOid
   *      finds the entry (in typinfo) of the type with the given oid
   *      returns NULL if not found
-  *
-  * NOTE:  should hash this, but just do linear search for now
   */
  TypeInfo *
  findTypeByOid(Oid oid)
  {
!     int            i;
!
!     for (i = 0; i < numTypes; i++)
!     {
!         if (typinfo[i].dobj.catId.oid == oid)
!             return &typinfo[i];
!     }
!     return NULL;
  }

  /*
   * findFuncByOid
   *      finds the entry (in funinfo) of the function with the given oid
   *      returns NULL if not found
-  *
-  * NOTE:  should hash this, but just do linear search for now
   */
  FuncInfo *
  findFuncByOid(Oid oid)
  {
!     int            i;
!
!     for (i = 0; i < numFuncs; i++)
!     {
!         if (funinfo[i].dobj.catId.oid == oid)
!             return &funinfo[i];
!     }
!     return NULL;
  }

  /*
   * findOprByOid
   *      finds the entry (in oprinfo) of the operator with the given oid
   *      returns NULL if not found
-  *
-  * NOTE:  should hash this, but just do linear search for now
   */
  OprInfo *
  findOprByOid(Oid oid)
  {
!     int            i;
!
!     for (i = 0; i < numOperators; i++)
!     {
!         if (oprinfo[i].dobj.catId.oid == oid)
!             return &oprinfo[i];
!     }
!     return NULL;
  }


--- 708,751 ----
   * findTableByOid
   *      finds the entry (in tblinfo) of the table with the given oid
   *      returns NULL if not found
   */
  TableInfo *
  findTableByOid(Oid oid)
  {
!     return (TableInfo *) findObjectByOid(oid, tblinfoindex, numTables);
  }

  /*
   * findTypeByOid
   *      finds the entry (in typinfo) of the type with the given oid
   *      returns NULL if not found
   */
  TypeInfo *
  findTypeByOid(Oid oid)
  {
!     return (TypeInfo *) findObjectByOid(oid, typinfoindex, numTypes);
  }

  /*
   * findFuncByOid
   *      finds the entry (in funinfo) of the function with the given oid
   *      returns NULL if not found
   */
  FuncInfo *
  findFuncByOid(Oid oid)
  {
!     return (FuncInfo *) findObjectByOid(oid, funinfoindex, numFuncs);
  }

  /*
   * findOprByOid
   *      finds the entry (in oprinfo) of the operator with the given oid
   *      returns NULL if not found
   */
  OprInfo *
  findOprByOid(Oid oid)
  {
!     return (OprInfo *) findObjectByOid(oid, oprinfoindex, numOperators);
  }