Betternestedset talk - Jul 2007 - patch to add update conditions

Hi All,

I''ve written (and attached) a patch that adds additional WHERE  
conditions to the UPDATE statement used in the move_to method.

The conditions added are the same as those in the various CASE  
clauses, but by duplicating them in the WHERE clause, the database  
can take advantage of indices on the table. The previous UPDATE  
statement, without the extra conditions, would end up iterating  
through the entire tree. I assume it was smart enough to notice when  
a row wasn''t actually changed, but for a tiny update of a large tree,  
it adds up.

FYI, I have a multi-column index on my table, which includes the  
scope column, as well as the left and right columns. E.g.:

	add_index :tree_items, [:scope_id, :lft, :rgt]

I''ve tested using PostgreSQL, so it might be nice to hear from  
someone using MySQL and other databases.

thanks!
christian.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: bns_update_conditions.patch
Type: application/octet-stream
Size: 1377 bytes
Desc: not available
Url :
http://rubyforge.org/pipermail/betternestedset-talk/attachments/20070706/ee64891a/attachment.obj

Hi Christian,

Thanks for submitting a patch.

Are you seeing significant performance gains with this patch? Have you
benchmarked performance with different index setups? I''m reluctant to
commit a performance patch without good benchmarks. I''ve personally
seen unexpected results from what I thought would be straightforward
performance improvements (adding indexes just slowed the updates down
because the indexes needed to be refreshed on update, extra conditions
in the where clause didn''t help, etc.).

best,
Krishna

On 7/6/07, Christian Niles <christian at unit12.net>
wrote:
> Hi All,
>
> I''ve written (and attached) a patch that adds additional WHERE
> conditions to the UPDATE statement used in the move_to method.
>
> The conditions added are the same as those in the various CASE
> clauses, but by duplicating them in the WHERE clause, the database
> can take advantage of indices on the table. The previous UPDATE
> statement, without the extra conditions, would end up iterating
> through the entire tree. I assume it was smart enough to notice when
> a row wasn''t actually changed, but for a tiny update of a large
tree,
> it adds up.
>
> FYI, I have a multi-column index on my table, which includes the
> scope column, as well as the left and right columns. E.g.:
>
>         add_index :tree_items, [:scope_id, :lft, :rgt]
>
> I''ve tested using PostgreSQL, so it might be nice to hear from
> someone using MySQL and other databases.
>
> thanks!
> christian.
>
>
> _______________________________________________
> Betternestedset-talk mailing list
> Betternestedset-talk at rubyforge.org
> http://rubyforge.org/mailman/listinfo/betternestedset-talk
>
>
>

Hey Krishna,

I did some informal benchmarks for my own data, but some more  
specific ones are in order. My own observations showed that without  
the checks, the time taken for an UPDATE increased linearly. With the  
conditions, update time swayed from as little as a few milliseconds  
to a few seconds, depending on how many rows were updated. So my  
patch essentially halved the average

As a test, I just tried something. I ran an UPDATE statement that set  
the value of a column to its current value -- in effect, it doesn''t  
change it at all. E.g.

	UPDATE table SET id = id;

PostgreSQL re-wrote all rows to disk, which explains the linear  
performance I noticed -- even a small UPDATE caused every row of the  
table to be rewritten. MySQL 5, however, noticed that rows hadn''t  
been changed and didn''t write the rows to disk.

I also realized that my patch *should* improve performance, even  
without any extra indices on the table. All it''s doing is pre- 
evaluating the CASE conditions in the WHERE clause, which gives the  
database an earlier heads up that the row should or shouldn''t change.

Anyway, I''m getting more convinced that this did improve actual  
performance on PostgreSQL, rather than just perceived performance.  
I''ll put together some test cases and benchmarks in the next few days  
so we can test it out on different databases and configurations.

best,
christian.

On Jul 6, 2007, at 4:25 PM, Krishna Dole wrote:
> Hi Christian,
>
> Thanks for submitting a patch.
>
> Are you seeing significant performance gains with this patch? Have you
> benchmarked performance with different index setups? I''m reluctant
to
> commit a performance patch without good benchmarks. I''ve
personally
> seen unexpected results from what I thought would be straightforward
> performance improvements (adding indexes just slowed the updates down
> because the indexes needed to be refreshed on update, extra conditions
> in the where clause didn''t help, etc.).
>
> best,
> Krishna
>
> On 7/6/07, Christian Niles <christian at unit12.net> wrote:
>> Hi All,
>>
>> I''ve written (and attached) a patch that adds additional WHERE
>> conditions to the UPDATE statement used in the move_to method.
>>
>> The conditions added are the same as those in the various CASE
>> clauses, but by duplicating them in the WHERE clause, the database
>> can take advantage of indices on the table. The previous UPDATE
>> statement, without the extra conditions, would end up iterating
>> through the entire tree. I assume it was smart enough to notice when
>> a row wasn''t actually changed, but for a tiny update of a
large tree,
>> it adds up.
>>
>> FYI, I have a multi-column index on my table, which includes the
>> scope column, as well as the left and right columns. E.g.:
>>
>>         add_index :tree_items, [:scope_id, :lft, :rgt]
>>
>> I''ve tested using PostgreSQL, so it might be nice to hear from
>> someone using MySQL and other databases.
>>
>> thanks!
>> christian.
>>
>>
>> _______________________________________________
>> Betternestedset-talk mailing list
>> Betternestedset-talk at rubyforge.org
>> http://rubyforge.org/mailman/listinfo/betternestedset-talk
>>
>>
>>
> _______________________________________________
> Betternestedset-talk mailing list
> Betternestedset-talk at rubyforge.org
> http://rubyforge.org/mailman/listinfo/betternestedset-talk