Re: [HACKERS] SDP query optimizer

[Adriano Lange]

Hi,

On 22-03-2013 21:22, Josh Berkus wrote:

Woah!  Way cool.

As a warning, we're in the closing throes of version 9.3 right now, so
if you code/ideas doesn't get the attention it deserves, that's why.


Ok. No problem. :-)


There is an incomplete project from a few years back to make the
non-exhaustive query planner pluggable so that we could use different
algorithms.  Unfortunately, it was never finished and merged with the
core code.  Your planner is yet another reason it would be great to
complete this.


Yes. I looked at the Julius and Tomas' project in pgFoundry [1] some 
years ago, but it was inactive. Therefore, I decided to start a new one.


[1] - http://pgfoundry.org/projects/optimizer/

Anyway, good work for all of you.

--
Adriano Lange



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

Re: [HACKERS] SDP query optimizer

[Adriano Lange]

On 23-03-2013 10:15, Andres Freund wrote:

I just want to mention that unless you skew the statistics for the individual
tables from their empty/default state this mostly measures a pretty degenerate
case where optima are very rare and not very differentiated. Thats a useful
thing to test, but not to have as the target to optimize for.
So it might be interesting to run that thing with some table
stats/contents stats set up.



Yes, the search space obtained from this experiment may be very simpler 
than a real case. Beyond this experiment, I can construct classical 
queries used to evaluate this kind of algorithm, as stars, cliques, 
chains and cycles. Beyond these queries I have no idea how can I further 
test it.


Regards,

Adriano Lange


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

Re: [HACKERS] TwoPO: experimental join order algorithm

[Adriano Lange]

On Fri, Jul 30, 2010 at 7:02 AM, Jan Urbański wulc...@wulczer.org wrote:
 On 24/07/10 15:20, Adriano Lange wrote:

 Hi,

 Hi!


 I'd like to release the last version of my experimental join order
 algorithm (TwoPO - Two Phase Optimization [1]):

 http://git.c3sl.ufpr.br/gitweb?p=lbd/ljqo.git;a=summary

 This algorithm is not production-ready, but an experimental set of
 ideas, which need to be refined and evaluated. As the join order
 optimization is a hard problem, the evaluation of a search strategy is
 also a hard task. Therefore, I think the most important TODO item
 related to replacement of GEQO algorithm is to define a set of
 evaluation criteria considered as relevant.

 Good to hear from you --  I don't know if you are aware about a simulated
 annealing join search module that I'm working on. When I first started, I
 planned to base is on the patch that you sent to -hackers some time ago (and
 actually, if you look at the repo for my module, twopo.c is still in there)
 but ended up doing it from scratch. However, reading your code was a big
 help in the beginning.

 I gave a talk at this year's PGCon
 (http://www.pgcon.org/2010/schedule/events/211.en.html) and you will find
 your name in the acknowledgments section of the presentation :)

 I'll make sure to read your new code and compare the approaches, my results
 so far are not perfect, but also not very pessimistic. I think there is
 actually a chance to replace GEQO with SA in the future, or at least to ship
 more join search modules with the standard distribution and gather field
 reports.

 Cheers,
 Jan


Hi Jan,

It's good to know that you are also interested about this issue!

I saw the slides of your presentation at PGCon and I noted excellent
ideas. I think that as more as implementations and ideas will be
raised, more easily will be to converge them in a reliable and
competitive solution.

