oqgraph-dev team mailing list archive

[Andrew McDonnell <bugs@xxxxxxxxxxxxxxxxxxx>]

Hi Arjen

NO_SEARCH causes different behaviour depending on how it is used:

In my branch lines 707-749 of graphcore.cc

NO_SEARCH alone returns a vertices_cursor(share)

but

NO_SEARCH with HAVE_DEST does

        if ((op & HAVE_DEST) &&
            (cursor || (cursor= new (std::nothrow) stack_cursor(share))) &&
	    dest)
        {
          graph_traits<Graph>::in_edge_iterator ei, ei_end;
          for (boost::tuples::tie(ei, ei_end)= in_edges(*dest, share->g); ei
!= ei_end; ++ei)
          {
            Vertex v= source(*ei, share->g);
            static_cast<stack_cursor*>(cursor)->
                results.push(reference(++seq, v, *ei,
                    get(boost::edge_weight, share->g, *ei)));
          }
        }

NO_SEARCH with HAVE_ORIG does

        if ((cursor= new (std::nothrow) stack_cursor(share)) && orig)
        {
          graph_traits<Graph>::out_edge_iterator ei, ei_end;
          for (boost::tuples::tie(ei, ei_end)= out_edges(*orig, share->g); ei
!= ei_end; ++ei)
          {
            Vertex v= target(*ei, share->g);
            static_cast<stack_cursor*>(cursor)->
                results.push(reference(++seq, v, *ei,
                    get(boost::edge_weight, share->g, *ei)));
          }
        }

and falls through to the HAVE_DEST handler above

I dont (yet) understand the above graph code, but I'll instrument this to see
which is being called, although an educated guess is that the third case is if
I assume that HAVE_ORIG and HAVE_DEST are derived from columns in the query...

In the process of that I should further be able to learn how the boost graph
code actually works


It seems that basic.test has no queries that exercise no_search without dest
or orig, so I'll add some.  Same goes for no latch there are no tests yet either

--Andrew


On 29/05/13 08:08, Arjen Lentz wrote:
> Hi Andrew
> 
>> what should a no_search latch return?
> 
> For latch=0/no_search, the table should look as inserted (i.e. like a regular table).
> 
> I was just wondering if you'd also set "no_search" as the default, but I reckon it might be better to use an empty string or NULL rather than no_search. Can you change that without causing hassles elsewhere?
> 
> 
>> Given the data below, there is only one directed link between vertexes
>> 1,2 and one directed link between vertexes 2,1
>>
>> So by my logic if you are looking for 'things' with a destid of vertex
>> 2 and and source vertext of 1 then only one row should be returned?
> 
> yes.
> 
> 
>> INSERT INTO graph_base(from_id, to_id) VALUES (1,2), (2,1);
>> INSERT INTO graph_base(from_id, to_id) VALUES (1,3), (3,1);
>> INSERT INTO graph_base(from_id, to_id) VALUES (3,4), (4,3);
>> INSERT INTO graph_base(from_id, to_id) VALUES (5,6), (6,5);
>>
>> SELECT * FROM graph WHERE latch='no_search' and destid=2 and origid=1;
>>
>> yields
>>
>> latch origid destid weight seq linkid
>> no_search 1 2 1 3 1
>> no_search 1 2 1 2 3
>> no_search 1 2 1 1 2
>>
>>
>> (And simlar for the integer latch equivalent)
>>
>> latch origid destid weight seq linkid
>> 0 1 2 1 3 1
>> 0 1 2 1 2 3
>> 0 1 2 1 1 2
> 
> Without a latch command, seq/linkid should come back NULL.
> So it appears the computation engine is doing some path search there, as there is an seq.
> The result above is wrong, but I'm very curious what it is actually doing? (which bit of code is getting executed?)
> 
> You could install a MariaDB 5.3 to compare behaviour with v2, but asking me works also ;-)
> 
> 
> Without a latch, you can return either any rows that match the origid/destid/weight conditions (as they're the only real columns), or you can be lazy and return everything - the server core will filter it for you according to the WHERE conditions!
> The latter is useful because it allows us to cheaply return the correct result for constructs like WHERE origid BETWEEN 10 and 20 without processing pushdown conditions (something we will want to do for other tasks, such as restricting search depth, but that's a separate gig).
> 
> 
> Regards,
> Arjen.