DATA PARTITIONING AND ORDERING

• US 20160335304A1
• Filed: 05/14/2016
• Published: 11/17/2016
• Est. Priority Date: 05/14/2015
• Status: Active Grant

• Current Assignee: Deephaven Data Labs, LLC
• Original Assignee: Walleye Software LLC
• Inventors: Teodorescu, Radu, Caudy, Ryan, Kent, David R. IV, Wright, Charles
• Granted Patent: US 10,353,893 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/1483 using an access-table, e.g. matrix or list
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/144 Query formulation
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2291 : User-Defined Types; Storage management thereof
• CPC Class Codes: G06F 16/23 : Updating
• CPC Class Codes: G06F 16/2308 : Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2358 : Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 : Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/2372 : Updates performed during offline database operations
• CPC Class Codes: G06F 16/2379 : Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/242 : Query formulation
• CPC Class Codes: G06F 16/2428 : Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/245 : Query processing
• CPC Class Codes: G06F 16/2453 : Query optimisation
• CPC Class Codes: G06F 16/24534 : Query rewriting; Transformation
• CPC Class Codes: G06F 16/24535 : of sub-queries or views
• CPC Class Codes: G06F 16/24537 : of operators
• CPC Class Codes: G06F 16/24539 : using cached or materialised query results
• CPC Class Codes: G06F 16/2455 : Query execution
• CPC Class Codes: G06F 16/24553 : of query operations
• CPC Class Codes: G06F 16/2456 : Join operations
• CPC Class Codes: G06F 16/24561 : Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06F 16/2457 : with adaptation to user needs
• CPC Class Codes: G06F 16/24575 : using context
• CPC Class Codes: G06F 16/248 : Presentation of query results
• CPC Class Codes: G06F 16/254 : Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/27 : Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/278 : Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/285 : Clustering or classification
• CPC Class Codes: G06F 16/9024 : Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/907 : Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 : Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 : Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 : Presentation of query results
• CPC Class Codes: G06F 16/9566 : URL specific, e.g. using aliases, detecting broken or misspelled links
• CPC Class Codes: G06F 16/9574 : of access to content, e.g. by caching
• CPC Class Codes: G06F 17/40 : Data acquisition and logging for input to computer G06F3/00
• CPC Class Codes: G06F 21/00 : Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
• CPC Class Codes: G06F 21/6209 : to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 2201/805 : Real-time
• CPC Class Codes: G06F 2201/84 : Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2212/1052 : Security improvement
• CPC Class Codes: G06F 2212/154 : Networked environment
• CPC Class Codes: G06F 2212/163 : Server or database system
• CPC Class Codes: G06F 2212/60 : Details of cache memory
• CPC Class Codes: G06F 3/0481 : based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 3/0482 : Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/0483 : Interaction with page-structured environments, e.g. book metaphor
• CPC Class Codes: G06F 3/04847 : Interaction techniques to control parameter settings, e.g. interaction with sliders or dials
• CPC Class Codes: G06F 3/0485 : Scrolling or panning
• CPC Class Codes: G06F 3/04895 : Guidance during keyboard input operation, e.g. prompting
• CPC Class Codes: G06F 3/0605 : by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0656 : Data buffering arrangements
• CPC Class Codes: G06F 3/067 : Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 40/117 : Tagging; Marking up details of markup languages G06F40/143; Designating a block; Setting of attributes style sheets, e.g. eXtensible Stylesheet Language Transformation [XSLT], G06F40/154
• CPC Class Codes: G06F 40/134 : Hyperlinking
• CPC Class Codes: G06F 40/166 : Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/174 : Form filling; Merging
• CPC Class Codes: G06F 40/177 : of tables; using ruled lines
• CPC Class Codes: G06F 40/18 : of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06F 40/183 : Tabulation, i.e. one-dimensional positioning
• CPC Class Codes: G06F 40/216 : using statistical methods
• CPC Class Codes: G06F 40/274 : Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 8/30 : Creation or generation of source code
• CPC Class Codes: G06F 8/41 : Compilation
• CPC Class Codes: G06F 8/427 : Parsing
• CPC Class Codes: G06F 8/60 : Software deployment
• CPC Class Codes: G06Q 40/04 : Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: H04L 12/18 : for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 51/046 : Interoperability with other network applications or services
• CPC Class Codes: H04L 51/212 : using filtering or selective blocking
• CPC Class Codes: H04L 61/5069 : for group communication, multicast communication or broadcast communication
• CPC Class Codes: H04L 63/101 : Access control lists [ACL]
• CPC Class Codes: H04L 63/102 : Entity profiles
• CPC Class Codes: H04L 67/01 : Protocols
• CPC Class Codes: H04L 67/1001 : for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/141 : Setup of application sessions admission control or resource allocation in data switching networks H04L47/70
• CPC Class Codes: H04L 67/34 : involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 67/56 : Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/566 : Grouping or aggregating service requests, e.g. for unified processing
• CPC Class Codes: H04L 67/568 : Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/5681 : Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 69/16 : Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