The current version of TwoPO is suitable for the classic
select-project-join problem. Therefore, there are some issues not
covered yet, as I have observed in a test schema presented by Andres
Freund (http://archives.postgresql.org/pgsql-hackers/2009-07/msg00546.php).
I think we will need to build a robust benchmark to deal with it.

At this moment I'm really busy with a homework, but I hope to
dedicate more time to this issue next month.

--
Adriano Lange

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

Re: [HACKERS] TwoPO: experimental join order algorithm

[Adriano Lange]

Em 25-07-2010 17:44, Robert Haas escreveu:
 On Sat, Jul 24, 2010 at 9:20 AM, Adriano Lange alange0...@gmail.com wrote:
 I'd like to release the last version of my experimental join order
 algorithm (TwoPO - Two Phase Optimization [1]):

 http://git.c3sl.ufpr.br/gitweb?p=lbd/ljqo.git;a=summary

 This algorithm is not production-ready, but an experimental set of
 ideas, which need to be refined and evaluated. As the join order
 optimization is a hard problem, the evaluation of a search strategy is
 also a hard task. Therefore, I think the most important TODO item
 related to replacement of GEQO algorithm is to define a set of
 evaluation criteria considered as relevant.
 
 As you may know, we're in the middle of a CommitFest right now; I'd
 suggest adding this patch to the next one.
 
 https://commitfest.postgresql.org/action/commitfest_view/open
 
 Someone might have time to look at it sooner, but at least if you add
 it here we'll not lose track of it.
 

Yes, I know. This is only a notice, not a patch.
As I said, this algorithm is experimental, which do not match with the
CommitFest life cycle.

--
Adriano Lange

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

Re: [HACKERS] TwoPO: experimental join order algorithm

[Adriano Lange]

Em 25-07-2010 19:17, Robert Haas escreveu:
 On Sun, Jul 25, 2010 at 6:45 PM, Adriano Lange alange0...@gmail.com wrote:
 Yes, I know. This is only a notice, not a patch.
 As I said, this algorithm is experimental, which do not match with the
 CommitFest life cycle.
 
 It matches just fine - you just want a review and some good feedback,
 rather than an actual commit.  It's just... I don't have time to do
 that tonight.  :-)
 

:-)
Just a notice of an experimental algorithm for now.
I think there are no clear criteria for review this kind of algorithm yet.

--
Adriano Lange

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

[HACKERS] TwoPO: experimental join order algorithm

[Adriano Lange]

Hi,

I'd like to release the last version of my experimental join order
algorithm (TwoPO - Two Phase Optimization [1]):

http://git.c3sl.ufpr.br/gitweb?p=lbd/ljqo.git;a=summary

This algorithm is not production-ready, but an experimental set of
ideas, which need to be refined and evaluated. As the join order
optimization is a hard problem, the evaluation of a search strategy is
also a hard task. Therefore, I think the most important TODO item
related to replacement of GEQO algorithm is to define a set of
evaluation criteria considered as relevant.

TwoPO is encapsulated in a plug-in called LJQO (Large Join Query
Optimization [2]). This plug-in has two main GUC variables:

ljqo_threshold = N (like geqo_threshold)
ljqo_algorithm = {twopo|geqo}

As its name means, TwoPO has internally two search strategies that
constitute its two phases of optimization:

 * Iterative Improvement (II) – Biased Sampling + Local Search
 * Simulated Annealing (SA)

This algorithm also works in two search spaces:

 * deep-trees (subset of bushy-trees)
- list of baserels
- initial states: biased sampling using
  Prim algorithm over join graph (new, very efficient)
- moves: swap, 3cycle [2]
 * bushy-trees
- binary join tree representation
- initial states: biased sampling using
  Kruskal's algorithm over join graph [3,4].
- moves: associative

You can modify the functionality of TwoPO through the following parameters:

twopo_bushy_space = {true|false}
  - set it to false if you want only deep-trees
default=true
twopo_heuristic_states = {true|false}
  - enables heuristic to initial states
default=true
twopo_ii_stop = Int
  - number of initial states
default=10
twopo_ii_improve_states = {true|false}
  - find local-minimum of each initial state
default=true
twopo_sa_phase = {true|false}
  - enables Simulated Annealing (SA) phase
default=true
twopo_sa_initial_temperature = Float
  - initial temperature for SA phase
default=0.1
twopo_sa_temperature_reduction = Float
  - temperature reduction
default=0.95
twopo_sa_equilibrium = Int
  - number of states generated for each temperature
(Int * State Size)
default=16


References:

