Efficient indexing for querying arrays in databases

1. A method for optimizing queries of databases, the method comprising:

storing, by a database system, a set of documents comprising a plurality of fields, the plurality of fields including an array field, wherein the array field stores an array including a first instance of a value and a second instance of the value for a document from the set of documents;

generating, by the database system, a de-duplication index corresponding to the array field including a unique entry for the value, the unique entry including an identifier of the document;

generating, by the database system, a conventional index corresponding to the array field including a first entry for the first instance of the value and a second entry for the second instance of the value, the first and second entry including the identifier of the document;

receiving, by the database system from a client device, a query statement for querying a database, the query statement specifying the value;

querying the database based on the query statement, the querying comprising:

comparing the de-duplication index and the conventional index based on a set of optimization criteria, wherein the comparison includes comparing costs associated with executing the query statement using the de-duplication index and the conventional index;

selecting, based on the comparison, the de-duplication index; and

retrieving, using the de-duplication index, the document from the database; and

providing the document to the client device.

2. The method of claim 1 , wherein the array field stores a second array including the value for a second document from the set of documents, and the unique entry of the de-duplication index further includes an identifier of the second document.

3. The method of claim 2 , wherein the plurality of fields includes a second field which stores a second value for the second document, and further comprising:

generating, by the database system, a second de-duplication index corresponding to the second field including a second unique entry for the second value, the second unique entry including an identifier of the second document;

receiving, by the database system, a second query statement for querying the database, the second query statement specifying the value and the second value;

querying the database based on the second query statement, the querying comprising:

retrieving, using the de-duplication index and the second de-duplication index, the second document from the database; and

providing the second document to the client device.

4. The method of claim 3 , wherein generating the first and second de-duplication indexes comprises:

generating a multi-field de-duplication index for the array field and the second field, the multi-field de-duplication index including the first and second de-duplication indexes.

5. The method of claim 4 , wherein the second query statement includes:

a first filter applied to the array field specifying the value;

a second filter applied to the second field specifying the second value; and

a logical operator applied to the first and second filters.

6. The method of claim 5 , wherein executing the second query statement further comprises:

responsive to determining, based on the first filter, the document includes the value using the de-duplication index, receiving first index results including the identifier of the document;

responsive to determining, based on the second filter, the second document includes the second value using the second de-duplication index, receiving second index results the identifier of the second document; and

applying the logical operator to the first and second index results.

7. The method of claim 6 , wherein the first and second index results are represented using a bitmap, and applying the logical operator further comprises:

performing one or more bitwise operations corresponding to the logical operator on the bitmap.

8. The method of claim 1 , wherein selecting the de-duplication index comprises:

determining, based on the optimization criteria, a first cost of executing the query statement using the de-duplication index;

determining, based on the optimization criteria, a second cost of executing the query statement using the conventional index; and

selecting the de-duplication index based on a comparison of the first cost and the second cost.

9. The method of claim 1 , wherein the optimization criteria include a set of rules for selecting an optimal index, and selecting the de-duplication index comprises:

determining, based on the set of rules, the de-duplication index is the optimal index for the query statement relative to the conventional index.

10. The method of claim 1 , wherein retrieving the document further comprises:

generating a set of distinct query plans for querying the database using the de-duplication index;

determining costs corresponding to each query plan of the set of distinct query plans;

selecting, based on the costs, an optimal query plan; and

retrieving the document from the database using the optimal query plan.

11. The method of claim 1 , wherein the de-duplication index corresponds to a field of an object stored by the array field.

12. The method of claim 1 , wherein the query statement is represented using structured query language (SQL).

13. The method of claim 1 , wherein the de-duplication index is an inverted index.

14. A method for optimizing queries of databases, the method comprising:

storing, by a database system, a set of documents comprising a plurality of fields, the plurality of fields including an array field, wherein the array field stores arrays including a value for a plurality of documents from the set of documents;

receiving, by the database system from a client device, a query statement for querying a database, the query statement specifying the value;

identifying a de-duplication index based on a cost of executing the query statement using the de-duplication index, the de-duplication index corresponding to the array field including a unique entry for the value, the unique entry including a plurality of respective identifiers for the plurality of documents;

retrieving, using the de-duplication index, a document from the plurality of documents including the value stored by the array field from the database; and

providing the retrieved document to the client device.

15. The method of claim 14 , wherein the plurality of fields includes a second array field which stores a second value for a second plurality of documents from the set of documents, and further comprising:

receiving, by the database system, a second query statement for querying the database, the second query statement specifying the value and the second value;

determining a second de-duplication index corresponding to the second array field including a unique entry for the second value, the unique entry for the second value including a plurality of respective identifiers for the second plurality of documents;

retrieving, using the de-duplication index and the second de-duplication index, a second document included in the second plurality of documents from the database, the second document including the second value stored by the field; and

providing the second document to the client device.

16. The method of claim 15 , wherein generating the first and second de-duplication indexes comprises:

generating a multi-field de-duplication index for the array field and the second field, the multi-field de-duplication index including the first and second de-duplication indexes.

17. The method of claim 14 , wherein identifying the de-duplication index comprises:

determining a cost of executing the query statement using the de-duplication index based on a set of optimization criteria, the set of optimization criteria including comparing costs associated with query execution plans for executing the query statement using the de-duplication index; and

selecting the de-duplication index based on the cost.

18. The method of claim 14 , wherein retrieving the document further comprises:

generating a set of distinct query plans for querying the database using the de-duplication index;

determining costs corresponding to each query plan of the set of distinct query plans;

selecting, based on the costs, an optimal query plan; and

retrieving the document from the database using the optimal query plan.

19. A non-transitory computer readable storage medium storing instructions that when executed by a computer processor, cause the computer processor to perform the steps comprising:

storing, by a database system, a set of documents comprising a plurality of fields, the plurality of fields including an array field, wherein the array field stores an array including a first instance of a value and a second instance of the value for a document from the set of documents;

generating, by the database system, a de-duplication index corresponding to the array field including a unique entry for the value, the unique entry including an identifier of the document;

generating, by the database system, a conventional index corresponding to the array field including a first entry for the first instance of the value and a second entry for the second instance of the value, the first and second entry including the identifier for the document;

receiving, by the database system from a client device, a query statement for querying a database, the query statement specifying the value;

querying the database based on the query statement, the querying comprising:

comparing the de-duplication index and the conventional index based on a set of optimization criteria, wherein the comparison includes comparing costs associated with executing the query statement using the de-duplication index and the conventional index;

selecting, based on the comparison, the de-duplication index; and

retrieving, using the de-duplication index, the document from the database; and

providing the document to the client device.

20. The non-transitory computer readable storage medium of claim 19 , wherein the array field stores a second array including the value for a second document from the set of documents, and the unique entry of the de-duplication index further includes an identifier of the second document.