DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=message-id:date:from:to:subject:cc:in-reply-to:mime-version
	:content-type:content-transfer-encoding:content-disposition
	:references;
	b=mS4Gbzuyo0XCIctNOJItA44FxCFrwdgTNK5BWT6d3iWkq0t7AF3fuxa3XSL6BlyH7o
	gvR+NHgOXsTv+Dg1DDDOdKHHiq8VlEfYrnObLjbOF+k4YpsTlrTVnJBpuxpVQEG0KA6A
	bcnaAWeBYqADsf0gX0C6aVhqMDzTMTk57e3AI=
Message-ID: <603c8f070812092025k6325e0fcud001b205a507a634@mail.gmail.com>
Date: Tue, 9 Dec 2008 23:25:01 -0500
From: "Robert Haas" <robertmhaas@gmail.com>
To: "Gregory Stark" <stark@enterprisedb.com>
Subject: Re: benchmarking the query planner
Cc: "Greg Stark" <greg.stark@enterprisedb.com>,
	"Kevin Grittner" <Kevin.Grittner@wicourts.gov>,
	"jd@commandprompt.com" <jd@commandprompt.com>,
	"Josh Berkus" <josh@agliodbs.com>,
	"Greg Smith" <gsmith@gregsmith.com>, pgsql-hackers@postgresql.org
In-Reply-To: <87ljuq4rmk.fsf@oxford.xeocode.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <603c8f070812061019r5aca3aajeaa5493b11c5feff@mail.gmail.com>
	<9897C4AF-6D47-4F44-AD3D-F5A82AC392DB@enterprisedb.com>
	<87ljuq4rmk.fsf@oxford.xeocode.com>

On Mon, Dec 8, 2008 at 10:24 AM, Gregory Stark <stark@enterprisedb.com> wrote:
> I tried a different query, trying to get quadratic growth and again failed. It

The profiling results I sent the other day show an exactly-linear
increase in the number of times eqjoinsel invokes FunctionCall2.
Reading through the the eqjoinsel_inner loop in selfuncs.c beginning
around line 2042, I think what is happening is this: since the two
tables are really the same table, nvalues1 and nvalues2 are the same
array, and therefore contain the same elements in the same order.  As
a result, for each i, we skip over the first i - 1 entries in
nvalues2, which have already been matched, and then compare element i
of nvalues1 to element i of nvalues2 and mark them both as matched.

Although this is technically an O(n^2) algorithm, the constant is very
low, because this code is Really Fast:

if (hasmatch[j])
    continue;

To get observable quadratic behavior, I think you might need to
construct two MCV arrays where all the values are the same, but the
arrays are not in the same order.  I believe they are sorted by
frequency, so it might be sufficient to arrange things so that the
N'th most common value in one table is the (statistics_target  + 1 -
N)'th most common value in the other.  It might also help to use a
function with a real slow comparison function (perhaps one
intentionally constructed to be slow).

...Robert