[1] Yannis E. Ioannidis e Younkyung Kang. Randomized algorithms for
optimizing large join queries. SIGMOD Rec., 19(2):312-321, 1990.

[2] Arun Swami e Anoop Gupta. Optimization of large join queries. SIGMOD
'88: Proceedings of the 1988 ACM SIGMOD international conference on
Management of data, pages 8-17, New York, NY, USA, 1988. ACM.

[3] P.B. Guttoski, M. S. Sunye, e F. Silva. Kruskal's algorithm for
query tree optimization. IDEAS '07: Proceedings of the 11th
International Database Engineering and Applications Symposium, pages
296-302, Washington, DC, USA, 2007. IEEE Computer Society.

[4] Florian Waas e Arjan Pellenkoft. Join order selection - good enough
is easy. BNCOD, pages 51-67, 2000.


Att,
Adriano Lange


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

Re: [HACKERS] join ordering via Simulated Annealing

[Adriano Lange]

Em 22-12-2009 22:23, Jan Urbański escreveu:
  o) the initial state is not really a random plan, it's usualy a
 left-deep tree (and is very inefficient) and this might skew results.

Maybe a QuickPick + SA.
http://www.springerlink.com/content/garn64gt61ju5xfa/
http://portal.acm.org/citation.cfm?doid=1559845.1559889


Att
Adriano Lange

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

Re: [HACKERS] Memory context usage

[Adriano Lange]

Tom Lane escreveu:

Adriano Lange alange0...@gmail.com writes:

I need to control the size of a memory context on the fly and take
some actions when
the used memory exceeds a defined size.


The existing places that do that sort of thing do their own counting
of how much they've allocated.


I have seen that the AllocSet structure is hid by MemoryContext which 
has only a stderr output interface for its stats. I would need these 
stats internally but maybe this is only my demand for now.


Thanks for attention.

Adriano

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

Re: [HACKERS] Memory context usage

[Adriano Lange]

On Fri, Aug 28, 2009 at 5:18 AM, Greg Smithgsm...@gregsmith.com wrote:
 On Fri, 28 Aug 2009, Tom Lane wrote:

 MemoryContextStats() might help.  It just dumps the info to stderr
 though.

 Which means it ends up in the database log files in the common configuration
 where where the database's stderr is redirected to there. I even script
 running this regularly against stuff I'm suspicious of, using something like
 this passed the PID of the process I want to watch:

 #!/bin/bash
 gdb -p $1 EOF
 p MemoryContextStats(TopMemoryContext)
 detach
 quit
 EOF

 --
 * Greg Smith gsm...@gregsmith.com http://www.gregsmith.com Baltimore, MD


Is there another way to get it in the source code?
I need to control the size of a memory context on the fly and take
some actions when
the used memory exceeds a defined size.

Thanks

Adriano

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

[HACKERS] Memory context usage

[Adriano Lange]

Hi,

How can I get the used memory of a memory context?

Is there some function like:

int getMemoryUsage( MemoryContext )

?

I still working in a subplan cache for a query optimizer and I need to know
whether a temporary memory context is in certain limits.

Thanks

Adriano

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

Re: [HACKERS] GEQO: ERX

[Adriano Lange]

Hi

Tobias Zahn escreveu:

Hello Adriano,
thank you very much for posting your patch. I think it will help to make
further work easier, too. I hope you don't mind when I ask you some
questions.

When you said that this new approach is worse or equal than GEQO, did
you refer to performance or to the quality of results?


Not exactly this approach, but the implemented (and not configured) 
algorithm was worse than GEQO in a little test made. I just used a 
sequence of 8 executions of a query with 18 relations for each 
algorithm. The costs generated by GEQO was little better than 2PO, in 
average and standard deviation. But 8 executions and 1 query don't prove 
anything. I want to make some further tests, but this little difference 
seems good for me.



Why do you think that compressed annealing might be the better approach?


I don't think if compressed annealing is better or not. I don't read 
about it yet.


However, an optimizer can be better in a context but worse in another.

Regards,
Adriano

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

