Tree::Predicate 0.03 NAME Tree::Predicate - a tree of predicate logic (e.g. an SQL predicate) SYNOPSIS use Tree::Predicate qw(:logical); my $left_branch = OR('a', 'b'); my $right_branch = OR('c', 'd'); my $tree = AND($left_branch, $right_branch); my $sql = $tree->as_string; my @subtrees = $tree->split; for (@subtrees) { print $_->as_string; } DESCRIPTION Improving static queries for optimal performance is almost as old as SQL itself. A relatively recent discussion (on which this module is based) can be found in the book "High Performance MySQL" from O'Reilly. One technique for improving queries relies on the way that MySQL chooses which indexes to use. Prior to MySQL 5.0, a query such as: SELECT * FROM foo WHERE a = 1 OR b = 2 would result in a full-table scan, regardless of whether foo is indexed on a or b. For MySQL 5.0 or later, a combination index would be used for that query. But for this query: SELECT * FROM foo WHERE c IN ('foo', 'bar') AND (a = 1 OR b = 2) both before-5.0 and after-5.0 will use an index on c before considering a merged index of a/b. For such queries, a significant improvement is available by rewriting the query as: SELECT * FROM foo WHERE c IN ('foo', 'bar') AND a = 1 UNION SELECT * FROM foo WHERE c IN ('foo', 'bar') AND b = 2 Even if we are using placeholders, it is straight-forward to rewrite any static query in whatever form performs best. What about queries that are created dynamically, though? This is where Tree::Predicate comes in. Construct a tree with its logical operators (AND/OR/NOT). The "split" method will return a list of subtrees that can be used as predicates in a series of UNION queries that are logically equivalent to the original predicate. The subtrees can be used to construct a complete query or can be used to query a database successively so that previous results can be used to modify subsequent queries. Suppose we have a tree $tree that is being used to query table items: my @ids; for my $subtree ($tree->split) { if (@ids) { my $ids = join ',' => @ids; my $phrase = "NOT IN ($ids)"; my $new_subtree = AND($phrase, $subtree); my $sql = "SELECT id FROM items WHERE " . $new_subtree->as_string; my $aryref = $dbh->selectcol_arrayref($sql); push @ids, @$aryref; } else { my $sql = "SELECT id FROM items WHERE " . $subtree->as_string; my $aryref = $dbh->selectcol_arrayref($sql); @ids = @$aryref; } } This is just an example, of course. Actual implementations will probably be more sophisticated. CAVEATS Particularly with slower predicate atoms, such as REGEXP and LIKE, it is possible to turn a slow query into a VERY slow query by splitting its predicate into several. You will probably want a heuristic that governs when you try to improve the dynamically-generate query or whether you just give the whole mess to the database to sort out. FUTURE DIRECTIONS I have several ideas for future directions for this module. One is to allow associating anticipated selectivity and cost information with an atom so that the module can order subtrees accordingly. (Obviously, we should choose to execute predicates that can find as much of the total result as cheaply as possible.) Two related ideas would entail giving the tree a database handler, plus other information, so that it can compute its own result. This would allow the short-circuit emulation above to become internal to the module. Additionally, tables that are joined for the purpose of evaluating one part of the predicate could be joined when that predicate is part of the subtree being evaluated. Some parts of a predicate could be stored elsewhere, such as in a cache, which could avoid some database activity. INSTALLATION To install this module, run the following commands: perl Makefile.PL make make test make install SUPPORT AND DOCUMENTATION After installing, you can find documentation for this module with the perldoc command. perldoc Tree::Predicate You can also look for information at: RT, CPAN's request tracker http://rt.cpan.org/NoAuth/Bugs.html?Dist=Tree-Predicate AnnoCPAN, Annotated CPAN documentation http://annocpan.org/dist/Tree-Predicate CPAN Ratings http://cpanratings.perl.org/d/Tree-Predicate Search CPAN http://search.cpan.org/dist/Tree-Predicate/ COPYRIGHT AND LICENSE Copyright (C) 2010 Yahoo!, Inc. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.