In some embodiments, a method receives a packet at an instance of a distributed firewall associated with one of a plurality of workloads running on a hypervisor. Each of the plurality of workloads has an associated instance of the distributed firewall. An index table is accessed for the workload where the index table includes a set of references to a set of rules in a rules table. Each workload in the plurality of workloads is associated with an index table that references rules that are applicable to each respective workload. The method then accesses at least one rule in a set of rules associated with the set of references from the rules table and compares one or more attributes for the packet to information stored for the at least one rule in the set of rules to determine a rule in the set of rules to apply to the packet.