Re: [HACKERS] GEQO: ERX

[Adriano Lange]

Robert Haas escreveu:

On Wed, May 13, 2009 at 4:14 PM, Tobias Zahn tobias-z...@arcor.de wrote:

Hello,
thank you for posting the paper, it was quite interesting to read. I
think it would be a good idea to give the two-phase optimization a try.
As far as I know and understand the current (geqo) optimizer source,
many important parts are already there. For example, we can calculate
the costs of a given join order. Therefore, it would only be necessary
to write an algorithm witch chooses the right input for the cost function.
I would be interested in your opinion.


I'm very interested in any improvements we can make to planning large
join nests.  Unfortunately the paper seems to conclude that it's not
really feasible to use heuristics, as had been my hope, but I'd be
very interested in any other approaches we can come up with.  I
probably do not have time to implement anything myself, but I'm happy
to help with ideas and code review.



I implemented the 2PO algorithm last month but I didn't have much time 
to do an extensive test and to comment all code. The code was posted in 
this list in a previous thread. In that occasion, I was interested in a 
kind of cache structure to avoid the constructing a complete RelOptInfo 
from scratch every time when the cheapest total_cost must be calculated 
(this occur in GEQO).


I’m sending a patch for the 8.3 release.

I also changed some GUC variables to facilitate some tests:
(remove) geqo
(remove) geqo_threshold
(add) ljqo_enable (bool) – activate Large Join Query Optimizer
(add) ljqo_algorithm {geqo|twopo}
(add) ljqo_threshold (int) – like geqo_threshold
(add) twopo_heuristic_states (bool) – initial heuristic states
(add) twopo_ii_stop (int) – II phase loop
(add) twopo_sa_phase (bool) – enable SA phase
(add) twopo_sa_initial_temperature (float)
(add) twopo_sa_temperature_reduction (float)
(add) twopo_sa_equilibrium (int)

In my little tests, this algorithm seems equal or worse than geqo, 
except when using heuristic in order to bias the initial state. Maybe 
some tunings are needed but I prefer spend yet some time reading more 
about the compressed annealing, cited in TODO list. Anyway, I think that 
to build another annealing-like algorithm might be easier if some 
structures and functions in 2PO source code are correct.


Sincerely,

Adriano Lange


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

Re: [HACKERS] GEQO: ERX

[Adriano Lange]

Adriano Lange escreveu:
I implemented the 2PO algorithm last month but I didn't have much time 
to do an extensive test and to comment all code. The code was posted in 
this list in a previous thread. In that occasion, I was interested in a 
kind of cache structure to avoid the constructing a complete RelOptInfo 
from scratch every time when the cheapest total_cost must be calculated 
(this occur in GEQO).


I’m sending a patch for the 8.3 release.


I forgot it.



I also changed some GUC variables to facilitate some tests:
(remove) geqo
(remove) geqo_threshold
(add) ljqo_enable (bool) – activate Large Join Query Optimizer
(add) ljqo_algorithm {geqo|twopo}
(add) ljqo_threshold (int) – like geqo_threshold
(add) twopo_heuristic_states (bool) – initial heuristic states
(add) twopo_ii_stop (int) – II phase loop
(add) twopo_sa_phase (bool) – enable SA phase
(add) twopo_sa_initial_temperature (float)
(add) twopo_sa_temperature_reduction (float)
(add) twopo_sa_equilibrium (int)

In my little tests, this algorithm seems equal or worse than geqo, 
except when using heuristic in order to bias the initial state. Maybe 
some tunings are needed but I prefer spend yet some time reading more 
about the compressed annealing, cited in TODO list. Anyway, I think that 
to build another annealing-like algorithm might be easier if some 
structures and functions in 2PO source code are correct.


Sincerely,

Adriano Lange

