troels knak-nielsen | 2 Dec 13:26 2007
Picon

performance of trees

Hi list.

We're about to implement an application, which will use a tree
structure as the main taxonomy. Instead of implementing the algorithm
ourself, we are considering using the tree from ezc. We are keen on
using a modified preorder (nested set), but looking through the table
at http://ezcomponents.org/docs/tutorials/Tree I had a few questions.
When the phrase "Simple operation" is used, I suppose that it means
that it's "cheap" to execute -- Not that the implementation is simple?
Also, does "simple" mean that it's a constant cost or what happens,
when the size of the tree scales? I'm sure, an in-depth answer gets
rather complex, but some indication of how each operation scales,
would be most informative. For example, I'm not entirely sure, what
the implications of using LIKE on large datasets is? I suppose, that
in theory, LIKE should be able to perform reasonably well, since the
match is anchored, but I'm not sure how well MySql (We use MySql)
works.

Thanks

--

-- 
troels
Derick Rethans | 2 Dec 13:43 2007
Picon

Re: performance of trees

Hello Troels,

On Sun, 2 Dec 2007, troels knak-nielsen wrote:

> We're about to implement an application, which will use a tree 
> structure as the main taxonomy. Instead of implementing the algorithm 
> ourself, we are considering using the tree from ezc. We are keen on 
> using a modified preorder (nested set), but looking through the table 
> at http://ezcomponents.org/docs/tutorials/Tree I had a few questions. 
> When the phrase "Simple operation" is used, I suppose that it means 
> that it's "cheap" to execute -- Not that the implementation is simple?

Yes, it's often a simple query, which uses an index of some sorts. As 
the queries are simple, so is the implementation of course.

> Also, does "simple" mean that it's a constant cost or what happens, 
> when the size of the tree scales? I'm sure, an in-depth answer gets 
> rather complex, but some indication of how each operation scales, 
> would be most informative.

That's basically what the table tries to say without reverting to O 
notations. The value "Simple Operation" tells you that the backend only 
has to do one (or two or three) queries to get the result - and that the 
number of queries is always constant.

> For example, I'm not entirely sure, what the implications of using 
> LIKE on large datasets is? I suppose, that in theory, LIKE should be 
> able to perform reasonably well, since the match is anchored, but I'm 
> not sure how well MySql (We use MySql) works.

(Continue reading)

Gaetano Giunta | 2 Dec 14:47 2007
Picon

Re: performance of trees


For example, I'm not entirely sure, what the implications of using LIKE on large datasets is? I suppose, that in theory, LIKE should be able to perform reasonably well, since the match is anchored, but I'm not sure how well MySql (We use MySql) works.
I'm not a real MySQL guru either, but I could run some benchmarks on this next week I suppose. If you have a more specific question about the cost of an operation, I'd be happy to explain you the algorithm.
Using the 'like' operator has usually the same cost as using an equality operator, regardless of db, so there is no huge speed penalty involved, if any at all.
Otoh index selectivity plays a big role in performance: the more rows (children) a select fetches, the more it will be slower compared to a select done on eg. the pk (note: this is all unscientific evidence, gathered from tests on ezpublish installations done with mysql).

bye
Gaetano
<div>
<br><blockquote cite="mid:alpine.DEB.0.98.0712021338010.20723@..." type="cite">
  <blockquote type="cite">
    For example, I'm not entirely sure, what the implications of using 
LIKE on large datasets is? I suppose, that in theory, LIKE should be 
able to perform reasonably well, since the match is anchored, but I'm 
not sure how well MySql (We use MySql) works.

  </blockquote>

I'm not a real MySQL guru either, but I could run some benchmarks on 
this next week I suppose. If you have a more specific question about 
the cost of an operation, I'd be happy to explain you the algorithm.

