Received: from malur.postgresql.org ([217.196.149.56])
 by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from
 <pgsql-performance-owner+M52011=pgsql-performance-ar@postgresql.org>)
 id 1XC4Nd-0007EJ-68
 for pgsql-performance@arkaria.postgresql.org; Tue, 29 Jul 2014 10:11:37 +0000
Received: from localhost ([127.0.0.1] helo=postgresql.org)
 by malur.postgresql.org with smtp (Exim 4.80) (envelope-from
 <pgsql-performance-owner+M52011=pgsql-performance-ar@postgresql.org>)
 id 1XC4Nc-000293-Lm
 for pgsql-performance@arkaria.postgresql.org; Tue, 29 Jul 2014 10:11:36 +0000
Received: from makus.postgresql.org ([2001:4800:1501:1::229])
 by malur.postgresql.org with esmtps (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256)
 (Exim 4.80) (envelope-from <nadvornik.ji@gmail.com>)
 id 1XC4Nb-00028v-Gz
 for pgsql-performance@postgresql.org; Tue, 29 Jul 2014 10:11:35 +0000
Received: from mail-wi0-x232.google.com ([2a00:1450:400c:c05::232])
 by makus.postgresql.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.80) (envelope-from <nadvornik.ji@gmail.com>)
 id 1XC4NX-0007sp-TW
 for pgsql-performance@postgresql.org; Tue, 29 Jul 2014 10:11:33 +0000
Received: by mail-wi0-f178.google.com with SMTP id hi2so679278wib.17
 for <pgsql-performance@postgresql.org>; Tue, 29 Jul 2014 03:11:29 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
 h=from:to:cc:references:in-reply-to:subject:date:message-id
 :mime-version:content-type:content-transfer-encoding:thread-index
 :content-language;
 bh=tA2fzd7/YotTSdO6N3ZyeoPso1qbI5RKU1BllhBK36Y=;
 b=QY89Nm+5fh/VGNZ3mo8urCiTWt3ziyMeSD/OyfbR/ghAwGrkXTCi18ixZKNhvYGqUt
 mbJgnFhDzMbSyHqMbbsy2hGLzrwtNHii/EozJ5ctcNDkBAfsBKJR+Bbj2HlLOzv318g7
 ZhMvqjI468wDOYjkuwyT7Mfb4uYFti9msv8mDaWtKZEUzzEYK1m37XmORC3Doyb2bhna
 hmAsTM+6nNOinumqxnaWo4cvg51WHhQ2VzgK33veSvpPDbeHm4JkkLvfbIG1yeec3Tqh
 YYsilX1r7QYKpl1htskMi7cgSXFrcxnlOk0GHjHCso/+ONqNhTykMsCXj2NsJWYZhp8s
 lIyQ==
X-Received: by 10.180.106.138 with SMTP id gu10mr40244410wib.21.1406628688440;
 Tue, 29 Jul 2014 03:11:28 -0700 (PDT)
Received: from ssvnadvornik (37-48-46-236.tmcz.cz. [37.48.46.236])
 by mx.google.com with ESMTPSA id cx5sm56401967wjb.8.2014.07.29.03.11.26
 for <multiple recipients>
 (version=TLSv1 cipher=ECDHE-RSA-AES128-SHA bits=128/128);
 Tue, 29 Jul 2014 03:11:27 -0700 (PDT)
From: =?UTF-8?B?SmnFmcOtIE7DoWR2b3Juw61r?= <nadvornik.ji@gmail.com>
To: <obartunov@gmail.com>
Cc: <pgsql-performance@postgresql.org>,
 "'Sergey Karpov'" <karpov.sv@gmail.com>
References: <01d201cfa8be$dd746880$985d3980$@gmail.com>
 <CAF4Au4w7E2N=WL4Fw-8uObhWCA4YykFxr5BT7dvDcjP=9iT-3Q@mail.gmail.com>
In-Reply-To: 
 <CAF4Au4w7E2N=WL4Fw-8uObhWCA4YykFxr5BT7dvDcjP=9iT-3Q@mail.gmail.com>
