New metadata store for log entries & index provider

[sezruby]

NOTE: This is for the design discussion in new metadata store. Later we will create a design proposal PR.

Currently, Hyperspace loads all index log entries in system directory at once when it requires the list of indexes such as query optimizer, refreshIndex, deleteIndex, ... etc and caching all the entries for the next use.

However, this is not desirable & scalable in terms of

1. there can be numerous indexes
2. IndexLogEntry might take large memory space when it has many source files. (mainly file paths)
3. iterating all indexes for a relation is inefficient
4. cannot utilize indexes on different index system location at once.
5. ...

There're some comments from @clee704 in #405. (Thanks!)

Instead, how about making things simple and less regular, until we finally grasp the idea of how applicable indices should be found? We can try to find applicable indices for each relation in the plan (or each node in the plan, considering indexed views in the future):

def findApplicableIndices(plan: LogicalPlan, indexProvider: IndexProvider):
    Map[LogicalPlan, Seq[IndexLogEntry]] = {
  plan.map(node => (node, indexProvider.findApplicableIndices(node))).toMap
}

IndexProvider above is to support different types of indices (we may have to change IndexLogEntry too). For covering indices, the type of data source might not matter much except that some data sources might want to put the relation's info in the index metadata to expedite the index finding, but for non-covering indices, it might matter. Without an actual implementation of IndexProvider yet, we could have used the following interim implementation:

object IndexProvider {
  val indexManager = Hyperspace
       .getContext(spark)
       .indexCollectionManager
  def findApplicableIndices(node: LogicalPlan): Seq[IndexLogEntry] = {
    indexManager
      .getIndexes(ACTIVE)
      .filter(checkColumns(node, _))
      .filter(checkSignature(node, _))
  }
}

It has the same computational complexity as the original proposal because it involves iterating all indices and relations.

Index log entry is metadata, but it's currently scattered across the file system and there is no way to lookup a specific index efficiently other than loading all indices and checking one by one, which is basically the current implementation or this PR is doing. This PR doesn't change what was already being done, but I'm raising a concern here because it might impact the scalability of this project now and in the future. What I'm proposing is not new metadata for metadata; rather, it's more about the structure in which the metadata is laid out for efficient retrieval. For example, we can put entire index log entry data in a single data frame and store it in the file system. Being a DataFrame we can also cache() it. It would be much faster than reading 1000 different JSON files to create 1000 index log entries and iterating them to find the candidates. Maybe rootPaths is not adequate as you said. But I think we can find a way. Also, for relations with metadata like Delta and Iceberg tables, you see the benefit is clear.

Originally posted by @clee704 in #405 (comment)

Things to discuss

Key for retrieving indexes

Since we don't define "table identifier" for each source dataframe, it's hard to mapping the relations in query plan to index source relation. We could do this by filtering

• Source data column schema
  • Q. what if there's additional/removed column in a relation but unrelated?
  • required column resolution at retrieving?
• Root paths
  • root paths can be differ depending on User's input e.g. "path/to/a" or "path/to/a/a, path/to/a/b/"
  • Q. can we force users to use one type of rootPaths to apply indexes?
  • Q. can we support "subset" of rootPaths for Hybrid Scan? like
    • index rootPaths: a/b/c, query relation: a/b => might match
    • index rootPaths; a/b/c, query relation: a/b/c/d => might match
• Other metadata
  • in case of other data sources - delta lake or iceberg, we could use table name as the identifier

For support index view later, we should consider the query plan has multiple relations + indexes can be built on multiple relations.

Metadata format

• Parquet forma with columns:
  • index name
  • index location (path)
  • index column schema
  • (?) source data column schema
  • index root paths
    • what if there're >100k root paths
  • source metadata (table name / version? for delta lake / iceberg)

Metadata Location

• systemPath/hyperspace/md.parquet

Concurrency

• only one client can write md.parquet - file rw lock?

===

Please feel free to add any comment/idea/question on this :)

[sezruby]

@clee704 I think index provider can be a good improvement for Hyperspace. Could you review it and add some comments? Thanks!
cc @imback82 @rapoth