You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "BlakeOrth (via GitHub)" <gi...@apache.org> on 2025/11/21 00:50:11 UTC

[PR] POC for DefaultListFilesCache [datafusion]

BlakeOrth opened a new pull request, #18855:
URL: https://github.com/apache/datafusion/pull/18855

   
   
   ## Which issue does this PR close?
   
   POC for:
    - https://github.com/apache/datafusion/issues/18827
   
   ## Rationale for this change
   
   This is a POC for initial feedback and is not intended for merge at this time.
   
   ## What changes are included in this PR?
   
    - Implements a POC version of a default ListFilesCache
    - Refactors the existing ListFilesCache to mirror the MetadataCache by defining a new trait instead of a fixed type wrapping a trait
    - Bounds the size of the cache based on number of entries
    - Expires entries in the cache after a default timeout duration
   
   ## Are these changes tested?
   
   This code is functional and some tests clearly show a reduction in Object Store requests! However, existing tests are broken around `INSERT` commands, which is a key point of discussion that needs to be covered.
   
   ## Are there any user-facing changes?
   
   Yes, this work will likely break the existing `ListFilesCache` public API.
   
   ## Additional Context
   
   This PR is a basic functional implementation which heavily mirrors the existing `MetadataCache` and its semantics. One very key omission here that needs to be discussed is how `INSERT` statements are handled. On the surface it seems like there are two options:
    1. Invalidate the cache key(s) associated with the table that corresponds to the `INSERT` statement
    2. Intercept the object(s) that correspond to an `INSERT` statement and add them to the cache
   
   The first option here seems much easier, but the 2nd option seems more ideal since a user is likely to issue a query against newly inserted data. Any input here, or other strategies I haven't thought of to handle inserts, would be great!
   
   I will also leave some inline comments around some `TODO` items that I think should be discussed.
   
   cc @alamb @alchemist51 
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561910320