</blockquote>
Using the 'like' operator has usually the same cost as using an
equality operator, regardless of db, so there is no huge speed penalty
involved, if any at all.<br>
Otoh index selectivity plays a big role in performance: the more rows
(children) a select fetches, the more it will be slower compared to a
select done on eg. the pk (note: this is all unscientific evidence,
gathered from tests on ezpublish installations done with mysql).<br><br>
bye<br>
Gaetano<br>
</div>
troels knak-nielsen | 3 Dec 10:56 2007
Picon

Re: performance of trees

On Dec 2, 2007 1:43 PM, Derick Rethans <dr@...> wrote:
> Hello Troels,
>
> On Sun, 2 Dec 2007, troels knak-nielsen wrote:
> > Also, does "simple" mean that it's a constant cost or what happens,
> > when the size of the tree scales? I'm sure, an in-depth answer gets
> > rather complex, but some indication of how each operation scales,
> > would be most informative.
>
> That's basically what the table tries to say without reverting to O
> notations. The value "Simple Operation" tells you that the backend only
> has to do one (or two or three) queries to get the result - and that the
> number of queries is always constant.
So it means constant, right?
Perhaps that would be a better description to put in the documentation then?

> > For example, I'm not entirely sure, what the implications of using
> > LIKE on large datasets is? I suppose, that in theory, LIKE should be
> > able to perform reasonably well, since the match is anchored, but I'm
> > not sure how well MySql (We use MySql) works.
>
> I'm not a real MySQL guru either, but I could run some benchmarks on
> this next week I suppose. If you have a more specific question about
> the cost of an operation, I'd be happy to explain you the algorithm.
I could run a benchmark as well, but to my experience, databases are
bit like black magic. Just blindly running a benchmark, may test the
wrong thing. I'll try to investigate a bit further and post back here,
if I find get any wiser.

On Dec 2, 2007 2:47 PM, Gaetano Giunta <gg@...> wrote:
>  Using the 'like' operator has usually the same cost as using an equality
> operator, regardless of db, so there is no huge speed penalty involved, if
> any at all.
>  Otoh index selectivity plays a big role in performance: the more rows
> (children) a select fetches, the more it will be slower compared to a select
> done on eg. the pk (note: this is all unscientific evidence, gathered from
> tests on ezpublish installations done with mysql).
The question is really, if MySql can make use of indices, when using
LIKE. I'm guessing, that it might be able, as long as the pattern is
anchored -- Which would be the case, when searching by a materialised
path.

--

-- 
troels
troels knak-nielsen | 3 Dec 12:50 2007
Picon

Re: performance of trees

On Dec 3, 2007 10:56 AM, troels knak-nielsen <troelskn@...> wrote:
> wrong thing. I'll try to investigate a bit further and post back here,
> if I find get any wiser.

I've been googling a bit, this morning and while I haven't found an
answer to the performance of LIKE on large datasets, I did come by
this article, during my search:
http://fungus.teststation.com/~jon/treehandling/TreeHandling.htm
It describes how to deal with a normalised variant of the materialised
path, and has queries for operations on the scheme. Some of them seem
a bit hairy -- I'm not sure MySql would be able to handle them. Still,
it might be something to look further into.

--

-- 
troels
Falko Menge | 4 Dec 21:08 2007
Picon

Integration of Static Reflection into ezcReflection

Hi everyone,

sorry for writing such a long email, but this design
decision is very important for the completion of the
Reflection component.

Sebastian Bergmann wrote:
> Stefan Marr schrieb:
>> And there has been a discussion to include another Interface definition in
>> between the reflection classes and the underlying infrastructure, to be able
>> to use a parser and handle Reflection without loading the classes. Butdon't
>> know how that much about this idea. Falko?
> 
>  Yes, Static Reflection (ie. being able to use the Reflection API without
>  the class being loaded) is something I would really like to see in the
>  component.

Recently I studied several approaches for the integration of
the Static Reflection concept we developed at the FrOSCon.

