Message-ID: <4E5CA88C.50008@enterprisedb.com>
Date: Tue, 30 Aug 2011 12:08:28 +0300
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; fi-FI;
	rv:1.9.2.20) Gecko/20110820 Icedove/3.1.12
MIME-Version: 1.0
To: Alexander Korotkov <aekorotkov@gmail.com>
CC: Robert Haas <robertmhaas@gmail.com>,
	pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: WIP: Fast GiST index build
References: <BANLkTikgOQ1+r=A9b08szNTeEWsk-cNMMg@mail.gmail.com>
	<4E3FAB1D.1060105@enterprisedb.com>
	<CAPpHfdsovwbgs30TojJc_zDsc+0ghapm+-AALfP58UaHiYjr2A@mail.gmail.com>
	<CAPpHfdvi5WZKdRD+s60R+pdm8dLczRQ5_RYt4L8OA_bhorPjpg@mail.gmail.com>
	<4E42DFCE.3050904@enterprisedb.com>
	<CAPpHfdvhoYKUUCVaC-yFbDaE5j2QTa94cVgYuKnzX4xwWUjSTg@mail.gmail.com>
	<CA+TgmoZoON6aAE3NB9=GF9oAdF=Kkz21+MmoE5P_kA9aKN-OQA@mail.gmail.com>
	<CAPpHfdu4DusbHtMLE+csQJj61rMg_JtFOGSwrQVoOF5wPBkixQ@mail.gmail.com>
	<CAPpHfdtMe6yizpbT+Lsx0mWSW9thPV9KosSrUsSEMNRBHUWUPw@mail.gmail.com>
	<4E4AAC49.7070401@enterprisedb.com>
	<CAPpHfduTY5FqYdA_AB2zQ5MYyaeEqc5fRLLPgGBOymDXu16gFQ@mail.gmail.com>
	<4E4AC0B9.8070203@enterprisedb.com>
	<4E4AC1C3.4070003@enterprisedb.com>
	<CAPpHfdtAcs9UujarOUJdJR2-uPczBbaegooAa3vYwM6q5zVBBQ@mail.gmail.com>
	<CAPpHfdu80rXcNHZ9gen-qA4sZc0bQAKS9hEU_EP5GRqWN4F0Ng@mail.gmail.com>
	<4E569D9A.4020308@enterprisedb.com>
	<CAPpHfdsoHciGGearBYQv8+J5L=Eni3mzJ0qjHpq3jb+BjzzYGg@mail.gmail.com>
In-Reply-To: 
 <CAPpHfdsoHciGGearBYQv8+J5L=Eni3mzJ0qjHpq3jb+BjzzYGg@mail.gmail.com>
Content-Type: multipart/mixed; boundary="------------010307000402090803070608"

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

On 26.08.2011 17:18, Alexander Korotkov wrote:
> On Thu, Aug 25, 2011 at 11:08 PM, Heikki Linnakangas<
> heikki.linnakangas@enterprisedb.com>  wrote:
>
>> Could you share the test scripts, patches and data sets etc. needed to
>> reproduce the tests you've been running? I'd like to try them out on a test
>> server.
>>
>
> 1) I've updated links to the datasets on the wiki page.
> 2) Script for index quality testing fastbuild_test.php is in the attachment.
> In order to run it you need PHP with pdo and pdo_pgsql modules. Also
> plantuner moduler is required (it is used to force planer to use specific
> index). After running that script following query returns relative score of
> index quality:
>
> select indexname, avg(count::real/(select count from test_result a2 where
> a2.indexname = 'usnoa2_idx3' and a2.predicate = a1.predicate and
> a2.tablename = a1.tablename)::real) from test_result a1 where a1.tablename =
> 'usnoa2' group by indexname;
>
> where 'usnoa2' - table name, 'usnoa2_idx3' - name of index which quality was
> assumed to be 1.
> 3) Patch which makes plantuner work with HEAD is also in attachment.
> 4) Patch with my split algorithm implementation is attached. Now it's form
> is appropriate only for testing purposes.
> 5) For indexes creation I use simple script which is attached as
> 'indexes.sql'. Also, similar script with different index names I'm running
> with my split patch.
>
> Feel free to ask questions about all this stuff.

Thanks. Meanwhile, I hacked together my own set of test scripts, and let 
them run over the weekend. I'm still running tests with ordered data, 
but here are some preliminary results:

            testname           |   nrows   |    duration     | accesses
-----------------------------+-----------+-----------------+----------
  points unordered auto       | 250000000 | 08:08:39.174956 |  3757848
  points unordered buffered   | 250000000 | 09:29:16.47012  |  4049832
  points unordered unbuffered | 250000000 | 03:48:10.999861 |  4564986

