布尔表达式检索是广告受众定向的检索问题，本文从基础概念和方法出发，结合实际案例，深入浅出地阐述了布尔表达式检索的作用以及用法。
广告主投放广告的本质是流量的采买，所以广告主在投放时会选择自身角度的潜在用户群，也就是当代广告的受众定向售卖方式。现在的广告系统对于大数据量处理及实时性都有着极高的要求，当用户发起广告请求时，广告引擎如何快速筛选出符合定向条件的广告，让索引设计变得极为关键。
基础概念
这里的定向条件用布尔表达式进行表示：
a1=｛age∈（20）∩gender∈（female）｝∪｛age∈（25）∩geo∈（一线）｝
这里的形式即为析取范式（Disjunctive Normal Form，DNF）
每个DNF都可以分解成一个或者多个交集（conjunction），即age∈（25）∩geo∈（一线）
每个交集进一步分解成一个或者多个赋值集（assignment），即age∈（25），geo∈（一线）
双层索引结构设计
算法会维护一个两层的倒排索引，即conjunction-ad，attribute-conjunction。
实际检索过程中：
通过assignment筛选出满足条件的 conjunction，再根据conjunction找出满足条件的广告集合。
下面就是一步一步的举例过程！
Ad1：age∈（20）
Ad2：age∈（20）∩ gender∈（female）
Ad3：age∈（20）∩ geo∈（一线）
Ad4：age∈（20）∩ gender∈（female）∩geo∈（一线）
Ad5：age∈（20）∩ gender∈（female）∩geo∈（一线）
Ad6：age∈（20）∩ geo∈（一线）∩ mobile∉（apple）
Ad7：age∈（20）∩ gender∈（female）∩mobile∈（apple）
对应有6种定向条件，将定向条件编辑如下（其中size表示其中含有几个assignment）：
Conjunction1：age∈（20），size1
Conjunction2：age∈（20）∩ gender∈（female），size2
Conjunction3：age∈（20）∩geo∈（一线），size2
Conjunction4：age∈（20）∩gender∈（female）∩ geo∈（一线），size3
Conjunction5：age∈（20）∩geo∈（一线）∩ mobile∉（apple），size3
Conjunction6：age∈（20）∩gender∈（female）∩mobile∈（apple），size3
则可以建立从conjunction到ad的第一层倒排索引：
Conjunction1：Ad1
Conjunction2：Ad2
Conjunction3：Ad3
Conjunction4：Ad4，Ad5
Conjunction5：Ad6
Conjunction6：Ad7
根据conjunction 的size大小及包含情况建立从attribute到conjunction的第二层倒排索引（标注conjunction是否含有/不含有该assignment）：
Size1：age∈（20），（1，∈）
Size2：
age∈（20），（2，∈）（3，∈）
gender∈（female），（2，∈）
geo∈（一线），（3，∈）
Size3：
age∈（20），（4，∈）（5，∈）（6，∈）
gender∈（female），（4，∈）（6，∈）
geo∈（一线），（4，∈）（5，∈）
mobile∈（apple），（5，∉）（6，∈）
线上请求检索过程
当某次广告请求的定向条件满足某个conjunction，一定满足包含该conjunction的所有广告。如果用size of（query）表示请求中的定向标签个数，如果size of（query）＜size of（conjunction），该conjunction一定不满足要求。可以先利用这个判断减少计算。
当线上有一个用户发起了广告请求，该用户的标签为：
age∈（20）∩geo∈（一线）
因为size of（query）=2，则从size为1和2的conjunction中进行查询
Size=2的查询
age∈（20） （2，∈）（3，∈）
geo∈（一线） （3，∈）
只有Conjunction3满足条件，对应Ad3
Size=1的查询
age∈（20） （1，∈）
只有Conjunction1满足条件，对应Ad1
维度爆炸问题
这里的维度组合并不取决于标签的乘积，即2个性别，100个年龄，34个地理……（2*100*34……），而是取决于广告的规模，假设有100w的广告，每个广告的定向标签都不一样，也只是百万级的检索，并且大量的广告受众定向是重复的，远远小于广告数量。