The idea we discussed at the conference was not to include
the parser for static analysis directly in the ezcReflection
component (at least for the first release).
Instead we wanted to introduce a layer of interface which
should then be implemented by ezcReflection and Static
Reflection classes. This would allow for tools like
ezcCodeAnalyzer, ezcWsdl or PHPCallGraph to leverage both
reflection implementations.

Jakob and me developed some tools to generate PHP code out
of reflection objects. You may have a look at them in our
Subversion repositories at:
svn://svn.pureenergy.cc/staticReflection
https://instantsvc.svn.sourceforge.net/svnroot/instantsvc/branches/reflection2php

Interestingly we discovered that this kind of code
generation can be leveraged for refactoring and quality
assurance. On the one hand the tools enable the generation
of interfaces out of classes or class skeletons out of
interfaces. On the other hand it allows for comparing
properties and method signatures among various classes,
e.g. between ezcReflection classes and the PHP Reflection
API. (Try a Diff-Viewer on the output in the svn.)

However the design with interfaces does not seem
to be very elegant because it would require a
complete reimplementation of nearly all features
of the ezcReflection component in the Static
Reflection classes. Thus I propose a dependency injection
approach:
We could allow the injection of instances of external
Reflection implementations through the constructors of the
ezcReflection classes. Such an external Reflection
implementation would have to extend the PHP reflection
classes as well as the ezcReflection does. If such an
instance is given the ezcReflection would leverage it as its
data source. Otherwise PHP Reflection would be utilized as
usual. Additional features of the external instance could
also be leveraged by forwarding calls via overloading.

class ezcReflectionClass extends ReflectionClass
{
     protected $class;

     /**
      *  <at> param string|object|ReflectionClass $argument
      *        name, instance or ReflectionClass object of
      *        the class to be reflected
      */
     public function __construct( $argument )
     {
         if ( !$argument instanceof ReflectionClass )
         {
             parent::__construct($argument);
         }
	$this->class = $argument;
	...
     }

     public function getName() {
         if ( $this->class instanceof ReflectionClass )
         {
             // query external reflection object
             $name = $this->class->getName();
         } else {
             $name = parent::getName();
         }
         return $name;
     }

     public function __call( $method, $arguments )
     {
         if ( !$this->class instanceof ReflectionClass )
         {
             return call_user_method(
                 $this->class,
                 $method, $arguments
             );
         } else {
             throw new Exception(
                 'Call to undefined method '
                 . __CLASS__ . '::' . $method
             );
         }
     }

     ...
}

This aproach would enable users of the ezcReflection to
leverage various reflection extensions (e.g.
StaticReflection or a version extended with intercession
features of Runkit as Stefan proposed it) together with the
annotation mechanism and the type system.
Furthermore the reimplementation of all methods would allow
us to provide a complete documentation since the section of
the PHP manual is more or less incomplete.

Do you have any other ideas on how to solve this integration
problem or improve the proposed design?

Kind regards,
Falko

Derick Rethans | 5 Dec 13:44 2007
Picon

Re: Integration of Static Reflection into ezcReflection

On Tue, 4 Dec 2007, Falko Menge wrote:

