Dynamic diagonal search in databases

• US 10,417,229 B2
• Filed: 06/27/2017
• Issued: 09/17/2019
• Est. Priority Date: 06/27/2017
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Uthappa, Mandanna Mandechanda
• Primary Examiner(s): Le, Thu Nguyet T
• Application Number:
  US15/633,757
• Publication Number:
  US 20180373759A1
• Time in Patent Office: 812 Days
• Field of Search: 707718, 707713
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A query identifier is generated for a query received in a database. The received query identifier is matched with query identifiers stored in a dynamic table. It is determined whether an execution plan is available based on matching the query identifiers in the dynamic table. For the matching query identifier, it is determined whether dynamic search criteria are met. Upon determining that the dynamic search criteria are met, a memory address corresponding to the query identifier is retrieved from the dynamic table. Based on the available diagonal search execution plan, the dynamic diagonal search is performed in the table from the memory address to retrieve search result. The dynamic diagonal search involves incrementing a data pointer to access the memory address in a diagonal manner in the table.

Claims

1. A non-transitory computer-readable medium to store instructions, which when executed by a computer, cause the computer to perform operations comprising:

generate a query identifier for a query received in a database;

match the received query identifier with query identifiers stored in a dynamic table;

based on matching the query identifier, determine whether a diagonal search execution plan is available; and

based on the available diagonal search execution plan, perform a dynamic diagonal search in a table in the database to retrieve a search result, wherein the dynamic diagonal search involves incrementing a data pointer to access a subsequent memory address in a diagonal manner.

2. The non-transitory computer-readable medium of claim 1, further comprises instructions which when executed by the computer further cause the computer to:

for the matching query identifier, determine whether a dynamic search criteria are met;

upon determining that the dynamic search criteria are met, retrieve a memory address corresponding to the query identifier from the dynamic table; and

based on the available diagonal search execution plan, perform the dynamic diagonal search in the table from the memory address to retrieve search result.

3. The non-transitory computer-readable medium of claim 1, further comprises instructions which when executed by the computer further cause the computer to:

upon determining that the diagonal search execution plan is not available, perform search in the table with a default search logic to retrieve the search result.

4. The non-transitory computer-readable medium of claim 1, wherein the execution plan further comprises instructions which when executed by the computer further cause the computer to:

perform the dynamic diagonal search as a main thread in a columnar table, wherein the dynamic diagonal search inherently initiates multiple parallel threads of column search on individual columns in the columnar table; and

retrieve the search result from the columnar table.

5. The non-transitory computer-readable medium of claim 1, further comprises instructions which when executed by the computer further cause the computer to:

perform the dynamic diagonal search as a main thread in a row store table, wherein the dynamic diagonal search inherently initiates multiple parallel threads of row search on specific range of rows in the row store table; and

retrieve the search result from the columnar table.

6. The non-transitory computer-readable medium of claim 2, further comprises instructions which when executed by the computer further cause the computer to:

upon determining that the dynamic search criteria are met, increment a count corresponding to the query identifier in the dynamic table; and

generate a heat map of the database based on the count, wherein a threshold associated with the count indicates a frequency pattern of a value associated with the memory address in the heat map.

7. The non-transitory computer-readable medium of claim 6, further comprises instructions which when executed by the computer further cause the computer to:

defragment the values based on the frequency pattern in the heat map by moving the value to a contiguous memory address.

8. A computer-implemented method of dynamic diagonal search in a database, the method comprising:

generating a query identifier for a query received in a database;

matching the received query identifier with query identifiers;

based on matching the query identifier, determining whether a diagonal search execution plan is available; and

based on the available diagonal search execution plan, performing a dynamic diagonal search in a table in the database to retrieve a search result, wherein the dynamic diagonal search involves incrementing a data pointer to access a subsequent memory address in a diagonal manner.

9. The method of claim 8, further comprising:

for the matching query identifier, determining whether a dynamic search criteria are met;

upon determining that the dynamic search criteria are met, retrieving a memory address corresponding to the query identifier from the dynamic table; and

based on the available diagonal search execution plan, performing the dynamic diagonal search in the table from the memory address to retrieve search result.

10. The method of claim 8, further comprising:

upon determining that the diagonal search execution plan is not available, performing search in the table with a default search logic to retrieve the search result.

11. The method of claim 8, further comprising:

performing the dynamic diagonal search as a min thread in a columnar table, wherein the dynamic diagonal search inherently initiates multiple parallel threads of column search on individual columns in the columnar table; and

retrieving the search result from the columnar table.

12. The method of claim 8, further comprising:

performing the dynamic diagonal search as a main thread in a row store table, wherein the dynamic diagonal search inherently initiates multiple parallel threads of row search on specific range of rows in the row store table; and

retrieving the search result from the columnar table.

13. The method of claim 9, further comprising:

upon determining that the dynamic search criteria are met, incrementing a count corresponding to the query identifier in the dynamic table; and

generating a heat map of the database based on the count, wherein a threshold associated with the count indicates a frequency pattern of a value associated with the memory address in the heat map.

14. The method of claim 13, further comprising:

defragmenting the values based on the frequency pattern in the heat map by moving the value to a contiguous memory address.

15. A computer system for dynamic diagonal search in databases, comprising:

a computer memory to store program code; and

a processor to execute the program code to;

generate a query identifier for a query received in a database;

match the received query identifier with query identifiers stored in a dynamic table;

based on matching the query identifier, determine whether a diagonal search execution plan is available; and

based on the available diagonal search execution plan, perform a dynamic diagonal search in a table in the database to retrieve a search result, wherein the dynamic diagonal search involves incrementing a data pointer to access a subsequent memory address in a diagonal manner.

16. The system of claim 15, wherein the processor further executes the program code to:

for the matching query identifier, determine whether a dynamic search criteria are met;

upon determining that the dynamic search criteria are met, retrieve a memory address corresponding to the query identifier from the dynamic table; and

based on the available diagonal search execution plan, perform the dynamic diagonal search in the table from the memory address to retrieve search result.

17. The system of claim 15, wherein the processor further executes the program code to:

upon determining that the diagonal search execution plan is not available, perform search in the table with a default search logic to retrieve the search result.

18. The system of claim 15, wherein the processor further executes the program code to:

perform the dynamic diagonal search as a main thread in a columnar table, wherein the dynamic diagonal search inherently initiates multiple parallel threads of column search on individual columns in the columnar table; and

retrieve the search result from the columnar table.

19. The system of claim 18, wherein the processor further executes the program code to:

perform the dynamic diagonal search as a main thread in a row store table, wherein the dynamic diagonal search inherently initiates multiple parallel threads of row search on specific range of rows in the row store table; and

retrieve the search result from the columnar table.

20. The system of claim 16, wherein the processor further executes the program code to:

upon determining that the dynamic search criteria are met, increment a count corresponding to the query identifier in the dynamic table; and

generate a heat map of the database based on the count, wherein a threshold associated with the count indicates a frequency pattern of a value associated with the memory address in the heat map.