Learning Z-Order Indexes with Dynamic Bit Allocation
The Z-order curve is a space-filling curve that maps multi-dimensional data to singledimensional values. Z-order has been used in databases to sort multi-dimensional data. Modern data management systems such as Amazon Redshift and Databricks Delta Lake give users the ability to sort on multiple colu...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/150189 |
| _version_ | 1811068914198642688 |
|---|---|
| author | Gao, Jenny |
| author2 | Madden, Samuel |
| author_facet | Madden, Samuel Gao, Jenny |
| author_sort | Gao, Jenny |
| collection | MIT |
| description | The Z-order curve is a space-filling curve that maps multi-dimensional data to singledimensional values. Z-order has been used in databases to sort multi-dimensional data. Modern data management systems such as Amazon Redshift and Databricks Delta Lake give users the ability to sort on multiple columns using Z-order. However, the Z-order is difficult to tune, with tunable parameters such as which columns to include in the Z-order. Currently, users must specify the columns for Z-order when using the systems and might not necessarily achieve the best performance, as the choice of columns has a significant impact on performance. Another drawback is that the systems give equal weight to the columns, which often does not result in the best performance due to the unequal impact columns have on query performance. Our work aims to automatically determine the best Z-order configuration for a particular dataset and workload. In this thesis, we introduce learning Z-order indexes using an approach we refer to as dynamic bit allocation, which considers not only which columns to include, but also the weight to put on each column. Our learned Z-order indexes outperform existing techniques by up to 11× in query time and up to 30.2× in rows scanned, revealing the potential of tuning Z-order to improve query performance. |
| first_indexed | 2024-09-23T08:02:48Z |
| format | Thesis |
| id | mit-1721.1/150189 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:02:48Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1501892023-04-01T04:06:10Z Learning Z-Order Indexes with Dynamic Bit Allocation Gao, Jenny Madden, Samuel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science The Z-order curve is a space-filling curve that maps multi-dimensional data to singledimensional values. Z-order has been used in databases to sort multi-dimensional data. Modern data management systems such as Amazon Redshift and Databricks Delta Lake give users the ability to sort on multiple columns using Z-order. However, the Z-order is difficult to tune, with tunable parameters such as which columns to include in the Z-order. Currently, users must specify the columns for Z-order when using the systems and might not necessarily achieve the best performance, as the choice of columns has a significant impact on performance. Another drawback is that the systems give equal weight to the columns, which often does not result in the best performance due to the unequal impact columns have on query performance. Our work aims to automatically determine the best Z-order configuration for a particular dataset and workload. In this thesis, we introduce learning Z-order indexes using an approach we refer to as dynamic bit allocation, which considers not only which columns to include, but also the weight to put on each column. Our learned Z-order indexes outperform existing techniques by up to 11× in query time and up to 30.2× in rows scanned, revealing the potential of tuning Z-order to improve query performance. M.Eng. 2023-03-31T14:38:32Z 2023-03-31T14:38:32Z 2023-02 2023-02-27T18:43:26.907Z Thesis https://hdl.handle.net/1721.1/150189 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Gao, Jenny Learning Z-Order Indexes with Dynamic Bit Allocation |
| title | Learning Z-Order Indexes with Dynamic Bit Allocation |
| title_full | Learning Z-Order Indexes with Dynamic Bit Allocation |
| title_fullStr | Learning Z-Order Indexes with Dynamic Bit Allocation |
| title_full_unstemmed | Learning Z-Order Indexes with Dynamic Bit Allocation |
| title_short | Learning Z-Order Indexes with Dynamic Bit Allocation |
| title_sort | learning z order indexes with dynamic bit allocation |
| url | https://hdl.handle.net/1721.1/150189 |
| work_keys_str_mv | AT gaojenny learningzorderindexeswithdynamicbitallocation |