> However the design with interfaces does not seem to be very elegant 
> because it would require a complete reimplementation of nearly all 
> features of the ezcReflection component in the Static Reflection 
> classes. Thus I propose a dependency injection approach:
>
> We could allow the injection of instances of external Reflection 
> implementations through the constructors of the ezcReflection classes. 
> Such an external Reflection implementation would have to extend the 
> PHP reflection classes as well as the ezcReflection does. If such an 
> instance is given the ezcReflection would leverage it as its data 
> source. Otherwise PHP Reflection would be utilized as usual. 
> Additional features of the external instance could also be leveraged 
> by forwarding calls via overloading.
> 
> class ezcReflectionClass extends ReflectionClass
> {
>      protected $class;
> 
>      /**
>       *  <at> param string|object|ReflectionClass $argument
>       *        name, instance or ReflectionClass object of
>       *        the class to be reflected
>       */
>      public function __construct( $argument )
>      {
>          if ( !$argument instanceof ReflectionClass )
>          {
>              parent::__construct($argument);
>          }
> 	$this->class = $argument;
> 	...
>      }

We already do some form of dependency injection in some places, most 
notable where we return classes. Take for example this example from 
DatabaseSchema:

http://ezcomponents.org/docs/api/trunk/DatabaseSchema/ezcDbSchema.html#setOptions
and
http://ezcomponents.org/docs/api/trunk/DatabaseSchema/ezcDbSchemaOptions.html

or the mailClass property of the ezcMailParser:
http://ezcomponents.org/docs/api/trunk/Mail/ezcMailParserOptions.html#prop-$mailClass
example is:
http://ezcomponents.org/docs/api/trunk/Mail/ezcMailParserOptions.html#prop-$mailClass
(first example).

In those cases, we don't really have to make if () statements to figure 
out which part to call, but just juse this classname. Something similar 
can be done for compatible implementations of reflection, without 
actually having to wrap it like you do above.

regards,
Derick
Derick Rethans | 5 Dec 14:14 2007
Picon

eZ Components 2007.2RC1 released

Hello!

The eZ Components development team is pleased to announce the first 
release candidate of the 2007.2 release, due to be out shortly. There 
are only a few addressed issues since the beta release, you can find the 
list below. We invite all interested parties to try out the release 
candidate, and report any issues in our issue tracker 
<http://issues.ez.no/ProjectSelect.php?Id=1>.

The final release is expected on December 17th.

Download
~~~~~~~~

The release candidate can be downloaded from the download page 
<http://ezcomponents.org/download/dl_components>, or installed through 
the PEAR installer. You can upgrade to the release candidate by issuing 
the following command:

    pear upgrade ezc/ezcomponents-beta

Updated documentation is also available on the documentation page:
http://ezcomponents.org/docs/api/2007.2rc1

The full announcement can be found here: 
http://ezcomponents.org/resources/news/news-2007-12-05

with kind regards,
--

-- 
Derick Rethans
eZ components Product Manager
eZ systems | http://ez.no
Piotrek Karas | 8 Dec 12:50 2007
Picon

eZ Publish extension using Components - legal

Hello everyone,

How exactly do I license an eZ Publish extension that makes use of eZ 
Components? I've just created one and published it under GPL:
http://ez.no/developer/contribs/applications/ez_human_captcha

Is that OK? Seems to me that eZC license grants huge amount of freedom, 
but wouldn't like to miss something.

Thanks,
Piotrek Karaś

--

-- 
Components mailing list
Components@...
http://lists.ez.no/mailman/listinfo/components

Tobias Schlitt | 8 Dec 20:23 2007
Picon

Re: eZ Publish extension using Components - legal

Hi Piotrek!

On 12/08/2007 12:50 PM Piotrek Karas wrote:

> How exactly do I license an eZ Publish extension that makes use of eZ 
> Components? I've just created one and published it under GPL:
> http://ez.no/developer/contribs/applications/ez_human_captcha

> Is that OK? Seems to me that eZC license grants huge amount of freedom, 
> but wouldn't like to miss something.

I'm not a lawyer, but I know that we've explicitly chosen the New BSD
license for eZ Components to be GPL compatible. Therefore the licensing
for your extension should be perfectly fine.

Great to see extension rising up that make use of eZ Components! :)

Regards,
Toby
-- 
Mit freundlichen Grüßen / Med vennlig hilsen / With kind regards

Tobias Schlitt (GPG: 0xC462BC14) eZ Components Developer

ts <at> ez.no | eZ Systems AS | ez.no
--

-- 
Components mailing list
Components <at> lists.ez.no
http://lists.ez.no/mailman/listinfo/components

Gmane