Index: src/include/optimizer/ljqo.h
===
--- src/include/optimizer/ljqo.h	(revisão 0)
+++ src/include/optimizer/ljqo.h	(revisão 14)
@@ -0,0 +1,39 @@
+/*
+ *
+ * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * contributed by:
+ *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
+ *  Adriano Lange  *  C3SL - Centro de Computação*
+ *  adri...@c3sl.ufpr.br   *  Científica e Software Livre /  *
+ * *  Departamento de Informática /  *
+ * *  Universidade Federal do Paraná *
+ * *  Curitiba, Brasil   *
+ * * *
+ * *  http://www.c3sl.ufpr.br*
+ * * *
+ *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
+ */
+
+#ifndef LJQO_H
+#define LJQO_H
+
+#include nodes/relation.h
+
+typedef enum ljqo_algorithms {
+	ljqo_a_geqo,
+	ljqo_a_twopo,
+} ljqo_algorithms;
+
+#define DEFAULT_LJQO_ENABLE true
+#define MIN_LJQO_THRESHOLD  2
+#define DEFAULT_LJQO_THRESHOLD  10
+#define DEFAULT_LJQO_ALGORITHM  ljqo_a_geqo
+#define DEFAULT_LJQO_ALGORITHM_STR  geqo
+
+const char * assign_ljqo_algorithm(const char *newval, bool doit);
+RelOptInfo * ljqo(PlannerInfo *root, int levels_needed, List *initial_rels);
+
+
+#endif   /* LJQO_H */
Index: src/include/optimizer/twopo.h
===
--- src/include/optimizer/twopo.h	(revisão 0)
+++ src/include/optimizer/twopo.h	(revisão 14)
@@ -0,0 +1,52 @@
+/*
+ * twopo.h
+ *Two Phase Optimization
+ *
+ * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * contributed by:
+ *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
+ *  Adriano Lange  *  C3SL - Centro de Computação*
+ *  adri...@c3sl.ufpr.br   *  Científica e Software Livre /  *
+ * *  Departamento de Informática /  *
+ * *  Universidade Federal do Paraná *
+ * *  Curitiba, Brasil   *
+ * * *
+ * *  http://www.c3sl.ufpr.br*
+ * * *
+ *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
+ *
+ * Implementation based on:
+ *   Y. E. Ioannidis and Y. Kang, Randomized algorithms for optimizing
+ *   large join queries, SIGMOD Rec., vol. 19, no. 2, pp. 312–321, 1990.
+ */
+
+#ifndef TWOPO_H
+#define TWOPO_H
+
+#include nodes/relation.h
+
+#define DEFAULT_TWOPO_HEURISTIC_STATES  true
+#define DEFAULT_TWOPO_II_STOP   10
+#define MIN_TWOPO_II_STOP   1
+#define DEFAULT_TWOPO_SA_PHASE  true
+#define DEFAULT_TWOPO_SA_INITIAL_TEMPERATURE0.2
+#define MIN_TWOPO_SA_INITIAL_TEMPERATURE0.01
+#define DEFAULT_TWOPO_SA_TEMPERATURE_REDUCTION  0.95
+#define MIN_TWOPO_SA_TEMPERATURE_REDUCTION  0.1
+#define DEFAULT_TWOPO_SA_EQUILIBRIUM16
+#define

[HACKERS] RelOptInfo cache

[Adriano Lange]

Hi,

I implemented the Two Phase Optimizer based on an Ioannidis' paper to 
make some tests. In this source, I used a struct, named treeNode, witch 
can control a bottom-up RelOptInfo construction cache. This struct has a 
RelOptInfo, 2 child pointer (treeNode *inner_child, *outer_child) and a 
parent list (List *parents). The main idea is, if we want to join two 
treeNodes (joinNodes()), we can first search in parent list of one 
treeNode if the other treeNode is its brother.


Is there any structural problem in this approach? I have saw in geqo 
source that there was a comment about this lack of optimization. I 
remember that the geqo used a memory context switch for each plan 
evaluation.


The source code of 2PO (twopo) is attached for any test.

(Sorry by any (many) grammatical mistake)

