Pruning index generation and enhancement

1. A system comprising:

at least one hardware processor; and

at least one memory storing instructions that cause the at least one hardware processor to perform operations comprising:

generating a pruning index comprising a set of filters that index distinct values in each column of a source table organized into a set of batch units, the generating of the pruning index comprising:

generating a filter corresponding to a batch unit in the set of batch units; and

merging rows of the filter until a density threshold is reached, the density threshold being based on a target false positive rate for the pruning index; and

storing, in a database, the pruning index with an association with the source table.

2. The system of claim 1 , wherein the filter is represented as an array with multiple dimensions in the pruning index.

3. The system of claim 1 , wherein the generating of the filter comprises:

for a given data value,

identifying a cell within the filter based on the data value;

generating a hash value based on the data value; and

populating the cell in the filter using the hash value.

4. The system of claim 3 , wherein the operations further comprise computing a number of levels in the filter;

wherein the identifying of the cell comprises:

identifying a slice in the filter based on the data value and the number of levels in the filter; and

identifying a filter column based on the data value and a number of filter columns in the filter.

5. The system of claim 1 , wherein:

each filter of the set of filters comprises multiple bloom filters, a number of bloom filters in each filter being based on a target false positive rate.

6. The system of claim 1 , wherein:

each filter in the set of filters comprises a set of bloom filters; and

the pruning index further comprises a plurality of columns, the plurality of columns comprising a batch unit identifier column, a slice number column, and the set of bloom filters.

7. The system of claim 6 , further comprising:

clustering the pruning index based on the slice number column.

8. The system of claim 7 , wherein the operations further comprise:

detecting a change to the source table;

generating one or more additional rows for the pruning index based on the change to the source table; and

reclustering the pruning index based on slice numbers.

9. The system of claim 1 , wherein the operations further comprise:

processing a query using the pruning index, the processing of the query comprising:

identifying, using the pruning index, a sub-set of batch units to scan for data matching the query; and

scanning only the sub-set of batch units of the source table to identify data matching the query.

10. The system of claim 9 , wherein the processing of the query using the pruning index comprises:

generating a hash value based on an equality predicate included in the query;

identifying one or more values in the pruning index that match the hash value; and

identifying one or more batch units that potentially satisfy the equality predicate based on the one or more values in the pruning index that match the hash value.

11. The system of claim 9 , wherein the identifying of the sub-set of batch units to scan for the data matching the query comprises identifying one or more batch units in which data matching the query is not stored.

12. The system of claim 9 , wherein the identifying of the sub-set of batch units to scan for the data matching the query comprises identifying one or more batch units in which data matching the query is potentially stored.

13. A method comprising:

generating, by at least one hardware processor, a pruning index comprising a set of filters that index distinct values in each column of a source table organized into a set of batch units, the generating of the pruning index comprising:

generating a filter corresponding to a batch unit in the set of batch units; and

merging rows of the filter until a density threshold is reached, the density threshold being based on a target false positive rate for the pruning index; and

storing, in a database, the pruning index with an association with the source table.

14. The method of claim 13 , wherein the filter is represented as an array with multiple dimensions in the pruning index.

15. The method of claim 13 , wherein the generating of the filter comprises:

for a given data value,

identifying a cell within the filter based on the data value;

generating a hash value based on the data value; and

populating the cell in the filter using the hash value.

16. The method of claim 13 , wherein:

each filter in the set of filters comprises a set of bloom filters; and

the pruning index further comprises a plurality of columns, the plurality of columns comprising a batch unit identifier column, a slice number column, and the set of bloom filters; and

the method further comprises clustering the pruning index based on the slice number column.

17. The method of claim 16 , further comprising:

detecting a change to the source table;

generating one or more additional rows for the pruning index based on the change to the source table; and

reclustering the pruning index based on slice numbers.

18. The method of claim 17 , wherein detecting the change to the source table comprises at least one of:

detecting a new row being added to the source table; and

detecting an existing row being removed from the source table.

19. The method of claim 13 , further comprising:

processing a query using the pruning index, the processing of the query comprising:

identifying, using the pruning index, a sub-set of batch units to scan for data matching the query; and

scanning only the sub-set of batch units of the source table to identify data matching the query.

20. A computer-storage medium comprising instructions that, when executed by one or more processors of a machine, configure the machine to perform operations comprising:

generating a pruning index comprising a set of filters that index distinct values in each column of a source table organized into a set of batch units, the generating of the pruning index comprising:

generating a filter corresponding to a batch unit in the set of batch units; and

merging rows of the filter until a density threshold is reached, the density threshold being based on a target false positive rate for the pruning index; and

storing, in a database, the pruning index with an association with the source table.