Queries for thin database indexing

Patent metadata

Field	Value
Publication number	US-9292553-B2
Application number	US-201313971735-A
Country	US
Kind code	B2
Filing date	Aug 20, 2013
Priority date	Aug 20, 2013
Publication date	Mar 22, 2016
Grant date	Mar 22, 2016

Abstract

A method of database indexing is disclosed. Two functions (f and g) from row values to row number values are set. The functions are utilized to determine a row number in a database column containing a target search value, wherein the target search value comprises a search value being sought in the database column. A candidate row number variable is set initially to the function g of the target search value by a processor. Iteratively the following is performed: a current value of the candidate row number variable is used as an address to read a value in a corresponding row in the database column, and the current value of the candidate row number variable is updated to the function f of the most recently read value in a corresponding row in the database column.

First claim

What is claimed is:

1. A method of finding data in a database, comprising:
determining a row number in a database of a row that has a column that contains a target search value, wherein the target search value comprises a search value being sought in the database column, comprising:
determining an initial candidate row number from the target search value by a processor,
iteratively determining a subsequent candidate row number from a current candidate row number until the row of the database having the subsequent candidate row number has an encoded column value matching the initial candidate row number, including:
determining whether an encoded column value in the current candidate row number of the database column corresponds to a special element of a plurality of special elements,
if the encoded column value in the current candidate row number of the database column does not correspond to a special element, updating the current candidate row number by applying a permutation function f to the encoded column value in the current candidate row number in the database column, wherein the permutation function f converts row numbers to encoded column values, and
if the encoded column value in the current candidate row number of the database column corresponds to a special element, updating the current candidate row number to a subsequent candidate row number associated with the special element instead of updating the current candidate row number using the permutation function f; and

providing the subsequent candidate row number having the encoded column value matching the initial candidate row number.

2. The method of claim 1 , wherein the permutation function f is an invertible function.

3. The method of claim 1 , wherein determining the initial candidate row number comprises applying a function g to the target search value, wherein the function g converts target search values to initial candidate row numbers.

4. The method of claim 1 , wherein applying the permutation function f to a row number generates a subsequent value of a permutation cycle.

5. The method of claim 1 , wherein applying the permutation function f to a row number can be performed in memory without accessing other database content.

6. The method of claim 1 , further comprising:
receiving a request for row information having the target search value; and
wherein providing the current candidate row number having the encoded column value matching the initial candidate row number is performed in response to receiving the request.

7. The method of claim 1 , further comprising generating the special elements in a permutation cycle defined by the permutation function f, including generating at least a threshold value L special elements distributed throughout elements of the permutation cycle.

8. The method of claim 7 , further comprising:
generating an additional shortcuts in the permutation cycle for any sequence of elements of the permutation cycle that does not have a special element and that is longer than a predetermined threshold value S.

9. The method of claim 1 , further comprising:
receiving a database query; and
determining the target search value based on the database query.

10. The method of claim 1 , further comprising:
maintaining a conversion table between original column values and encoded column values.

11. The method of claim 1 , wherein original column values in the database column are encoded as encoded values of a permutation cycle.

12. The method of claim 1 , wherein the permutation function f is chosen randomly from a set of candidate permutation functions.

13. The method of claim 1 , further comprising retrieving, from the database, an entire row having an encoded column value matching the initial candidate row number.

14. A system for database indexing, the system comprising:
one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
determining a row number in a database of a row that has a column that contains a target search value, wherein the target search value comprises a search value being sought in the database column, comprising:
determining an initial candidate row number from the target search value,
iteratively determining a subsequent candidate row number from a current candidate row number until the row of the database having the subsequent candidate row number has an encoded column value matching the initial candidate row number, including:
determining whether an encoded column value in the current candidate row number of the database column corresponds to a special element of a plurality of special elements,
if the encoded column value in the current candidate row number of the database column does not correspond to a special element, updating the current candidate row number by applying a permutation function f to the encoded column value in the current candidate row number in the database column, wherein the permutation function f converts row numbers to encoded column values, and
if the encoded column value in the current candidate row number of the database column corresponds to a special element, updating the current candidate row number to a subsequent candidate row number associated with the special element instead of updating the current candidate row number using the permutation function f; and

providing the subsequent candidate row number having the encoded column value matching the initial candidate row number.

15. The system of claim 14 , wherein the permutation function f is an invertible function.

16. The system of claim 14 , wherein determining the initial candidate row number comprises applying a function g to the target search value, wherein the function g converts target search values to initial candidate row numbers.

17. The system of claim 14 , wherein applying the permutation function f to a row number generates a subsequent value of a permutation cycle.

18. The system of claim 14 , wherein applying the permutation function f to a row number can be performed in memory without accessing other database content.

19. The system of claim 14 , wherein the operations further comprise:
receiving a request for row information having the target search value; and
wherein providing the current candidate row number having the encoded column value matching the initial candidate row number is performed in response to receiving the request.

20. The system of claim 14 , wherein the operations further comprise generating the special elements in a permutation cycle defined by the permutation function f, including generating at least a threshold value L special elements distributed throughout elements of the permutation cycle.

21. The system of claim 20 , wherein the operations further comprise:
generating an additional shortcuts in the permutation cycle for any sequence of elements of the permutation cycle that does not have a special element and that is longer than a predetermined threshold value S.

22. The system of claim 14 , wherein the operations further comprise:
receiving a database query; and
determining the target search value based on the database query.

23. The system of claim 14 , wherein the operations further comprise maintaining a conversion table between original column values and encoded column values.

24. The system of claim 14 , wherei

Assignees

• Pivotal Software Inc

Inventors

• Brand Michael

Classifications

• G06F16/2228 Primary

  Indexing structures · CPC title

• G06F16/2272

  Management thereof · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F16/31

  Indexing; Data structures therefor; Storage structures · CPC title