[DISCUSSION] Expression ( Predicate ) Design

[mapleFU]

Iceberg [1] and iceberg-rust [2] both have expression system. There are some design trade-off:

Bind

Both iceberg and iceberg-rust have concept of "bind". I guess this concept is from database query compiler. Specifically, it means bind the reference ( we name it as "term" later ) from "name" to a iceberg Schema with case_sensitive setting.

In the iceberg java and iceberg-rust's code, the expression itself doesn't need to Bind from expr naming to a specific structure.

Term

In Java's implementation, Term has the derivation below:

interface Term;
interface Unbound {
  Bounded Bind(Schema, caseSensitive);
  NamedReference<?> ref();
}
class UnboundTerm : Term, Unbound;
class BoundedTerm : Term;

class NamedReference : UnboundTerm;
class UnbounedTransform : UnboundTerm;
class UnbounedExtract : UnboundTerm;

class BoundReference : BoundTerm;
class BounedTransform : BoundTerm;
class BounedExtract : BoundTerm;

The rust also has bind and Transform, but it uses different way to handle this:

type Term = UnboundedTerm;

Instead, it uses InclusiveProjection to convert the PartitionSpec to a expression, rules may like [3][4]:

1. Create InclusiveProjection
2. Each Transform has a project method, with project the partition expression to the normal expression, and return a Predicate ( unbounded filter )

Reference

In java and rust, Reference implements use similiar way:

1. Unbounded has a "name"
2. Bounded is has (name, accessor, ..)

The accessor of Schema is like "index of vector".

Expression

Expression itself doesn't have any bind logic, it just bind all subfields

Evaluator

TBD

[1] https://github.com/apache/iceberg/tree/e5541de0fd1e850f188ff89cac1417b3ae3500a4/api/src/main/java/org/apache/iceberg/expressions
[2] https://github.com/apache/iceberg-rust/tree/f1e79c0d9c76e90cb4ceb1f2c409ef8d1b68b273/crates/iceberg/src/expr
[3] https://github.com/apache/iceberg-rust/blob/f1e79c0d9c76e90cb4ceb1f2c409ef8d1b68b273/crates/iceberg/src/expr/visitors/inclusive_projection.rs#L85
[4] https://github.com/apache/iceberg-rust/blob/f1e79c0d9c76e90cb4ceb1f2c409ef8d1b68b273/crates/iceberg/src/spec/transform.rs#L471

[Kelvinyu1117]

I think we can follow the design in Rust by using C++ concepts/templates, which provide some kind of compile-time type checking.

Like the following:

template<typename T, size_t N>
struct LogicalExpression {
    public:
        std::array<std::shared_ptr<T>, N> inputs;
};

struct BoundPredicate {
    public:
        enum class PredicateOps {
            True,
            False,
            And,
            Or
        };

        using PredicateT = std::variant<
            LogicalExpression<BoundPredicate, 2>
        >;
        BoundPredicate(PredicateOps op, PredicateT predicate)
            : op_(op), predicate_(predicate) {}

        BoundPredicate(const BoundPredicate&) = default;
        BoundPredicate(BoundPredicate&&) = default;
        BoundPredicate& operator=(const BoundPredicate&) = default;
        BoundPredicate& operator=(BoundPredicate&&) noexcept = default;

        BoundPredicate And(const BoundPredicate& that) {
            return BoundPredicate(
                    PredicateOps::And, 
                    LogicalExpression<BoundPredicate, 2>{
                        std::make_shared<BoundPredicate>(op_, predicate_), 
                        std::make_shared<BoundPredicate>(that)
                    });
        }
    private:
        PredicateOps op_;
        PredicateT predicate_;
        
};

The PredicateOps can be just a subset of values of the enum Expression::Operation.
But the style looks quite different from the existing codebase.

[mapleFU]

I'm not sure using same structure here is a good way. enum in rust is well optimized and easily supported. In iceberg, Expression itself is not a bottleneck, and a derive-based implemention might be more clear and easier to implemented

[Kelvinyu1117]

The enum class in C++ is just a int with strong typed (like enum class : uint8_t). Understand that a derive-based implementation might be easier to read. Using C++ templates and concepts is mainly for enforcing as many compile-time checks as possible, and more generic as well, so that we can try to catch more mistakes during compilation, similar to Rust.

[zhjwpku]

#177 has been merged to main, I think this issue can be closed.