As you can see, the results are very disappointing :-(. The buffered 
builds take a lot *longer* than unbuffered ones. I was expecting the 
buffering to be very helpful at least in these unordered tests. On the 
positive side, the buffering made index quality somewhat better 
(accesses column, smaller is better), but that's not what we're aiming at.

What's going on here? This data set was large enough to not fit in RAM, 
the table was about 8.5 GB in size (and I think the index is even larger 
than that), and the box has 4GB of RAM. Does the buffering only help 
with even larger indexes that exceed the cache size even more?


Test methodology
----------------

These tests consist of creating a gist index using the point datatype.

      Table "public.points"
   Column |  Type   | Modifiers
--------+---------+-----------
   x      | integer |
   y      | integer |

CREATE INDEX testindex ON points_ordered USING gist (point(x,y)) WITH 
(buffering = 'on');

The points in the table are uniformly distributed. In the 'unordered' 
tests, they are in random order. The ordered tests use the exact same 
data, but sorted by x, y coordinates.

The 'accesses' column measures the quality of the produced index. 
Smaller is better. It is calculated by performing a million queries on 
the table, selecting points within a small square at evenly spaced 
locations. Like:

(SELECT COUNT(*) FROM points WHERE point(x,y) <@ box(point(xx-20, 
yy-20), point(xx+20, yy+20)));

The number of index pages touched by those queries are count from 
pg_statio_user_indexes, and that number is reported in the 'accesses' 
column.

I've attached the whole script used. Pass the number of rows to use in 
the test as argument, and the script does the rest.

-- 
    Heikki Linnakangas
    EnterpriseDB   http://www.enterprisedb.com


--------------010307000402090803070608
Content-Type: application/x-sh;
 name="rungisttests.sh"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="rungisttests.sh"

#!/bin/bash

NROWS=$1

echo "BEGIN;"
echo "DROP TABLE IF EXISTS points, points_ordered;"
echo "CREATE TABLE points (x int4, y int4);"

cat > /tmp/creategistdata.c <<EOF
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
  int nrows;
  int i;

  if (argc != 2)
    exit(1);

  nrows = atoi(argv[1]);
  for (i = 0; i < nrows; i++)
    printf("%d\t%d\n", random() % 100000, random() % 100000);
}
EOF
gcc /tmp/creategistdata.c -o /tmp/creategistdata

echo "COPY points FROM stdin;"
/tmp/creategistdata $NROWS
echo "\."

echo "CREATE TABLE points_ordered AS SELECT * FROM points ORDER BY x, y;";

echo "COMMIT;"

echo "CREATE TABLE results (testname text, nrows int4, begintime timestamp, endtime timestamp, blks_accessed int4, totalrowsmatched int4);"

# Run tests

function measureindexquality {
cat <<EOF
  set enable_seqscan=off;
  SELECT pg_stat_reset_single_table_counters('testindex'::regclass);
  DO \$\$
    declare
      totalrows int4 := 0;
      xx int4;
      yy int4;
      ordered bool;
    begin
      -- Figure out if this test was on the ordered data set
      ordered := ((SELECT indrelid::regclass::text FROM pg_index where indexrelid='testindex'::regclass) = 'points_ordered');

      FOR xx IN 1..100000 BY 1000 LOOP
        FOR yy IN 1..100000 BY 1000 LOOP
          IF ordered THEN
            totalrows = totalrows + (SELECT COUNT(*) FROM points_ordered WHERE point(x,y) <@ box(point(xx-20, yy-20), point(xx+20, yy+20)));
          ELSE
            totalrows = totalrows + (SELECT COUNT(*) FROM points WHERE point(x,y) <@ box(point(xx-20, yy-20), point(xx+20, yy+20)));
          END IF;
        END LOOP;
      END LOOP;
      UPDATE results SET totalrowsmatched = totalrows WHERE totalrowsmatched IS NULL;
    end;
  \$\$;
  SELECT pg_sleep(1); -- Sleep a bit to make sure we get fresh results from pg_statio
  UPDATE results SET blks_accessed = 
        (SELECT idx_blks_hit + idx_blks_read FROM pg_statio_user_indexes WHERE indexrelname='testindex')
  WHERE blks_accessed IS NULL;
EOF
}

function runtest {
  ITERATIONS=1
  TESTNAME=$1
  TESTSQL=$2
  for ((n=1; n <= $ITERATIONS; n++))
  do
    echo "CHECKPOINT;"
    echo "INSERT INTO results (testname, nrows, begintime) VALUES ('$TESTNAME', $NROWS, now());"
    echo $TESTSQL
    echo "UPDATE results SET endtime = now() WHERE endtime IS NULL;"
    measureindexquality
    echo "DROP INDEX testindex;"
  done;
}

runtest "points ordered buffered" "CREATE INDEX testindex ON points_ordered USING gist (point(x,y)) WITH (buffering = 'on');"
runtest "points unordered buffered" "CREATE INDEX testindex ON points USING gist (point(x,y)) WITH (buffering = 'on');"

runtest "points ordered auto" "CREATE INDEX testindex ON points_ordered USING gist (point(x,y)) WITH (buffering = 'auto');"
runtest "points unordered auto" "CREATE INDEX testindex ON points USING gist (point(x,y)) WITH (buffering = 'auto');"

runtest "points ordered unbuffered" "CREATE INDEX testindex ON points_ordered USING gist (point(x,y)) WITH (buffering = 'off');"
runtest "points unordered unbuffered" "CREATE INDEX testindex ON points USING gist (point(x,y)) WITH (buffering = 'off');"


cat <<EOF
SELECT testname, nrows,
       MIN(endtime - begintime) AS mintime,
       AVG(endtime - begintime) AS avgtime,
       MAX(endtime - begintime) AS maxtime,
       MIN(blks_accessed) AS minaccesses,
       MAX(blks_accessed) AS maxaccesses,
       MIN(totalrowsmatched) AS minmatches,
       MAX(totalrowsmatched) AS maxmatches
FROM results GROUP BY testname, nrows ORDER BY nrows, testname;
EOF


--------------010307000402090803070608--