Re: graph representation of data structures in optimizer

Hi,

I'm interested in data representation and debug of optimizer routines.
Thus, I've changed the debug functions of allpaths.c to make a
graphviz-like output of RelOptInfo structure.

Any idea about this?
Is there some project or improvement like this?

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

Adriano Lange <adriano(at)c3sl(dot)ufpr(dot)br> writes:

> Hi,
>
> I'm interested in data representation and debug of optimizer routines. Thus,
> I've changed the debug functions of allpaths.c to make a graphviz-like output
> of RelOptInfo structure.
>
> Any idea about this?
> Is there some project or improvement like this?

Several people have asked about ways to see what possible plans were
considered and why the were rejected, it was one of the repeat offenders in
the recent Postgres Pet Peeves thread so this is a very interesting area to
explore.

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.

I'm not sure how to do any better but I would be fascinated to see any new
images you generate :)

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com
Ask me about EnterpriseDB's PostGIS support!

On Wed, Feb 18, 2009 at 10:22 AM, Adriano Lange <adriano(at)c3sl(dot)ufpr(dot)br> wrote:
> Hi,
>
> I'm interested in data representation and debug of optimizer routines. Thus,
> I've changed the debug functions of allpaths.c to make a graphviz-like
> output of RelOptInfo structure.
>
> Any idea about this?
> Is there some project or improvement like this?

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.

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

...Robert

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> Adriano Lange <adriano(at)c3sl(dot)ufpr(dot)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.

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

Tom Lane escreveu:
> Gregory Stark <stark(at)enterprisedb(dot)com> writes:
>> Adriano Lange <adriano(at)c3sl(dot)ufpr(dot)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

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

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

On Thursday 19 February 2009 22:17:54 Adriano Lange wrote:
> 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.

http://prefuse.org could be useful for that.

Hi,

The patch attached is an implementation for graph generation of data
structures in postgres. The file debuggraph.c is a simple library that
generate graphs in the format supported by graphviz. Example:

#include "nodes/debuggraph.h"
...
DebugGraph *graph;
DebugNode *node;

graph = createDebugGraph();
node = newDebugNode( graph, "node1", "Node 1" );
addDebugNodeAttribute( node, "Attribute 1", "Value 1" );
newDebugNode( graph, "node2", "Node 2" );
newDebugEdge( graph, "node1", "node2", "Edge 1" );

printGraphvizToFile( graph, stderr );
destroyDebugGraph( graph );

I've also made a reimplementation of outfuncs.c to outfuncs_graph.c for
an entire node output support.

#include "nodes/outfuncs_graph.h"
...
printGraphNodes( node, stderr );

I hope that this may be useful for somebody.

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

Adriano Lange <adriano(at)c3sl(dot)ufpr(dot)br> wrote:

> The patch attached is an implementation for graph generation of data
> structures in postgres. The file debuggraph.c is a simple library that
> generate graphs in the format supported by graphviz.

It's interesting, but I don't think it is suitable for a core feature.
Could you split the patch into a core-patch and an extension module?
The extension module would be put in contrib or in a pgFoundry project.
XML might be good for communications between the core and the module;
XML-explain was ongoingly discussed, but had not been completed yet.

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center