Subject: Re: Cursor + upsert (astronomical data)
Date: Tue, 29 Jul 2014 12:11:23 +0200
Message-ID: <004e01cfab15$765c7f30$63157d90$@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Mailer: Microsoft Outlook 15.0
Thread-Index: AQHSB3FUPUcQjIVcmXO3GnoQtcDS6gF+S2a+m6YjvfA=
Content-Language: cs
X-Pg-Spam-Score: -2.0 (--)
List-Archive: <http://archives.postgresql.org/pgsql-performance>
List-Help: <mailto:majordomo@postgresql.org?body=help>
List-ID: <pgsql-performance.postgresql.org>
List-Owner: <mailto:pgsql-performance-owner@postgresql.org>
List-Post: <mailto:pgsql-performance@postgresql.org>
List-Subscribe: <mailto:majordomo@postgresql.org?body=sub%20pgsql-performance>
List-Unsubscribe: 
 <mailto:majordomo@postgresql.org?body=unsub%20pgsql-performance>
X-Mailing-List: pgsql-performance
Precedence: bulk
Sender: pgsql-performance-owner@postgresql.org

Hi Oleg, Sergey,

The problem would be crossmatch if I would have a catalog to crossmatch wit=
h. But I am actually trying to build this catalog.

The crossmatching can be actually used to solve that problem, when I crossm=
atch the observations with themselves on q3c_join with 1 arcsec. But as I s=
aid, that crashes on the fact that we have ~thousand images overlapping. Th=
is is the factor of quadratic complexity of self-crossmatching the table (s=
elf-joining is the same thing if I understand the crossmatching term correc=
tly).=20

I actually managed to write a silver-bullet query, which did the self-joini=
ng in the most nested subquery and then worked with the results via analyti=
c methods like count and rank, which found the best candidate of these self=
-joined tuples to compute the average coordination on which I grouped them =
and got my identifier. I can send you the code if you are interested.

It worked like charm for smaller data - fast and small error (<1%). But sel=
f-joining 3e8 rows when in the highest density areas you multiply each obse=
rvation by the factor of 1000^2, the temporary results run out of disk spac=
e (didn=E2=80=99t have more than 1.5 TB). So I managed to solve this by div=
iding the dataset to smaller parts (cca 25000 for one part). When ran in pa=
rallel on 8 cores, it used them quite good (cca 6 cores fully loaded at one=
 time) and the 24 GB memory had load at ~75%.=20

If the time was linear compared to processed results, the time to process t=
he 3e8 rows was ~9 days. However I tried this only once (for obvious reason=
s) and the RDMS crashed after cca 4 days of this heavy load. Don't know whe=
ther I was stretching Postgres over it's limits here so I tried to find an =
algorithm with linear complexity at that point. That's how I got into the p=
oint where I'm right now.

P.S.: I consulted this with people from catalina and they are doing this th=
ing by Friends-of-Friends algorithm - but they don't have most of the stars=
 in the high density areas like SMC as we do. That's why I didn't decide to=
 not use it as I think it would crash horribly when you have the distances =
comparable with the threshold of your astrometry.

Thank you very much for your invested effort.

Kind Regards,

Jiri Nadvornik

-----Original Message-----
From: Oleg Bartunov [mailto:obartunov@gmail.com]=20
Sent: Sunday, July 27, 2014 6:57 PM
To: Ji=C5=99=C3=AD N=C3=A1dvorn=C3=ADk
Cc: pgsql-performance@postgresql.org; Sergey Karpov
Subject: Re: [PERFORM] Cursor + upsert (astronomical data)

Jiri,

as I understand your problem is called crossmatch ?  I attach pdf of our wo=
rk in progress, where we compared several spatial indexing techniques, incl=
uding postgis, q3c and new pgsphere.  Sergey Karpov made these benchmarks.

New pgsphere you may find here
https://github.com/akorotkov/pgsphere

Oleg