Described are methods, systems and computer readable media for data partitioning and ordering.

Claims

1. A method for storing ordered data in a computer data system, the method comprising:

receiving an electronic message containing one or more data items;

storing the received data items to a first set of one or more first partitions as first stored data in a first electronic data storage device;

remapping the data items stored in the first set of partitions to a second set of one or more second partitions in a second electronic data storage device, each of the second partitions having a respective grouping;

storing the remapped first stored data as second stored data in the second set of partitions in a second electronic data storage device according to the respective grouping;

sorting each second partition of the second set of partitions according to a strict ordering to generate ordered second partitions; and

storing the ordered second partitions in the second electronic data storage device so as to maintain the strict ordering.

2. The method of claim 1, further comprising:

organizing each ordered second partition into one or more groups having one or more grouping levels based on one or more column values, wherein the organizing includes generating grouping metadata associated with the respective ordered second partition.

3. The method of claim 1, wherein the each second partition of the second set of partitions corresponds to a directory in a file system.

4. The method of claim 1, wherein the first electronic data storage device and the second electronic data storage device are different from each other.

5. The method of claim 1, wherein the second partitions are arranged according to an overall schema and the ordered partitions are arranged according to a partition schema associated with each respective ordered partition.

6. A method for retrieving ordered data in a computer data system, the method comprising:

receiving an electronic message including a computer data system query;

performing first processing of the computer data system query to identify one or more data objects within a set of partitions stored on an electronic data storage device, the one or more data objects identified as containing data responsive to the query;

generating an intermediate result data object based on the first processing;

performing second processing of the computer data system query to generate an ordered collection of index values corresponding to one or more data items from the identified data objects having data responsive to the query, wherein the ordered collection contains index values into one or more data objects maintained according to a strict ordering associated with the data objects;

generating a subsequent result data object based on the second processing; and

providing a reference to the subsequent result data object containing the ordered collection as a query result, the subsequent result data object including references to data and corresponding index values for that data, wherein the subsequent result data object maintains the strict ordering associated with the data objects.

7. The method of claim 6, wherein the intermediate result data object includes only locations and location keys of data responsive to the query.

8. The method of claim 6, wherein the subsequent result data object includes locations of data responsive to the query and one or more references to data responsive to the query.

9. The method of claim 6, wherein accessing and movement of data is delayed until after the first processing of the computer data system query.

10. The method of claim 6, wherein the set of pa ions includes a hierarchical arrangement of partitions.

11. A method for computer data system data object schema modification, the method comprising:

receiving a request to modify a schema associated with a data object;

retrieving schema information from metadata associated with the data object;

modifying only the schema information according to the received request; and

storing the modified schema information in the metadata associated with the data object, wherein the data object is accessible according to the modified schema information.

12. The method of claim 11, further comprising providing the modified schema from the metadata associated with the data object in response to a request for information about the data object.

13. The method of claim 11, wherein the request to modify the schema includes a request to add a column to the data object, and wherein the column is added by schema modification without accessing any of the data in the data object.

14. The method of claim 11, wherein the request to modify the schema includes a request to remove a column from the data object, and wherein the column is removed by schema modification without accessing any of the data in the data object.

15. The method of claim 11, wherein the request to modify the schema includes a request to modify a data type of a column within a data object, and the modified schema information includes a modified data type for that column based on the request.

16. The method of claim 11, wherein the request to modify the schema includes a request to add a formula column to the data object, wherein a definition of the formula column resides in the schema information and the formula column does not contain stored data, and wherein when data is requested from the formula column, the computer data system computes a response result to the request for data from the formula column based on one or more data columns referenced by the formula column and returns that result.

17. The method of claim 11, wherein the request to modify the schema includes a request to add a formula column to the data object, wherein a definition of the formula column resides in the schema information and only a portion of rows in the formula column contain stored data, and wherein when data is requested from the formula column, the computer data system computes a response result to the request for data from the formula column based on stored data in the formula column for rows where data is present and, for rows where data is not present in the formula column, computes a response result to the request for data from the formula column based on one or more data columns referenced by the formula column and returns that result.