---
Adriano Lange
/*
 * twopo.c
 *Two Phase Optimization
 *
 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * contributed by:
 *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 *  Adriano Lange  *  C3SL - Centro de Computação*
 *  adri...@c3sl.ufpr.br   *  Científica e Software Livre /  *
 * *  Departamento de Informática /  *
 * *  Universidade Federal do Paraná *
 * *  Curitiba, Brasil   *
 * * *
 * *  http://www.c3sl.ufpr.br*
 * * *
 *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*
 *
 * Implementation based on:
 *   Y. E. Ioannidis and Y. Kang, Randomized algorithms for optimizing
 *   large join queries, SIGMOD Rec., vol. 19, no. 2, pp. 312–321, 1990.
 */

#include postgres.h

#include math.h

#include optimizer/twopo.h
#include optimizer/pathnode.h
#include optimizer/paths.h
#include optimizer/joininfo.h
#include parser/parsetree.h
#include utils/memutils.h

//#define TWOPO_DEBUG

#define TWOPO_CACHE_PLANS

#define nodeCost(node) node-rel-cheapest_total_path-total_cost

#define swapValues(type,v1,v2) \
	{ \
		type aux = v1; \
		v1 = v2; \
		v2 = aux; \
	}

// heuristic initial states (see makeInitialState())
bool   twopo_heuristic_states  = DEFAULT_TWOPO_HEURISTIC_STATES;
// number of initial states in Iterative Improvement (II) phase
inttwopo_ii_stop   = DEFAULT_TWOPO_II_STOP;
// enable Simulated Annealing (SA) phase
bool   twopo_sa_phase  = DEFAULT_TWOPO_SA_PHASE;
// SA initial temperature: T = X * cost( min_state_from_ii_phase )
double twopo_sa_initial_temperature= DEFAULT_TWOPO_SA_INITIAL_TEMPERATURE;
// SA temperature reduction: Tnew = X * Told
double twopo_sa_temperature_reduction  = DEFAULT_TWOPO_SA_TEMPERATURE_REDUCTION;
// SA inner loop equilibrium: for( i=0; i  E * Joins ; i++ )
inttwopo_sa_equilibrium= DEFAULT_TWOPO_SA_EQUILIBRIUM;

/**
 * treeNode:
 *Optimizer's main struct.
 *Represent either a base relation or a binary join operation.
 *It has cache support (see joinNodes()).
 */
typedef struct treeNode {
	RelOptInfo *rel;
	List   *parents;
	struct treeNode*inner_child;
	struct treeNode*outer_child;
	// only for two-level nodes: (used in buildBushyTree())
	int head_idx;
	int tail_idx;
} treeNode;

/**
 * tempCtx:
 *Temporary memory context struct.
 *Store main informations needed context switch.
 */
typedef struct tempCtx {
	MemoryContext  mycontext;
	MemoryContext  oldcxt;
	intsavelength;
	struct HTAB   *savehash;
} tempCtx;

static treeNode*
createTreeNodes( int items )
{
	return (treeNode*) palloc0(items * sizeof(treeNode));
}

static treeNode*
buildOneLevelNodes( List *initial_rels, int levels_needed )
{
	int  i = 0;
	ListCell*x;
	RelOptInfo  *rel;
	treeNode*oneLevelNodes = createTreeNodes( levels_needed );

	foreach(x, initial_rels)
	{
		rel = (RelOptInfo *) lfirst(x);
		oneLevelNodes[i++].rel = rel;
	}

	return oneLevelNodes;
}

