Filter evaluation in a database system

A computer-implemented method of processing a query in a database management system, the query defining a set of filter parameters and at least one Boolean operator, the method comprising:

• evaluating the set of filter parameters and the at least one Boolean operator, the set of filter parameters and the at least one Boolean operator being represented by a filter tree comprising a plurality of nodes of at least one parent node having a said Boolean operator and at least one child node having a said filter parameter, the evaluating comprising:
• transforming the filter tree by:
• replacing any parent node that has a single child node with said single child node;
• and
• replacing any parent node that has at least one child node and that contains the same filter parameter as its own parent node, with the at least one child node of that parent node;
• such that each parent node has a plurality of child nodes that do not contain the same filter parameter as said parent node;
• traversing the transformed filter tree by, for each node of the plurality of nodes:
• identifying whether said node is a root of a sub-tree comprising other nodes of the transformed filter tree;
• generating a cost for said node by processing a sample input comprising a plurality of data items of a data source using the filter parameter and measuring the time taken for the plurality of data items to be processed, wherein if said node is identified as a root of a sub-tree, said cost is also based on a determined cost and selectivity of the other nodes of the sub-tree;
• and
• determining a selectivity of said node based on an output of its filter parameter as a result of processing the sample input using the filter parameter;
• re-ordering at least some of the plurality of nodes of the transformed filter tree having the same parent node based on their relative costs and selectivities to generate a re-ordered filter tree for the set of filter parameters;
• and
• processing a second input comprising a predetermined number of different data items of the data source against the re-ordered filter tree in order to generate an output representative of at least one data item of the different data items that satisfies each of the filter parameters of the re-ordered filter tree;
• and
• generating a query response that includes the output.