@@ -30,18 +30,22 @@ use arrow::array::{
3030 cast:: AsArray ,
3131} ;
3232use arrow:: array:: {
33- Datum , GenericListArray , Int32Array , Int64Array , MutableArrayData , make_array,
33+ ArrowPrimitiveType , Datum , GenericListArray , Int32Array , Int64Array ,
34+ MutableArrayData , PrimitiveArray , make_array,
3435} ;
3536use arrow:: buffer:: OffsetBuffer ;
3637use arrow:: compute:: kernels:: cmp:: neq;
3738use arrow:: compute:: kernels:: length:: length;
3839use arrow:: compute:: { SortColumn , SortOptions , partition} ;
39- use arrow:: datatypes:: { DataType , Field , SchemaRef } ;
40+ use arrow:: datatypes:: {
41+ ArrowNativeType , DataType , Field , Int32Type , Int64Type , SchemaRef ,
42+ } ;
4043#[ cfg( feature = "sql" ) ]
4144use sqlparser:: { ast:: Ident , dialect:: GenericDialect , parser:: Parser } ;
4245use std:: borrow:: { Borrow , Cow } ;
4346use std:: cmp:: { Ordering , min} ;
4447use std:: collections:: HashSet ;
48+ use std:: iter:: repeat_n;
4549use std:: num:: NonZero ;
4650use std:: ops:: Range ;
4751use std:: sync:: { Arc , LazyLock } ;
@@ -1099,6 +1103,74 @@ fn truncate_list_nulls<O: OffsetSizeTrait>(
10991103 Ok ( list. clone ( ) )
11001104}
11011105
1106+ /// If `array` is a list or a map, returns a new array of the same length as it's inner values
1107+ /// where each value is the 1-based index of the sublist it's contained. Example:
1108+ ///
1109+ /// `[[1], [2, 3], [4, 5, 6]] => [1, 2, 2, 3, 3, 3]`
1110+ ///
1111+ /// Otherwise returns an error
1112+ pub fn list_values_row_number ( array : & dyn Array ) -> Result < ArrayRef > {
1113+ match array. data_type ( ) {
1114+ DataType :: List ( _) => Ok ( Arc :: new ( variable_size_list_values_row_number :: <
1115+ Int32Type ,
1116+ > ( array. as_list ( ) . offsets ( ) ) ) ) ,
1117+ DataType :: LargeList ( _) => Ok ( Arc :: new ( variable_size_list_values_row_number :: <
1118+ Int64Type ,
1119+ > ( array. as_list ( ) . offsets ( ) ) ) ) ,
1120+ DataType :: ListView ( _) => Ok ( Arc :: new ( variable_size_list_values_row_number :: <
1121+ Int32Type ,
1122+ > ( array. as_list_view ( ) . offsets ( ) ) ) ) ,
1123+ DataType :: LargeListView ( _) => {
1124+ Ok ( Arc :: new ( variable_size_list_values_row_number :: < Int64Type > (
1125+ array. as_list_view ( ) . offsets ( ) ,
1126+ ) ) )
1127+ }
1128+ DataType :: FixedSizeList ( _, _) => {
1129+ let fixed_size_list = array. as_fixed_size_list ( ) ;
1130+
1131+ Ok ( Arc :: new ( fsl_values_row_number (
1132+ fixed_size_list. value_length ( ) ,
1133+ fixed_size_list. len ( ) ,
1134+ ) ?) )
1135+ }
1136+ DataType :: Map ( _, _) => Ok ( Arc :: new ( variable_size_list_values_row_number :: <
1137+ Int32Type ,
1138+ > ( array. as_map ( ) . offsets ( ) ) ) ) ,
1139+ other => _exec_err ! ( "expected list, got {other}" ) ,
1140+ }
1141+ }
1142+
1143+ /// [0, 2, 2, 5, 6] -> [0, 0, 2, 2, 2, 3]
1144+ fn variable_size_list_values_row_number < T : ArrowPrimitiveType > (
1145+ offsets : & [ T :: Native ] ,
1146+ ) -> PrimitiveArray < T > {
1147+ let mut rows_number = Vec :: with_capacity (
1148+ offsets[ offsets. len ( ) - 1 ] . to_usize ( ) . unwrap ( ) - offsets[ 0 ] . to_usize ( ) . unwrap ( ) ,
1149+ ) ;
1150+
1151+ for ( i, w) in offsets. windows ( 2 ) . enumerate ( ) {
1152+ let len = w[ 1 ] . as_usize ( ) - w[ 0 ] . as_usize ( ) ;
1153+ rows_number. extend ( repeat_n ( T :: Native :: usize_as ( i) , len) ) ;
1154+ }
1155+
1156+ PrimitiveArray :: new ( rows_number. into ( ) , None )
1157+ }
1158+
1159+ /// (2, 3) -> [0, 0, 1, 1, 2, 2]
1160+ fn fsl_values_row_number ( list_size : i32 , array_len : usize ) -> Result < Int32Array > {
1161+ let list_size = list_size. to_usize ( ) . ok_or_else ( || {
1162+ _exec_datafusion_err ! ( "fsl_values_index: invalid list_size {list_size}" )
1163+ } ) ?;
1164+
1165+ let mut rows_number = Vec :: with_capacity ( list_size * array_len) ;
1166+
1167+ for i in 0 ..array_len {
1168+ rows_number. extend ( repeat_n ( i as i32 , list_size) ) ;
1169+ }
1170+
1171+ Ok ( PrimitiveArray :: new ( rows_number. into ( ) , None ) )
1172+ }
1173+
11021174#[ cfg( test) ]
11031175mod tests {
11041176 use std:: sync:: Arc ;
@@ -1535,4 +1607,85 @@ mod tests {
15351607 assert_eq ! ( res. values( ) , expected. values( ) ) ;
15361608 assert_eq ! ( res. offsets( ) , expected. offsets( ) ) ;
15371609 }
1610+
1611+ #[ test]
1612+ fn test_list_array_values_row_number ( ) {
1613+ assert_eq ! (
1614+ variable_size_list_values_row_number:: <Int32Type >(
1615+ & OffsetBuffer :: from_lengths( [ 1 , 3 , 0 , 2 , ] )
1616+ ) ,
1617+ Int32Array :: from( vec![ 0 , 1 , 1 , 1 , 3 , 3 ] )
1618+ ) ;
1619+
1620+ assert_eq ! (
1621+ variable_size_list_values_row_number:: <Int32Type >(
1622+ & OffsetBuffer :: from_lengths( [ ] )
1623+ ) ,
1624+ Int32Array :: new_null( 0 )
1625+ ) ;
1626+
1627+ assert_eq ! (
1628+ variable_size_list_values_row_number:: <Int32Type >(
1629+ & OffsetBuffer :: from_lengths( [ 0 ] )
1630+ ) ,
1631+ Int32Array :: new_null( 0 )
1632+ ) ;
1633+
1634+ assert_eq ! (
1635+ variable_size_list_values_row_number:: <Int32Type >(
1636+ & OffsetBuffer :: from_lengths( [ 0 , 0 ] )
1637+ ) ,
1638+ Int32Array :: new_null( 0 )
1639+ ) ;
1640+
1641+ assert_eq ! (
1642+ variable_size_list_values_row_number:: <Int32Type >(
1643+ & OffsetBuffer :: from_lengths( [ 1 ] )
1644+ ) ,
1645+ Int32Array :: from( vec![ 0 ] )
1646+ ) ;
1647+
1648+ assert_eq ! (
1649+ variable_size_list_values_row_number:: <Int32Type >(
1650+ & OffsetBuffer :: from_lengths( [ 2 ] )
1651+ ) ,
1652+ Int32Array :: from( vec![ 0 , 0 ] )
1653+ ) ;
1654+ }
1655+
1656+ #[ test]
1657+ fn test_fsl_values_row_number ( ) {
1658+ assert_eq ! (
1659+ fsl_values_row_number( 2 , 3 ) . unwrap( ) ,
1660+ Int32Array :: from( vec![ 0 , 0 , 1 , 1 , 2 , 2 ] )
1661+ ) ;
1662+
1663+ assert_eq ! (
1664+ fsl_values_row_number( 1 , 3 ) . unwrap( ) ,
1665+ Int32Array :: from( vec![ 0 , 1 , 2 ] )
1666+ ) ;
1667+
1668+ assert_eq ! (
1669+ fsl_values_row_number( 2 , 1 ) . unwrap( ) ,
1670+ Int32Array :: from( vec![ 0 , 0 ] )
1671+ ) ;
1672+
1673+ assert_eq ! (
1674+ fsl_values_row_number( 2 , 0 ) . unwrap( ) ,
1675+ Int32Array :: new_null( 0 ) ,
1676+ ) ;
1677+
1678+ assert_eq ! (
1679+ fsl_values_row_number( 0 , 2 ) . unwrap( ) ,
1680+ Int32Array :: new_null( 0 ) ,
1681+ ) ;
1682+
1683+ assert_eq ! (
1684+ fsl_values_row_number( 0 , 0 ) . unwrap( ) ,
1685+ Int32Array :: new_null( 0 ) ,
1686+ ) ;
1687+
1688+ fsl_values_row_number ( -1 , 2 ) . unwrap_err ( ) ;
1689+ fsl_values_row_number ( -1 , 0 ) . unwrap_err ( ) ;
1690+ }
15381691}
0 commit comments