static treeNode*
joinNodes( PlannerInfo *root, treeNode *inner_node, treeNode *outer_node )
{
	treeNode *new_node = NULL;
	RelOptInfo *jrel;

#	ifdef TWOPO_CACHE_PLANS
	if ( inner_node-parents ) {
		ListCell *x;
		treeNode *node;
		foreach( x, inner_node-parents )
		{
			node = lfirst(x);
			if( node-inner_child == outer_node
|| node-outer_child == outer_node )
			{
new_node = node;
break;
			}
		}
	}
#	endif

	if ( ! new_node ) {
		if( bms_overlap(inner_node-rel-relids, outer_node-rel-relids ) ){
			elog( ERROR, joinNodes(): Overlap error!);
		}
		jrel = make_join_rel(root, inner_node-rel, outer_node-rel);
		if (jrel) {
			set_cheapest( jrel );
			new_node = createTreeNodes(1);
			new_node-rel = jrel;
			new_node-inner_child

Re: [HACKERS] graph representation of data structures in optimizer

[Adriano Lange]

Tom Lane escreveu:

But really I think the problem with this approach is that the
information density is too low --- imagine what it would look like in a
six-or-more-way join.  I don't think the graphical approach is helpful
at all here.


I was thinking about the hard visualization and navigability in the 
graph. I think that a good solution for this would be a dynamic 
navigability in their nodes and a rearrange their positions by focused 
node. I'm not remembering now, but I've saw a tool like this.


Thanks

--
Adriano Lange
C3SL/UFPR - www.c3sl.ufpr.br

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

Re: [HACKERS] graph representation of data structures in optimizer

[Adriano Lange]

Tom Lane escreveu:

Gregory Stark st...@enterprisedb.com writes:

Adriano Lange adri...@c3sl.ufpr.br writes:

I've changed the debug functions of allpaths.c to make a graphviz-like output
of RelOptInfo structure.



However I have to say this graph you've generated is amazingly hard to
decipher :) It took me a while to even figure out what information it was
presenting.



Worse, it's not useful unless you add a lot more information to it such as
what relations are actually being scanned or joined at each path which is
going to make it a hell of a lot harder to read.


Labeling the bottom-level scan paths with their relations would help a
lot.  The label at the top level isn't real helpful.

But really I think the problem with this approach is that the
information density is too low --- imagine what it would look like in a
six-or-more-way join.  I don't think the graphical approach is helpful
at all here.


Certainly. That example had only three relations. Six relations in a 
RelOptInfo will make a big graph and too hard to understand.


So, I will think about this for a while. A interesting thing for me is 
to identify the in-degree pointers of each structure.



Also, showing the final Path data structure has the problem that a lot
of the information someone might want is already gone, because we throw
away Paths that are determined to be dominated by other paths.  The
question someone usually wants answered is was a path of this structure
considered at all, and if so what was the estimated cost?.  In a large
fraction of cases, that's not answerable from the paths that remain at
the end of the search.  I think some sort of on-the-fly tracing of all
add_path calls might be a more useful approach.

regards, tom lane


Humm. This temporal approach may be dificult to represent in this 
graphical mode. I guess that the text-like pretty_format_node_dump() 
representation and diff are yet more usefull for this.


--
Adriano Lange
C3SL/UFPR - www.c3sl.ufpr.br


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

Re: [HACKERS] graph representation of data structures in optimizer

[Adriano Lange]

Robert Haas escreveu:

That is pretty cool.

It would help a lot to label the baserels with their names.

 

You might also want to move the RestrictInfo out of line so that it's
easier to see where the inner and outer joinpath arrows are going.


Humm. Maybe this is not easy to do in dot command line graph generator.
Perhaps I should to try this in other application. The output generated
by debug is only a text plain description of vertex and edges, without
any information about position or path. See the attached file.


It would be really sweet if there were some compact way to see the pathkeys.


Several attributes and objects are missing yet, but I will add them.

Thanks,

Adriano Lange
C3SL/UFPR - www.c3sl.ufpr.br



RelOptInfo_graph.dot
Description: application/crossover-dot

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

[HACKERS] GEQO Publications

[Adriano Lange]

Hi all,

I'm looking for materials explaining GEQO module. I've found
something related in
http://www.mail-archive.com/pgsql-hackers@postgresql.org/msg40584.html 
and PostgreSQL's documentation.


Nevertheless, is there some other cientific publication about it?
I've tried also send email to Martin Utesch at [EMAIL PROTECTED]
but this email appear invalid.

If someone can help me.

Thanks for attention,

Adriano


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