On Sat, Jul 26, 2014 at 1:46 PM, Ji=C5=99=C3=AD N=C3=A1dvorn=C3=ADk <nadvor=
nik.ji@gmail.com> wrote:
> Hello guys.
>
>
>
> My issue kind of hits multiple topics, but the main question is about=20
> performance. I think you need to understand the background a little=20
> bit to be able to help me. So I will firstly define the problem and my=20
> solutions to it and place the questions for you to the end of this messag=
e.
>
>
>
> Problem:
>
> I have a table of observations of objects on the sky. The most=20
> important columns are the coordinates (x,y). All other columns in=20
> there are just additional information about the observation. The=20
> problem is that when I take an image of the same object on the sky=20
> twice, the coordinates x,y won=E2=80=99t be the same, they will be only c=
lose=20
> to each other. My task is to generate a common identifier to all of=20
> the observations of the same object and assign the observations to it=20
> (N:1 relation). The criterium is that all of the observations which=20
> are within 1 arcsec of this identifier are considered as the same=20
> object. I keep the identifiers in a separate table (objcat) and have a fo=
reign key in the observations table.
>
> The reason why I solve the performance issues here is that the table=20
> of observations has atm cca 3e8 rows after 1.5 year of gathering the=20
> data. The number growth is linear.
>
>
>
> Technical background:
>
> I=E2=80=99m trying to keep the whole algoritm in DB if possible because I=
 have=20
