Sanity check - BinaryLink searches

[Ed Kleban]

On 12/13/05 2:35 AM, "Ruslan Zasukhin" <sunshine at public.kherson.ua> wrote:

> On 12/13/05 6:39 AM, "Ed Kleban" <Ed at Kleban.com> wrote:
> 
> Hi Ed,
> 
>> A quick sanity check to make sure I have things straight.
>> 
>> If I create a BinaryLink between:
>> TblCar.fldModel and TblOptions.fColor
>> 
>> And add some some links:
>> 
>>     ( PintoRid, GreenRid )
>>     ( PintoRid,  BlueRid )
>>     ( TarusRid, GreenRid )
>>     ( TarusRid, BlackRid )
>> 
>> 
>> And then perform a FindLinked( PintoRid, fldModel, fColor )
>> 
>> Then it is necessarily the case that:
>  
>> 1) The search will be fast because FindLinked on a BinaryLink is always fast
>> because searches on either the left field and searches on the right field
>> are always performed using Indexes to perform something fast like a Binary
>> search.
> 
> yes
>  

Great

>> 2) The list of Rids returned in the resulting VSet will necessarily be in
>> the order that that I defined the links,
> 
> Here points: 

>     you an get set as ArraySet then yes.
Super

>     you can get set as VBitSet, then no order at all.

Are you sure?  That does not make sense.  Surely if I use a VBitSet then the
results are necessarily ordered by physical recId.  That's fundamental to
the way VBitSet is defined in the kernel documentation.  I may have to
create and use a Sequencer to iterate over the BitSet and retrieve the
ordered list of rids, how surely the results represented by a VBitSet are
ordered.
> 
> BUT !!!!!
> 
> If you delete in table some record, and later add new, it will REUSE old
> RecID. So new record, can be inserted BEFORE older in list of binary link.

Aha!  Good point.  I had not considered that, but no matter since I never
delete records.
  
>> and therefore:
>> 
>> 3) Whatever sorting technique is used for creating the index is a stable
>> sort that will preserve the relative order links that have the same Rid
>> value for a given left field or a given right field.
> 
> Not clear.

My words are not clear to you?

Or your understanding of how the interals work is not clear?

My understanding is that if (1) is true, and (2) is true, then whether
intended or not by your implementation, by virute of the definition of
"stable" sort (3) must be true.

To quote Charles Yeomans ArraySorter documentation:

"A stable sort is one that preserves the relative order of items with equal
keys. Suppose that you sort an array of objects first on one property, then
on a second.  A stable sort will preserve the first sort order when it
performs the second."

In this context, the records of a table are inherently first sorted by order
of links added to the Links table.

 >     given left field  -- cannot be linked 2 times with the same right
recid
> 

That scares me. I do not understand.

Are you saying that if I have a RECURSIVE link, then everything we discussed
above is true for a   MANY:MANY table

    If I use kFromChildToParent,

    but NOT

    If I use kFromParentToChild?

Why would that be?  I presume that when FindLinked is called the effective
sort order is 1st by by RecId for the corresponding field, and secondly by
order of entry in Link table (i.e. LinkRid ).  If that is true, then it
should not matter whether you have 1:1, 1:M, M:1, or M:M.    If that is not
true, then I am confused.

Thanks!
--Ed