X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org
Received: from localhost (av.hub.org [200.46.204.144])
	by postgresql.org (Postfix) with ESMTP id 291249DC842
	for <pgsql-performance-postgresql.org@localhost.postgresql.org>;
	Fri, 20 Jan 2006 17:50:31 -0400 (AST)
Received: from postgresql.org ([200.46.204.71])
	by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024)
	with ESMTP id 87988-01
	for <pgsql-performance-postgresql.org@localhost.postgresql.org>;
	Fri, 20 Jan 2006 17:50:29 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130])
	by postgresql.org (Postfix) with ESMTP id 8DF2A9DCB92
	for <pgsql-performance@postgreSQL.org>;
	Fri, 20 Jan 2006 17:50:20 -0400 (AST)
Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1])
	by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id k0KLoHdN027265;
	Fri, 20 Jan 2006 16:50:17 -0500 (EST)
To: Martijn van Oosterhout <kleptog@svana.org>
cc: Stephan Vollmer <svollmer@gmx.de>, pgsql-performance@postgreSQL.org
Subject: Re: [GENERAL] Creation of tsearch2 index is very slow 
In-reply-to: <20060120213754.GG31908@svana.org> 
References: <43D0ED57.1020608@gmx.de> <17454.1137771321@sss.pgh.pa.us>
	<20060120170452.GC31908@svana.org> <26153.1137784469@sss.pgh.pa.us>
	<20060120201036.GE31908@svana.org> <26583.1137788505@sss.pgh.pa.us>
	<20060120205132.GF31908@svana.org> <26958.1137791955@sss.pgh.pa.us>
	<20060120213754.GG31908@svana.org>
Comments: In-reply-to Martijn van Oosterhout <kleptog@svana.org>
	message dated "Fri, 20 Jan 2006 22:37:54 +0100"
Date: Fri, 20 Jan 2006 16:50:17 -0500
Message-ID: <27264.1137793817@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>
X-Virus-Scanned: by amavisd-new at hub.org
X-Spam-Status: No, score=0.094 required=5 tests=[AWL=0.094]
X-Spam-Score: 0.094
X-Spam-Level: 
X-Archive-Number: 200601/366
X-Sequence-Number: 16844

Martijn van Oosterhout <kleptog@svana.org> writes:
> Given that all it's doing is counting bits, a simple fix would be to
> loop over bytes, use XOR and count ones. For extreme speedup create a
> lookup table with 256 entries to give you the answer straight away...

Yeah, I just finished doing that and got about a 20x overall speedup
(30-some seconds to build the index instead of 10 minutes).  However,
hemdistsign is *still* 70% of the runtime after doing that.  The problem
seems to be that gtsvector_picksplit is calling it an inordinate number
of times:

                0.53   30.02    1649/1649        FunctionCall2 <cycle 2> [19]
[20]    52.4    0.53   30.02    1649         gtsvector_picksplit [20]
               29.74    0.00 23519673/33035195     hemdistsign [18]
                0.14    0.00 22985469/22985469     hemdistcache [50]
                0.12    0.00  268480/10030581     makesign [25]
                0.02    0.00  270400/270400      fillcache [85]
                0.00    0.00    9894/4077032     AllocSetAlloc [34]
                0.00    0.00    9894/2787477     MemoryContextAlloc [69]

(hemdistcache calls hemdistsign --- I think gprof is doing something
funny with tail-calls here, and showing hemdistsign as directly called
from gtsvector_picksplit when control really arrives through hemdistcache.)

The bulk of the problem is clearly in this loop, which performs O(N^2)
comparisons to find the two entries that are furthest apart in hemdist
terms:

    for (k = FirstOffsetNumber; k < maxoff; k = OffsetNumberNext(k))
    {
        for (j = OffsetNumberNext(k); j <= maxoff; j = OffsetNumberNext(j))
        {
            if (k == FirstOffsetNumber)
                fillcache(&cache[j], GETENTRY(entryvec, j));

            size_waste = hemdistcache(&(cache[j]), &(cache[k]));
            if (size_waste > waste)
            {
                waste = size_waste;
                seed_1 = k;
                seed_2 = j;
            }
        }
    }

I wonder if there is a way to improve on that.

			regards, tom lane