> a good PostgreSQL plugin Q3C for indexing the coordinates of the=20
> objects on the sky=20
> (https://code.google.com/p/q3c/source/browse/README.q3c). It also has=20
> quite a few stored procedures to look in that table for near neighbors=20
> which is what I=E2=80=99m doing. The function q3c_join(x1, x2, y1, y2, ra=
dius)=20
> returns true if the object y is within radius of the object x. It=20
> simply generates a list of index bitmap or queries with the operators=20
> <=3D, >=3D which define the position on sky. Asking for the nearest neigh=
bors are then only index scans.
>
>
>
> Solution:
>
> After lot of experimentation with clustering the objects and trying to=20
> process them all together in one =E2=80=9Csilver-bullet=E2=80=9D SQL quer=
y I decided=20
> to use some more simple approach. The main problem with the =E2=80=9Cproc=
ess=20
> all at once approach=E2=80=9D is that the finding neighbours for each=20
> observation is in definition quadratic and for 3e8 rows just runs out=20
> of disk space (~TBs of memory for the temporary results).
>
> The simplest approach I could think of is that I process each row of=20
> the 3e8 rows sequentially and ask:
>
> Do I have an identifier in the radius of 1 arcsec?
>
> No: Generate one and assign me to it.
>
> Yes: Update it and assigne me to it. The update is done as weighted=20
> average =E2=80=93 I keep the number of how many observations the identifi=
er=20
> has been computed. The result is that the identifier will have average=20
> coordinates of all the observations it identifies =E2=80=93 it will be th=
e center.
>
>
>
> So here I come with my procedure. It has 3 params. The first two are=20
> range of oids to list in the table. Used for scaling and=20
> parallelization of the algorithm. The third is the radius in which to sea=
rch for the neighbours.
>
>
>
> DROP TYPE IF EXISTS coords;
>
> CREATE TYPE coords AS (
>
>                 raj2000 double precision,
>
>                 dej2000 double precision
>
>                 );
>
>
>
>
>
> DROP FUNCTION IF EXISTS build_catalog(int,int,double precision);
>
> CREATE OR REPLACE FUNCTION build_catalog (fromOID int, toOID int,=20
> radius double precision)
>
>                 RETURNS VOID AS $$
>
> DECLARE
>
>                 cur1 CURSOR FOR
>
>                                SELECT
>
>                                                raj2000, dej2000
>
>                                FROM
>
>                                                \schema.observation AS=20
> obs
>
>                                WHERE
>
>                                                obs.oid >=3D fromOID
>
>                                AND
>
>                                                obs.oid < toOID;
>
>                 curr_raj2000 double precision;
>
>                 curr_dej2000 double precision;
>
>                 curr_coords_cat coords;
>
>                 cnt int;
>
>
>
> BEGIN
>
> /*SELECT current_setting('transaction_isolation') into tmp;
>
> raise notice 'Isolation level %', tmp;*/
>
> OPEN cur1;
>
> cnt:=3D0;
>
> LOCK TABLE \schema.objcat IN SHARE ROW EXCLUSIVE MODE;
>
> LOOP
>
>                 FETCH cur1 INTO curr_raj2000, curr_dej2000;
>
>                                EXIT WHEN NOT found;
>
>
>
>                 WITH
>
>                                upsert
>
>                 AS
>
>                                (UPDATE
>
>                                                \schema.objcat
>
>                                SET
>
>                                                ipix_cat=3Dq3c_ang2ipix(
>
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
> (raj2000 * weight + curr_raj2000) / (weight + 1),
>
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
> (dej2000 * weight + curr_dej2000) / (weight + 1)
>
>                                                ),
>
>                                                raj2000 =3D (raj2000 *=20
> weight +
> curr_raj2000) / (weight + 1),
>
>                                                dej2000 =3D (dej2000 *=20
> weight +
> curr_dej2000) / (weight + 1),
>
>                                                weight=3Dweight+1
>
>                                WHERE
>
>                                                q3c_join(curr_raj2000,=20
> curr_dej2000,
>
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
> raj2000, dej2000,
>
>                                                                radius)
>
>                                RETURNING *),
>
>                 ins AS
>
>                 (INSERT INTO
>
>                                                \schema.objcat
>
>                                                (ipix_cat, raj2000,=20
> dej2000,
> weight)
>
>                                SELECT
>
>=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=
=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20=20
> (q3c_ang2ipix(curr_raj2000, curr_dej2000)),
>
>                                                curr_raj2000,
>
>                                                curr_dej2000,
>
>                                                1
>
>                 WHERE NOT EXISTS
>
>                                (SELECT * FROM upsert)
>
>                 RETURNING *)
>
>                 UPDATE
>
>                                \schema.observation
>
>                 SET
>
>                                id_cat =3D (SELECT DISTINCT
>
>                                                                id_cat
>
>                                                FROM
>
>                                                                upsert
>
>                                                UNION
>
>                                                SELECT
>
>                                                                id_cat
>
>                                                FROM
>
>                                                                ins
>
>                                                WHERE id_cat IS NOT=20
> NULL
>
>                                                LIMIT 1)
>
>                 WHERE CURRENT OF cur1;
>
>                 cnt:=3Dcnt+1;
>
>
>
>                 IF ((cnt % 100000 ) =3D 0) THEN
>
>                                RAISE NOTICE 'Processed % entries',=20
> cnt;
>
>                 END IF;
>
>
>
> END LOOP;
>
> CLOSE cur1;
>
> END;
>
> $$ LANGUAGE plpgsql;
>
>
>
> Results: When I run the query only once (1 client thread), it runs cca=20
> 1 mil rows per hour. Which is days for the whole dataset. When I run=20
> it in parallel with that lock to ensure pessimistic synchronization,=20
> it runs sequentially too J the other threads just waiting. When I=20
> delete that lock and hope to solve the resulting conflicts later, the=20
> ssd disk serves up to 4 threads relatively effectively =E2=80=93 which ca=
n=20
> divide my days of time by 4 =E2=80=93 still inacceptable.
>
>
>
> The reason is quite clear here =E2=80=93 I=E2=80=99m trying to write some=
thing in one=20
> cycle of the script to a table =E2=80=93 then in the following cycle I ne=
ed to=20
> read that information.
>
>
>
> Questions for you:
>
> 1.       The first question is if you can think of a better way how to do
> this and maybe if SQL is even capable of doing such thing =E2=80=93 or do=
 I=20
> have to do it in C? Would rewriting the SQL function to C help?
>
> 2.       Could I somehow bend the commiting during the algorithm for my
> thing? Ensure that inside one cycle, the whole part of the identifiers=20
> table would be kept in memory for faster lookups?
>
> 3.       Why is this so slow? J It is comparable to the quadratic algorit=
hm
> in the terms of speed =E2=80=93 only does not use any memory.
>
>
>
> I tried to sum this up the best I could =E2=80=93 for more information pl=
ease=20
> don=E2=80=99t hesitate to contact me.
>
>
>
> Thank you very much for even reading this far.
>
>
>
> Best Regards,
>
>
>
> Jiri Nadvornik
>
>
>
>



--=20
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance