Database system utilizing probabilistic indexing
A database system operates by: storing a plurality of variable-length data of a column of a plurality of rows; storing a plurality of fixed-length index values of a probabilistic indexing scheme for the column; and identifying a filtered subset of the plurality of rows having variable-length data of the column equal to a given value based on: identifying a first subset of rows as a proper subset of the plurality of rows based on the plurality of fixed-length index values; and comparing the variable-length data of only rows in the first subset of rows to the given value to identify the filtered subset as a subset of the first subset of rows.
1. A method for execution by at least one processor of a database system, comprising:
storing a plurality of variable-length data of a column of a plurality of rows;
storing a plurality of fixed-length index values of a probabilistic indexing scheme for the column; and
identifying a filtered subset of the plurality of rows having variable-length data of the column equal to a given value based on:
identifying a first subset of rows as a proper subset of the plurality of rows based on the plurality of fixed-length index values; and
comparing the variable-length data of only rows in the first subset of rows to the given value to identify the filtered subset as a subset of the first subset of rows.
2. The method of claim 1 , wherein identifying the filtered subset of the plurality of rows is further based on:
reading a set of variable-length data based on reading the variable-length data from only rows in the first subset of rows;
wherein comparing the variable-length data of only the rows in the first subset of rows to the given value is based on utilizing only variable-length data in the set of variable-length data.
3. The method of claim 1 , wherein the variable-length data is implemented via one of: a string datatype or a varchar datatype.
4. The method of claim 1 , wherein a set difference between the filtered subset and the first subset of rows is non-null.
5. The method of claim 1 , wherein the probabilistic indexing scheme for the column is an inverted indexing scheme, and wherein the first subset of rows are identified based on inverted index values of the inverted indexing scheme.
6. The method of claim 1 , wherein the plurality of fixed-length index values of the probabilistic indexing scheme are a plurality of hash values computed by performing a hash function on corresponding variable-length data of the column.
7. The method of claim 6 , wherein identifying the filtered subset of the plurality of rows includes:
computing a first hash value for the given value; and
identifying ones of the plurality of rows having corresponding ones of the plurality of hash value equal to the first hash value.
8. The method of claim 7 , wherein a set difference between the first subset of rows and the filtered subset includes ones of the plurality of rows with variable-length data of the column having hash collisions with the given value.
9. The method of claim 6 , wherein the fixed-length is based on a false-positive tuning parameter of the hash function, wherein a first number of rows included in the first subset of rows is based on the false-positive tuning parameter of the hash function, and wherein a second number of rows included in a set difference between the first subset of rows and the filtered subset is based on the tuning parameter of the hash function.
10. The method of claim 9 , further comprising:
determining the false-positive tuning parameter as a selected false-positive tuning parameter from a plurality of false-positive tuning parameter options.
11. The method of claim 1 , wherein identifying the filtered subset of the plurality of rows includes applying at least one probabilistic index-based IO construct of an IO pipeline generated for a query indicating the given value in at least one query predicate.
12. A query processing system includes:
at least one processor; and
a memory that stores operational instructions that, when executed by the at least one processor, cause the query processing system to perform operations that include:
storing a plurality of variable-length data of a column of a plurality of rows;
storing a plurality of fixed-length index values of a probabilistic indexing scheme for the column; and
identifying a filtered subset of the plurality of rows having variable-length data of the column equal to a given value based on:
identifying a first subset of rows as a proper subset of the plurality of rows based on the plurality of fixed-length index values; and
comparing the variable-length data of only rows in the first subset of rows to the given value to identify the filtered subset as a subset of the first subset of rows.
13. The query processing system of claim 12 , wherein identifying the filtered subset of the plurality of rows is further based on:
reading a set of variable-length data based on reading the variable-length data from only rows in the first subset of rows;
wherein comparing the variable-length data of only the rows in the first subset of rows to the given value is based on utilizing only variable-length data in the set of variable-length data.
14. The query processing system of claim 12 , wherein the variable-length data is implemented via one of: a string datatype or a varchar datatype.
15. The query processing system of claim 12 , wherein a set difference between the filtered subset and the first subset of rows is non-null.
16. The query processing system of claim 12 , wherein the probabilistic indexing scheme for the column is an inverted indexing scheme, and wherein the first subset of rows are identified based on inverted index values of the inverted indexing scheme.
17. The query processing system of claim 12 , wherein the plurality of fixed-length index values of the probabilistic indexing scheme are a plurality of hash values computed by performing a hash function on corresponding variable-length data of the column.
18. The query processing system of claim 17 , wherein identifying the filtered subset of the plurality of rows includes:
computing a first hash value for the given value; and
identifying ones of the plurality of rows having corresponding ones of the plurality of hash value equal to the first hash value;
wherein a set difference between the first subset of rows and the filtered subset includes ones of the plurality of rows with variable-length data of the column having hash collisions with the given value.
19. The query processing system of claim 17 , wherein the fixed-length is based on a false-positive tuning parameter of the hash function, wherein a first number of rows included in the first subset of rows is based on the false-positive tuning parameter of the hash function, and wherein a second number of rows included in a set difference between the first subset of rows and the filtered subset is based on the tuning parameter of the hash function.
20. A non-transitory computer readable storage medium comprises:
at least one memory section that stores operational instructions that, when executed by a processing module that includes a processor and a memory, causes the processing module to:
store variable-length data of a column of a plurality of rows;
store a plurality of fixed-length index values of a probabilistic indexing scheme for the column; and
identify a filtered subset of the plurality of rows having variable-length data of the column equal to a given value based on:
identifying a first subset of rows as a proper subset of the plurality of rows based on the plurality of fixed-length index values; and
comparing the variable-length data of only rows in the first subset of rows to the given value to identify the filtered subset as a subset of the first subset of rows.