##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min
+
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, (Arc<Vec<ObjectMeta>>, Instant)>,
+    capacity: usize, // TODO: do "bytes" matter here, or should we stick with "entries"?
+    size: usize,
+    ttl: Duration,
+}
+
+// TODO: Do we even want to support "default" here?
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            size: 0,
+            ttl: DEFAULT_LIST_FILES_CACHE_TTL,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity,
+            size: 0,
+            ttl,
+        }
+    }
+
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {

Review Comment:
   I reviewed the changes from the above PR and I believe the implementation follows the same mutability pattern as the Metadata cache. The `CacheAccessor::remove` method takes `&self` and the methods for the `DefaultListFilesCacheState` still need to take `&mut self`.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550958560


##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min

Review Comment:
   > their expected workflow of new objects being picked up on every query will be broken. 
   
   I agree with this
   
   On the other hand, I am not sure what your patience level is but it is very unlikely I would wait 10 minutes... If it doesn't work within a few seconds, I would probably go start looking for problems.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#issuecomment-3581424052

   Thanks @BlakeOrth  -- I'll try and give this one a look today


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2593409700


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;
+
+        Some(Self {
+            metas,
+            size_bytes,
+            expires: ttl.map(|t| Instant::now() + t),
+        })
+    }
+}
+
+/// Calculates the number of bytes an [`ObjectMeta`] occupies in the heap.
+fn meta_heap_bytes(object_meta: &ObjectMeta) -> usize {
+    let mut size = object_meta.location.as_ref().len();
+
+    if let Some(e) = &object_meta.e_tag {
+        size += e.len();
+    }
+    if let Some(v) = &object_meta.version {
+        size += v.len();
+    }
+
+    size
+}
+
+/// The default memory limit for the [`DefaultListFilesCache`]
+pub(super) const DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT: usize = 1024 * 1024; // 1MiB
+
+/// Handles the inner state of the [`DefaultListFilesCache`] struct.
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, ListFilesEntry>,
+    memory_limit: usize,
+    memory_used: usize,
+    ttl: Option<Duration>,
+}
+
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit: DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT,
+            memory_used: 0,
+            ttl: None,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit,
+            memory_used: 0,
+            ttl,
+        }
+    }
+
+    /// Returns the respective entry from the cache, if it exists and the entry has not expired.
+    /// If the entry exists it becomes the most recently used. If the entry has expired it is
+    /// removed from the cache
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = self.lru_queue.get(key)?;
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(key);
+                None
+            }
+            _ => Some(Arc::clone(&entry.metas)),
+        }
+    }
+
+    /// Checks if the respective entry is currently cached. If the entry has expired it is removed
+    /// from the cache.
+    /// The LRU queue is not updated.
+    fn contains_key(&mut self, k: &Path) -> bool {
+        let Some(entry) = self.lru_queue.peek(k) else {
+            return false;
+        };
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(k);
+                false
+            }
+            _ => true,
+        }
+    }
+
+    /// Adds a new key-value pair to cache, meaning LRU entries might be evicted if required.
+    /// If the key is already in the cache, the previous entry is returned.
+    /// If the size of the entry is greater than the `memory_limit`, the value is not inserted.
+    fn put(
+        &mut self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = ListFilesEntry::try_new(value, self.ttl)?;
+        let entry_size = entry.size_bytes;
+
+        // no point in trying to add this value to the cache if it cannot fit entirely
+        if entry_size > self.memory_limit {
+            return None;
+        }
+
+        // if the key is already in the cache, the old value is removed
+        let old_value = self.lru_queue.put(key.clone(), entry);
+        self.memory_used += entry_size;
+
+        if let Some(entry) = &old_value {
+            self.memory_used -= entry.size_bytes;
+        }
+
+        self.evict_entries();
+
+        old_value.map(|v| v.metas)
+    }
+
+    /// Evicts entries from the LRU cache until `memory_used` is lower than `memory_limit`.
+    fn evict_entries(&mut self) {
+        while self.memory_used > self.memory_limit {
+            if let Some(removed) = self.lru_queue.pop() {
+                self.memory_used -= removed.1.size_bytes;
+            } else {
+                // cache is empty while memory_used > memory_limit, cannot happen
+                debug_assert!(
+                    false,
+                    "cache is empty while memory_used > memory_limit, cannot happen"
+                );
+                return;
+            }
+        }
+    }
+
+    /// Removes an entry from the cache and returns it, if it exists.
+    fn remove(&mut self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        if let Some(entry) = self.lru_queue.remove(k) {
+            self.memory_used -= entry.size_bytes;
+            Some(entry.metas)
+        } else {
+            None
+        }
+    }
+
+    /// Returns the number of entries currently cached.
+    fn len(&self) -> usize {
+        self.lru_queue.len()
+    }
+
+    /// Removes all entries from the cache.
+    fn clear(&mut self) {
+        self.lru_queue.clear();
+        self.memory_used = 0;
+    }
+}
+
+impl ListFilesCache for DefaultListFilesCache {
+    fn cache_limit(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.memory_limit
+    }
+
+    fn cache_ttl(&self) -> Option<Duration> {
+        let state = self.state.lock().unwrap();
+        state.ttl
+    }
+
+    fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+}
+
+impl CacheAccessor<Path, Arc<Vec<ObjectMeta>>> for DefaultListFilesCache {
+    type Extra = ObjectMeta;
+
+    fn get(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.get(k)
+    }
+
+    fn get_with_extra(&self, k: &Path, _e: &Self::Extra) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.get(k)
+    }
+
+    fn put(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.put(key, value)
+    }
+
+    fn put_with_extra(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+        _e: &Self::Extra,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.put(key, value)
+    }
+
+    fn remove(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.remove(k)
+    }
+
+    fn contains_key(&self, k: &Path) -> bool {
+        let mut state = self.state.lock().unwrap();
+        state.contains_key(k)
+    }
+
+    fn len(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.len()
+    }
+
+    fn clear(&self) {
+        let mut state = self.state.lock().unwrap();
+        state.clear();
+    }
+
+    fn name(&self) -> String {
+        String::from("DefaultListFilesCache")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use chrono::DateTime;
+    use std::thread;
+
+    /// Helper function to create a test ObjectMeta with a specific path and location string size
+    fn create_test_object_meta(path: &str, location_size: usize) -> ObjectMeta {
+        // Create a location string of the desired size by padding with zeros
+        let location_str = if location_size > path.len() {
+            format!("{}{}", path, "0".repeat(location_size - path.len()))
+        } else {
+            path.to_string()
+        };
+
+        ObjectMeta {
+            location: Path::from(location_str),
+            last_modified: DateTime::parse_from_rfc3339("2022-09-27T22:36:00+02:00")
+                .unwrap()
+                .into(),
+            size: 1024,
+            e_tag: None,
+            version: None,
+        }
+    }
+
+    /// Helper function to create a vector of ObjectMeta with at least meta_size bytes
+    fn create_test_list_files_entry(
+        path: &str,
+        count: usize,
+        meta_size: usize,
+    ) -> (Path, Arc<Vec<ObjectMeta>>, usize) {
+        let metas: Vec<ObjectMeta> = (0..count)
+            .map(|i| create_test_object_meta(&format!("file{i}"), meta_size))
+            .collect();
+        let metas = Arc::new(metas);
+
+        // Calculate actual size using the same logic as ListFilesEntry::try_new
+        let size = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).sum::<usize>();
+
+        (Path::from(path), metas, size)
+    }
+
+    #[test]
+    fn test_basic_operations() {
+        let cache = DefaultListFilesCache::default();
+        let path = Path::from("test_path");
+
+        // Initially cache is empty
+        assert!(cache.get(&path).is_none());
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put an entry
+        let meta = create_test_object_meta("file1", 50);
+        let value = Arc::new(vec![meta.clone()]);
+        cache.put(&path, Arc::clone(&value));
+
+        // Entry should be retrievable
+        assert!(cache.contains_key(&path));
+        assert_eq!(cache.len(), 1);
+        let retrieved = cache.get(&path).unwrap();
+        assert_eq!(retrieved.len(), 1);
+        assert_eq!(retrieved[0].location, meta.location);
+
+        // Remove the entry
+        let removed = cache.remove(&path).unwrap();
+        assert_eq!(removed.len(), 1);
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put multiple entries
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 3, 50);
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Clear all entries
+        cache.clear();
+        assert_eq!(cache.len(), 0);
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_lru_eviction_basic() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to exactly fit all three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // All three entries should fit
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Adding a new entry should evict path1 (LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_lru_ordering_after_access() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to fit exactly three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Access path1 to move it to front (MRU)
+        // Order is now: path2 (LRU), path3, path1 (MRU)
+        cache.get(&path1);
+
+        // Adding a new entry should evict path2 (the LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1)); // Still present (recently accessed)
+        assert!(!cache.contains_key(&path2)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_reject_too_large() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+
+        // Set cache limit to fit both entries
+        let cache = DefaultListFilesCache::new(size * 2, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Try to add an entry that's too large to fit in the cache
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 1000);
+        cache.put(&path_large, value_large);
+
+        // Large entry should not be added
+        assert!(!cache.contains_key(&path_large));
+        assert_eq!(cache.len(), 2);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_multiple_evictions() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit for exactly 3 entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Add a large entry that requires evicting 2 entries
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 200);
+        cache.put(&path_large, value_large);
+
+        // path1 and path2 should be evicted (both LRU), path3 and path_large remain
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(!cache.contains_key(&path2)); // Evicted
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path_large));
+    }
+
+    #[test]
+    fn test_cache_limit_resize() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Resize cache to only fit one entry
+        cache.update_cache_limit(size);
+
+        // Should keep only the most recent entry (path3, the MRU)
+        assert_eq!(cache.len(), 1);
+        assert!(cache.contains_key(&path3));
+        // Earlier entries (LRU) should be evicted
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_entry_update_with_size_change() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3_v1, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3_v1);
+        assert_eq!(cache.len(), 3);
+
+        // Update path3 with same size - should not cause eviction
+        let (_, value3_v2, _) = create_test_list_files_entry("path3", 1, 100);
+        cache.put(&path3, value3_v2);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Update path3 with larger size that requires evicting path1 (LRU)
+        let (_, value3_v3, _) = create_test_list_files_entry("path3", 1, 200);
+        cache.put(&path3, value3_v3);
+
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+    }
+
+    #[test]
+    fn test_cache_with_ttl() {
+        let ttl = Duration::from_millis(100);
+        let cache = DefaultListFilesCache::new(10000, Some(ttl));
+
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 2, 50);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+
+        // Entries should be accessible immediately
+        assert!(cache.get(&path1).is_some());
+        assert!(cache.get(&path2).is_some());
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert_eq!(cache.len(), 2);
+
+        // Wait for TTL to expire
+        thread::sleep(Duration::from_millis(150));
+
+        // Entries should now return None and be removed when observed through get or contains_key
+        assert!(cache.get(&path1).is_none());
+        assert_eq!(cache.len(), 1); // path1 was removed by get()
+        assert!(!cache.contains_key(&path2));
+        assert_eq!(cache.len(), 0); // path2 was removed by contains_key()
+    }
+
+    #[test]
+    fn test_cache_with_ttl_and_lru() {

Review Comment:
   Yeah, I agree this is almost certainly due to timing. I can't think of a surefire way to test TTL based items outside of timing unfortunately. We could relax the test criteria a bit here and simply omit this test since we exercise LRU and TTL separately in other tests. LRU+TTL is a bit of a more complex interaction, but in theory if they work in isolation they should work as expected together. What do you think?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alchemist51 (via GitHub)" <gi...@apache.org>.
alchemist51 commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2548491341


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   I think one of the things I would like to do in the Cache Manager caches is to segregate the cache eviction policy. Personally I think the user should be given an option on what is the eviction behaviour they want. wdyt @alamb  @BlakeOrth  ? I can work on getting some draft out this weekend on it.



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -209,6 +255,8 @@ impl Default for CacheManagerConfig {
         Self {
             table_files_statistics_cache: Default::default(),
             list_files_cache: Default::default(),
+            list_files_cache_limit: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            list_files_cache_ttl: DEFAULT_LIST_FILES_CACHE_TTL,

Review Comment:
   Some usecases don't need a TTL, we should provide a way to keep that disable as well.



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -228,13 +276,30 @@ impl CacheManagerConfig {
     }
 
     /// Set the cache for listing files.
-    ///     
+    ///
     /// Default is `None` (disabled).
-    pub fn with_list_files_cache(mut self, cache: Option<ListFilesCache>) -> Self {
+    pub fn with_list_files_cache(
+        mut self,
+        cache: Option<Arc<dyn ListFilesCache>>,
+    ) -> Self {
         self.list_files_cache = cache;
         self
     }
 
+    pub fn with_list_files_cache_limit(mut self, limit: usize) -> Self {
+        self.list_files_cache_limit = limit;
+        self
+    }
+
+    pub fn with_list_files_cache_ttl(mut self, ttl: Duration) -> Self {
+        self.list_files_cache_ttl = ttl;
+        if ttl.is_zero() {

Review Comment:
   Why are we setting it to None in case of no TTL?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550959411


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   Yes, that sounds like a great idea to me



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2582916461


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;

Review Comment:
   Thank you for double checking this!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alchemist51 (via GitHub)" <gi...@apache.org>.
alchemist51 commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2560294003


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   A little bit side topic. @alamb  was looking into other caches, didn't understand why `DefaultFileStatisticsCache` isn't memory bound yet. Do we want to do it incrementally? 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561916333


##########
datafusion/core/tests/datasource/object_store_access.rs:
##########
@@ -117,8 +117,7 @@ async fn query_multi_csv_file() {
     +---------+-------+-------+
     ------- Object Store Request Summary -------
     RequestCountingObjectStore()
-    Total Requests: 4
-    - LIST prefix=data
+    Total Requests: 3

Review Comment:
   These tests have been backed out of the most recent commit because the cache is no longer enabled by default (since it doesn't quite fulfill those requirements yet). Integration level testing changes/enhancements will come once we get the ability to configure the cache from the user level.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#issuecomment-3578016378

   @alamb I have done a decent amount of cleanup, implemented tests, added/edited doc strings etc. and I believe this PR is now out of a POC state moving towards being merge ready. Given the constructive comments that have already been made here, I decided to just update and clean up this existing PR. I'm also happy to open a fresh PR if we want a clean slate!


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2582851884


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+

Review Comment:
   I this something you are willing to do, or shall I make one?



##########
docs/source/library-user-guide/upgrading.md:
##########
@@ -40,6 +40,23 @@ directly on the `Field`. For example:
 + let field = Arc::clone(df_schema.field("my_column"));
 ```
 
+### ListingTableProvider now caches `LIST` commands

Review Comment:
   I added this section to communicate the new behavior



##########
datafusion/core/tests/datasource/object_store_access.rs:
##########
@@ -98,6 +98,59 @@ async fn create_multi_file_csv_file() {
     );
 }
 
+#[tokio::test]
+async fn multi_query_multi_file_csv_file() {
+    let test = Test::new().with_multi_file_csv().await;
+    assert_snapshot!(
+        test.query("select * from csv_table").await,
+        @r"
+    ------- Query Output (6 rows) -------
+    +---------+-------+-------+
+    | c1      | c2    | c3    |
+    +---------+-------+-------+
+    | 0.0     | 0.0   | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00001 | 1e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00002 | 2e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    +---------+-------+-------+
+    ------- Object Store Request Summary -------
+    RequestCountingObjectStore()
+    Total Requests: 4
+    - LIST prefix=data
+    - GET  (opts) path=data/file_0.csv
+    - GET  (opts) path=data/file_1.csv
+    - GET  (opts) path=data/file_2.csv
+    "
+    );
+
+    // the second query should re-use the cached LIST results and should not reissue LIST
+    assert_snapshot!(
+        test.query("select * from csv_table").await,
+        @r"
+    ------- Query Output (6 rows) -------
+    +---------+-------+-------+
+    | c1      | c2    | c3    |
+    +---------+-------+-------+
+    | 0.0     | 0.0   | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00001 | 1e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00002 | 2e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    +---------+-------+-------+
+    ------- Object Store Request Summary -------
+    RequestCountingObjectStore()
+    Total Requests: 4

Review Comment:
   @BlakeOrth  this seems wrong to me -- now that we have a ListFilesCache, I would expect this query to *NOT* need to do a `LIST` command 🤔 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550800835


##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min
+
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, (Arc<Vec<ObjectMeta>>, Instant)>,
+    capacity: usize, // TODO: do "bytes" matter here, or should we stick with "entries"?
+    size: usize,
+    ttl: Duration,
+}
+
+// TODO: Do we even want to support "default" here?
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            size: 0,
+            ttl: DEFAULT_LIST_FILES_CACHE_TTL,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity,
+            size: 0,
+            ttl,
+        }
+    }
+
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {

Review Comment:
   Ah, thanks for pointing this out. I ran into and resolved one merge conflict related to that PR and didn't realize it may have had a subtly wider impact than just the method that caused a conflict on my rebase. I will make sure to revisit this.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#issuecomment-3564402495

   @alamb Thanks for the initial review and comments! I think there's one key decision that needs to be made before moving forward in earnest here, which is what action we should take with the cache for `INSERT` statements. 
   
   > One very key omission here that needs to be discussed is how INSERT statements are handled. On the surface it seems like there are two options:
   >
   >    1. Invalidate the cache key(s) associated with the table that corresponds to the INSERT statement
   >    2. Intercept the object(s) that correspond to an INSERT statement and add them to the cache
   >
   > The first option here seems much easier, but the 2nd option seems more ideal since a user is likely to issue a query against newly inserted data. 
   
   Do you have any thoughts or preferences on this?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561114654


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   I am not sure what you are asking -- do you mean `metadata_cache_limit` on https://datafusion.apache.org/user-guide/configs.html#runtime-configuration-settings ?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2548182236


##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min
+
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, (Arc<Vec<ObjectMeta>>, Instant)>,
+    capacity: usize, // TODO: do "bytes" matter here, or should we stick with "entries"?

Review Comment:
   I didn't feel like limiting this cache by "bytes" really made sense because the data stored in the cache is generally very uniform in size, perhaps aside from the path. I felt that it was probably small enough that simply limiting it by the number of entries should suffice, and "entries" seems like it would be easier for users to configure.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550554230


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -209,6 +255,8 @@ impl Default for CacheManagerConfig {
         Self {
             table_files_statistics_cache: Default::default(),
             list_files_cache: Default::default(),
+            list_files_cache_limit: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            list_files_cache_ttl: DEFAULT_LIST_FILES_CACHE_TTL,

Review Comment:
   I actually agree with your first assessment that TTL can, and likely should, be optional if a user has a use case where they know the underlying objects are immutable once written (my personal use of DataFusion falls into this category). In either case, we may have to accept some differences between this cache and the Metadata cache. Unlike the Metadata cache, which can issue HEAD requests against objects to detect modification, there's no mechanism in an object store to inquire whether or not paths/sub-paths have been changed, so this cache will need to make some concessions around that limitation.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550755591


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -140,7 +155,17 @@ impl CacheManager {
         let file_statistic_cache =
             config.table_files_statistics_cache.as_ref().map(Arc::clone);
 
-        let list_files_cache = config.list_files_cache.as_ref().map(Arc::clone);
+        let list_files_cache = config
+            .list_files_cache
+            .as_ref()
+            .map(Arc::clone)
+            .unwrap_or_else(|| {
+                Arc::new(DefaultListFilesCache::new(
+                    // TODO: config
+                    512 * 1024,
+                    Duration::new(600, 0),

Review Comment:
   Yes, I think we could also do some of the more complex desires for this cache, like being "prefix aware" in some way, as follow-on issues once this initial scaffolding exists.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2582910705


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+

Review Comment:
   Yes, I'm happy to make an issue for this!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2582697006


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -189,13 +228,20 @@ pub struct CacheManagerConfig {
     /// Avoid get same file statistics repeatedly in same datafusion session.
     /// Default is disable. Fow now only supports Parquet files.
     pub table_files_statistics_cache: Option<FileStatisticsCache>,
-    /// Enable cache of file metadata when listing files.
-    /// This setting avoids listing file meta of the same path repeatedly
-    /// in same session, which may be expensive in certain situations (e.g. remote object storage).
+    /// Enable caching of file metadata when listing files.
+    /// Enabling the cache avoids repeat list and metadata fetch operations, which may be expensive
+    /// in certain situations (e.g. remote object storage), for objects under paths that are
+    /// cached.
     /// Note that if this option is enabled, DataFusion will not see any updates to the underlying
-    /// location.  
-    /// Default is disable.
-    pub list_files_cache: Option<ListFilesCache>,
+    /// storage for at least `list_files_cache_ttl` duration.
+    /// Default is disabled.
+    pub list_files_cache: Option<Arc<dyn ListFilesCache>>,
+    /// Limit the number of objects to keep in the `list_files_cache`. Default: ~125k objects
+    pub list_files_cache_limit: usize,

Review Comment:
   I see this setup is used to support runtime configuration of the cache. See for example 
   
   https://github.com/apache/datafusion/blob/838e1dea832e3cd8585498ba12216e1ad9f584a4/datafusion/core/src/execution/context/mod.rs#L1160-L1163
   
   I think what we should do (as a follow on PR) is to add runtime configuration settings for the max cache size and its ttl in  https://datafusion.apache.org/user-guide/configs.html#runtime-configuration-settings
   
   I filed a ticket to do so: 
   - https://github.com/apache/datafusion/issues/19056



##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;
+
+        Some(Self {
+            metas,
+            size_bytes,
+            expires: ttl.map(|t| Instant::now() + t),
+        })
+    }
+}
+
+/// Calculates the number of bytes an [`ObjectMeta`] occupies in the heap.
+fn meta_heap_bytes(object_meta: &ObjectMeta) -> usize {
+    let mut size = object_meta.location.as_ref().len();
+
+    if let Some(e) = &object_meta.e_tag {
+        size += e.len();
+    }
+    if let Some(v) = &object_meta.version {
+        size += v.len();
+    }
+
+    size
+}
+
+/// The default memory limit for the [`DefaultListFilesCache`]
+pub(super) const DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT: usize = 1024 * 1024; // 1MiB
+
+/// Handles the inner state of the [`DefaultListFilesCache`] struct.
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, ListFilesEntry>,
+    memory_limit: usize,
+    memory_used: usize,
+    ttl: Option<Duration>,
+}
+
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit: DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT,
+            memory_used: 0,
+            ttl: None,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit,
+            memory_used: 0,
+            ttl,
+        }
+    }
+
+    /// Returns the respective entry from the cache, if it exists and the entry has not expired.
+    /// If the entry exists it becomes the most recently used. If the entry has expired it is
+    /// removed from the cache
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = self.lru_queue.get(key)?;
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(key);
+                None
+            }
+            _ => Some(Arc::clone(&entry.metas)),
+        }
+    }
+
+    /// Checks if the respective entry is currently cached. If the entry has expired it is removed
+    /// from the cache.
+    /// The LRU queue is not updated.
+    fn contains_key(&mut self, k: &Path) -> bool {
+        let Some(entry) = self.lru_queue.peek(k) else {
+            return false;
+        };
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(k);
+                false
+            }
+            _ => true,
+        }
+    }
+
+    /// Adds a new key-value pair to cache, meaning LRU entries might be evicted if required.
+    /// If the key is already in the cache, the previous entry is returned.
+    /// If the size of the entry is greater than the `memory_limit`, the value is not inserted.
+    fn put(
+        &mut self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = ListFilesEntry::try_new(value, self.ttl)?;
+        let entry_size = entry.size_bytes;
+
+        // no point in trying to add this value to the cache if it cannot fit entirely
+        if entry_size > self.memory_limit {
+            return None;
+        }
+
+        // if the key is already in the cache, the old value is removed
+        let old_value = self.lru_queue.put(key.clone(), entry);
+        self.memory_used += entry_size;
+
+        if let Some(entry) = &old_value {
+            self.memory_used -= entry.size_bytes;
+        }
+
+        self.evict_entries();
+
+        old_value.map(|v| v.metas)
+    }
+
+    /// Evicts entries from the LRU cache until `memory_used` is lower than `memory_limit`.
+    fn evict_entries(&mut self) {
+        while self.memory_used > self.memory_limit {
+            if let Some(removed) = self.lru_queue.pop() {
+                self.memory_used -= removed.1.size_bytes;
+            } else {
+                // cache is empty while memory_used > memory_limit, cannot happen
+                debug_assert!(
+                    false,
+                    "cache is empty while memory_used > memory_limit, cannot happen"
+                );
+                return;
+            }
+        }
+    }
+
+    /// Removes an entry from the cache and returns it, if it exists.
+    fn remove(&mut self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        if let Some(entry) = self.lru_queue.remove(k) {
+            self.memory_used -= entry.size_bytes;
+            Some(entry.metas)
+        } else {
+            None
+        }
+    }
+
+    /// Returns the number of entries currently cached.
+    fn len(&self) -> usize {
+        self.lru_queue.len()
+    }
+
+    /// Removes all entries from the cache.
+    fn clear(&mut self) {
+        self.lru_queue.clear();
+        self.memory_used = 0;
+    }
+}
+
+impl ListFilesCache for DefaultListFilesCache {
+    fn cache_limit(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.memory_limit
+    }
+
+    fn cache_ttl(&self) -> Option<Duration> {
+        let state = self.state.lock().unwrap();
+        state.ttl
+    }
+
+    fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+}
+
+impl CacheAccessor<Path, Arc<Vec<ObjectMeta>>> for DefaultListFilesCache {
+    type Extra = ObjectMeta;
+
+    fn get(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.get(k)
+    }
+
+    fn get_with_extra(&self, k: &Path, _e: &Self::Extra) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.get(k)
+    }
+
+    fn put(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.put(key, value)
+    }
+
+    fn put_with_extra(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+        _e: &Self::Extra,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.put(key, value)
+    }
+
+    fn remove(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.remove(k)
+    }
+
+    fn contains_key(&self, k: &Path) -> bool {
+        let mut state = self.state.lock().unwrap();
+        state.contains_key(k)
+    }
+
+    fn len(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.len()
+    }
+
+    fn clear(&self) {
+        let mut state = self.state.lock().unwrap();
+        state.clear();
+    }
+
+    fn name(&self) -> String {
+        String::from("DefaultListFilesCache")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use chrono::DateTime;
+    use std::thread;
+
+    /// Helper function to create a test ObjectMeta with a specific path and location string size
+    fn create_test_object_meta(path: &str, location_size: usize) -> ObjectMeta {
+        // Create a location string of the desired size by padding with zeros
+        let location_str = if location_size > path.len() {
+            format!("{}{}", path, "0".repeat(location_size - path.len()))
+        } else {
+            path.to_string()
+        };
+
+        ObjectMeta {
+            location: Path::from(location_str),
+            last_modified: DateTime::parse_from_rfc3339("2022-09-27T22:36:00+02:00")
+                .unwrap()
+                .into(),
+            size: 1024,
+            e_tag: None,
+            version: None,
+        }
+    }
+
+    /// Helper function to create a vector of ObjectMeta with at least meta_size bytes
+    fn create_test_list_files_entry(
+        path: &str,
+        count: usize,
+        meta_size: usize,
+    ) -> (Path, Arc<Vec<ObjectMeta>>, usize) {
+        let metas: Vec<ObjectMeta> = (0..count)
+            .map(|i| create_test_object_meta(&format!("file{i}"), meta_size))
+            .collect();
+        let metas = Arc::new(metas);
+
+        // Calculate actual size using the same logic as ListFilesEntry::try_new
+        let size = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).sum::<usize>();
+
+        (Path::from(path), metas, size)
+    }
+
+    #[test]
+    fn test_basic_operations() {
+        let cache = DefaultListFilesCache::default();
+        let path = Path::from("test_path");
+
+        // Initially cache is empty
+        assert!(cache.get(&path).is_none());
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put an entry
+        let meta = create_test_object_meta("file1", 50);
+        let value = Arc::new(vec![meta.clone()]);
+        cache.put(&path, Arc::clone(&value));
+
+        // Entry should be retrievable
+        assert!(cache.contains_key(&path));
+        assert_eq!(cache.len(), 1);
+        let retrieved = cache.get(&path).unwrap();
+        assert_eq!(retrieved.len(), 1);
+        assert_eq!(retrieved[0].location, meta.location);
+
+        // Remove the entry
+        let removed = cache.remove(&path).unwrap();
+        assert_eq!(removed.len(), 1);
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put multiple entries
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 3, 50);
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Clear all entries
+        cache.clear();
+        assert_eq!(cache.len(), 0);
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_lru_eviction_basic() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to exactly fit all three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // All three entries should fit
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Adding a new entry should evict path1 (LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_lru_ordering_after_access() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to fit exactly three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Access path1 to move it to front (MRU)
+        // Order is now: path2 (LRU), path3, path1 (MRU)
+        cache.get(&path1);
+
+        // Adding a new entry should evict path2 (the LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1)); // Still present (recently accessed)
+        assert!(!cache.contains_key(&path2)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_reject_too_large() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+
+        // Set cache limit to fit both entries
+        let cache = DefaultListFilesCache::new(size * 2, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Try to add an entry that's too large to fit in the cache
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 1000);
+        cache.put(&path_large, value_large);
+
+        // Large entry should not be added
+        assert!(!cache.contains_key(&path_large));
+        assert_eq!(cache.len(), 2);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_multiple_evictions() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit for exactly 3 entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Add a large entry that requires evicting 2 entries
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 200);
+        cache.put(&path_large, value_large);
+
+        // path1 and path2 should be evicted (both LRU), path3 and path_large remain
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(!cache.contains_key(&path2)); // Evicted
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path_large));
+    }
+
+    #[test]
+    fn test_cache_limit_resize() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Resize cache to only fit one entry
+        cache.update_cache_limit(size);
+
+        // Should keep only the most recent entry (path3, the MRU)
+        assert_eq!(cache.len(), 1);
+        assert!(cache.contains_key(&path3));
+        // Earlier entries (LRU) should be evicted
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_entry_update_with_size_change() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3_v1, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3_v1);
+        assert_eq!(cache.len(), 3);
+
+        // Update path3 with same size - should not cause eviction
+        let (_, value3_v2, _) = create_test_list_files_entry("path3", 1, 100);
+        cache.put(&path3, value3_v2);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Update path3 with larger size that requires evicting path1 (LRU)
+        let (_, value3_v3, _) = create_test_list_files_entry("path3", 1, 200);
+        cache.put(&path3, value3_v3);
+
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+    }
+
+    #[test]
+    fn test_cache_with_ttl() {
+        let ttl = Duration::from_millis(100);
+        let cache = DefaultListFilesCache::new(10000, Some(ttl));
+
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 2, 50);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+
+        // Entries should be accessible immediately
+        assert!(cache.get(&path1).is_some());
+        assert!(cache.get(&path2).is_some());
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert_eq!(cache.len(), 2);
+
+        // Wait for TTL to expire
+        thread::sleep(Duration::from_millis(150));
+
+        // Entries should now return None and be removed when observed through get or contains_key
+        assert!(cache.get(&path1).is_none());
+        assert_eq!(cache.len(), 1); // path1 was removed by get()
+        assert!(!cache.contains_key(&path2));
+        assert_eq!(cache.len(), 0); // path2 was removed by contains_key()
+    }
+
+    #[test]

Review Comment:
   these are very nice tests



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   > A little bit side topic. @alamb was looking into other caches, didn't understand why `DefaultFileStatisticsCache` isn't memory bound yet. Do we want to do it incrementally?
   
   I have filed a ticket for this item:
   - https://github.com/apache/datafusion/issues/19052



##########
datafusion/catalog-listing/src/table.rs:
##########
@@ -578,6 +578,11 @@ impl TableProvider for ListingTable {
         let keep_partition_by_columns =
             state.config_options().execution.keep_partition_by_columns;
 
+        // Invalidate cache entries for this table if they exist
+        if let Some(lfc) = state.runtime_env().cache_manager.get_list_files_cache() {
+            let _ = lfc.remove(table_path.prefix());
+        }

Review Comment:
   makes sense. Thank you



##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;

Review Comment:
   👌  i double checked and I believe this captures the heap size accurately



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2548174534


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -140,7 +155,17 @@ impl CacheManager {
         let file_statistic_cache =
             config.table_files_statistics_cache.as_ref().map(Arc::clone);
 
-        let list_files_cache = config.list_files_cache.as_ref().map(Arc::clone);
+        let list_files_cache = config
+            .list_files_cache
+            .as_ref()
+            .map(Arc::clone)
+            .unwrap_or_else(|| {
+                Arc::new(DefaultListFilesCache::new(
+                    // TODO: config
+                    512 * 1024,
+                    Duration::new(600, 0),

Review Comment:
   This POC doesn't implement any of the user configuration. This seems like a good opportunity to divide the work on this effort! We could get the base `DefaultListFilesCache` approved for merge without user configuration, and leave it disabled, and user configuration could be added by anyone who wants to contribute.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #18855:
URL: https://github.com/apache/datafusion/pull/18855


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2586304515


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+

Review Comment:
   Issue created here:
    - https://github.com/apache/datafusion/issues/19074



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#issuecomment-3608850772

   > Thanks @BlakeOrth
   
   @alamb thanks for the careful review and the additional help with the upgrade guide and tests! :rocket: 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2582905212


##########
datafusion/core/tests/datasource/object_store_access.rs:
##########
@@ -98,6 +98,59 @@ async fn create_multi_file_csv_file() {
     );
 }
 
+#[tokio::test]
+async fn multi_query_multi_file_csv_file() {
+    let test = Test::new().with_multi_file_csv().await;
+    assert_snapshot!(
+        test.query("select * from csv_table").await,
+        @r"
+    ------- Query Output (6 rows) -------
+    +---------+-------+-------+
+    | c1      | c2    | c3    |
+    +---------+-------+-------+
+    | 0.0     | 0.0   | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00001 | 1e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00002 | 2e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    +---------+-------+-------+
+    ------- Object Store Request Summary -------
+    RequestCountingObjectStore()
+    Total Requests: 4
+    - LIST prefix=data
+    - GET  (opts) path=data/file_0.csv
+    - GET  (opts) path=data/file_1.csv
+    - GET  (opts) path=data/file_2.csv
+    "
+    );
+
+    // the second query should re-use the cached LIST results and should not reissue LIST
+    assert_snapshot!(
+        test.query("select * from csv_table").await,
+        @r"
+    ------- Query Output (6 rows) -------
+    +---------+-------+-------+
+    | c1      | c2    | c3    |
+    +---------+-------+-------+
+    | 0.0     | 0.0   | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00001 | 1e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00002 | 2e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    +---------+-------+-------+
+    ------- Object Store Request Summary -------
+    RequestCountingObjectStore()
+    Total Requests: 4

Review Comment:
   With the current state of this PR I think this result is actually expected. I chose to remove the code that enables the cache by default, as well as this test (they were in the POC for illustration purposes). I thought since the cache currently cannot be configured, and really specifically that cannot be disabled, it would be best to leave it disabled by default to avoid breaking users.
   
   Additionally, quite a few of the `sqllogic` tests seem to rely on the `copy` functionality and the existing expectation that DataFusion will pick up the changes on query. The easiest way to handle those tests will be to disable this cache for the duration of the tests, but that again relies on the cache having some configuration.
   
   All that being said, I'm more than happy to move forward on this effort in whatever way you think is best! I can add a very simple configuration option (and docs etc.) to enable/disable this cache so we can keep this test you've written and have it show a reduction in `LIST` operations, or we can leave that as a portion of the "configuration issue" associated with this cache.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2548186345


##########
datafusion/execution/src/cache/mod.rs:
##########
@@ -19,6 +19,7 @@ pub mod cache_manager;
 pub mod cache_unit;
 pub mod lru_queue;
 
+// TODO: driveby-cleanup
 /// The cache accessor, users usually working on this interface while manipulating caches.

Review Comment:
   I noticed this doc comment could be edited for additional clarity, so I figured while we were in this area of code we could improve this!



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alchemist51 (via GitHub)" <gi...@apache.org>.
alchemist51 commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2548539964


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -209,6 +255,8 @@ impl Default for CacheManagerConfig {
         Self {
             table_files_statistics_cache: Default::default(),
             list_files_cache: Default::default(),
+            list_files_cache_limit: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            list_files_cache_ttl: DEFAULT_LIST_FILES_CACHE_TTL,

Review Comment:
   Well thinking more, I understand why you have kept it.. I feel it diverges from the metadata cache and could confuse the end users somewhat



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550788827


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   @alamb After reading your thoughts on this I'm wondering if a more complex cache infrastructure would be a good project to start in https://github.com/datafusion-contrib and if it gains enough traction perhaps it could be promoted to the core repo?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2594059602


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;
+
+        Some(Self {
+            metas,
+            size_bytes,
+            expires: ttl.map(|t| Instant::now() + t),
+        })
+    }
+}
+
+/// Calculates the number of bytes an [`ObjectMeta`] occupies in the heap.
+fn meta_heap_bytes(object_meta: &ObjectMeta) -> usize {
+    let mut size = object_meta.location.as_ref().len();
+
+    if let Some(e) = &object_meta.e_tag {
+        size += e.len();
+    }
+    if let Some(v) = &object_meta.version {
+        size += v.len();
+    }
+
+    size
+}
+
+/// The default memory limit for the [`DefaultListFilesCache`]
+pub(super) const DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT: usize = 1024 * 1024; // 1MiB
+
+/// Handles the inner state of the [`DefaultListFilesCache`] struct.
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, ListFilesEntry>,
+    memory_limit: usize,
+    memory_used: usize,
+    ttl: Option<Duration>,
+}
+
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit: DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT,
+            memory_used: 0,
+            ttl: None,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit,
+            memory_used: 0,
+            ttl,
+        }
+    }
+
+    /// Returns the respective entry from the cache, if it exists and the entry has not expired.
+    /// If the entry exists it becomes the most recently used. If the entry has expired it is
+    /// removed from the cache
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = self.lru_queue.get(key)?;
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(key);
+                None
+            }
+            _ => Some(Arc::clone(&entry.metas)),
+        }
+    }
+
+    /// Checks if the respective entry is currently cached. If the entry has expired it is removed
+    /// from the cache.
+    /// The LRU queue is not updated.
+    fn contains_key(&mut self, k: &Path) -> bool {
+        let Some(entry) = self.lru_queue.peek(k) else {
+            return false;
+        };
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(k);
+                false
+            }
+            _ => true,
+        }
+    }
+
+    /// Adds a new key-value pair to cache, meaning LRU entries might be evicted if required.
+    /// If the key is already in the cache, the previous entry is returned.
+    /// If the size of the entry is greater than the `memory_limit`, the value is not inserted.
+    fn put(
+        &mut self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = ListFilesEntry::try_new(value, self.ttl)?;
+        let entry_size = entry.size_bytes;
+
+        // no point in trying to add this value to the cache if it cannot fit entirely
+        if entry_size > self.memory_limit {
+            return None;
+        }
+
+        // if the key is already in the cache, the old value is removed
+        let old_value = self.lru_queue.put(key.clone(), entry);
+        self.memory_used += entry_size;
+
+        if let Some(entry) = &old_value {
+            self.memory_used -= entry.size_bytes;
+        }
+
+        self.evict_entries();
+
+        old_value.map(|v| v.metas)
+    }
+
+    /// Evicts entries from the LRU cache until `memory_used` is lower than `memory_limit`.
+    fn evict_entries(&mut self) {
+        while self.memory_used > self.memory_limit {
+            if let Some(removed) = self.lru_queue.pop() {
+                self.memory_used -= removed.1.size_bytes;
+            } else {
+                // cache is empty while memory_used > memory_limit, cannot happen
+                debug_assert!(
+                    false,
+                    "cache is empty while memory_used > memory_limit, cannot happen"
+                );
+                return;
+            }
+        }
+    }
+
+    /// Removes an entry from the cache and returns it, if it exists.
+    fn remove(&mut self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        if let Some(entry) = self.lru_queue.remove(k) {
+            self.memory_used -= entry.size_bytes;
+            Some(entry.metas)
+        } else {
+            None
+        }
+    }
+
+    /// Returns the number of entries currently cached.
+    fn len(&self) -> usize {
+        self.lru_queue.len()
+    }
+
+    /// Removes all entries from the cache.
+    fn clear(&mut self) {
+        self.lru_queue.clear();
+        self.memory_used = 0;
+    }
+}
+
+impl ListFilesCache for DefaultListFilesCache {
+    fn cache_limit(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.memory_limit
+    }
+
+    fn cache_ttl(&self) -> Option<Duration> {
+        let state = self.state.lock().unwrap();
+        state.ttl
+    }
+
+    fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+}
+
+impl CacheAccessor<Path, Arc<Vec<ObjectMeta>>> for DefaultListFilesCache {
+    type Extra = ObjectMeta;
+
+    fn get(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.get(k)
+    }
+
+    fn get_with_extra(&self, k: &Path, _e: &Self::Extra) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.get(k)
+    }
+
+    fn put(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.put(key, value)
+    }
+
+    fn put_with_extra(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+        _e: &Self::Extra,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.put(key, value)
+    }
+
+    fn remove(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.remove(k)
+    }
+
+    fn contains_key(&self, k: &Path) -> bool {
+        let mut state = self.state.lock().unwrap();
+        state.contains_key(k)
+    }
+
+    fn len(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.len()
+    }
+
+    fn clear(&self) {
+        let mut state = self.state.lock().unwrap();
+        state.clear();
+    }
+
+    fn name(&self) -> String {
+        String::from("DefaultListFilesCache")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use chrono::DateTime;
+    use std::thread;
+
+    /// Helper function to create a test ObjectMeta with a specific path and location string size
+    fn create_test_object_meta(path: &str, location_size: usize) -> ObjectMeta {
+        // Create a location string of the desired size by padding with zeros
+        let location_str = if location_size > path.len() {
+            format!("{}{}", path, "0".repeat(location_size - path.len()))
+        } else {
+            path.to_string()
+        };
+
+        ObjectMeta {
+            location: Path::from(location_str),
+            last_modified: DateTime::parse_from_rfc3339("2022-09-27T22:36:00+02:00")
+                .unwrap()
+                .into(),
+            size: 1024,
+            e_tag: None,
+            version: None,
+        }
+    }
+
+    /// Helper function to create a vector of ObjectMeta with at least meta_size bytes
+    fn create_test_list_files_entry(
+        path: &str,
+        count: usize,
+        meta_size: usize,
+    ) -> (Path, Arc<Vec<ObjectMeta>>, usize) {
+        let metas: Vec<ObjectMeta> = (0..count)
+            .map(|i| create_test_object_meta(&format!("file{i}"), meta_size))
+            .collect();
+        let metas = Arc::new(metas);
+
+        // Calculate actual size using the same logic as ListFilesEntry::try_new
+        let size = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).sum::<usize>();
+
+        (Path::from(path), metas, size)
+    }
+
+    #[test]
+    fn test_basic_operations() {
+        let cache = DefaultListFilesCache::default();
+        let path = Path::from("test_path");
+
+        // Initially cache is empty
+        assert!(cache.get(&path).is_none());
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put an entry
+        let meta = create_test_object_meta("file1", 50);
+        let value = Arc::new(vec![meta.clone()]);
+        cache.put(&path, Arc::clone(&value));
+
+        // Entry should be retrievable
+        assert!(cache.contains_key(&path));
+        assert_eq!(cache.len(), 1);
+        let retrieved = cache.get(&path).unwrap();
+        assert_eq!(retrieved.len(), 1);
+        assert_eq!(retrieved[0].location, meta.location);
+
+        // Remove the entry
+        let removed = cache.remove(&path).unwrap();
+        assert_eq!(removed.len(), 1);
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put multiple entries
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 3, 50);
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Clear all entries
+        cache.clear();
+        assert_eq!(cache.len(), 0);
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_lru_eviction_basic() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to exactly fit all three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // All three entries should fit
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Adding a new entry should evict path1 (LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_lru_ordering_after_access() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to fit exactly three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Access path1 to move it to front (MRU)
+        // Order is now: path2 (LRU), path3, path1 (MRU)
+        cache.get(&path1);
+
+        // Adding a new entry should evict path2 (the LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1)); // Still present (recently accessed)
+        assert!(!cache.contains_key(&path2)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_reject_too_large() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+
+        // Set cache limit to fit both entries
+        let cache = DefaultListFilesCache::new(size * 2, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Try to add an entry that's too large to fit in the cache
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 1000);
+        cache.put(&path_large, value_large);
+
+        // Large entry should not be added
+        assert!(!cache.contains_key(&path_large));
+        assert_eq!(cache.len(), 2);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_multiple_evictions() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit for exactly 3 entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Add a large entry that requires evicting 2 entries
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 200);
+        cache.put(&path_large, value_large);
+
+        // path1 and path2 should be evicted (both LRU), path3 and path_large remain
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(!cache.contains_key(&path2)); // Evicted
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path_large));
+    }
+
+    #[test]
+    fn test_cache_limit_resize() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Resize cache to only fit one entry
+        cache.update_cache_limit(size);
+
+        // Should keep only the most recent entry (path3, the MRU)
+        assert_eq!(cache.len(), 1);
+        assert!(cache.contains_key(&path3));
+        // Earlier entries (LRU) should be evicted
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_entry_update_with_size_change() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3_v1, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3_v1);
+        assert_eq!(cache.len(), 3);
+
+        // Update path3 with same size - should not cause eviction
+        let (_, value3_v2, _) = create_test_list_files_entry("path3", 1, 100);
+        cache.put(&path3, value3_v2);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Update path3 with larger size that requires evicting path1 (LRU)
+        let (_, value3_v3, _) = create_test_list_files_entry("path3", 1, 200);
+        cache.put(&path3, value3_v3);
+
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+    }
+
+    #[test]
+    fn test_cache_with_ttl() {
+        let ttl = Duration::from_millis(100);
+        let cache = DefaultListFilesCache::new(10000, Some(ttl));
+
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 2, 50);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+
+        // Entries should be accessible immediately
+        assert!(cache.get(&path1).is_some());
+        assert!(cache.get(&path2).is_some());
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert_eq!(cache.len(), 2);
+
+        // Wait for TTL to expire
+        thread::sleep(Duration::from_millis(150));
+
+        // Entries should now return None and be removed when observed through get or contains_key
+        assert!(cache.get(&path1).is_none());
+        assert_eq!(cache.len(), 1); // path1 was removed by get()
+        assert!(!cache.contains_key(&path2));
+        assert_eq!(cache.len(), 0); // path2 was removed by contains_key()
+    }
+
+    #[test]
+    fn test_cache_with_ttl_and_lru() {

Review Comment:
   One classic way is to pass a template / object to the cache to provide the current time, rather than calling `std::instant::now()` directly
   
   Then the tests can use a mock version of the time provider (that is explicitly controlled) and the normal code uses std::Instant::now
   
   The downside of this approach is that it does mean what is tested has some differences than what is in production



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2592171980


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;
+
+        Some(Self {
+            metas,
+            size_bytes,
+            expires: ttl.map(|t| Instant::now() + t),
+        })
+    }
+}
+
+/// Calculates the number of bytes an [`ObjectMeta`] occupies in the heap.
+fn meta_heap_bytes(object_meta: &ObjectMeta) -> usize {
+    let mut size = object_meta.location.as_ref().len();
+
+    if let Some(e) = &object_meta.e_tag {
+        size += e.len();
+    }
+    if let Some(v) = &object_meta.version {
+        size += v.len();
+    }
+
+    size
+}
+
+/// The default memory limit for the [`DefaultListFilesCache`]
+pub(super) const DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT: usize = 1024 * 1024; // 1MiB
+
+/// Handles the inner state of the [`DefaultListFilesCache`] struct.
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, ListFilesEntry>,
+    memory_limit: usize,
+    memory_used: usize,
+    ttl: Option<Duration>,
+}
+
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit: DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT,
+            memory_used: 0,
+            ttl: None,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit,
+            memory_used: 0,
+            ttl,
+        }
+    }
+
+    /// Returns the respective entry from the cache, if it exists and the entry has not expired.
+    /// If the entry exists it becomes the most recently used. If the entry has expired it is
+    /// removed from the cache
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = self.lru_queue.get(key)?;
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(key);
+                None
+            }
+            _ => Some(Arc::clone(&entry.metas)),
+        }
+    }
+
+    /// Checks if the respective entry is currently cached. If the entry has expired it is removed
+    /// from the cache.
+    /// The LRU queue is not updated.
+    fn contains_key(&mut self, k: &Path) -> bool {
+        let Some(entry) = self.lru_queue.peek(k) else {
+            return false;
+        };
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(k);
+                false
+            }
+            _ => true,
+        }
+    }
+
+    /// Adds a new key-value pair to cache, meaning LRU entries might be evicted if required.
+    /// If the key is already in the cache, the previous entry is returned.
+    /// If the size of the entry is greater than the `memory_limit`, the value is not inserted.
+    fn put(
+        &mut self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = ListFilesEntry::try_new(value, self.ttl)?;
+        let entry_size = entry.size_bytes;
+
+        // no point in trying to add this value to the cache if it cannot fit entirely
+        if entry_size > self.memory_limit {
+            return None;
+        }
+
+        // if the key is already in the cache, the old value is removed
+        let old_value = self.lru_queue.put(key.clone(), entry);
+        self.memory_used += entry_size;
+
+        if let Some(entry) = &old_value {
+            self.memory_used -= entry.size_bytes;
+        }
+
+        self.evict_entries();
+
+        old_value.map(|v| v.metas)
+    }
+
+    /// Evicts entries from the LRU cache until `memory_used` is lower than `memory_limit`.
+    fn evict_entries(&mut self) {
+        while self.memory_used > self.memory_limit {
+            if let Some(removed) = self.lru_queue.pop() {
+                self.memory_used -= removed.1.size_bytes;
+            } else {
+                // cache is empty while memory_used > memory_limit, cannot happen
+                debug_assert!(
+                    false,
+                    "cache is empty while memory_used > memory_limit, cannot happen"
+                );
+                return;
+            }
+        }
+    }
+
+    /// Removes an entry from the cache and returns it, if it exists.
+    fn remove(&mut self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        if let Some(entry) = self.lru_queue.remove(k) {
+            self.memory_used -= entry.size_bytes;
+            Some(entry.metas)
+        } else {
+            None
+        }
+    }
+
+    /// Returns the number of entries currently cached.
+    fn len(&self) -> usize {
+        self.lru_queue.len()
+    }
+
+    /// Removes all entries from the cache.
+    fn clear(&mut self) {
+        self.lru_queue.clear();
+        self.memory_used = 0;
+    }
+}
+
+impl ListFilesCache for DefaultListFilesCache {
+    fn cache_limit(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.memory_limit
+    }
+
+    fn cache_ttl(&self) -> Option<Duration> {
+        let state = self.state.lock().unwrap();
+        state.ttl
+    }
+
+    fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+}
+
+impl CacheAccessor<Path, Arc<Vec<ObjectMeta>>> for DefaultListFilesCache {
+    type Extra = ObjectMeta;
+
+    fn get(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.get(k)
+    }
+
+    fn get_with_extra(&self, k: &Path, _e: &Self::Extra) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.get(k)
+    }
+
+    fn put(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.put(key, value)
+    }
+
+    fn put_with_extra(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+        _e: &Self::Extra,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.put(key, value)
+    }
+
+    fn remove(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.remove(k)
+    }
+
+    fn contains_key(&self, k: &Path) -> bool {
+        let mut state = self.state.lock().unwrap();
+        state.contains_key(k)
+    }
+
+    fn len(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.len()
+    }
+
+    fn clear(&self) {
+        let mut state = self.state.lock().unwrap();
+        state.clear();
+    }
+
+    fn name(&self) -> String {
+        String::from("DefaultListFilesCache")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use chrono::DateTime;
+    use std::thread;
+
+    /// Helper function to create a test ObjectMeta with a specific path and location string size
+    fn create_test_object_meta(path: &str, location_size: usize) -> ObjectMeta {
+        // Create a location string of the desired size by padding with zeros
+        let location_str = if location_size > path.len() {
+            format!("{}{}", path, "0".repeat(location_size - path.len()))
+        } else {
+            path.to_string()
+        };
+
+        ObjectMeta {
+            location: Path::from(location_str),
+            last_modified: DateTime::parse_from_rfc3339("2022-09-27T22:36:00+02:00")
+                .unwrap()
+                .into(),
+            size: 1024,
+            e_tag: None,
+            version: None,
+        }
+    }
+
+    /// Helper function to create a vector of ObjectMeta with at least meta_size bytes
+    fn create_test_list_files_entry(
+        path: &str,
+        count: usize,
+        meta_size: usize,
+    ) -> (Path, Arc<Vec<ObjectMeta>>, usize) {
+        let metas: Vec<ObjectMeta> = (0..count)
+            .map(|i| create_test_object_meta(&format!("file{i}"), meta_size))
+            .collect();
+        let metas = Arc::new(metas);
+
+        // Calculate actual size using the same logic as ListFilesEntry::try_new
+        let size = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).sum::<usize>();
+
+        (Path::from(path), metas, size)
+    }
+
+    #[test]
+    fn test_basic_operations() {
+        let cache = DefaultListFilesCache::default();
+        let path = Path::from("test_path");
+
+        // Initially cache is empty
+        assert!(cache.get(&path).is_none());
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put an entry
+        let meta = create_test_object_meta("file1", 50);
+        let value = Arc::new(vec![meta.clone()]);
+        cache.put(&path, Arc::clone(&value));
+
+        // Entry should be retrievable
+        assert!(cache.contains_key(&path));
+        assert_eq!(cache.len(), 1);
+        let retrieved = cache.get(&path).unwrap();
+        assert_eq!(retrieved.len(), 1);
+        assert_eq!(retrieved[0].location, meta.location);
+
+        // Remove the entry
+        let removed = cache.remove(&path).unwrap();
+        assert_eq!(removed.len(), 1);
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put multiple entries
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 3, 50);
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Clear all entries
+        cache.clear();
+        assert_eq!(cache.len(), 0);
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_lru_eviction_basic() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to exactly fit all three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // All three entries should fit
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Adding a new entry should evict path1 (LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_lru_ordering_after_access() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to fit exactly three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Access path1 to move it to front (MRU)
+        // Order is now: path2 (LRU), path3, path1 (MRU)
+        cache.get(&path1);
+
+        // Adding a new entry should evict path2 (the LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1)); // Still present (recently accessed)
+        assert!(!cache.contains_key(&path2)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_reject_too_large() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+
+        // Set cache limit to fit both entries
+        let cache = DefaultListFilesCache::new(size * 2, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Try to add an entry that's too large to fit in the cache
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 1000);
+        cache.put(&path_large, value_large);
+
+        // Large entry should not be added
+        assert!(!cache.contains_key(&path_large));
+        assert_eq!(cache.len(), 2);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_multiple_evictions() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit for exactly 3 entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Add a large entry that requires evicting 2 entries
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 200);
+        cache.put(&path_large, value_large);
+
+        // path1 and path2 should be evicted (both LRU), path3 and path_large remain
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(!cache.contains_key(&path2)); // Evicted
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path_large));
+    }
+
+    #[test]
+    fn test_cache_limit_resize() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Resize cache to only fit one entry
+        cache.update_cache_limit(size);
+
+        // Should keep only the most recent entry (path3, the MRU)
+        assert_eq!(cache.len(), 1);
+        assert!(cache.contains_key(&path3));
+        // Earlier entries (LRU) should be evicted
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_entry_update_with_size_change() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3_v1, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3_v1);
+        assert_eq!(cache.len(), 3);
+
+        // Update path3 with same size - should not cause eviction
+        let (_, value3_v2, _) = create_test_list_files_entry("path3", 1, 100);
+        cache.put(&path3, value3_v2);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Update path3 with larger size that requires evicting path1 (LRU)
+        let (_, value3_v3, _) = create_test_list_files_entry("path3", 1, 200);
+        cache.put(&path3, value3_v3);
+
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+    }
+
+    #[test]
+    fn test_cache_with_ttl() {
+        let ttl = Duration::from_millis(100);
+        let cache = DefaultListFilesCache::new(10000, Some(ttl));
+
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 2, 50);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+
+        // Entries should be accessible immediately
+        assert!(cache.get(&path1).is_some());
+        assert!(cache.get(&path2).is_some());
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert_eq!(cache.len(), 2);
+
+        // Wait for TTL to expire
+        thread::sleep(Duration::from_millis(150));
+
+        // Entries should now return None and be removed when observed through get or contains_key
+        assert!(cache.get(&path1).is_none());
+        assert_eq!(cache.len(), 1); // path1 was removed by get()
+        assert!(!cache.contains_key(&path2));
+        assert_eq!(cache.len(), 0); // path2 was removed by contains_key()
+    }
+
+    #[test]
+    fn test_cache_with_ttl_and_lru() {
+        let ttl = Duration::from_millis(200);
+        let cache = DefaultListFilesCache::new(1000, Some(ttl));
+
+        let (path1, value1, _) = create_test_list_files_entry("path1", 1, 400);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 400);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 400);
+
+        cache.put(&path1, value1);
+        thread::sleep(Duration::from_millis(50));
+        cache.put(&path2, value2);
+        thread::sleep(Duration::from_millis(50));
+
+        // path3 should evict path1 due to size limit
+        cache.put(&path3, value3);
+        assert!(!cache.contains_key(&path1)); // Evicted by LRU
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Wait for path2 to expire
+        thread::sleep(Duration::from_millis(150));
+        assert!(!cache.contains_key(&path2)); // Expired
+        assert!(cache.contains_key(&path3)); // Still valid
+    }

Review Comment:
   this seems flaky.
   
   see:
   - https://github.com/apache/datafusion/actions/runs/19957661839/job/57235793957?pr=19101
   
   which only enable feature flag in benchmark for physical plan



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561931745


##########
datafusion/catalog-listing/src/table.rs:
##########
@@ -578,6 +578,11 @@ impl TableProvider for ListingTable {
         let keep_partition_by_columns =
             state.config_options().execution.keep_partition_by_columns;
 
+        // Invalidate cache entries for this table if they exist
+        if let Some(lfc) = state.runtime_env().cache_manager.get_list_files_cache() {
+            let _ = lfc.remove(table_path.prefix());
+        }

Review Comment:
   For the initial implementation I chose to use the simple option of invalidating a table's cache entries on `INSERT`. Since the default TTL is infinite any `DataSink` that only supports writing new files (as opposed to appending) would never pick up inserts without some action being taken here.
   
   It would be very nice to handle this more elegantly in the future.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2593205128


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;
+
+        Some(Self {
+            metas,
+            size_bytes,
+            expires: ttl.map(|t| Instant::now() + t),
+        })
+    }
+}
+
+/// Calculates the number of bytes an [`ObjectMeta`] occupies in the heap.
+fn meta_heap_bytes(object_meta: &ObjectMeta) -> usize {
+    let mut size = object_meta.location.as_ref().len();
+
+    if let Some(e) = &object_meta.e_tag {
+        size += e.len();
+    }
+    if let Some(v) = &object_meta.version {
+        size += v.len();
+    }
+
+    size
+}
+
+/// The default memory limit for the [`DefaultListFilesCache`]
+pub(super) const DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT: usize = 1024 * 1024; // 1MiB
+
+/// Handles the inner state of the [`DefaultListFilesCache`] struct.
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, ListFilesEntry>,
+    memory_limit: usize,
+    memory_used: usize,
+    ttl: Option<Duration>,
+}
+
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit: DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT,
+            memory_used: 0,
+            ttl: None,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit,
+            memory_used: 0,
+            ttl,
+        }
+    }
+
+    /// Returns the respective entry from the cache, if it exists and the entry has not expired.
+    /// If the entry exists it becomes the most recently used. If the entry has expired it is
+    /// removed from the cache
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = self.lru_queue.get(key)?;
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(key);
+                None
+            }
+            _ => Some(Arc::clone(&entry.metas)),
+        }
+    }
+
+    /// Checks if the respective entry is currently cached. If the entry has expired it is removed
+    /// from the cache.
+    /// The LRU queue is not updated.
+    fn contains_key(&mut self, k: &Path) -> bool {
+        let Some(entry) = self.lru_queue.peek(k) else {
+            return false;
+        };
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(k);
+                false
+            }
+            _ => true,
+        }
+    }
+
+    /// Adds a new key-value pair to cache, meaning LRU entries might be evicted if required.
+    /// If the key is already in the cache, the previous entry is returned.
+    /// If the size of the entry is greater than the `memory_limit`, the value is not inserted.
+    fn put(
+        &mut self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = ListFilesEntry::try_new(value, self.ttl)?;
+        let entry_size = entry.size_bytes;
+
+        // no point in trying to add this value to the cache if it cannot fit entirely
+        if entry_size > self.memory_limit {
+            return None;
+        }
+
+        // if the key is already in the cache, the old value is removed
+        let old_value = self.lru_queue.put(key.clone(), entry);
+        self.memory_used += entry_size;
+
+        if let Some(entry) = &old_value {
+            self.memory_used -= entry.size_bytes;
+        }
+
+        self.evict_entries();
+
+        old_value.map(|v| v.metas)
+    }
+
+    /// Evicts entries from the LRU cache until `memory_used` is lower than `memory_limit`.
+    fn evict_entries(&mut self) {
+        while self.memory_used > self.memory_limit {
+            if let Some(removed) = self.lru_queue.pop() {
+                self.memory_used -= removed.1.size_bytes;
+            } else {
+                // cache is empty while memory_used > memory_limit, cannot happen
+                debug_assert!(
+                    false,
+                    "cache is empty while memory_used > memory_limit, cannot happen"
+                );
+                return;
+            }
+        }
+    }
+
+    /// Removes an entry from the cache and returns it, if it exists.
+    fn remove(&mut self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        if let Some(entry) = self.lru_queue.remove(k) {
+            self.memory_used -= entry.size_bytes;
+            Some(entry.metas)
+        } else {
+            None
+        }
+    }
+
+    /// Returns the number of entries currently cached.
+    fn len(&self) -> usize {
+        self.lru_queue.len()
+    }
+
+    /// Removes all entries from the cache.
+    fn clear(&mut self) {
+        self.lru_queue.clear();
+        self.memory_used = 0;
+    }
+}
+
+impl ListFilesCache for DefaultListFilesCache {
+    fn cache_limit(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.memory_limit
+    }
+
+    fn cache_ttl(&self) -> Option<Duration> {
+        let state = self.state.lock().unwrap();
+        state.ttl
+    }
+
+    fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+}
+
+impl CacheAccessor<Path, Arc<Vec<ObjectMeta>>> for DefaultListFilesCache {
+    type Extra = ObjectMeta;
+
+    fn get(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.get(k)
+    }
+
+    fn get_with_extra(&self, k: &Path, _e: &Self::Extra) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.get(k)
+    }
+
+    fn put(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.put(key, value)
+    }
+
+    fn put_with_extra(
+        &self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+        _e: &Self::Extra,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.put(key, value)
+    }
+
+    fn remove(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.remove(k)
+    }
+
+    fn contains_key(&self, k: &Path) -> bool {
+        let mut state = self.state.lock().unwrap();
+        state.contains_key(k)
+    }
+
+    fn len(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.len()
+    }
+
+    fn clear(&self) {
+        let mut state = self.state.lock().unwrap();
+        state.clear();
+    }
+
+    fn name(&self) -> String {
+        String::from("DefaultListFilesCache")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use chrono::DateTime;
+    use std::thread;
+
+    /// Helper function to create a test ObjectMeta with a specific path and location string size
+    fn create_test_object_meta(path: &str, location_size: usize) -> ObjectMeta {
+        // Create a location string of the desired size by padding with zeros
+        let location_str = if location_size > path.len() {
+            format!("{}{}", path, "0".repeat(location_size - path.len()))
+        } else {
+            path.to_string()
+        };
+
+        ObjectMeta {
+            location: Path::from(location_str),
+            last_modified: DateTime::parse_from_rfc3339("2022-09-27T22:36:00+02:00")
+                .unwrap()
+                .into(),
+            size: 1024,
+            e_tag: None,
+            version: None,
+        }
+    }
+
+    /// Helper function to create a vector of ObjectMeta with at least meta_size bytes
+    fn create_test_list_files_entry(
+        path: &str,
+        count: usize,
+        meta_size: usize,
+    ) -> (Path, Arc<Vec<ObjectMeta>>, usize) {
+        let metas: Vec<ObjectMeta> = (0..count)
+            .map(|i| create_test_object_meta(&format!("file{i}"), meta_size))
+            .collect();
+        let metas = Arc::new(metas);
+
+        // Calculate actual size using the same logic as ListFilesEntry::try_new
+        let size = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).sum::<usize>();
+
+        (Path::from(path), metas, size)
+    }
+
+    #[test]
+    fn test_basic_operations() {
+        let cache = DefaultListFilesCache::default();
+        let path = Path::from("test_path");
+
+        // Initially cache is empty
+        assert!(cache.get(&path).is_none());
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put an entry
+        let meta = create_test_object_meta("file1", 50);
+        let value = Arc::new(vec![meta.clone()]);
+        cache.put(&path, Arc::clone(&value));
+
+        // Entry should be retrievable
+        assert!(cache.contains_key(&path));
+        assert_eq!(cache.len(), 1);
+        let retrieved = cache.get(&path).unwrap();
+        assert_eq!(retrieved.len(), 1);
+        assert_eq!(retrieved[0].location, meta.location);
+
+        // Remove the entry
+        let removed = cache.remove(&path).unwrap();
+        assert_eq!(removed.len(), 1);
+        assert!(!cache.contains_key(&path));
+        assert_eq!(cache.len(), 0);
+
+        // Put multiple entries
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 3, 50);
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Clear all entries
+        cache.clear();
+        assert_eq!(cache.len(), 0);
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_lru_eviction_basic() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to exactly fit all three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // All three entries should fit
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Adding a new entry should evict path1 (LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_lru_ordering_after_access() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit to fit exactly three entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Access path1 to move it to front (MRU)
+        // Order is now: path2 (LRU), path3, path1 (MRU)
+        cache.get(&path1);
+
+        // Adding a new entry should evict path2 (the LRU)
+        let (path4, value4, _) = create_test_list_files_entry("path4", 1, 100);
+        cache.put(&path4, value4);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1)); // Still present (recently accessed)
+        assert!(!cache.contains_key(&path2)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path4));
+    }
+
+    #[test]
+    fn test_reject_too_large() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+
+        // Set cache limit to fit both entries
+        let cache = DefaultListFilesCache::new(size * 2, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        assert_eq!(cache.len(), 2);
+
+        // Try to add an entry that's too large to fit in the cache
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 1000);
+        cache.put(&path_large, value_large);
+
+        // Large entry should not be added
+        assert!(!cache.contains_key(&path_large));
+        assert_eq!(cache.len(), 2);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_multiple_evictions() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        // Set cache limit for exactly 3 entries
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Add a large entry that requires evicting 2 entries
+        let (path_large, value_large, _) = create_test_list_files_entry("large", 1, 200);
+        cache.put(&path_large, value_large);
+
+        // path1 and path2 should be evicted (both LRU), path3 and path_large remain
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted
+        assert!(!cache.contains_key(&path2)); // Evicted
+        assert!(cache.contains_key(&path3));
+        assert!(cache.contains_key(&path_large));
+    }
+
+    #[test]
+    fn test_cache_limit_resize() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3);
+        assert_eq!(cache.len(), 3);
+
+        // Resize cache to only fit one entry
+        cache.update_cache_limit(size);
+
+        // Should keep only the most recent entry (path3, the MRU)
+        assert_eq!(cache.len(), 1);
+        assert!(cache.contains_key(&path3));
+        // Earlier entries (LRU) should be evicted
+        assert!(!cache.contains_key(&path1));
+        assert!(!cache.contains_key(&path2));
+    }
+
+    #[test]
+    fn test_entry_update_with_size_change() {
+        let (path1, value1, size) = create_test_list_files_entry("path1", 1, 100);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 1, 100);
+        let (path3, value3_v1, _) = create_test_list_files_entry("path3", 1, 100);
+
+        let cache = DefaultListFilesCache::new(size * 3, None);
+
+        // Add three entries
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+        cache.put(&path3, value3_v1);
+        assert_eq!(cache.len(), 3);
+
+        // Update path3 with same size - should not cause eviction
+        let (_, value3_v2, _) = create_test_list_files_entry("path3", 1, 100);
+        cache.put(&path3, value3_v2);
+
+        assert_eq!(cache.len(), 3);
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+
+        // Update path3 with larger size that requires evicting path1 (LRU)
+        let (_, value3_v3, _) = create_test_list_files_entry("path3", 1, 200);
+        cache.put(&path3, value3_v3);
+
+        assert_eq!(cache.len(), 2);
+        assert!(!cache.contains_key(&path1)); // Evicted (was LRU)
+        assert!(cache.contains_key(&path2));
+        assert!(cache.contains_key(&path3));
+    }
+
+    #[test]
+    fn test_cache_with_ttl() {
+        let ttl = Duration::from_millis(100);
+        let cache = DefaultListFilesCache::new(10000, Some(ttl));
+
+        let (path1, value1, _) = create_test_list_files_entry("path1", 2, 50);
+        let (path2, value2, _) = create_test_list_files_entry("path2", 2, 50);
+
+        cache.put(&path1, value1);
+        cache.put(&path2, value2);
+
+        // Entries should be accessible immediately
+        assert!(cache.get(&path1).is_some());
+        assert!(cache.get(&path2).is_some());
+        assert!(cache.contains_key(&path1));
+        assert!(cache.contains_key(&path2));
+        assert_eq!(cache.len(), 2);
+
+        // Wait for TTL to expire
+        thread::sleep(Duration::from_millis(150));
+
+        // Entries should now return None and be removed when observed through get or contains_key
+        assert!(cache.get(&path1).is_none());
+        assert_eq!(cache.len(), 1); // path1 was removed by get()
+        assert!(!cache.contains_key(&path2));
+        assert_eq!(cache.len(), 0); // path2 was removed by contains_key()
+    }
+
+    #[test]
+    fn test_cache_with_ttl_and_lru() {

Review Comment:
   This test is failing intermittently on main -- see https://github.com/apache/datafusion/issues/19114
   
   I suspect it is due to timing



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2548179325


##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min

Review Comment:
   The actual default values here probably need to be discussed. These seemed relatively sane to me, but any input here on what values these should have to best accommodate a variety of workflows would be useful feedback.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alchemist51 (via GitHub)" <gi...@apache.org>.
alchemist51 commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2548494519


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -228,13 +276,30 @@ impl CacheManagerConfig {
     }
 
     /// Set the cache for listing files.
-    ///     
+    ///
     /// Default is `None` (disabled).
-    pub fn with_list_files_cache(mut self, cache: Option<ListFilesCache>) -> Self {
+    pub fn with_list_files_cache(
+        mut self,
+        cache: Option<Arc<dyn ListFilesCache>>,
+    ) -> Self {
         self.list_files_cache = cache;
         self
     }
 
+    pub fn with_list_files_cache_limit(mut self, limit: usize) -> Self {
+        self.list_files_cache_limit = limit;
+        self
+    }
+
+    pub fn with_list_files_cache_ttl(mut self, ttl: Duration) -> Self {
+        self.list_files_cache_ttl = ttl;
+        if ttl.is_zero() {

Review Comment:
   Why are we setting it to None in case of no TTL?



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550537134


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   I think this is a reasonable suggestion, and it looks like there may be some ongoing discussion around this topic here:
    - https://github.com/apache/datafusion/issues/18405
   
   While that work would undoubtedly impact this (and other) default cache implementations, I think it should probably be discussed separately to this effort.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550795060


##########
datafusion/core/tests/datasource/object_store_access.rs:
##########
@@ -237,8 +233,7 @@ async fn query_partitioned_csv_file() {
     +---------+-------+-------+---+----+-----+
     ------- Object Store Request Summary -------
     RequestCountingObjectStore()
-    Total Requests: 2
-    - LIST prefix=data
+    Total Requests: 1

Review Comment:
   Yes, I think that's a good test case, and obviously any tests have more or less been ignored thus far. The only tests I actually focused on initially were these tests since they both show (and helped me validate) this code was actually performing internal caching as expected.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2586593992


##########
datafusion/core/tests/datasource/object_store_access.rs:
##########
@@ -98,6 +98,59 @@ async fn create_multi_file_csv_file() {
     );
 }
 
+#[tokio::test]
+async fn multi_query_multi_file_csv_file() {
+    let test = Test::new().with_multi_file_csv().await;
+    assert_snapshot!(
+        test.query("select * from csv_table").await,
+        @r"
+    ------- Query Output (6 rows) -------
+    +---------+-------+-------+
+    | c1      | c2    | c3    |
+    +---------+-------+-------+
+    | 0.0     | 0.0   | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00001 | 1e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00002 | 2e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    +---------+-------+-------+
+    ------- Object Store Request Summary -------
+    RequestCountingObjectStore()
+    Total Requests: 4
+    - LIST prefix=data
+    - GET  (opts) path=data/file_0.csv
+    - GET  (opts) path=data/file_1.csv
+    - GET  (opts) path=data/file_2.csv
+    "
+    );
+
+    // the second query should re-use the cached LIST results and should not reissue LIST
+    assert_snapshot!(
+        test.query("select * from csv_table").await,
+        @r"
+    ------- Query Output (6 rows) -------
+    +---------+-------+-------+
+    | c1      | c2    | c3    |
+    +---------+-------+-------+
+    | 0.0     | 0.0   | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00001 | 1e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    | 0.00002 | 2e-12 | true  |
+    | 0.00003 | 5e-12 | false |
+    +---------+-------+-------+
+    ------- Object Store Request Summary -------
+    RequestCountingObjectStore()
+    Total Requests: 4

Review Comment:
   I think it makes sense to do additional work in a follow on R --  I see there is already a ticket tracking the work to turn it on by default,
   - https://github.com/apache/datafusion/issues/18827
   
   



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550777095


##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min

Review Comment:
   Hmmm, my initial thought here was that here are certainly going to be users who don't read the release notes and their expected workflow of new objects being picked up on every query will be broken. With a relatively short TTL their data will at least appear eventually, which may be preferable to not-at-all. However, I really like the strategy of using the most deterministic solution as the default (infinite), especially as the long-term solution.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550959411


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   Yes, that sounds like a great idea to me -- i think there is a wide wonderful world of complex caching strategies that people might want



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] POC for DefaultListFilesCache [datafusion]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2550693419


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:
+    CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>
+{
+    // Returns the cache's object limit.
+    fn cache_limit(&self) -> usize;
+
+    // Returns the cache's object ttl.
+    fn cache_ttl(&self) -> Duration;
+
+    // Updates the cache with a new boject limit.

Review Comment:
   ```suggestion
       // Updates the cache with a new object limit.
   ```



##########
datafusion/core/tests/datasource/object_store_access.rs:
##########
@@ -237,8 +233,7 @@ async fn query_partitioned_csv_file() {
     +---------+-------+-------+---+----+-----+
     ------- Object Store Request Summary -------
     RequestCountingObjectStore()
-    Total Requests: 2
-    - LIST prefix=data
+    Total Requests: 1

Review Comment:
   Could we also add a test that shows that once the cache eviction happens, a subsquent query does actually make a new LIST request? 



##########
datafusion/core/tests/datasource/object_store_access.rs:
##########
@@ -117,8 +117,7 @@ async fn query_multi_csv_file() {
     +---------+-------+-------+
     ------- Object Store Request Summary -------
     RequestCountingObjectStore()
-    Total Requests: 4
-    - LIST prefix=data
+    Total Requests: 3

Review Comment:
   it is pretty neat to see this in action



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details

Review Comment:
   This is technically a breaking API change (a good one in my mind). I am just pointing it out



##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min
+
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, (Arc<Vec<ObjectMeta>>, Instant)>,
+    capacity: usize, // TODO: do "bytes" matter here, or should we stick with "entries"?
+    size: usize,
+    ttl: Duration,
+}
+
+// TODO: Do we even want to support "default" here?
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            size: 0,
+            ttl: DEFAULT_LIST_FILES_CACHE_TTL,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity,
+            size: 0,
+            ttl,
+        }
+    }
+
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {

Review Comment:
   I think we just changes some of these APIs to take `&self` rather than `&mut self` -- I am not sure if we want to do the same thing here.
   -  https://github.com/apache/datafusion/pull/18726



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -189,13 +228,20 @@ pub struct CacheManagerConfig {
     /// Avoid get same file statistics repeatedly in same datafusion session.
     /// Default is disable. Fow now only supports Parquet files.
     pub table_files_statistics_cache: Option<FileStatisticsCache>,
-    /// Enable cache of file metadata when listing files.
-    /// This setting avoids listing file meta of the same path repeatedly
-    /// in same session, which may be expensive in certain situations (e.g. remote object storage).
+    /// Enable caching of file metadata when listing files.
+    /// Enabling the cache avoids repeat list and metadata fetch operations, which may be expensive
+    /// in certain situations (e.g. remote object storage), for objects under paths that are
+    /// cached.
     /// Note that if this option is enabled, DataFusion will not see any updates to the underlying
-    /// location.  
-    /// Default is disable.
-    pub list_files_cache: Option<ListFilesCache>,
+    /// storage for at least `list_files_cache_ttl` duration.
+    /// Default is disabled.
+    pub list_files_cache: Option<Arc<dyn ListFilesCache>>,
+    /// Limit the number of objects to keep in the `list_files_cache`. Default: ~125k objects
+    pub list_files_cache_limit: usize,

Review Comment:
   I found it a little strange that the cache size is set on the cache manager itself rather than an options struct -- though now i see it is consistent with how metadata_cache_limits work



##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min

Review Comment:
   My personal opinion is that we should set TTL much longer (maybe even infinite) by default. Users who know their files are changing are likely going to have to crank it down from a default anyways, so we might as well make the default behavior more deterministic 



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -209,6 +255,8 @@ impl Default for CacheManagerConfig {
         Self {
             table_files_statistics_cache: Default::default(),
             list_files_cache: Default::default(),
+            list_files_cache_limit: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            list_files_cache_ttl: DEFAULT_LIST_FILES_CACHE_TTL,

Review Comment:
   I do agree having a "infinite TTL" is an important usecase 
   
   I don't have a strong opinion on how that is expressed in the config options



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -140,7 +155,17 @@ impl CacheManager {
         let file_statistic_cache =
             config.table_files_statistics_cache.as_ref().map(Arc::clone);
 
-        let list_files_cache = config.list_files_cache.as_ref().map(Arc::clone);
+        let list_files_cache = config
+            .list_files_cache
+            .as_ref()
+            .map(Arc::clone)
+            .unwrap_or_else(|| {
+                Arc::new(DefaultListFilesCache::new(
+                    // TODO: config
+                    512 * 1024,
+                    Duration::new(600, 0),

Review Comment:
   I agree
   
   Another thing we should do is some way to introspect the cache as part of datafusion-cli



##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min
+
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, (Arc<Vec<ObjectMeta>>, Instant)>,
+    capacity: usize, // TODO: do "bytes" matter here, or should we stick with "entries"?

Review Comment:
   I think that bytes makes more sense, mostly because that is the resource that is actually used. count of items is a proxy for resource usage



##########
datafusion/execution/src/cache/cache_unit.rs:
##########
@@ -111,64 +113,224 @@ impl CacheAccessor<Path, Arc<Statistics>> for DefaultFileStatisticsCache {
 ///
 /// Collected files metadata for listing files.
 ///
-/// Cache is not invalided until user calls [`Self::remove`] or [`Self::clear`].
+/// # Internal details
+///
+/// The `capacity` parameter controls the maximum number of entries in the cache, using a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `capacity`, the least recently used entries are evicted until the total
+/// entries are lower than the `capacity`.
 ///
 /// [`ListFilesCache`]: crate::cache::cache_manager::ListFilesCache
 #[derive(Default)]
 pub struct DefaultListFilesCache {
-    statistics: DashMap<Path, Arc<Vec<ObjectMeta>>>,
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    pub fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(capacity, ttl)),
+        }
+    }
+
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().capacity
+    }
+
+    pub fn cache_ttl(&self) -> Duration {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+pub(super) const DEFAULT_LIST_FILES_CACHE_LIMIT: usize = 128 * 1024; // ~130k objects
+pub(super) const DEFAULT_LIST_FILES_CACHE_TTL: Duration = Duration::new(600, 0); // 10min
+
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, (Arc<Vec<ObjectMeta>>, Instant)>,
+    capacity: usize, // TODO: do "bytes" matter here, or should we stick with "entries"?
+    size: usize,
+    ttl: Duration,
+}
+
+// TODO: Do we even want to support "default" here?
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity: DEFAULT_LIST_FILES_CACHE_LIMIT,
+            size: 0,
+            ttl: DEFAULT_LIST_FILES_CACHE_TTL,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(capacity: usize, ttl: Duration) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            capacity,
+            size: 0,
+            ttl,
+        }
+    }
+
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let (object_metas, expires) = self.lru_queue.get(key)?;
+
+        if Instant::now() > *expires {
+            self.remove(key);
+            None
+        } else {
+            Some(Arc::clone(object_metas))
+        }
+    }
+
+    fn contains_key(&mut self, k: &Path) -> bool {
+        let Some((_, expires)) = self.lru_queue.peek(k) else {
+            return false;
+        };
+
+        if Instant::now() > *expires {
+            self.remove(k);
+            return false;
+        }
+
+        true
+    }
+
+    fn put(
+        &mut self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let value_size = value.len();
+
+        // no point in trying to add this value to the cache if it cannot fit entirely
+        if value_size > self.capacity {
+            return None;
+        }
+
+        // if the key is already in the cache, the old value is removed
+        let expires = Instant::now() + self.ttl;
+        let old_value = self.lru_queue.put(key.clone(), (value, expires));
+        self.size += value_size;
+        if let Some((ref old_metas, _)) = old_value {
+            self.size -= old_metas.len();
+        }
+
+        self.evict_entries();
+
+        old_value.map(|v| v.0)
+    }
+
+    fn evict_entries(&mut self) {
+        while self.size > self.capacity {
+            if let Some(removed) = self.lru_queue.pop() {
+                let metas: Arc<Vec<ObjectMeta>> = removed.1 .0;
+                self.size -= metas.len();
+            } else {
+                // cache is empty while memory_used > memory_limit, cannot happen
+                debug_assert!(
+                    false,
+                    "cache is empty while memory_used > memory_limit, cannot happen"
+                );
+                return;
+            }
+        }
+    }
+
+    /// Removes an entry from the cache and returns it, if it exists.
+    fn remove(&mut self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        if let Some((old_metas, _)) = self.lru_queue.remove(k) {
+            self.capacity -= old_metas.len();
+            Some(old_metas)
+        } else {
+            None
+        }
+    }
+
+    /// Returns the number of entries currently cached.
+    fn len(&self) -> usize {
+        self.lru_queue.len()
+    }
+
+    /// Removes all entries from the cache.
+    fn clear(&mut self) {
+        self.lru_queue.clear();
+        self.capacity = 0;
+    }
+}
+
+impl ListFilesCache for DefaultListFilesCache {
+    fn cache_limit(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.capacity
+    }
+
+    fn cache_ttl(&self) -> Duration {
+        let state = self.state.lock().unwrap();
+        state.ttl
+    }
+
+    fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.capacity = limit;
+        state.evict_entries();
+    }
 }
 
 impl CacheAccessor<Path, Arc<Vec<ObjectMeta>>> for DefaultListFilesCache {
     type Extra = ObjectMeta;
 
     fn get(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
-        self.statistics.get(k).map(|x| Arc::clone(x.value()))
+        let mut state = self.state.lock().unwrap();
+        state.get(k)
     }
 
-    fn get_with_extra(
-        &self,
-        _k: &Path,
-        _e: &Self::Extra,
-    ) -> Option<Arc<Vec<ObjectMeta>>> {
-        panic!("Not supported DefaultListFilesCache get_with_extra")

Review Comment:
   I can't remember what the rationale for this panic was. It seems to have come in via
   - https://github.com/apache/datafusion/pull/7620
   
   Maybe @Ted-Jiang or @suremarc have some thoughts here



##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -42,8 +47,18 @@ pub type FileStatisticsCache =
 /// especially when done over remote object stores.
 ///
 /// See [`crate::runtime_env::RuntimeEnv`] for more details
-pub type ListFilesCache =
-    Arc<dyn CacheAccessor<Path, Arc<Vec<ObjectMeta>>, Extra = ObjectMeta>>;
+pub trait ListFilesCache:

Review Comment:
   I am personally in favor of keeping what is in DataFusion as simple to use / understand as possible (which i think this and the metadata cache do)
   
   In terms of customizable eviction strategy, as we have mentioned elsewhere that is already possible today, but it requires effectively copying/forking the entire cache implementation which adds to the maintenance burden of downstream projects
   
   However, adding more APIs to DataFusion increases the maintenance burden on the core project
   
   So I see customizable eviction strategies as a tradeoff. If there are multiple users who are likely to use a customizable eviction strategy, I agree it makes sense to put it in the core repo. If there are not that many, I think it would be better to keep DataFusion simpler and move the burden downstream for those users who need it.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561940077


##########
datafusion/execution/src/cache/cache_manager.rs:
##########
@@ -189,13 +228,20 @@ pub struct CacheManagerConfig {
     /// Avoid get same file statistics repeatedly in same datafusion session.
     /// Default is disable. Fow now only supports Parquet files.
     pub table_files_statistics_cache: Option<FileStatisticsCache>,
-    /// Enable cache of file metadata when listing files.
-    /// This setting avoids listing file meta of the same path repeatedly
-    /// in same session, which may be expensive in certain situations (e.g. remote object storage).
+    /// Enable caching of file metadata when listing files.
+    /// Enabling the cache avoids repeat list and metadata fetch operations, which may be expensive
+    /// in certain situations (e.g. remote object storage), for objects under paths that are
+    /// cached.
     /// Note that if this option is enabled, DataFusion will not see any updates to the underlying
-    /// location.  
-    /// Default is disable.
-    pub list_files_cache: Option<ListFilesCache>,
+    /// storage for at least `list_files_cache_ttl` duration.
+    /// Default is disabled.
+    pub list_files_cache: Option<Arc<dyn ListFilesCache>>,
+    /// Limit the number of objects to keep in the `list_files_cache`. Default: ~125k objects
+    pub list_files_cache_limit: usize,

Review Comment:
   Yes, it does seem like this API could be easier to use. It seems to me that this would be something that we might want to do as future work and fix up both the metadata and list cache at the same time since this PR has already grown to a pretty sizeable amount of code.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561943263


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+

Review Comment:
   I thought the `cache_unit.rs` file was already getting pretty large so I pulled this implementation into a new module to better organize the code and tests. I think the Metadata cache could probably also be isolated into its own module, but I didn't want to get too heavy handed in this PR.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561943263


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+

Review Comment:
   I thought the `cache_unit.rs` file was already getting pretty large so I pulled this implementation into a new module to better organize the code and tests.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org


Re: [PR] Adds memory-bound DefaultListFilesCache [datafusion]

Posted by "BlakeOrth (via GitHub)" <gi...@apache.org>.
BlakeOrth commented on code in PR #18855:
URL: https://github.com/apache/datafusion/pull/18855#discussion_r2561961610


##########
datafusion/execution/src/cache/list_files_cache.rs:
##########
@@ -0,0 +1,731 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::{
+    sync::{Arc, Mutex},
+    time::Duration,
+};
+
+use datafusion_common::instant::Instant;
+use object_store::{path::Path, ObjectMeta};
+
+use crate::cache::{cache_manager::ListFilesCache, lru_queue::LruQueue, CacheAccessor};
+
+/// Default implementation of [`ListFilesCache`]
+///
+/// Caches file metadata for file listing operations.
+///
+/// # Internal details
+///
+/// The `memory_limit` parameter controls the maximum size of the cache, which uses a Least
+/// Recently Used eviction algorithm. When adding a new entry, if the total number of entries in
+/// the cache exceeds `memory_limit`, the least recently used entries are evicted until the total
+/// size is lower than the `memory_limit`.
+///
+/// # `Extra` Handling
+///
+/// Users should use the [`Self::get`] and [`Self::put`] methods. The
+/// [`Self::get_with_extra`] and [`Self::put_with_extra`] methods simply call
+/// `get` and `put`, respectively.
+#[derive(Default)]
+pub struct DefaultListFilesCache {
+    state: Mutex<DefaultListFilesCacheState>,
+}
+
+impl DefaultListFilesCache {
+    /// Creates a new instance of [`DefaultListFilesCache`].
+    ///
+    /// # Arguments
+    /// * `memory_limit` - The maximum size of the cache, in bytes.
+    /// * `ttl` - The TTL (time-to-live) of entries in the cache.
+    pub fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            state: Mutex::new(DefaultListFilesCacheState::new(memory_limit, ttl)),
+        }
+    }
+
+    /// Returns the cache's memory limit in bytes.
+    pub fn cache_limit(&self) -> usize {
+        self.state.lock().unwrap().memory_limit
+    }
+
+    /// Updates the cache with a new memory limit in bytes.
+    pub fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+
+    /// Returns the TTL (time-to-live) applied to cache entries.
+    pub fn cache_ttl(&self) -> Option<Duration> {
+        self.state.lock().unwrap().ttl
+    }
+}
+
+struct ListFilesEntry {
+    metas: Arc<Vec<ObjectMeta>>,
+    size_bytes: usize,
+    expires: Option<Instant>,
+}
+
+impl ListFilesEntry {
+    fn try_new(metas: Arc<Vec<ObjectMeta>>, ttl: Option<Duration>) -> Option<Self> {
+        let size_bytes = (metas.capacity() * size_of::<ObjectMeta>())
+            + metas.iter().map(meta_heap_bytes).reduce(|acc, b| acc + b)?;
+
+        Some(Self {
+            metas,
+            size_bytes,
+            expires: ttl.map(|t| Instant::now() + t),
+        })
+    }
+}
+
+/// Calculates the number of bytes an [`ObjectMeta`] occupies in the heap.
+fn meta_heap_bytes(object_meta: &ObjectMeta) -> usize {
+    let mut size = object_meta.location.as_ref().len();
+
+    if let Some(e) = &object_meta.e_tag {
+        size += e.len();
+    }
+    if let Some(v) = &object_meta.version {
+        size += v.len();
+    }
+
+    size
+}
+
+/// The default memory limit for the [`DefaultListFilesCache`]
+pub(super) const DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT: usize = 1024 * 1024; // 1MiB
+
+/// Handles the inner state of the [`DefaultListFilesCache`] struct.
+pub struct DefaultListFilesCacheState {
+    lru_queue: LruQueue<Path, ListFilesEntry>,
+    memory_limit: usize,
+    memory_used: usize,
+    ttl: Option<Duration>,
+}
+
+impl Default for DefaultListFilesCacheState {
+    fn default() -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit: DEFAULT_LIST_FILES_CACHE_MEMORY_LIMIT,
+            memory_used: 0,
+            ttl: None,
+        }
+    }
+}
+
+impl DefaultListFilesCacheState {
+    fn new(memory_limit: usize, ttl: Option<Duration>) -> Self {
+        Self {
+            lru_queue: LruQueue::new(),
+            memory_limit,
+            memory_used: 0,
+            ttl,
+        }
+    }
+
+    /// Returns the respective entry from the cache, if it exists and the entry has not expired.
+    /// If the entry exists it becomes the most recently used. If the entry has expired it is
+    /// removed from the cache
+    fn get(&mut self, key: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = self.lru_queue.get(key)?;
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(key);
+                None
+            }
+            _ => Some(Arc::clone(&entry.metas)),
+        }
+    }
+
+    /// Checks if the respective entry is currently cached. If the entry has expired it is removed
+    /// from the cache.
+    /// The LRU queue is not updated.
+    fn contains_key(&mut self, k: &Path) -> bool {
+        let Some(entry) = self.lru_queue.peek(k) else {
+            return false;
+        };
+
+        match entry.expires {
+            Some(exp) if Instant::now() > exp => {
+                self.remove(k);
+                false
+            }
+            _ => true,
+        }
+    }
+
+    /// Adds a new key-value pair to cache, meaning LRU entries might be evicted if required.
+    /// If the key is already in the cache, the previous entry is returned.
+    /// If the size of the entry is greater than the `memory_limit`, the value is not inserted.
+    fn put(
+        &mut self,
+        key: &Path,
+        value: Arc<Vec<ObjectMeta>>,
+    ) -> Option<Arc<Vec<ObjectMeta>>> {
+        let entry = ListFilesEntry::try_new(value, self.ttl)?;
+        let entry_size = entry.size_bytes;
+
+        // no point in trying to add this value to the cache if it cannot fit entirely
+        if entry_size > self.memory_limit {
+            return None;
+        }
+
+        // if the key is already in the cache, the old value is removed
+        let old_value = self.lru_queue.put(key.clone(), entry);
+        self.memory_used += entry_size;
+
+        if let Some(entry) = &old_value {
+            self.memory_used -= entry.size_bytes;
+        }
+
+        self.evict_entries();
+
+        old_value.map(|v| v.metas)
+    }
+
+    /// Evicts entries from the LRU cache until `memory_used` is lower than `memory_limit`.
+    fn evict_entries(&mut self) {
+        while self.memory_used > self.memory_limit {
+            if let Some(removed) = self.lru_queue.pop() {
+                self.memory_used -= removed.1.size_bytes;
+            } else {
+                // cache is empty while memory_used > memory_limit, cannot happen
+                debug_assert!(
+                    false,
+                    "cache is empty while memory_used > memory_limit, cannot happen"
+                );
+                return;
+            }
+        }
+    }
+
+    /// Removes an entry from the cache and returns it, if it exists.
+    fn remove(&mut self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        if let Some(entry) = self.lru_queue.remove(k) {
+            self.memory_used -= entry.size_bytes;
+            Some(entry.metas)
+        } else {
+            None
+        }
+    }
+
+    /// Returns the number of entries currently cached.
+    fn len(&self) -> usize {
+        self.lru_queue.len()
+    }
+
+    /// Removes all entries from the cache.
+    fn clear(&mut self) {
+        self.lru_queue.clear();
+        self.memory_used = 0;
+    }
+}
+
+impl ListFilesCache for DefaultListFilesCache {
+    fn cache_limit(&self) -> usize {
+        let state = self.state.lock().unwrap();
+        state.memory_limit
+    }
+
+    fn cache_ttl(&self) -> Option<Duration> {
+        let state = self.state.lock().unwrap();
+        state.ttl
+    }
+
+    fn update_cache_limit(&self, limit: usize) {
+        let mut state = self.state.lock().unwrap();
+        state.memory_limit = limit;
+        state.evict_entries();
+    }
+}
+
+impl CacheAccessor<Path, Arc<Vec<ObjectMeta>>> for DefaultListFilesCache {
+    type Extra = ObjectMeta;
+
+    fn get(&self, k: &Path) -> Option<Arc<Vec<ObjectMeta>>> {
+        let mut state = self.state.lock().unwrap();
+        state.get(k)
+    }
+
+    fn get_with_extra(&self, k: &Path, _e: &Self::Extra) -> Option<Arc<Vec<ObjectMeta>>> {
+        self.get(k)
+    }

Review Comment:
   Looking forward, I'm wondering if these methods can end up supporting this cache's ability to be "prefix aware". Maybe it makes sense to have `type Extra = Path;` where `k: &Path` is the table path and `e: &Self::Extra` is the prefix. That way the cache can internally differentiate between entries that are just table list entries vs entries that have prefixes.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org