Received: from makus.postgresql.org (makus.postgresql.org [98.129.198.125]) by mail.postgresql.org (Postfix) with ESMTP id 93610192715B for ; Tue, 26 Jun 2012 02:07:28 -0300 (ADT) Received: from 2605ds1-ynoe.3.fullrate.dk ([90.185.142.83] helo=shrek.krogh.cc) by makus.postgresql.org with esmtp (Exim 4.72) (envelope-from ) id 1SjNwN-0001K2-Ma for pgsql-performance@postgresql.org; Tue, 26 Jun 2012 05:03:53 +0000 Received: from localhost (localhost [127.0.0.1]) by shrek.krogh.cc (Postfix) with ESMTP id 59D8D1FD702; Tue, 26 Jun 2012 07:03:34 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at shrek.krogh.cc Received: from shrek.krogh.cc ([127.0.0.1]) by localhost (shrek.krogh.cc [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id r3Am73MmbMLf; Tue, 26 Jun 2012 07:03:28 +0200 (CEST) Received: from [90.185.142.91] (2605ds1-ynoe.4.fullrate.dk [90.185.142.91]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: jesper@krogh.cc) by shrek.krogh.cc (Postfix) with ESMTPSA id EF6F21FD6DF; Tue, 26 Jun 2012 07:03:27 +0200 (CEST) Message-ID: <4FE9429E.5070905@krogh.cc> Date: Tue, 26 Jun 2012 07:03:26 +0200 From: Jesper Krogh User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:12.0) Gecko/20120430 Thunderbird/12.0.1 MIME-Version: 1.0 To: Maxim Boguk CC: pgsql-performance@postgresql.org Subject: Re: Performance of a large array access by position (tested version 9.1.3) References: In-Reply-To: Content-Type: multipart/alternative; boundary="------------030000040907070103070700" X-Pg-Spam-Score: -1.9 (-) X-Archive-Number: 201206/139 X-Sequence-Number: 47165 This is a multi-part message in MIME format. --------------030000040907070103070700 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit On 22/06/12 09:02, Maxim Boguk wrote: > Hi all, > > May be I completely wrong but I always assumed that the access speed > to the array element in PostgreSQL should be close to constant time. > But in tests I found that access speed degrade as O(N) of array size. > > Test case (performed on large not busy server with 1GB work_mem to > ensure I working with memory only): > > WITH > t AS (SELECT ARRAY(SELECT * FROM generate_series(1,N)) AS _array) > SELECT count((SELECT _array[i] FROM t)) FROM generate_series(1,10000) > as g(i); > > Results for N between 1 and 10.000.000 (used locally connected psql > with \timing): > > N: Time: > 1 5.8ms > 10 5.8ms > 100 5.8ms > 1000 6.7ms > --until there all reasonable > 5k 21ms > 10k 34ms > 50k 177ms > 100k 321ms > 500k 4100ms > 1M 8100ms > 2M 22000ms > 5M 61000ms > 10M 220000ms = 22ms to sinlge array element access. > > > Is that behaviour is correct? > > PS: what I actually lookin for - constant fast access by position > tuplestore for use with recursive queries and/or pl/pgsql, but without > using C programming. Default column storage is to "compress it, and store in TOAST" with large values. This it what is causing the shift. Try to change the column storage of the column to EXTERNAL instead and rerun the test. ALTER TABLE ALTER COLUMN SET STORAGE EXTERNAL Default is EXTENDED which runs compression on it, which again makes it hard to position into without reading and decompressing everything. http://www.postgresql.org/docs/9.1/static/sql-altertable.html Let us know what you get.? Jesper --------------030000040907070103070700 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 22/06/12 09:02, Maxim Boguk wrote:

Hi all,

May be I completely wrong but I always assumed that the access speed to the array element in PostgreSQL should be close to constant time.
But in tests I found that access speed degrade as O(N) of array size.

Test case (performed on large not busy server with 1GB work_mem to ensure I working with memory only):

WITH
t AS (SELECT ARRAY(SELECT * FROM generate_series(1,N)) AS _array) SELECT count((SELECT _array[i] FROM t)) FROM generate_series(1,10000) as g(i);

Results for N between 1 and 10.000.000 (used locally connected psql with \timing):

N:=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 =C2=A0 =C2=A0 Time:
1=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 5.8ms
10=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 5.8ms
100=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 5.8ms
1000=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0 6.7ms
--until there all reasonable
5k=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 21ms
10k =C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0 34ms
50k=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0 177ms
100k=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 321ms
500k=C2=A0=C2=A0=C2= =A0=C2=A0 4100ms
1M=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 8100ms
2M=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 22000ms
5M=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0 61000ms
10M=C2=A0=C2=A0=C2= =A0 220000ms =3D 22ms to sinlge array element access.

Is that behaviour is correct?

PS: what I actually lookin for - constant fast access by position tuplestore for use with recursive queries and/or pl/pgsql, but without using C programming.

Default column storage is to "compress it, and store in TOAST" with large values.
This it what is causing the shift. Try to change the column storage of the column
to EXTERNAL instead and rerun the test.

ALTER TABLE <tablename> ALTER COLUMN <column name> SET STORAGE EXTERNAL

Default is EXTENDED which runs compression on it, which again makes it hard to
position into without reading and decompressing everything.

http://www.postgresql.org/docs/9.1/s= tatic/sql-altertable.html

Let us know what you get.?

Jesper

--------------030000040907070103070700--