pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Tarcizio Bini <tarcizioab@c3sl.ufpr.br>
To: pgsql-performance@postgresql.org
Subject: Query Optimization with Kruskal’s Algorithm
Date: Wed, 7 May 2008 13:28:04 -0300
Message-ID: <461a87490805070928h14226615hb87bf2574e26f330@mail.gmail.com> (raw)

Hello friends,

I'm working on optimizing queries using the Kruskal algorithm (
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4318118). I did several
tests in the database itself and saw interesting results.
I did 10 executions with each query using unchanged source of Postgres and
then adapted to the algorithm of Kruskal.
The query I used is composed of 12 tables and 11 joins.

Results Postgresql unchanged (ms): (\ timing)

170,690
168,214
182,832
166,172
174,466
167,143
167,287
172,891
170,452
165,665
average=> 170,5812 ms


Results of Postgresql with the Kruskal algorithm (ms): (\ timing)

520,590
13,533
8,410
5,162
5,543
4,999
9,871
4,984
5,010
8,883
average=> 58,6985 ms


As you can see the result, using the Kruskal algorithm, the first query
takes more time to return results. This does not occur when using the
original source of Postgres.
So how is the best method to conduct the tests? I take into consideration
the average of 10 executions or just the first one?
Do you think I must clean the cache after each query? (because the other (9)
executions may have information in memory).

regards, Tarcizio Bini.

Message-ID: <461a87490805070928h14226615hb87bf2574e26f330@mail.gmail.com>
Permalink:  ../461a87490805070928h14226615hb87bf2574e26f330@mail.gmail.com/
Also on:    postgresql.org/message-id/461a87490805070928h14226615hb87bf2574e26f330@mail.gmail.com

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-performance@postgresql.org
  Cc: tarcizioab@c3sl.ufpr.br
  Subject: Re: Query Optimization with Kruskal’s Algorithm
  In-Reply-To: <461a87490805070928h14226615hb87bf2574e26f330@mail.gmail.com>
  References: <461a87490805070928h14226615hb87bf2574e26f330@mail.gmail.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox